2
INTERNET-DRAFT David Boreham, Netscape
3
Jim Sermersheim, Novell
4
Anoop Anantha, Microsoft
5
Michael Armijo, Microsoft
6
ldapext Working Group 6 April, 2000
9
LDAP Extensions for Scrolling View Browsing of Search Results
11
draft-ietf-ldapext-ldapv3-vlv-04.txt
12
This document expires on 5 October 2000
14
1. Status of this Memo
16
This document is an Internet-Draft and is in full conformance with all
17
provisions of Section 10 of RFC2026. Internet-Drafts are working docu-
18
ments of the Internet Engineering Task Force (IETF), its areas, and its
19
working groups. Note that other groups may also distribute working
20
documents as Internet-Drafts.
22
Internet-Drafts are draft documents valid for a maximum of six months
23
and may be updated, replaced, or obsoleted by other documents at any
24
time. It is inappropriate to use Internet- Drafts as reference material
25
or to cite them other than as "work in progress."
27
The list of current Internet-Drafts can be accessed at
28
http://www.ietf.org/ietf/1id-abstracts.txt
30
The list of Internet-Draft Shadow Directories can be accessed at
31
http://www.ietf.org/shadow.html.
35
This document describes a Virtual List View control extension for the
36
LDAP Search operation. This control is designed to allow the "virtual
37
list box" feature, common in existing commercial e-mail address book
38
applications, to be supported efficiently by LDAP servers. LDAP servers'
39
inability to support this client feature is a significant impediment to
40
LDAP replacing proprietary protocols in commercial e-mail systems.
42
The control allows a client to specify that the server return, for a
43
given LDAP search with associated sort keys, a contiguous subset of the
44
search result set. This subset is specified in terms of offsets into the
45
ordered list, or in terms of a greater than or equal comparison value.
49
A Virtual List is a graphical user interface technique employed where
53
Boreham et al [Page 1]
62
ordered lists containing a large number of entries need to be displayed.
63
A window containing a small number of visible list entries is drawn. The
64
visible portion of the list may be relocated to different points within
65
the list by means of user input. This input can be to a scroll bar
66
slider; from cursor keys; from page up/down keys; from alphanumeric keys
67
for "typedown". The user is given the impression that they may browse
68
the complete list at will, even though it may contain millions of
69
entries. It is the fact that the complete list contents are never
70
required at any one time that characterizes Virtual List View. Rather
71
than fetch the complete list from wherever it is stored (typically from
72
disk or a remote server), only that information which is required to
73
display the part of the list currently in view is fetched. The subject
74
of this document is the interaction between client and server required
75
to implement this functionality in the context of the results from a
76
sorted LDAP search request.
78
For example, suppose an e-mail address book application displays a list
79
view onto the list containing the names of all the holders of e-mail
80
accounts at a large university. The list is sorted alphabetically.
81
While there may be tens of thousands of entries in this list, the
82
address book list view displays only 20 such accounts at any one time.
83
The list has an accompanying scroll bar and text input window for type-
84
down. When first displayed, the list view shows the first 20 entries in
85
the list, and the scroll bar slider is positioned at the top of its
86
range. Should the user drag the slider to the bottom of its range, the
87
displayed contents of the list view should be updated to show the last
88
20 entries in the list. Similarly, if the slider is positioned somewhere
89
in the middle of its travel, the displayed contents of the list view
90
should be updated to contain the 20 entries located at that relative
91
position within the complete list. Starting from any display point, if
92
the user uses the cursor keys or clicks on the scroll bar to request
93
that the list be scrolled up or down by one entry, the displayed con-
94
tents should be updated to reflect this. Similarly the list should be
95
displayed correctly when the user requests a page scroll up or down.
96
Finally, when the user types characters in the type-down window, the
97
displayed contents of the list should "jump" or "seek" to the appropri-
98
ate point within the list. For example, if the user types "B", the
99
displayed list could center around the first user with a name beginning
100
with the letter "B". When this happens, the scroll bar slider should
101
also be updated to reflect the new relative location within the list.
103
This document defines a request control which extends the LDAP search
104
operation. Always used in conjunction with the server side sorting
105
control[SSS], this allows a client to retrieve selected portions of
106
large search result set in a fashion suitable for the implementation of
109
The key words "MUST", "SHOULD", and "MAY" used in this document are to
113
Boreham et al [Page 2]
122
be interpreted as described in [Bradner97].
124
4. Client-Server Interaction
126
The Virtual List View control extends a regular LDAP Search operation
127
which must also include a server-side sorting control[SSS]. Rather than
128
returning the complete set of appropriate SearchResultEntry messages,
129
the server is instructed to return a contiguous subset of those entries,
130
taken from the sorted result set, centered around a particular target
131
entry. Henceforth, in the interests of brevity, the sorted search result
132
set will be referred to as "the list".
134
The sort control MAY contain any sort specification valid for the
135
server. The attributeType field in the first SortKeyList sequence ele-
136
ment has special significance for "typedown".
138
The desired target entry, and the number of entries to be returned both
139
before, and after, that target entry in the list, are determined by the
140
client's VirtualListViewRequest control.
142
When the server returns the set of entries to the client, it attaches a
143
VirtualListViewResponse control to the SearchResultDone message. The
144
server returns in this control: its current estimate for the list con-
145
tent count, the location within the list corresponding to the target
146
entry, and any error codes.
148
The target entry is specified in the VirtualListViewRequest control by
149
one of two methods. The first method is for the client to indicate the
150
target entry's offset within the list. The second way is for the client
151
to supply an attribute assertion value. The value is compared against
152
the values of the attribute specified as the primary sort key in the
153
sort control attached to the search operation. The first sort key in
154
the SortKeyList is the primary sort key. The target entry is the first
155
entry in the list with value greater than or equal to (in the primary
156
sort order), the presented value. The order is determined by rules
157
defined in [SSS]. Selection of the target entry by this means is
158
designed to implement "typedown". Note that it is possible that no
159
entry satisfies these conditions, in which case there is no target
160
entry. This condition is indicated by the server returning the special
161
value contentCount + 1 in the target position field.
163
Because the server may not have an accurate estimate of the number of
164
entries in the list, and to take account of cases where the list size is
165
changing during the time the user browses the list, and because the
166
client needs a way to indicate specific list targets "beginning" and
167
"end", offsets within the list are transmitted between client and server
168
as ratios---offset to content count. The server sends its latest esti-
169
mate as to the number of entries in the list (content count) to the
173
Boreham et al [Page 3]
182
client in every response control. The client sends its assumed value
183
for the content count in every request control. The server examines the
184
content count and offsets presented by the client and computes the
185
corresponding offsets within the list, based on its own idea of the con-
191
Si is the actual list offset used by the server
192
Sc is the server's estimate for content count
193
Ci is the client's submitted offset
194
Cc is the client's submitted content count
195
The result is rounded to the nearest integer.
197
If the content count is stable, and the client returns to the server the
198
content count most recently received, Cc = Sc and the offsets transmit-
199
ted become the actual server list offsets.
201
The following special cases are allowed: a client sending a content
202
count of zero (Cc = 0) means "client has no idea what the content count
203
is, server MUST use its own content count estimate in place of the
204
client's". An offset value of one (Ci = 1) always means that the target
205
is the first entry in the list. Client specifying an offset which equals
206
the content count specified in the same request control (Ci = Cc) means
207
that the target is the last entry in the list. Ci may only equal zero
208
when Cc is also zero. This signifies the last entry in the list.
210
Because the server always returns contentCount and targetPosition, the
211
client can always determine which of the returned entries is the target
212
entry. Where the number of entries returned is the same as the number
213
requested, the client is able to identify the target by simple arith-
214
metic. Where the number of entries returned is not the same as the
215
number requested (because the requested range crosses the beginning or
216
end of the list, or both), the client must use the target position and
217
content count values returned by the server to identify the target
218
entry. For example, suppose that 10 entries before and 10 after the tar-
219
get were requested, but the server returns 13 entries, a content count
220
of 100 and a target position of 3. The client can determine that the
221
first entry must be entry number 1 in the list, therefore the 13 entries
222
returned are the first 13 entries in the list, and the target is the
225
A server-generated context identifier MAY be returned to clients. A
226
client receiving a context identifier SHOULD return it unchanged in a
227
subsequent request which relates to the same list. The purpose of this
228
interaction is to enhance the performance and effectiveness of servers
229
which employ approximate positioning.
233
Boreham et al [Page 4]
244
Support for the virtual list view control extension is indicated by the
245
presence of the OID "2.16.840.1.113730.3.4.9" in the supportedControl
246
attribute of a server's root DSE.
250
This control is included in the SearchRequest message as part of the
251
controls field of the LDAPMessage, as defined in Section 4.1.12 of
252
[LDAPv3]. The controlType is set to "2.16.840.1.113730.3.4.9". The cri-
253
ticality SHOULD be set to TRUE. If this control is included in a Sear-
254
chRequest message, a Server Side Sorting request control [SSS] MUST also
255
be present in the message. The controlValue is an OCTET STRING whose
256
value is the BER-encoding of the following SEQUENCE:
258
VirtualListViewRequest ::= SEQUENCE {
259
beforeCount INTEGER (0..maxInt),
260
afterCount INTEGER (0..maxInt),
262
byoffset [0] SEQUENCE {
263
offset INTEGER (0 .. maxInt),
264
contentCount INTEGER (0 .. maxInt) },
265
greaterThanOrEqual [1] AssertionValue },
266
contextID OCTET STRING OPTIONAL }
268
beforeCount indicates how many entries before the target entry the
269
client wants the server to send. afterCount indicates the number of
270
entries after the target entry the client wants the server to send.
271
offset and contentCount identify the target entry as detailed in section
272
4. greaterThanOrEqual is an attribute assertion value defined in
273
[LDAPv3]. If present, the value supplied in greaterThanOrEqual is used
274
to determine the target entry by comparison with the values of the
275
attribute specified as the primary sort key. The first list entry who's
276
value is no less than (less than or equal to when the sort order is
277
reversed) the supplied value is the target entry. If present, the con-
278
textID field contains the value of the most recently received contextID
279
field from a VirtualListViewResponse control. The type AssertionValue
280
and value maxInt are defined in [LDAPv3]. contextID values have no
281
validity outwith the connection on which they were received. That is, a
282
client should not submit a contextID which it received from another con-
283
nection, a connection now closed, or a different server.
286
5.2. Response Control
288
This control is included in the SearchResultDone message as part of the
289
controls field of the LDAPMessage, as defined in Section 4.1.12 of
293
Boreham et al [Page 5]
304
The controlType is set to "2.16.840.1.113730.3.4.10". The criticality is
305
FALSE (MAY be absent). The controlValue is an OCTET STRING, whose value
306
is the BER encoding of a value of the following SEQUENCE:
308
VirtualListViewResponse ::= SEQUENCE {
309
targetPosition INTEGER (0 .. maxInt),
310
contentCount INTEGER (0 .. maxInt),
311
virtualListViewResult ENUMERATED {
314
unwillingToPerform (53),
315
insufficientAccessRights (50),
317
timeLimitExceeded (3),
318
adminLimitExceeded (11),
319
sortControlMissing (60),
320
offsetRangeError (61),
322
contextID OCTET STRING OPTIONAL }
324
targetPosition gives the list offset for the target entry. contentCount
325
gives the server's estimate of the current number of entries in the
326
list. Together these give sufficient information for the client to
327
update a list box slider position to match the newly retrieved entries
328
and identify the target entry. The contentCount value returned SHOULD be
329
used in a subsequent VirtualListViewRequest control. contextID is a
330
server-defined octet string. If present, the contents of the contextID
331
field SHOULD be returned to the server by a client in a subsequent Vir-
332
tualListViewRequest control.
334
The virtualListViewResult codes which are common to the LDAP sear-
335
chResponse (adminLimitExceeded, timeLimitExceeded, busy, operationsEr-
336
ror, unwillingToPerform, insufficientAccessRights) have the same mean-
337
ings as defined in [LDAPv3], but they pertain specifically to the VLV
338
operation. For example, the server could exceed an administration limit
339
processing a SearchRequest with a VirtualListViewRequest control. How-
340
ever, the same administration limit would not be exceeded should the
341
same SearchRequest be submitted by the client without the VirtualList-
342
ViewRequest control. In this case, the client can determine that an
343
administration limit has been exceeded in servicing the VLV request, and
344
can if it chooses resubmit the SearchRequest without the VirtualList-
347
insufficientAccessRights means that the server denied the client permis-
348
sion to perform the VLV operation.
353
Boreham et al [Page 6]
362
If the server determines that the results of the search presented exceed
363
the range provided by the 32-bit offset values, it MUST return
368
Here we walk through the client-server interaction for a specific vir-
369
tual list view example: The task is to display a list of all 78564 peo-
370
ple in the US company "Ace Industry". This will be done by creating a
371
graphical user interface object to display the list contents, and by
372
repeatedly sending different versions of the same virtual list view
373
search request to the server. The list view displays 20 entries on the
376
We form a search with baseDN "o=Ace Industry, c=us"; search scope sub-
377
tree; filter "objectClass=inetOrgPerson". We attach a server sort order
378
control to the search, specifying ascending sort on attribute "cn". To
379
this base search, we attach a virtual list view request control with
380
contents determined by the user activity and send the search to the
381
server. We display the results from each search in the list window and
382
update the slider position.
384
When the list view is first displayed, we want to initialize the con-
385
tents showing the beginning of the list. Therefore, we set beforeCount =
386
0, afterCount = 19, contentCount = 0, offset = 1 and send the request to
387
the server. The server duly returns the first 20 entries in the list,
388
plus the content count = 78564 and targetPosition = 1. We therefore
389
leave the scroll bar slider at its current location (the top of its
392
Say that next the user drags the scroll bar slider down to the bottom of
393
its range. We now wish to display the last 20 entries in the list, so
394
we set beforeCount = 19, afterCount = 0, contentCount = 78564, offset =
395
78564 and send the request to the server. The server returns the last 20
396
entries in the list, plus the content count = 78564 and targetPosition =
399
Next the user presses a page up key. Our page size is 20, so we set
400
beforeCount = 0, afterCount = 19, contentCount = 78564, offset =
401
78564-19-20 and send the request to the server. The server returns the
402
preceding 20 entries in the list, plus the content count = 78564 and
403
targetPosition = 78525.
405
Now the user grabs the scroll bar slider and drags it to 68% of the way
406
down its travel. 68% of 78564 is 53424 so we set beforeCount = 9, after-
407
Count = 10, contentCount = 78564, offset = 53424 and send the request to
408
the server. The server returns the preceding 20 entries in the list,
409
plus the content count = 78564 and targetPosition = 53424.
413
Boreham et al [Page 7]
422
Lastly, the user types the letter "B". We set beforeCount = 9, after-
423
Count = 10 and greaterThanOrEqual = "B". The server finds the first
424
entry in the list not less than "B", let's say "Babs Jensen", and
425
returns the nine preceding entries, the target entry, and the proceeding
426
10 entries. The server returns content count = 78564 and targetPosition
427
= 5234 and so the client updates its scroll bar slider to 6.7% of full
430
7. Notes for Implementers
432
While the feature is expected to be generally useful for arbitrary
433
search and sort specifications, it is specifically designed for those
434
cases where the result set is very large. The intention is that this
435
feature be implemented efficiently by means of pre-computed indices per-
436
taining to a set of specific cases. For example, an offset relating to
437
"all the employees in the local organization, sorted by surname" would
440
The intention for client software is that the feature should fit easily
441
with the host platform's graphical user interface facilities for the
442
display of scrolling lists. Thus the task of the client implementers
443
should be one of reformatting up the requests for information received
444
from the list view code to match the format of the virtual list view
445
request and response controls.
447
Client implementers should note that any offset value returned by the
448
server may be approximate. Do not design clients > which only operate
449
correctly when offsets are exact.
451
Server implementers using indexing technology which features approximate
452
positioning should consider returning context identifiers to clients.
453
The use of a context identifier will allow the server to distinguish
454
between client requests which relate to different displayed lists on the
455
client. Consequently the server can decide more intelligently whether to
456
reposition an existing database cursor accurately to within a short dis-
457
tance of its current position, or to reposition to an approximate posi-
458
tion. Thus the client will see precise offsets for "short" repositioning
459
(e.g. paging up or down), but approximate offsets for a "long" reposi-
460
tion (e.g. a slider movement).
462
Server implementers are free to return status code unwillingToPerform
463
should their server be unable to service any particular VLV search.
464
This might be because the resolution of the search is computationally
465
infeasible, or because excessive server resources would be required to
468
Client implementers should note that this control is only defined on a
469
client interaction with a single server. If a server returns referrals
473
Boreham et al [Page 8]
482
as a part of its response to the search request, the client is responsi-
483
ble for deciding when and how to apply this control to the referred-to
484
servers, and how to collate the results from multiple servers.
487
8. Relationship to "Simple Paged Results"
489
These controls are designed to support the virtual list view, which has
490
proved hard to implement with the Simple Paged Results mechanism
491
[SPaged]. However, the controls described here support any operation
492
possible with the Simple Paged Results mechanism. The two mechanisms are
493
not complementary, rather one has a superset of the other's features.
494
One area where the mechanism presented here is not a strict superset of
495
the Simple Paged Results scheme is that here we require a sort order to
496
be specified. No such requirement is made for paged results.
499
9. Security Considerations
501
Server implementers may wish to consider whether clients are able to
502
consume excessive server resources in requesting virtual list opera-
503
tions. Access control to the feature itself; configuration options lim-
504
iting the feature's use to certain predetermined search base DNs and
505
filters; throttling mechanisms designed to limit the ability for one
506
client to soak up server resources, may be appropriate.
508
Consideration should be given as to whether a client will be able to
509
retrieve the complete contents, or a significant subset of the complete
510
contents of the directory using this feature. This may be undesirable in
511
some circumstances and consequently it may be necessary to enforce some
514
Clients can, using this control, determine how many entries are con-
515
tained within a portion of the DIT. This may constitute a security
516
hazard. Again, access controls may be appropriate.
518
Server implementers SHOULD exercise caution concerning the content of
519
the contextID. Should the contextID contain internal server state, it
520
may be possible for a malicious client to use that information to gain
521
unauthorized access to information.
525
Chris Weider of Microsoft co-authored a previous version of this docu-
533
Boreham et al [Page 9]
545
Wahl, M, S. Kille and T. Howes, "Lightweight Directory Access Pro-
546
tocol (v3)", Internet Standard, December, 1997. RFC2251.
549
Weider, C, A. Herron, A. Anantha, and T. Howes, "LDAP Control
550
Extension for Simple Paged Results Manipulation", September
553
[SSS]Wahl, M, A. Herron and T. Howes, "LDAP Control Extension for Server
554
Side Sorting of Search Results", Internet Draft, April, 1999.
555
Available as draft-ietf-asid-ldapv3-sorting-02.txt.
558
Bradner, S., "Key Words for use in RFCs to Indicate Requirement
559
Levels", BCP 14, RFC 2119, March 1997.
561
12. Authors' Addresses
564
iPlanet e-commerce solutions
565
501 E. Middlefield Road
566
Mountain View, CA 94043, USA
568
dboreham@netscape.com
573
Provo, Utah 84606, USA
579
Redmond, WA 98052, USA
586
Redmond, WA 98052, USA
588
micharm@microsoft.com
589
This document expires on 5 October 2000
593
Boreham et al [Page 10]
653
Boreham et al [Page 11]