Skip to content
Prague
Improve this page

Ordering and Determinism

Prague returns rows in some order on every path, and on most paths that order is reproducible enough to be mistaken for a promise. This page separates the two: what the engine guarantees about the sequence of a result, what merely falls out of the mechanism today, and how to ask for an order when you need one. Every claim below is a region of samples/Prague.Samples/Explanation/Ordering.cs followed by the assertion that pins it: a guaranteed sequence is asserted as a sequence, an unspecified one as a set.

The one-line version: the only ordered result is a sorted one with a total comparer. Everything else is a set that happens to arrive in a sequence.

What order does an eager query produce?

The eager builder has no planner; the order falls out of two mechanisms described in How Prague works: the first lane fills the candidate set in the order its index enumerates, every later lane removes survivors in place without reordering them, and the store read walks the survivors in slot order.

A Many index enumerates in insertion order — mostly

A Many bucket is a PooledSet: a slot array walked from slot 0 to the last used slot. New keys append, so the bucket reads back in insertion order:

cache.AddOrUpdate(NewOrder("ORD-003", 42));
cache.AddOrUpdate(NewOrder("ORD-001", 42));
cache.AddOrUpdate(NewOrder("ORD-002", 42));

var rows = cache.Query().WithCustomerId(42).Execute();           // 003, 001, 002 — the bucket's slot order

"Mostly", because a removal frees its slot and the next insertion reuses it (the free list is LIFO), so a removed-then-added key lands where the hole was, not at the end. Under a live writer that moves rows between buckets, insertion order is therefore not something to build on:

cache.Remove("ORD-001");                                          // frees the middle slot
cache.AddOrUpdate(NewOrder("ORD-004", 42));                       // takes it: 003, 004, 002

rows = cache.Query().WithCustomerId(42).Execute();

The first lane decides the sequence

Later lanes only delete. Two queries with the same lanes in a different order return the same rows in different sequences — here the customer bucket is in insertion order while ORD-001, which moved to Pending last, sits at the end of the Pending bucket:

// Customer 42's bucket: 001 … 006 in insertion order. The Pending bucket: 002, 003, 007, then 001,
// which moved to Pending last. The survivors come out in the first lane's order.
var byCustomerFirst = cache.Query().WithCustomerId(42).WithStatus(OrderStatus.Pending).Execute();
var byStatusFirst = cache.Query().WithStatus(OrderStatus.Pending).WithCustomerId(42).Execute();

This is also why the performance advice to put the most selective lane first changes the sequence of an unsorted result: the plan and the order are the same decision.

A Range lane walks in key order

The B+ tree enumerates ascending by index key regardless of when rows were inserted. The order inside a run of equal keys is unspecified:

var rows = cache.Query().WithCreatedAtUnixMs(q => q.Gte(0L)).Execute();   // 001, 002, 003 — tree order, not insertion

No lane means the store's order

A Where-only query (and an Or placed before any lane) enumerates the store's hash table. The sequence is whatever the table's bucket layout is; it is stable while the table is unchanged and changes when it resizes, so read it as a set:

// A query with no index lane walks the store's hash table. The rows are right, their sequence is
// the table's and moves when it resizes — treat it as a set.
var all = cache.Query().Where(static o => o.Total > 0).Execute();

What does Sort guarantee?

Sort(comparer) and SortBounded(comparer) are the two sorted plans (classic full sort versus a top-k selection of the page; Sorted Paging says when to use which). Both are stable: rows the comparer calls equal keep their encounter order, which is the base walk's order from the section above. The classic plan gets this from StableSort; the bounded plan stamps each row with its encounter ordinal and breaks ties on it. So for the same query the two plans return the same rows in the same sequence:

// Pending before Paid, nothing else: every row of one status compares equal.
private readonly struct ByStatus : IComparer<Order> {
    public int Compare(Order? x, Order? y) => x!.Status.CompareTo(y!.Status);
}

// ByStatus orders Pending before Paid and nothing else. Comparer-equal rows keep their encounter
// order — the customer bucket's: 002, 003 (Pending) then 001, 004 (Paid).
var sorted = cache.Query().WithCustomerId(42).Sort(default(ByStatus)).Execute();
var bounded = cache.Query().WithCustomerId(42).SortBounded(default(ByStatus)).Execute(skip: 0, take: 4);

Stability is what makes pages partition the result: consecutive skip / take windows of an unchanged result cover every row exactly once, and their concatenation is the whole:

var whole = cache.Query().WithCustomerId(42).Sort(default(ByStatus)).Execute();
var page1 = cache.Query().WithCustomerId(42).SortBounded(default(ByStatus)).Execute(skip: 0, take: 2);
var page2 = cache.Query().WithCustomerId(42).SortBounded(default(ByStatus)).Execute(skip: 2, take: 2);

With a total comparer — one that never returns 0 for two distinct rows, like the generated OrderCache.ByCreatedAtComparer whose OrderId tiebreak follows CreatedAtUnixMs — stability no longer matters: the sequence is a function of the rows alone, on every path. That is the only ordering Prague promises outright, and it is the one to use for anything a user or a downstream system will compare.

What changes with Prepare()?

Nothing. Build() records the chain and replays it into the eager core on each execution, so a prepared query produces the eager spelling's rows in the eager spelling's order — including the first-lane rule above:

// Build() records the chain and replays it into the eager core on every execution, so a prepared
// query's rows come out exactly as the eager spelling's — same lanes, same order.
var eager = cache.Query().WithStatus(OrderStatus.Pending).WithCustomerId(42).Execute();

