Prefix-level rankedCountable: place a CountIndexedTree at a non-terminal index level to rank groups by subtree count

[PastaPastaPasta]

Problem

The v14 ranked machinery groups at exactly one level: the deepest prefix property of an index, ranked by direct member count. Ranking one level higher — groups by their whole-subtree totals — is not expressible, and it blocks two natural features on the indexOnly-likes shape this repo itself ships as its reference fixture (yappr-likes-contract.json):

• Trending hashtags: like [hashtag, postId] → $ownerId (rankedCountable) serves top posts within a pinned hashtag, but "top hashtags by total likes" would need groupBy: hashtag — a prefix level.
• Creator leaderboard: like [postAuthor, postId] → $ownerId serves an author's top posts, but "top authors by likes received" needs the postAuthor level.

Shortening the index is not a workaround: on an indexOnly type, [hashtag] → $ownerId makes (hashtag, liker) the entry itself, so structural uniqueness limits each identity to one like per hashtag ever (and [postAuthor] → $ownerId to one like per author — we reproduced the 40105 on devnet). The prefix-pinned count query (count WHERE hashtag == X on the two-property index) is also refused by the exact-index-match rule, so the totals can't even be read individually.

The data already exists; so does the structure

With countable on the index, the prefix level is a CountTree: every hashtag's (or author's) whole-subtree like total is already maintained on chain — it just has no by-count ordering, so top-K over it would be O(n). GroveDB already has the right primitive: CountIndexedTree (cidx), the same order-statistic tree that backs today's group-level ranking, benchmarked in-repo (grovedb/benches/cidx_benchmark.rs: "Top-k by count: O(log n + k) for cidx vs O(n) for plain CountTree").

So the request is not a new data structure — it is wiring the existing cidx one level higher.

Proposed design

