Repository navigation
Description
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 needgroupBy: hashtag— a prefix level. - Creator leaderboard:
like [postAuthor, postId] → $ownerIdserves an author's top posts, but "top authors by likes received" needs thepostAuthorlevel.
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
- 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 torankedSummable. - 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 withpreallocated(drained groups stay rankable at 0). - Query/proof:
documents.ranked({ groupBy: '<prefix property>' })dispatches when the group property matches a declaredatlevel; proofs ride the existing indexed-axis PathQuery surface (refactor(drive)!: route ranked and having-range proofs through grovedb's unified PathQuery surface #4488). - 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.
Activity
QuantumExplorer commentedon Aug 29, 2026
Built this out as four PRs:
feat(dpp): therankedCountable: { "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 aboveat).atnaming the last property canonicalizes to today's boolean form.feat(drive)(stacked): the storage chain. Theatlevel's property-name tree becomes the Count-axisProvableCountIndexedTreeoverCountTreevalue 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,preallocatedcomposition and grovedb's integrity sweep.feat(drive)(stacked): the query surface.documents.ranked({ groupBy: 'hashtag' })dispatches whengroupBymatches a declaredatlevel — withaton the first property that's the global "top hashtags by total likes" with nothing pinned; a middle-levelatpins 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)(independent): the smaller sibling. Prefix-pinned count queries (count WHERE hashtag == Xon[hashtag, postId]) are served off the terminal property-name tree's own element aggregate — one element read with proof, working on already-registeredrangeCountablecontracts.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, theatform lays the chain out count-bearing from theatlevel 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 aNormalTreeprefix 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_secondariesis repair-only, requiring the tree to already be indexed). Enablingaton 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
atform is Count-axis only for now (it rejectsrankedSummable/rankedAverageableon 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 anat-form index keeps its terminal non-indexed, so the two features compose on the same index: group ranking at theatlevel and prefix-pinned totals off the terminal, which covers the yappr shape end to end.feat(dpp): rankedCountable.at array form declares both the prefix and…
test(drive): pin the both-levels ranked chain end to end
feat(drive): resolve the ranked level from the pin count so one index…
QuantumExplorer commentedon Aug 30, 2026
Follow-up: the "one ranked level per index" restriction is lifted.
atnow 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
ProvableCountIndexedTreeas 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.feat(dpp): rank any subset of an index's levels — ranked_countable_at…
test(drive): pin the fully ranked chain — every level of one index ra…
feat(drive): serve rankings at every declared level of an index
QuantumExplorer commentedon Aug 30, 2026
One more lift: the "at most one non-terminal level" scope note is gone.
atnow 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 alongsideat.fix(dpp): address ranked-at review findings — level-key identity, ter…
feat(drive): lay out and maintain the prefix-level ranked count chain
test(drive): pin the both-levels ranked chain end to end
test(drive): pin the fully ranked chain — every level of one index ra…
feat(drive): serve ranked and having-range queries at a prefix rankin…
feat(drive): resolve the ranked level from the pin count so one index…
feat(drive): serve rankings at every declared level of an index
test(drive): cover the untested prefix-ranking behaviours codecov sur…
test(drive): cover the prefix-count builder arm the two-property fixt…
feat(drive): serve ranked and having-range queries at a prefix rankin…
feat(drive): resolve the ranked level from the pin count so one index…
feat(drive): serve rankings at every declared level of an index
QuantumExplorer commentedon Aug 30, 2026
The full stack is now merged into
v4.2-dev:255a5d60ca) — therankedCountable: { "at": … }grammar, level-addressed: one property, or any subset of the index's levels (a fully ranked[tag, region, postId]is legal), with all validation and the update-immutability rules.4e7831c76c) — the storage chain: nested Count-axis indexed trees at every declared level, maintained entirely by grovedb's existing deep-write propagation, including thepreallocatedcomposition (groups surface in the secondary at zero before any entry exists, and drains keep them rankable at zero).a77d0d9b2a) — the query surface: each declared level serves its own ranking, addressed by the (group property, pin count) pair, with proofs; the having-range surface generalizes through the same resolution.So on the yappr shape,
[hashtag, postId]with{ "at": ["hashtag", "postId"] }now serves "top hashtags by total likes" AND "top posts within a pinned hashtag" from one index, proofs included.Still open: #4537 (the prefix-pinned count sibling — independent, mergeable). Not pursued, as discussed above: retrofitting
atonto an already-registered contract (needs a grovedb rebuild-as-cidx migration), and the sum axes alongsideat.feat(drive): serve prefix-pinned count queries off the terminal aggre…
test(drive): cover the prefix-count builder arm the two-property fixt…
test(drive): prove the at-form composition now that the ranking stack…
feat(drive): serve short-prefix counts off an at-chain's value trees