skip to content

What does pairing the LDAP server-side sorting control with simple paged results cost a directory server?

level: seniorimportance: should knowfreq 36%

answer

  1. order is a property of the set
  2. paging bounds messages, not work
  3. all the cost lands on page one
  4. limits measure the set, not the page
  5. sortResult may say unwillingToPerform

basics

~20 s

Ordering is defined over the whole result set, so the server must select and order everything before it can hand back page one. Paging then bounds the messages but not the work or the memory, and the server's own limits apply to the full set.

solid answer

~40 s

The server-side sorting request (1.2.840.113556.1.4.473) orders the entire result set; the sort response (1.2.840.113556.1.4.474) carries `sortResult` saying whether that succeeded. Pairing it with simple paged results is the combination that hurts, because a server cannot know which entries belong on page one until it has evaluated and ordered all of them. Paging then bounds the size of each message exchange, not the work behind it: memory and CPU scale with the whole set, and the server's administrative limits are measured against that set rather than against a page — so a search that would have streamed happily in pages can trip `adminLimitExceeded (11)` before the first page arrives. A server is also free to refuse the combination, and a critical sort control it will not honour fails the operation with `unavailableCriticalExtension (12)`.

code

asn1 · 4 lines
asn1
SortKeyList ::= SEQUENCE OF SEQUENCE {
    attributeType   AttributeDescription,
    orderingRule    [0] MatchingRuleId OPTIONAL,
    reverseOrder    [1] BOOLEAN DEFAULT FALSE }

go deeper

for a junior

Know that two separate controls are in play — one asks for an order, one asks for pages — and that asking for both is more expensive than asking for either alone.

for a middle

Explain the mechanism: ordering is defined over the whole result set, so the set must be materialised before page one, and paging bounds the message rather than the work.

for a senior

Diagnose from symptoms — a limit error that appeared the week sorting was added, a timeout only on the first page, server memory scaling with concurrent exports — and know when to sort in the consumer instead.

for a principal

Own the trade across the estate: where ordering is allowed to cost a server, what page-loop state you are willing to have resident, and whether exports are specified as ordered snapshots at all.

## Two controls that pull in opposite directions Simple paged results exists so that neither side has to hold a huge answer at once. The server-side sorting control exists so that the answer arrives in a defined order. Put them on the same `SearchRequest` and the second one destroys the property the first was bought for. The sorting control's request form (1.2.840.113556.1.4.473) carries a `SortKeyList`: for each key, the attribute type to order by, an optional `orderingRule` naming the matching rule to use, and `reverseOrder`. The response form (1.2.840.113556.1.4.474) carries `sortResult`, which is how the server says it ordered the results, or why it did not. ## Why page one cannot be cheap Ordering is a property of the whole result set. The entry that belongs first is whichever of all 50,000 matching directory entries sorts first, and there is no way to know which that is without having found all 50,000. So the sequence on the server is: 1. evaluate the search — base DN, LDAP search scope, filter — over the candidate entries; 2. collect every match, with at least the sort attribute for each; 3. order that collection by the `SortKeyList`; 4. return the first `size` entries and hold the rest, keyed by the paged-results cookie, for the client to come back for. Paging has bounded the **messages**. It has not bounded the **work**, and it has not bounded the **memory** — which is now held for the lifetime of the page loop, per client, per in-progress search. ## The failures this produces in production - **The limit moves.** A server's administrative cap applies to the result set it had to build, not to the page it sent. A nightly export that read 50,000 members in pages of 500 for a year starts returning `adminLimitExceeded (11)` the week somebody adds sorting, and nothing about the search or the data changed. - **The first page is slow, the rest are fast.** All the cost is in front. A client timeout tuned to per-page latency fires on page one and never sees the loop that would have worked. - **Concurrency multiplies it.** Ten sorted paged searches running at once are ten full result sets resident at once. Paging made the client's memory profile flat and moved the problem onto the server. - **An abandoned loop is now expensive.** The state left behind by a client that stops half way is not a position marker; it is a sorted result set. - **The server may simply decline.** Sorting a large set is optional behaviour, and a server is free to answer `sortResult` with `unwillingToPerform (53)` and return the results unsorted — which a non-critical sort control invites and a critical one turns into `unavailableCriticalExtension (12)` on the whole operation. ## Order across pages is only as stable as the state behind it The ordering holds within one page loop against one server, for as long as that server keeps the state the cookie refers to. Restart the loop — a reconnect, a failover, a timed-out cookie — and the set is evaluated again against data that has moved since. Entries that were added ahead of the position you had reached will now appear; entries behind it will not. The export is neither a snapshot nor idempotent, and a consumer that diffs last night's list against tonight's will see churn that no one caused. ## What to do instead | goal | approach | what it costs | |---|---|---| | stable order for a bulk export | page unsorted, sort in the consumer | client memory, but the server streams | | a first screenful in order, for a user | sort with a small page and a tight filter | the server still orders the matched set, so keep that set small | | ordered enumeration of a very large set | slice the enumeration by a narrower base DN and merge | more round trips, more client logic | | order the server can give cheaply | sort on a single attribute the server can order without materialising much | server-specific; verify, do not assume | The general rule: **sorting is worth asking a server for when the matched set is small and the client cannot sort; it is worth doing in the client when the matched set is large and you are paging precisely because it is large.** ## What an interviewer is checking That you can say *why* the two controls conflict rather than that they do — the ordering is defined over the set, the set must therefore exist, and paging only ever bounded the message. Then that you know where the consequence lands: administrative limits measured against the whole set, cost front-loaded onto page one, server memory held per loop, and an ordering that does not survive a restart.

  • How would you get a stable ordered export of 50,000 group members without asking the server to sort?
    Page the search unsorted so the server can stream it, and order the result in the consumer once the enumeration finishes. If the set is too large for the consumer to hold either, slice it by a narrower base DN and merge the ordered slices — more round trips, but no single component holds everything.
  • Why can a sorted paged export return a different membership two nights running with no failure anywhere?
    The loop is not a snapshot. If it restarts — reconnect, failover, expired cookie — the set is evaluated again against data that has moved. Entries added ahead of the position already reached appear, entries behind it do not, so the two runs legitimately disagree.
  • If the server cannot sort, does the search fail?
    It depends on the sort control's criticality. Non-critical, the server may return the results unsorted with `sortResult` explaining why — `unwillingToPerform (53)`, for instance. Critical, and a server that cannot honour it must not perform the operation, answering `unavailableCriticalExtension (12)`.
  • Does a small page size reduce what the server has to hold for a sorted search?
    No. The page size bounds how many entries go into each message exchange; the sorted set behind the cookie is the same size either way. A smaller page just means more round trips over the same resident result set.

saying these in an interview costs you the question

  • Says sorting is free because an index is already ordered
  • Thinks the page size caps what the server must hold
  • Believes size limits apply per page rather than to the whole set
  • Thinks a failed sort always fails the whole search
  • Treats page ordering as stable across a restarted loop
  • Assumes every server will accept sorting and paging together