[BUG] Remaining btree sorted-set regressions from #4359: module range iteration, NaN bounds, negative LIMIT offset, lex LIMIT cost

[xiaocj]

Describe the bug

While testing #4359 (B+ tree sorted sets) we cross-checked the btree encoding against listpack with randomized differentials and a small test module. Besides the problems already covered by #4497, #4554 and #4558, the following behaviours differ from listpack (and from the skiplist that #4359 replaced). All of them are reproducible on current unstable; each section below is independent and can be split into its own issue if preferred.

All reproductions use CONFIG SET zset-max-listpack-entries 0 to force the btree encoding; the same commands on a listpack-encoded key give the expected results.

1. VM_ZsetRangePrev after VM_ZsetRangeNext (and vice versa) re-returns the current element

The ordered index iterator uses a cursor-between-items model (orderedIndexNext returns values[current_index++], orderedIndexPrev returns values[--current_index]), while the module API and the listpack branch treat current as an element and step to its neighbour. The btree branches of VM_ZsetRangeNext / VM_ZsetRangePrev call orderedIndexNext / orderedIndexPrev directly without accounting for which side of current the cursor sits on.

With ZADD k 1 a 2 b 3 c 4 d 5 e and VM_ZsetFirstInScoreRange(key, 2, 4, 0, 0):

Calls	btree	listpack
Next, Next, Prev, then CurrentElement	b, c, then c again	b, c, b
Prev right after First: return value / EndReached / current	1 / 0 / b	0 / 1 / b
Next right after VM_ZsetLastInScoreRange	returns d again	steps past d: 0 / EndReached 1

Lex ranges go through the same code (zsetInitLexRange) and behave the same. A module walking with the documented while (!VM_ZsetRangeEndReached(key)) loop sees duplicates or one phantom element whenever it changes direction, and the outcome depends on the key's encoding.

2. VM_ZsetFirstInLexRange / VM_ZsetLastInLexRange return an out-of-range element for an empty or inverted lex range

zsetInitLexRange adopts whatever orderedIndexSeekToLexRange lands on as current without checking the far bound. Commands are unaffected because genericZrangebylexCommand checks the far bound per element, but the module API does not. On ZADD k 0 a 0 b 0 c 0 d 0 e:

Call	btree	listpack
VM_ZsetFirstInLexRange(key, "[c", "[b")	current c, EndReached 0	no element, EndReached 1
VM_ZsetFirstInLexRange(key, "(", "(")	current a	no element
VM_ZsetLastInLexRange(key, "(e", "+")	current e	no element

orderedIndexSeekToScoreRange validates the landed item against [min, max]; the lex seek does not. #4497 fixes the crossed-sentinel cases but not inverted or empty ranges with real bounds.

3. A NaN score bound returns an element through the module API

zslParseRange rejects NaN for commands, but the module API passes doubles straight through. The removed zslIsInRange pre-check made any NaN-bounded range empty; orderedIndexSeekToScoreRange only rejects min > max / equal-and-exclusive (both false with NaN) and validates the landed item with score > max (false for NaN), and scoreToSortable(NaN) maps beyond +inf. On ZADD k 1 a 2 b:

Call	btree	listpack
VM_ZsetFirstInScoreRange(key, 0, NAN, 0, 0)	current a, EndReached 0	no element
VM_ZsetLastInScoreRange(key, 0, NAN, 0, 0)	current b	no element

4. A negative LIMIT offset selects the reverse direction on btree keys

zrangeGenericCommand accepts any long as the LIMIT offset. The btree paths pass it into orderedIndexSeekToScoreRange / orderedIndexSeekToLexRange as reverse ? -offset - 1 : offset, where a negative value is the reverse-direction encoding, so the
cursor is positioned for prev() while the caller steps with next() (or vice versa) and exactly one wrong element is emitted. Listpack walks offset-- to the end and returns an empty array.

ZADD z 1 a 2 b 3 c 4 d 5 e
ZRANGEBYSCORE z 1 5 LIMIT -2 10      -> btree: e     listpack: (empty array)
ZREVRANGEBYSCORE z 5 1 LIMIT -2 10   -> btree: a     listpack: (empty array)
ZADD l 0 a 0 b 0 c 0 d 0 e
ZRANGEBYLEX l - + LIMIT -2 10        -> btree: e     listpack: (empty array)

The result of the same command now depends on the key's encoding. (-offset - 1 is also signed overflow for LONG_MIN.)

5. ZRANGEBYLEX ... LIMIT offset is O(offset) on btree keys

orderedIndexSeekToLexRange applies the offset with skipElements, a loop of fbtreeNext / fbtreePrev calls, although fbtreeSeekToValue (called via seekForBound) already returns the rank of the bound and the score path uses a single fbtreeSeekToRank(rank + offset). The replaced zslNthInLexRange reached the offset in O(log N) through the skiplist spans, so ZRANGEBYLEX key - + LIMIT 1000000 10 on a large key regressed from logarithmic to linear.

6. Minor / latent

• fbtreePostDeleteCleanup frees an emptied inner root with plain zfree and never calls innerNodeFreePrefix, leaking the heap block innerNodeSetPrefix allocates for a common prefix longer than EMBED_PREFIX_LEN. The sibling collapse branch does release it. Reachable today only through the stale-prefix sequence zset bugfix - Fix btree score range resolution and prefix staleness #4554 fixes, so effectively latent after that PR, but the branch is still wrong.
• orderedIndexResetIterator is documented as "reset to the initial unseeked state ... keeps the index association", but fbtreeResetIterator sets it->fbt = NULL, so next() / prev() return NULL afterwards; the seek functions rely on that detached
  state as their empty-result path.
• tests/unit/type/zset.tcl contains the ZRANGE with/without XX test twice, verbatim.

Expected behavior

Btree-encoded sorted sets behave like listpack-encoded ones (and like the previous skiplist) for the module range iteration API, NaN bounds, negative LIMIT offsets, and the cost of a lex LIMIT offset.

Additional information

Introduced by #4359. Verified against unstable at 85d02f6. We have fixes for all of the above (cursor-side tracking in the module iterator, far-bound validation in the lex seek, a NaN guard on the ordered index score entry points, a single offset guard in zrangeGenericCommand, rank arithmetic for the lex offset) with tests for both encodings, and can send them as separate PRs; the lex-offset change builds on #4497's sentinel handling, so it would follow that PR.

Disclosure: both the discovery of these problems and the draft fixes relied heavily on AI tooling; every finding and change was then reviewed and verified by hand before being written up here.

[rainsupreme]

Nice! Thank you so much @xiaocj, I really appreciate the testing you put into this, and this is an impressive list of bugs you've found. Please request reviews from me on the PR(s) you raise - I'm quite interested in checking out your fixes and getting them reviewed/approved/merged 😃