8000 Sorted-set rank and range commands are slow on large datasets · Issue #875 · kividbio/kividb · GitHub
[go: up one dir, main page]

Skip to content

Sorted-set rank and range commands are slow on large datasets #875

Open

Description

@Parikalp-Bhardwaj

Several sorted-set commands scan entries because SortedSetInner::by_score uses a BTreeMap without subtree counts.

This affects ZRANK, ZREVRANK, indexed ZRANGE, and ZCOUNT.

With 1 million members, ZRANK near the end takes 6.185 ms in KiviDB vs 0.078 ms in Redis (79× slower).

Results

Average latency:

Command KiviDB Redis Slowdown
ZRANK z m999990 6.185 ms 0.078 ms 79.3×
ZREVRANK z m500000 2.151 ms 0.147 ms 14.6×
ZRANGE z 500000 500009 3.142 ms 0.156 ms 20.1×
ZCOUNT z 1000 999000 6.059 ms 0.141 ms 43.0×

Tested on KiviDB 40e12b01 and Redis 8.10.3 with 1 million members, 200 requests, and 1 client. These are single-run local measurements.

What's causing this?

SortedSetInner::by_score uses:

BTreeMap<(OrderedFloat<f64>, ZMember), ()>

The commands walk through entries to find positions or count matches:

  • ZRANK / ZREVRANK use .range(...).count().
  • Indexed ZRANGE uses .skip(start).
  • ZCOUNT uses .range(range).count().

These operations can take O(N) time. As the sorted set grows, queries near the end or across large ranges become slower.

Code: src/commands/zset.rs

What could we improve?

We could look into an order-statistic index to find ranks and positions without scanning preceding entries.

For ZCOUNT, using the difference between boundary ranks could avoid counting every matching entry.

We should benchmark memory usage and ZADD/ZREM performance before making changes.

Related to #862, where random sampling also has inefficient positional access.

