1 2 3 4 5 6 7Network Working Group T. Howes 8Request for Comments: 2891 Loudcloud 9Category: Standards Track M. Wahl 10 Sun Microsystems 11 A. Anantha 12 Microsoft 13 August 2000 14 15 16 LDAP Control Extension for Server Side Sorting of Search Results 17 18Status of this Memo 19 20 This document specifies an Internet standards track protocol for the 21 Internet community, and requests discussion and suggestions for 22 improvements. Please refer to the current edition of the "Internet 23 Official Protocol Standards" (STD 1) for the standardization state 24 and status of this protocol. Distribution of this memo is unlimited. 25 26Copyright Notice 27 28 Copyright (C) The Internet Society (2000). All Rights Reserved. 29 30Abstract 31 32 This document describes two LDAPv3 control extensions for server side 33 sorting of search results. These controls allows a client to specify 34 the attribute types and matching rules a server should use when 35 returning the results to an LDAP search request. The controls may be 36 useful when the LDAP client has limited functionality or for some 37 other reason cannot sort the results but still needs them sorted. 38 Other permissible controls on search operations are not defined in 39 this extension. 40 41 The sort controls allow a server to return a result code for the 42 sorting of the results that is independent of the result code 43 returned for the search operation. 44 45 The key words "MUST", "SHOULD", and "MAY" used in this document are 46 to be interpreted as described in [bradner97]. 47 48 49 50 51 52 53 54 55 56 57 58Howes, et al. Standards Track [Page 1] 59 60RFC 2891 LDAP Control Extension for Server Side Sorting August 2000 61 62 631. The Controls 64 651.1 Request Control 66 67 This control is included in the searchRequest message as part of the 68 controls field of the LDAPMessage, as defined in Section 4.1.12 of 69 [LDAPv3]. 70 71 The controlType is set to "1.2.840.113556.1.4.473". The criticality 72 MAY be either TRUE or FALSE (where absent is also equivalent to 73 FALSE) at the client's option. The controlValue is an OCTET STRING, 74 whose value is the BER encoding of a value of the following SEQUENCE: 75 76 SortKeyList ::= SEQUENCE OF SEQUENCE { 77 attributeType AttributeDescription, 78 orderingRule [0] MatchingRuleId OPTIONAL, 79 reverseOrder [1] BOOLEAN DEFAULT FALSE } 80 81 The SortKeyList sequence is in order of highest to lowest sort key 82 precedence. 83 84 The MatchingRuleId, as defined in section 4.1.9 of [LDAPv3], SHOULD 85 be one that is valid for the attribute type it applies to. If it is 86 not, the server will return inappropriateMatching. 87 88 Each attributeType should only occur in the SortKeyList once. If an 89 attributeType is included in the sort key list multiple times, the 90 server should return an error in the sortResult of 91 unwillingToPerform. 92 93 If the orderingRule is omitted, the ordering MatchingRule defined for 94 use with this attribute MUST be used. 95 96 Any conformant implementation of this control MUST allow a sort key 97 list with at least one key. 98 991.2 Response Control 100 101 This control is included in the searchResultDone message as part of 102 the controls field of the LDAPMessage, as defined in Section 4.1.12 103 of [LDAPv3]. 104 105 The controlType is set to "1.2.840.113556.1.4.474". The criticality 106 is FALSE (MAY be absent). The controlValue is an OCTET STRING, whose 107 value is the BER encoding of a value of the following SEQUENCE: 108 109 110 111 112 113 114Howes, et al. Standards Track [Page 2] 115 116RFC 2891 LDAP Control Extension for Server Side Sorting August 2000 117 118 119 SortResult ::= SEQUENCE { 120 sortResult ENUMERATED { 121 success (0), -- results are sorted 122 operationsError (1), -- server internal failure 123 timeLimitExceeded (3), -- timelimit reached before 124 -- sorting was completed 125 strongAuthRequired (8), -- refused to return sorted 126 -- results via insecure 127 -- protocol 128 adminLimitExceeded (11), -- too many matching entries 129 -- for the server to sort 130 noSuchAttribute (16), -- unrecognized attribute 131 -- type in sort key 132 inappropriateMatching (18), -- unrecognized or 133 -- inappropriate matching 134 -- rule in sort key 135 insufficientAccessRights (50), -- refused to return sorted 136 -- results to this client 137 busy (51), -- too busy to process 138 unwillingToPerform (53), -- unable to sort 139 other (80) 140 }, 141 attributeType [0] AttributeDescription OPTIONAL } 142 1432. Client-Server Interaction 144 145 The sortKeyRequestControl specifies one or more attribute types and 146 matching rules for the results returned by a search request. The 147 server SHOULD return all results for the search request in the order 148 specified by the sort keys. If the reverseOrder field is set to TRUE, 149 then the entries will be presented in reverse sorted order for the 150 specified key. 151 152 There are six possible scenarios that may occur as a result of the 153 sort control being included on the search request: 154 155 1 - If the server does not support this sorting control and the 156 client specified TRUE for the control's criticality field, then 157 the server MUST return unavailableCriticalExtension as a return 158 code in the searchResultDone message and not send back any other 159 results. This behavior is specified in section 4.1.12 of 160 [LDAPv3]. 161 162 2 - If the server does not support this sorting control and the 163 client specified FALSE for the control's criticality field, then 164 the server MUST ignore the sort control and process the search 165 request as if it were not present. This behavior is specified in 166 section 4.1.12 of [LDAPv3]. 167 168 169 170Howes, et al. Standards Track [Page 3] 171 172RFC 2891 LDAP Control Extension for Server Side Sorting August 2000 173 174 175 3 - If the server supports this sorting control but for some reason 176 cannot sort the search results using the specified sort keys and 177 the client specified TRUE for the control's criticality field, 178 then the server SHOULD do the following: return 179 unavailableCriticalExtension as a return code in the 180 searchResultDone message; include the sortKeyResponseControl in 181 the searchResultDone message, and not send back any search result 182 entries. 183 184 4 - If the server supports this sorting control but for some reason 185 cannot sort the search results using the specified sort keys and 186 the client specified FALSE for the control's criticality field, 187 then the server should return all search results unsorted and 188 include the sortKeyResponseControl in the searchResultDone 189 message. 190 191 5 - If the server supports this sorting control and can sort the 192 search results using the specified sort keys, then it should 193 include the sortKeyResponseControl in the searchResultDone 194 message with a sortResult of success. 195 196 6 - If the search request failed for any reason and/or there are no 197 searchResultEntry messages returned for the search response, then 198 the server SHOULD omit the sortKeyResponseControl from the 199 searchResultDone message. 200 201 The client application is assured that the results are sorted in the 202 specified key order if and only if the result code in the 203 sortKeyResponseControl is success. If the server omits the 204 sortKeyResponseControl from the searchResultDone message, the client 205 SHOULD assume that the sort control was ignored by the server. 206 207 The sortKeyResponseControl, if included by the server in the 208 searchResultDone message, should have the sortResult set to either 209 success if the results were sorted in accordance with the keys 210 specified in the sortKeyRequestControl or set to the appropriate 211 error code as to why it could not sort the data (such as 212 noSuchAttribute or inappropriateMatching). Optionally, the server MAY 213 set the attributeType to the first attribute type specified in the 214 SortKeyList that was in error. The client SHOULD ignore the 215 attributeType field if the sortResult is success. 216 217 The server may not be able to sort the results using the specified 218 sort keys because it may not recognize one of the attribute types, 219 the matching rule associated with an attribute type is not 220 applicable, or none of the attributes in the search response are of 221 these types. Servers may also restrict the number of keys allowed in 222 the control, such as only supporting a single key. 223 224 225 226Howes, et al. Standards Track [Page 4] 227 228RFC 2891 LDAP Control Extension for Server Side Sorting August 2000 229 230 231 Servers that chain requests to other LDAP servers should ensure that 232 the server satisfying the client's request sort the entire result set 233 prior to sending back the results. 234 2352.1 Behavior in a chained environment 236 237 If a server receives a sort request, the client expects to receive a 238 set of sorted results. If a client submits a sort request to a server 239 which chains the request and gets entries from multiple servers, and 240 the client has set the criticality of the sort extension to TRUE, the 241 server MUST merge sort the results before returning them to the 242 client or MUST return unwillingToPerform. 243 2442.2 Other sort issues 245 246 An entry that meets the search criteria may be missing one or more of 247 the sort keys. In that case, the entry is considered to have a value 248 of NULL for that key. This standard considers NULL to be a larger 249 value than all other valid values for that key. For example, if only 250 one key is specified, entries which meet the search criteria but do 251 not have that key collate after all the entries which do have that 252 key. If the reverseOrder flag is set, and only one key is specified, 253 entries which meet the search criteria but do not have that key 254 collate BEFORE all the entries which do have that key. 255 256 If a sort key is a multi-valued attribute, and an entry happens to 257 have multiple values for that attribute and no other controls are 258 present that affect the sorting order, then the server SHOULD use the 259 least value (according to the ORDERING rule for that attribute). 260 2613. Interaction with other search controls 262 263 When the sortKeyRequestControl control is included with the 264 pagedResultsControl control as specified in [LdapPaged], then the 265 server should send the searchResultEntry messages sorted according to 266 the sort keys applied to the entire result set. The server should not 267 simply sort each page, as this will give erroneous results to the 268 client. 269 270 The sortKeyList must be present on each searchRequest message for the 271 paged result. It also must not change between searchRequests for the 272 same result set. If the server has sorted the data, then it SHOULD 273 send back a sortKeyResponseControl control on every searchResultDone 274 message for each page. This will allow clients to quickly determine 275 if the result set is sorted, rather than waiting to receive the 276 entire result set. 277 278 279 280 281 282Howes, et al. Standards Track [Page 5] 283 284RFC 2891 LDAP Control Extension for Server Side Sorting August 2000 285 286 2874. Security Considerations 288 289 Implementors and administrators should be aware that allowing sorting 290 of results could enable the retrieval of a large number of records 291 from a given directory service, regardless of administrative limits 292 set on the maximum number of records to return. 293 294 A client that desired to pull all records out of a directory service 295 could use a combination of sorting and updating of search filters to 296 retrieve all records in a database in small result sets, thus 297 circumventing administrative limits. 298 299 This behavior can be overcome by the judicious use of permissions on 300 the directory entries by the administrator and by intelligent 301 implementations of administrative limits on the number of records 302 retrieved by a client. 303 3045. References 305 306 [LDAPv3] Wahl, M, Kille, S. and T. Howes, "Lightweight Directory 307 Access Protocol (v3)", RFC 2251, December 1997. 308 309 [Bradner97] Bradner, S., "Key Words for use in RFCs to Indicate 310 Requirement Levels", BCP 14, RFC 2119, March 1997. 311 312 [LdapPaged] Weider, C., Herron, A., Anantha, A. and T. Howes, "LDAP 313 Control Extension for Simple Paged Results Manipulation", 314 RFC 2696, September 1999. 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338Howes, et al. Standards Track [Page 6] 339 340RFC 2891 LDAP Control Extension for Server Side Sorting August 2000 341 342 3436. Authors' Addresses 344 345 Anoop Anantha 346 Microsoft Corp. 347 1 Microsoft Way 348 Redmond, WA 98052 349 USA 350 351 Phone: +1 425 882-8080 352 EMail: anoopa@microsoft.com 353 354 355 Tim Howes 356 Loudcloud, Inc. 357 615 Tasman Dr. 358 Sunnyvale, CA 94089 359 USA 360 361 EMail: howes@loudcloud.com 362 363 364 Mark Wahl 365 Sun Microsystems, Inc. 366 8911 Capital of Texas Hwy Suite 4140 367 Austin, TX 78759 368 USA 369 370 EMail: Mark.Wahl@sun.com 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394Howes, et al. Standards Track [Page 7] 395 396RFC 2891 LDAP Control Extension for Server Side Sorting August 2000 397 398 3997. Full Copyright Statement 400 401 Copyright (C) The Internet Society (2000). All Rights Reserved. 402 403 This document and translations of it may be copied and furnished to 404 others, and derivative works that comment on or otherwise explain it 405 or assist in its implementation may be prepared, copied, published 406 and distributed, in whole or in part, without restriction of any 407 kind, provided that the above copyright notice and this paragraph are 408 included on all such copies and derivative works. However, this 409 document itself may not be modified in any way, such as by removing 410 the copyright notice or references to the Internet Society or other 411 Internet organizations, except as needed for the purpose of 412 developing Internet standards in which case the procedures for 413 copyrights defined in the Internet Standards process must be 414 followed, or as required to translate it into languages other than 415 English. 416 417 The limited permissions granted above are perpetual and will not be 418 revoked by the Internet Society or its successors or assigns. 419 420 This document and the information contained herein is provided on an 421 "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING 422 TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING 423 BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION 424 HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF 425 MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 426 427Acknowledgement 428 429 Funding for the RFC Editor function is currently provided by the 430 Internet Society. 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450Howes, et al. Standards Track [Page 8] 451 452