1. Grammar: allow the ranked axis to name the level it aggregates at, e.g.
   "rankedCountable": { "at": "hashtag" } on [hashtag, postId] (default: today's behavior). Same shape could later generalize to rankedSummable.
2. Storage/maintenance: a cidx at the declared prefix level, keyed by each group's subtree count. The count deltas already propagate through the CountTree hierarchy on every insert/delete; the new work is re-keying the affected group's cidx entry per delta — the same O(log n) pattern (bench: (k+1)·O(log n) write amplification) as existing ranked maintenance. Composes with preallocated (drained groups stay rankable at 0).
3. Query/proof: documents.ranked({ groupBy: '<prefix property>' }) dispatches when the group property matches a declared at level; proofs ride the existing indexed-axis PathQuery surface (refactor(drive)!: route ranked and having-range proofs through grovedb's unified PathQuery surface #4488).
4. Backfill / retrofit: because the CountTree at that level already stores every group's total, the cidx can plausibly be constructed from existing state at activation — allowing the flag to be enabled on an already-registered contract rather than forcing a re-registration. Confirming whether this is feasible would be valuable independent of the rest.

Smaller independent sibling

Relaxing the exact-index-match rule to allow prefix-pinned count queries (count WHERE hashtag == X on [hashtag, postId]) would expose the already-maintained totals as point lookups (e.g. a "likes received" profile stat) even before ranking ships.

Context

Verified against a live 4.2.0-dev.5 devnet with an indexOnly likes contract modeled on the pinned fixture: group-level ranking, structural uniqueness, and the prefix-count refusal all behave as described (exact error/behavior notes available on request). This is the last structural gap for like-derived discovery surfaces on the indexOnly shape — everything else (counts, membership with absence proofs, group-level top-K, delete-by-values) works end to end.

[QuantumExplorer]

Built this out as four PRs:

• feat(dpp): rankedCountable at-form for prefix-level count ranking #4531 — feat(dpp): the rankedCountable: { "at": "<property>" } grammar, the derived index-level stamps, and all validation (prerequisites, immutability, the at-level-exclusivity rule, and the aggregating-prefix rule one level above at). at naming the last property canonicalizes to today's boolean form.
• feat(drive): storage layout and maintenance for prefix-level ranked count indexes #4533 — feat(drive) (stacked): the storage chain. The at level's property-name tree becomes the Count-axis ProvableCountIndexedTree over CountTree value trees, with every level down to the terminal count-bearing. As the issue anticipated, no grovedb changes were needed — the one Drive-side change is that the chain's continuations are inserted contributing instead of zero-wrapped, and grovedb's existing deep-write propagation re-keys the group's secondary entry on every insert/update/delete. Verified e2e on the indexOnly shape (per-owner structural uniqueness intact), with drains, preallocated composition and grovedb's integrity sweep.
• feat(drive): serve ranked and having-range queries at a prefix ranking level #4535 — feat(drive) (stacked): the query surface. documents.ranked({ groupBy: 'hashtag' }) dispatches when groupBy matches a declared at level — with at on the first property that's the global "top hashtags by total likes" with nothing pinned; a middle-level at pins the properties before it (IN fan-out included). Proof round trips verify against the live root hash; the having-range surface generalizes through the same shared resolution.
• feat(drive): serve prefix-pinned count queries off the terminal aggregate #4537 — feat(drive) (independent): the smaller sibling. Prefix-pinned count queries (count WHERE hashtag == X on [hashtag, postId]) are served off the terminal property-name tree's own element aggregate — one element read with proof, working on already-registered rangeCountable contracts.

Two findings worth flagging:

One correction to the premise: the prefix level is not a CountTree today — counts stop at the terminal property-name tree (that's what the exact-index-match rule was protecting). The total the sibling reads lives one level lower than the issue assumed, at …/hashtag/X/postId (the terminal property-name tree's root aggregate), which is also why #4537 needs no storage change. For the ranking itself, the at form lays the chain out count-bearing from the at level down — opt-in per index, so existing layouts are untouched.

Backfill / retrofit (item 4) is not feasible at the current pin: grovedb has no promote-in-place path — a ProvableCountTree (let alone a NormalTree prefix level, which is what actually exists today) cannot be converted to a cidx, and adding an axis to a populated indexed tree is rejected ("no reindex path"; reconcile_indexed_tree_secondaries is repair-only, requiring the tree to already be indexed). Enabling at on an already-registered contract would need new grovedb work (an explicit rebuild-as-cidx migration op) plus a platform migration story; as designed it requires a re-registration.

Two scope notes: the at form is Count-axis only for now (it rejects rankedSummable/rankedAverageable on the same index — the count-propagation chain can't carry a sum axis; the generalization the issue sketches would follow the same pattern with sum-bearing chain levels). And #4537 can't serve a terminal-ranked index (its terminal element is an indexed tree, which grovedb's query dispatch refuses to return) — but an at-form index keeps its terminal non-indexed, so the two features compose on the same index: group ranking at the at level and prefix-pinned totals off the terminal, which covers the yappr shape end to end.

[QuantumExplorer]

Follow-up: the "one ranked level per index" restriction is lifted. at now accepts an array, so "rankedCountable": { "at": ["hashtag", "postId"] } on [hashtag, postId] declares both rankings on one index — top hashtags by total likes and top posts within a pinned hashtag, which is the full Yappr shape on a single index.

A direct probe against the pinned grovedb confirmed the nested shape (the terminal ProvableCountIndexedTree as a contributing child inside the prefix chain's count tree) works end to end at the current pin — counts propagate through it, both secondaries re-key on writes and deletes, and the integrity sweep stays clean — consistent with the book's "write amplification linear in the number of indexed levels" framing. No grovedb changes needed here either; landed across #4531 (grammar), #4533 (storage e2e — zero storage-code change was required), and #4535 (the query resolution now derives the ranked level from the request's pin count, since the index alone no longer determines it).

Still scoped out: more than one non-terminal level per index, and the sum axes alongside at.

[QuantumExplorer]

One more lift: the "at most one non-terminal level" scope note is gone. at now takes any subset of the index's properties — "rankedCountable": { "at": ["tag", "region", "postId"] } ranks every level of a three-property index, bounded only by the existing 10-property index cap. A four-deep nested-cidx probe against the pinned grovedb confirmed the chain composes at arbitrary depth (each ranked tree a contributing child of the level above; one leaf write re-keys every secondary on its path, matching the book's linear-in-k framing), and the platform storage layer needed no code changes beyond the level-set stamps — the same derivation and contributing-insert paths lay the whole chain down. Landed on #4531 / #4533 / #4535. Remaining scope note is just the sum axes alongside at.