Activity

  1. murtazayusuf commented on Nov 17, 2026

    @murtazayusuf
    Contributor

    Thanks @Parikalp-Bhardwaj, right on all four: .range(..).count() and .skip(start) walk the tree, and BTreeMap has no subtree counts to jump by. This is the sorted-set half of the collection storage work that #872 started (your integer sets are on master through it), and it joins #862 (ZRANDMEMBER walking the set) and #825 (800-member sets at 1.5x Redis's memory): all three want the same thing, an ordered index that knows ranks.

    How I'd split it, if you want the large-set half:

    • Small sorted sets (up to 128 members of up to 64 bytes, as Redis's listpack): I'm doing these next, as one packed block kept in score order, like the set block in src/packed_set.rs. Rank is then the position, and there is nothing to design for it.
    • Large sorted sets: an order-statistic index in place of BTreeMap<(score, member), ()>. This is the part with real choices, and it is yours if you'd like it. What it has to meet:
      • ZRANK/ZREVRANK, ZRANGE by index, ZCOUNT/ZLEXCOUNT (difference of two ranks), ZREMRANGEBYRANK and ZRANDMEMBER (a random rank) in O(log N);
      • memory per member goes down, not up: today a member is in the hash map and again in the tree, each holding an Arc (115.9 B a member at 3M 14-byte members, Redis 75.2). A counted B-tree whose leaves hold the entries, with the hash map pointing into it or holding only what it must, should be well under that; a skiplist as Redis has it is the comparison, not the target;
      • ZADD/ZREM/ZINCRBY/ZSCORE cost no more instructions than today (ZADD 5,991 and ZSCORE 6,379 per command on an 8-member set on master; measure large sets too), and nothing on the GET/SET path moves;
      • nothing on disk or on the wire changes (a sorted set is written as members and scores);
      • the type stays behind SortedSetInner's methods: today its two maps are pub and used directly in several files, so the first PR is probably just closing that off (no behaviour change), which also makes the small-set block possible. If you do that one first, I'll build the block on it.

    Numbers before code for the index itself: a note here with the structure you'd pick, its bytes per member and what a ZADD costs in it, and we settle it before the PR. Say if you'd rather I take all of it.

  2. Parikalp-Bhardwaj commented on Nov 17, 2026

    @Parikalp-Bhardwaj
    CollaboratorAuthor

    I am looking into ways to improve the sorted-set storage. An order-statistic tree could help with rank queries, indexed ranges, and the random sampling issue in #862.

    I'm thinking of testing a counted B-tree and a skiplist with spans to compare memory usage and ZADD/ZREM performance, @murtazayusuf any preference before I start working on a prototype?

  3. murtazayusuf commented on Nov 17, 2026

    @murtazayusuf
    Contributor

    A preference, yes: the counted B-tree, and I'd only build the skiplist far enough to have its numbers beside it.

    Why: a skiplist with spans is a node per member with a tower of pointers and spans (on average about two levels, 16 bytes each, plus the backward pointer and the node's own allocation header), which is where Redis's 75 bytes a member come from, and every step down it is a cache miss. A B-tree with wide nodes keeps 30 to 60 entries per allocation, a count per child gives rank in one descent, and a range is a walk along leaves that are already in the cache.

    The layout I'd try first, because it also removes the second copy of every member:

    • One block per member, allocated once: score: f64, length, the member's bytes. Nothing else owns the bytes; no Arc.
    • The hash index (for ZSCORE, ZADD's lookup) is a table of 8-byte pointers to those blocks, hashed and compared through the pointer (as src/store/entry.rs does for the keyspace, and MemberSet's table does with HashTable). The score is read from the block, so the map no longer stores it.
    • The ordered index is the counted B-tree, its entries (score, pointer): 16 bytes, ordered by score and then by the member's bytes through the pointer. The score in the entry means a descent compares floats and only touches a block on a tie.

    At 14-byte members that is roughly a 32-byte block, 8 / 0.6 ≈ 13 for the table and 16 / 0.7 ≈ 23 for the tree: about 68 bytes a member against 115.9 today and Redis's 75. Those are my estimates; your prototype is what decides it.

    Things that will bite, so they're in from the start:

    • A score change is remove-then-insert in the tree with the block updated in between; the block's address must not change while the tree holds it.
    • Iteration order for equal scores is by member bytes (Redis's order), and -0/0 and NaN handling stay as SortedSetInner::insert has them today.
    • Freeing: a set with a million blocks is a million frees; it has to go through the lazy-free path with an honest estimate, like the other large collections.
    • unsafe is fine for the blocks if it is confined to one small module with its invariants written down and a model test against BTreeMap + HashMap over long random sequences (inserts, score changes, removals, rank and range queries checked at every step), run under Miri if it can be.

    Assigned to you. The SortedSetInner closing-off PR first would help both of us.

  4. Parikalp-Bhardwaj commented on Nov 17, 2026

    @Parikalp-Bhardwaj
    CollaboratorAuthor

    Thanks @Parikalp-Bhardwaj, right on all four: .range(..).count() and .skip(start) walk the tree, and BTreeMap has no subtree counts to jump by. This is the sorted-set half of the collection storage work that #872 started (your integer sets are on master through it), and it joins #862 (ZRANDMEMBER walking the set) and #825 (800-member sets at 1.5x Redis's memory): all three want the same thing, an ordered index that knows ranks.

    How I'd split it, if you want the large-set half:

    • Small sorted sets (up to 128 members of up to 64 bytes, as Redis's listpack): I'm doing these next, as one packed block kept in score order, like the set block in src/packed_set.rs. Rank is then the position, and there is nothing to design for it.

    • Large sorted sets: an order-statistic index in place of BTreeMap<(score, member), ()>. This is the part with real choices, and it is yours if you'd like it. What it has to meet:

      • ZRANK/ZREVRANK, ZRANGE by index, ZCOUNT/ZLEXCOUNT (difference of two ranks), ZREMRANGEBYRANK and ZRANDMEMBER (a random rank) in O(log N);
      • memory per member goes down, not up: today a member is in the hash map and again in the tree, each holding an Arc (115.9 B a member at 3M 14-byte members, Redis 75.2). A counted B-tree whose leaves hold the entries, with the hash map pointing into it or holding only what it must, should be well under that; a skiplist as Redis has it is the comparison, not the target;
      • ZADD/ZREM/ZINCRBY/ZSCORE cost no more instructions than today (ZADD 5,991 and ZSCORE 6,379 per command on an 8-member set on master; measure large sets too), and nothing on the GET/SET path moves;
      • nothing on disk or on the wire changes (a sorted set is written as members and scores);
      • the type stays behind SortedSetInner's methods: today its two maps are pub and used directly in several files, so the first PR is probably just closing that off (no behaviour change), which also makes the small-set block possible. If you do that one first, I'll build the block on it.

    Numbers before code for the index itself: a note here with the structure you'd pick, its bytes per member and what a ZADD costs in it, and we settle it before the PR. Say if you'd rather I take all of it.

    Thanks @murtazayusuf i will take care of the large sorted-set work, will first move the direct map access into SortedSetInner methods without changing the current behavior.
    Then i will compare memory usage per member and ZADD/ZREM performance before deciding on the new index.

  5. murtazayusuf commented on Nov 18, 2026

    @murtazayusuf
    Contributor

    @Parikalp-Bhardwaj #892 is merged, so the two next steps can go side by side without touching the same code: you take the counted tree (rank, ZRANGE by index far in, ZCOUNT by subtracting ranks, ZRANDMEMBER by position: this issue and #862), and I take the packed block for small sorted sets (#825, the sorted-set row of #297), behind the same SortedSetInner methods. If you would rather split it another way, say so here before either of us starts on the other half. For the tree: range_by_rank, count_by_score/count_by_lex and member_at are the methods I would add to the type first, so both representations answer them.

  6. Parikalp-Bhardwaj commented on Nov 18, 2026

    @Parikalp-Bhardwaj
    CollaboratorAuthor

    @murtazayusuf I've been looking into the counted B-tree layout and memory usage before starting the implementation. I'm thinking of using stable member blocks with 8-byte pointers, a pointer-based hash table, and a counted B-tree with 31 entries per node.
    For a 14-byte member name, the block would need 26 bytes including the 12-byte header, but the actual allocation is around 32 bytes on macOS/mimalloc and an estimated 48 bytes on glibc. With 3M members, the current implementation uses 115.9 B/member with ascending inserts. The new approach could bring this down to around 56 B/member with position-aware splits or 64 B/member with random inserts, based on KiviDB's memory accounting. These are just estimates for now. On glibc, actual allocation could be around 78–86 B/member, which I'll verify on Linux before comparing with Redis. I am planning to build a counted B-tree prototype and compare memory usage, ZADD, ZREM, and ZSCORE against master. I'll also check pointer stability before trying value_slab.
    Does this approach look good to you? Also, should we prioritize KiviDB's used_memory or actual allocator-allocated bytes for memory comparisons?

  7. murtazayusuf commented on Nov 18, 2026

    @murtazayusuf
    Contributor

    @Parikalp-Bhardwaj measuring before building is the right order. Answers and two things to weigh:

    • Which number: both, but the bar is Linux with the default build, which uses glibc's allocator: used_memory (what we publish against Redis's used_memory) and RSS (what an operator pays for). macOS/mimalloc numbers are fine for iterating, not for the comparison. Compare against Redis 8.10.2 on the same box at 3M members with ascending and random inserts, and at 10k.
    • Scope: I've started the packed block for small sorted sets (up to zset-max-listpack-entries, 128 members, and 64-byte members), so the tree only has to be good above that; it does not need a small-set mode.
    • The per-member allocation is where glibc hurts (your 26 bytes becoming 48). Before settling on one block per member, please prototype the alternative where members live inside the leaves (or in chunk buffers the leaves po 10000 int into, as the chunked lists do), with the hash table holding member → score as today and lookups by member going hash → score → tree by (score, member). That drops the per-member malloc header and the pointer, at the price of moving bytes on a split. A table with bytes per member and instructions for ZADD new/existing, ZSCORE, ZREM, ZRANK, ZRANGE 0 9 far in, for both layouts against master, decides it.
    • 31 entries a node sounds right for a start; let the ZRANK/ZRANGE-by-index rows and the bytes pick the final fanout.
    • Pointer stability / value_slab: only worth it if the stable-block layout wins the table above; otherwise it is solving a problem the other layout does not have.

    The methods to add to SortedSetInner first, so both representations answer them: range_by_rank, count_by_score, count_by_lex, member_at. Hot-path rule as always: GET/SET must not move, and every sorted-set row in the #892 table gets re-measured on the release profile as shipped.

  8. Parikalp-Bhardwaj commented on Nov 18, 2026

    @Parikalp-Bhardwaj
    CollaboratorAuthor

    Thanks @murtazayusuf that makes sense, i will compare stable member blocks with storing members directly in leaves or chunks, including hash index overhead and node splits.
    I will run the memory benchmarks on Linux with the default allocator and Redis 8.10.2, using 10k and 3M members with both insertion patterns and also compare CPU instructions against master and recheck the #892 regression cases and share the results here before deciding which approach to use.

  9. murtazayusuf commented on Nov 18, 2026

    @murtazayusuf
    Contributor

    @Parikalp-Bhardwaj heads-up for your prototype: #926 is merged. SortedSetInner now has a packed form for sets of up to 128 members, and the large form (your side) is boxed behind it, so the per-key handle went from 88 to 32 bytes; the methods you call are the same. Please start from current master. One number that bears on your target: lifting the packed limit to 1,024 members would put #825's 800-member feeds at about 30 B a member (121 today, Redis with its limit raised 20.7) for roughly +8% on ZSCORE at 512 members and +16% at 1,024, so the tree mainly has to win above about a thousand members and on rank/range cost; worth keeping in mind when you pick the fanout and the layout.

  10. Parikalp-Bhardwaj commented on Nov 19, 2026

    @Parikalp-Bhardwaj
    CollaboratorAuthor

    Thanks @murtazayusuf! i saw #926 is merged, so i will update my counted-tree worktree to the latest master. The 10k-member baseline is complete, with all 234 measurements passing. KiviDB used around 10× more Callgrind instructions for ZRANK and 17× more for deep ZRANGE compared to Redis 8.10.2. I'm now testing the 3M-member memory baseline and comparing stable member blocks with leaf/chunk storage. I'll also check sizes around the 1,024-member limit and share the results before starting the implementation.

  11. Parikalp-Bhardwaj commented on Nov 20, 2026

    @Parikalp-Bhardwaj
    CollaboratorAuthor

    Hi @murtazayusuf , i have been working on a counted B-tree for KiviDB sorted sets to improve rank operations and reduce memory usage. The local implementation is showing promising results. Rank operations are much faster, and memory usage is around 15–29% lower. There are still some regressions in ZSCAN, ZADD, ZINCRBY, and GEOSEARCH that I'm investigating. Would you prefer I open a draft PR now for design feedback, or fix the major regressions first?
    I haven't pushed anything yet.

  12. murtazayusuf commented on Nov 20, 2026

    @murtazayusuf
    Contributor

    @Parikalp-Bhardwaj open the draft now, please. The layout is the part that is expensive to change later, so I'd rather look at it before you spend time on the regressions; some of them may come from the layout and go away with a different choice.

    Before you push, rebase onto today's master, because the sorted-set code moved under you:

    In the draft description, the things I need to judge it:

    • the layout in a few lines: what a leaf holds (members inline or pointers to stable blocks), fanout, how score → member and member → score are both answered, and what one member costs in bytes at 1k, 10k and 3M members next to master and Redis 8.10.2;
    • instructions for ZADD (new and existing member), ZINCRBY, ZSCORE, ZRANK, ZRANGE shallow and deep, ZRANGEBYSCORE, ZPOPMIN, ZREMRANGEBYRANK, GEOSEARCH, against master built in the same session with the same compiler (fat LTO, scripts/perf/run.sh), with the regressions left in and marked;
    • the plain GET/SET rows from the same run (LTO=fat EXEC=1 CMP=plain): they must not move;
    • what is not done yet.

    Sets of up to 128 members stay in the packed form, so the tree only has to win above that.

  13. Parikalp-Bhardwaj commented on Nov 20, 2026

    @Parikalp-Bhardwaj
    CollaboratorAuthor

    Thanks @murtazayusuf that makes sense, i will open a draft PR for the layout review, i will rebase onto the latest master, adapt the counted B-tree to #969, and preserve the ZRANDMEMBER and settle behavior and also rerun the benchmarks with fat LTO and scripts/perf/run.sh, including memory at 1k, 10k, and 3M members, instruction counts, and GET/SET, i will document the remaining regressions and leave ZSCAN optimization for later.

  14. added a commit that references this issue on Nov 20, 2026
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Labels

bugSomething isn't workingperformanceThroughput and latency

Type

No type

Projects

No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions

    0