Skip to main content

Module drive_document_ranked_query

drive::query

Module drive_document_ranked_query 

Source
Expand description

A query to rank an index’s groups by a per-group aggregate — “top 5 restaurants by average grade” — reading grovedb’s per-axis secondary Merk of an indexed tree (PR #657, PV14). Unlike the count / sum / average surfaces this one never opens the value trees: the ordering is maintained on write, so a ranked read is O(log n + k) with a proof. Types and module structure for the ranked (top-k / bottom-k) document query — SELECT <agg> GROUP BY <prop> ORDER BY <agg> DESC LIMIT n OFFSET m.

A ranked query answers “which n groups score highest (or lowest) on an aggregate, starting from rank m?” in O(log n + k) with a proof, by reading grovedb’s per-axis secondary Merk of an indexed tree (grovedb PR #657). The contract opts in per index via rankedCountable / rankedSummable / rankedAverageable (meta schema v3 / PV14); the write path keeps the secondaries in sync. See [crate::drive::document::ranked_index_tree_type] for the storage layout this query reads.

The implementation is split across siblings, mirroring [super::drive_document_count_query]:

§What makes this query shape different

Every other aggregate query in this crate walks value trees under a property-name tree and aggregates what it finds. A ranked query never touches the value trees at all: the answer lives pre-sorted in the secondary Merk, keyed by (sort_key ‖ group_key). Three consequences shape the API:

  1. where clauses are equality pins on a compound prefix — or absent. A single-property ranked index has no prefix to narrow, so its requests carry no where. A compound ranked index [p1, …, pn] maintains one secondary per prefix value (per-prefix semantics: each terminal pn property-name tree, inside the [p1, …, pn-1] value trees, is its own indexed tree — grovedb creates and populates it in the same document batch), so a request must pin every leading property with an equality clause to name which prefix’s secondary the walk reads. A where on the grouped (terminal) property itself would ask for a filtered ranking, which no secondary can express — it is sorted by aggregate, not by group key — and is rejected rather than silently ignored, as is any non-equality prefix clause except one IN: exactly one leading pin may carry 2..=[MAX_PREFIX_IN_BRANCHES] distinct elements (a single-element IN normalizes to the equality pin), read as one walk per element and merged by (aggregate, encoded pin, group key), proved in a single branched PathQuery envelope with per-element authenticated absence. A null pin cannot combine with an IN (null addresses its prefix through an empty path segment the branched proof cannot express), and OFFSET is rejected together with IN.
  2. limit is mandatory, offset is depth-bounded, start_at is refused. limit is the k of the walk and the ranked surface has no server default for it, so it must be supplied. offset is the rank the page starts at and is unbounded above: grovedb counts the skipped region from the subtree aggregates rather than walking it entry by entry, so both executors are O(log n + k) regardless of offset and a large offset is not a cost lever on either. Only the proved result additionally attests the count. So the offset needs no ceiling. start_at / start_after name a document id, which does not appear anywhere in an aggregate-ordered keyspace.
  3. Entry order IS the ranking order. The executor returns entries in the order grovedb walked the secondary; callers must not re-sort. Ties are broken by group key — see DriveDocumentRankedQuery::descending.

Re-exports§

pub use drive_dispatcher::DocumentRankedRequest;
pub use drive_dispatcher::DocumentRankedResponse;

Modules§

drive_dispatcher
Top-level dispatcher for the ranked (ORDER BY <aggregate> LIMIT n OFFSET m) request.
execute_top_k
The two ranked executors on DriveDocumentRankedQuery: a direct read of the axis secondary, and generation of the equivalent proof.
executors
Per-mode ranked executors on impl Drive. One file per response shape — the dispatcher (super::drive_dispatcher) picks between them on the request’s prove flag.
index_picker
Covering-index picker for the ranked query, plus the shared prefix-value encoding.
mode_detection
Request-shape validation for the ranked query, and the versioned (select, group_by, order_by, limit, offset) → DocumentRankedMode resolution.
path
The grove path a ranked read / proof / verification is issued against.

Structs§

DocumentRankedMode
The resolved shape of a ranked request: which axis, which direction, how many groups, and the (group property, aggregate field) pair the index picker needs.
DriveDocumentRankedQuery
A resolved ranked query. Shared by the prover and the verifier — both build the grove path through DriveDocumentRankedQuery::indexed_property_name_tree_path, so the two cannot drift on which subtree the proof is about.
PrefixPin
One pinned leading property of the covering compound index.
RankedEntry
One group in a ranked result: the group’s index key plus its aggregate.
RankedPage
A page of a ranked result: the entries, plus how many ranks were actually skipped to reach them.
RankedPaginationInputs
The pagination knobs a ranked request carries, bundled so the versioned validator reads them in one place.

Enums§

RankedAxis
Which per-group aggregate the groups are ranked by.
RankedEntryValue
The aggregate value carried by one ranked entry. Mirrors grovedb’s [grovedb::operations::proof::indexed_axis::AxisEntries] variants exactly, one scalar at a time, so a Vec<RankedEntry> and an AxisEntries carry the same information with the same types.

Constants§

MAX_PREFIX_IN_BRANCHES
Hard ceiling on the element count of the (at most one) IN prefix pin — the number of prefix branches one ranked / having-range request may fan out into.
MAX_RANKED_LIMIT
Hard ceiling on k (the request’s LIMIT).
RANKED_AVG_SCALE
The fixed-point scale grovedb’s Avg axis sorts by: avg_fixed_point = floor(sum * RANKED_AVG_SCALE / count) with euclidean (toward -∞) division.
RANKED_COUNT_ORDER_KEY
The ORDER BY field name that means “the group’s COUNT(*)”.

Functions§

present_entries_on_axis
Entries read on read_axis_for’s axis, presented on the requested axis: document counts read from sums come back as counts. A no-op whenever the read axis is the requested one.
read_axis_for
The axis whose secondary a ranked or having read of index walks for a request on axis: the requested one, except that a document count (Count) over a summableOffCountIndex index walks the Sum secondary. Such an index’s counters each count one group in its count trees and add their group’s documents to its sums, so its sums are its document counts (document_count_of_element).