var prepared = cache.Prepare<int>()
    .WithStatus(OrderStatus.Pending)
    .WithCustomerId(static a => a)
    .Build();
using var rows = prepared.ExecutePooled(42);

What changes with BuildFrozen()?

The order of an unsorted result is no longer promised, and the order inside a tie group of a sorted one is not either. Everything else is unchanged: the same rows, the same Count, TotalCount and Truncated, pages that are slices of the same whole, and a sorted result with a total comparer that is byte-identical to eager. This is the ordering contract of FrozenOptions, decided so the pipeline could seed from the narrowest lane for each execution's arguments instead of the first declared one — the freedom that pays for the 3–36× in Prepared and Frozen Queries.

So the rows of an unsorted frozen result are the eager rows, as a set:

// Same rows, same Count — but the frozen pipeline seeds from the narrowest lane for this
// execution, so the sequence is not the eager one and is not promised.
var eager = cache.Query().WithCustomerId(42).WithStatus(OrderStatus.Pending).Execute();

var frozen = cache.Prepare<int>()
    .WithCustomerId(static a => a)
    .WithStatus(OrderStatus.Pending)
    .BuildFrozen();
using var rows = frozen.ExecutePooled(42);

In a sorted frozen result the comparer still decides the groups; the free seed changes the encounter ordinals the bounded container breaks ties on, so a group's internal order can differ from eager:

// The comparer decides the groups; nothing decides the order inside a group. Assert what the
// comparer says — Pending before Paid — and read each tie group as a set.
var frozen = cache.Prepare()
    .WithCustomerId(42)
    .Sort(default(ByStatus))
    .BuildFrozen();
using var rows = frozen.ExecutePooled();

A total comparer removes the groups and with them the freedom — eager and frozen agree row for row, on Sort and SortBounded alike:

// ByCreatedAtComparer comes from [DataCacheSort("ByCreatedAt", "CreatedAtUnixMs:-1", "OrderId:1")]:
// the OrderId tiebreak makes it total, so eager and frozen agree row for row.
var eager = cache.Query().WithCustomerId(42).SortBounded(OrderCache.ByCreatedAtComparer).Execute(skip: 0, take: 3);

var frozen = cache.Prepare()
    .WithCustomerId(42)
    .SortBounded(OrderCache.ByCreatedAtComparer)
    .BuildFrozen();
using var page = frozen.ExecutePooled(skip: 0, take: 3);

PreserveEagerOrder

When the eager sequence itself is the requirement — a golden test, a snapshot diffed row by row — set FrozenOptions.PreserveEagerOrder. It pins the seed to the first declared lane, walks the store for an Or-first plan the way eager does, and replays the one join shape whose fused form regroups rows (an inner JoinOne driven by a symmetric Many index on the left). The result is byte-identical to eager, at the cost of the plans the flag forbids — measured on the benchmark shapes, the pinned list ∩ list runs at 7.6 µs where the free seed runs at 1.3 µs:

var frozen = cache.Prepare<int>()
    .WithCustomerId(static a => a)
    .WithStatus(OrderStatus.Pending)
    .BuildFrozen(new FrozenOptions { PreserveEagerOrder = true });    // seed pinned to the first declared lane
using var rows = frozen.ExecutePooled(42);

Count ignores the flag; its rows carry no order.

In what order do join rows arrive?

A JoinOne resolver fills a slot on each row the base walk produced and creates no rows of its own, so a joined result keeps the base walk's sequence — the same first-lane rule, with a Right attached:

// A JoinOne fills a slot on each row the base walk produced; the rows keep the base order.
var plain = orders.Query().WithCustomerId(42).Execute();
using var joined = orders.Query().WithCustomerId(42).JoinWithCustomer().ExecutePooled();

Two exceptions are documented rather than promised: an inner JoinOne driven by a symmetric Many index on the left emits its rows grouped by right key on the eager path (its fan-out creates them per bucket), and a frozen chain that fuses it keeps the seed's order instead — the shape PreserveEagerOrder sends back to the replay.

A JoinMany slot — the QueryResults<TRight> you read as row.Right — is a set. The eager resolver fills it in the order the distinct rights were first recorded, the frozen fused fill in the bucket's order; with rights shared across lefts the two differ, and neither is a contract:

// The lines of one order arrive as a QueryResults<OrderLine> slot. Read it as a set: eager fills
// it in pair-set order and the frozen fused fill in bucket order — the same lines either way.
using var withLines = orders.Query().WithKey("ORD-001").JoinWithOrderLine().ExecutePooled();
var lineIds = withLines[0].Right!.Select(static l => l.LineId).ToArray();

Summary

Result Sequence Guaranteed?
eager or Build(), unsorted, one or more lanes first lane's enumeration order; survivors in place no — mechanism, not contract
eager or Build(), unsorted, no lane store hash order no
BuildFrozen(), unsorted the seed lane's order no — explicitly unspecified
Sort / SortBounded, comparer with ties comparer order, ties in encounter order (eager) or unspecified (frozen) the groups yes, the ties only on the eager path
Sort / SortBounded, total comparer comparer order yes, on every path
BuildFrozen(PreserveEagerOrder = true) the eager sequence yes, at a cost
JoinWith{T} rows the base walk's order as the base walk
a JoinMany slot bucket or pair-set order no — read it as a set

Where to go next

Prague documentation