Skip to content

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

Open

Description

@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.

Activity

  1. QuantumExplorer commented on Aug 29, 2026

    @QuantumExplorer
    Member

    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.

  2. QuantumExplorer commented on Aug 30, 2026

    @QuantumExplorer
    Member

    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.

  3. QuantumExplorer commented on Aug 30, 2026

    @QuantumExplorer
    Member

    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.

  4. QuantumExplorer commented on Aug 30, 2026

    @QuantumExplorer
    Member

    The full stack is now merged into v4.2-dev:

    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 at onto an already-registered contract (needs a grovedb rebuild-as-cidx migration), and the sum axes alongside at.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions