You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
Sorted-set rank and range commands are slow on large datasets #875
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.
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?
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.
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.
@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.
@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?
@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.
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.
@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.
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.
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.
@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:
ZRANDMEMBER costs the count, not the size of the sorted set (#862) #969 changed src/sorted_set.rs and src/commands/zset.rs: ZRANDMEMBER now picks by position without a walk (random_each / random_distinct), and ZADD/GEOADD/bulk removals call settle so the member table is sized for what it holds. Your tree has to keep those properties (suites 16 and 37 gate them).
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.
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.
Activity
murtazayusuf commentedon Nov 17, 2026
Thanks @Parikalp-Bhardwaj, right on all four:
.range(..).count()and.skip(start)walk the tree, andBTreeMaphas 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 (ZRANDMEMBERwalking 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:
src/packed_set.rs. Rank is then the position, and there is nothing to design for it.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,ZRANGEby index,ZCOUNT/ZLEXCOUNT(difference of two ranks),ZREMRANGEBYRANKandZRANDMEMBER(a random rank) in O(log N);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/ZSCOREcost 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;SortedSetInner's methods: today its two maps arepuband 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
ZADDcosts in it, and we settle it before the PR. Say if you'd rather I take all of it.Parikalp-Bhardwaj commentedon Nov 17, 2026
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?
murtazayusuf commentedon Nov 17, 2026
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:
score: f64, length, the member's bytes. Nothing else owns the bytes; noArc.ZSCORE,ZADD's lookup) is a table of 8-byte pointers to those blocks, hashed and compared through the pointer (assrc/store/entry.rsdoes for the keyspace, andMemberSet's table does withHashTable). The score is read from the block, so the map no longer stores it.(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:
-0/0and NaN handling stay asSortedSetInner::inserthas them today.unsafeis fine for the blocks if it is confined to one small module with its invariants written down and a model test againstBTreeMap+HashMapover 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
SortedSetInnerclosing-off PR first would help both of us.Parikalp-Bhardwaj commentedon Nov 17, 2026
Thanks @murtazayusuf i will take care of the large sorted-set work, will first move the direct map access into
SortedSetInnermethods without changing the current behavior.Then i will compare memory usage per member and ZADD/ZREM performance before deciding on the new index.
murtazayusuf commentedon Nov 18, 2026
@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,
ZRANGEby index far in,ZCOUNTby subtracting ranks,ZRANDMEMBERby position: this issue and #862), and I take the packed block for small sorted sets (#825, the sorted-set row of #297), behind the sameSortedSetInnermethods. 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_lexandmember_atare the methods I would add to the type first, so both representations answer them.Parikalp-Bhardwaj commentedon Nov 18, 2026
@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_memoryor actual allocator-allocated bytes for memory comparisons?murtazayusuf commentedon Nov 18, 2026
@Parikalp-Bhardwaj measuring before building is the right order. Answers and two things to weigh:
used_memory(what we publish against Redis'sused_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.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.ZADDnew/existing,ZSCORE,ZREM,ZRANK,ZRANGE 0 9far in, for both layouts against master, decides it.ZRANK/ZRANGE-by-index rows and the bytes pick the final fanout.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
SortedSetInnerfirst, so both representations answer them:range_by_rank,count_by_score,count_by_lex,member_at. Hot-path rule as always:GET/SETmust not move, and every sorted-set row in the #892 table gets re-measured on the release profile as shipped.Parikalp-Bhardwaj commentedon Nov 18, 2026
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.
murtazayusuf commentedon Nov 18, 2026
@Parikalp-Bhardwaj heads-up for your prototype: #926 is merged.
SortedSetInnernow 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% onZSCOREat 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.Parikalp-Bhardwaj commentedon Nov 19, 2026
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.
Parikalp-Bhardwaj commentedon Nov 20, 2026
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.
murtazayusuf commentedon Nov 20, 2026
@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:
src/sorted_set.rsandsrc/commands/zset.rs:ZRANDMEMBERnow picks by position without a walk (random_each/random_distinct), andZADD/GEOADD/bulk removals callsettleso the member table is sized for what it holds. Your tree has to keep those properties (suites 16 and 37 gate them).CollectionTablewith an incremental cursor forSSCAN/HSCAN(table_scan).ZSCANis the one left on the old path (HSCAN/SSCAN/ZSCAN over a large collection are 10-20x slower than Redis (O(N^2/1024) full iteration) #770), so don't tuneZSCANon the old structure: say in the draft how a cursor would walk your layout while it grows, that is enough for now.In the draft description, the things I need to judge it:
ZADD(new and existing member),ZINCRBY,ZSCORE,ZRANK,ZRANGEshallow 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;GET/SETrows from the same run (LTO=fat EXEC=1 CMP=plain): they must not move;Sets of up to 128 members stay in the packed form, so the tree only has to win above that.
Parikalp-Bhardwaj commentedon Nov 20, 2026
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
ZRANDMEMBERandsettlebehavior and also rerun the benchmarks with fat LTO andscripts/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.Merge pull request #989 from kividbio/feat/zsets-on-the-table