Maintained Result Sets: Exact Top-N Under Continuous Change

#Abstract

A client subscribing to a filtered, sorted and limited query needs to be told exactly how the result set changes, not merely that it changed. This paper describes a construction maintaining the in-engine window as an exact prefix of the source-ordered result, using a cushion and keyset boundary refill, so that enter, leave, move and update deltas are exact at all times. The single-node case is implemented. The sharded case is not, and the correctness argument for it is incomplete.

#Problem

Given a query with a predicate, an ordering and a limit, and a stream of committed changes, produce for each subscriber a snapshot followed by a sequence of deltas such that applying the deltas to the snapshot yields at every moment the result the query would return if re-executed.

The naive implementation re-executes the query on every change, which is correct and does not scale. The common optimisation maintains a window of the top N rows in memory and updates it from the change stream, which scales and is incorrect at the boundary: a row leaving the window has no successor to promote, because the successor was never loaded.

#Construction

The window holds N + c rows, where c is a cushion. Deltas are emitted for the first N. When departures reduce the held set below N + c, a keyset query refills from the boundary.

The invariant maintained is that W is an exact prefix of the source-ordered result under σ. Given that, the first N rows of W are exactly the query result, and the four delta types are derivable by comparing successive states of that prefix.

Keyset rather than offset pagination is required, because offsets are not stable under concurrent insertion. This is the same reasoning that makes offset pagination unsuitable for any changing dataset [2].

#Correctness sketch

Three cases must preserve the prefix invariant.

1. Insert. A row satisfying σ is positioned by the ordering. If it falls within the held prefix it enters, displacing at most one row past position N, which leaves. If it falls beyond the held prefix it is ignored, which is sound because the prefix remains a prefix.
2. Delete or predicate exit. The row leaves. If it was within the first N, the row at position N + 1 enters. The cushion guarantees such a row is held unless the underlying result is genuinely shorter, and refill restores the cushion.
3. Update. If the sort key is unchanged, an update delta is emitted. If it changed, the operation is treated as a delete followed by an insert, which reduces to the previous cases.

The argument depends on changes being observed in the order the source committed them. Per-aggregate ordering from a versioned log provides this [1], and isolation level determines what "the result the query would return" means for concurrent transactions [3] [4]. The implementation assumes read-committed semantics at the source and states so, because under weaker isolation the target itself is ambiguous [5].

#Cost

Memory is O(N + c) per subscription. The refill cost is one indexed query per boundary crossing, and the crossing rate depends on churn near position N rather than on total change rate, which is the property that makes the construction practical: a high-churn dataset with a stable top N is inexpensive.

Choosing c trades memory against refill frequency. A cushion of roughly twenty per cent of N was adequate in the workloads examined, and no principled method for choosing it is offered.

#The sharded case

Where the source is partitioned, each shard can maintain a local prefix, and the global prefix is a merge of local prefixes. The complication is that a shard holding no rows near the global boundary cannot know whether its next row would enter, so either every shard maintains a cushion sized for the worst case or the merge coordinator issues boundary queries.

Neither has been implemented, and the correctness argument above does not extend without a stated ordering across shards. Where the ordering key is not globally comparable, the construction does not apply at all, and a conflict-free replicated formulation may be a better fit [6].

#Limitations

Single-node only, as above. No measurement of refill frequency against churn distribution is reported. The cushion parameter is chosen empirically. The construction assumes a total order on the sort key and degrades to re-execution when the ordering involves a computed expression the source cannot index.