[MOD-13920] Add find (range query) algorithm for numeric_range_tree#8302
[MOD-13920] Add find (range query) algorithm for numeric_range_tree#8302LukeMathWalker merged 1 commit intomasterfrom
Conversation
Codecov Report❌ Patch coverage is Additional details and impacted files@@ Coverage Diff @@
## master #8302 +/- ##
==========================================
- Coverage 83.09% 83.07% -0.02%
==========================================
Files 398 399 +1
Lines 58115 58251 +136
Branches 16264 16400 +136
==========================================
+ Hits 48289 48391 +102
- Misses 9660 9694 +34
Partials 166 166
Flags with carried forward coverage won't be shown. Click here to find out more. ☔ View full report in Codecov by Sentry. 🚀 New features to boost your workflow:
|
LukeMathWalker
force-pushed
the
numeric-range-tree-1-rust
branch
from
c4fe674 to
63087b3
Compare
LukeMathWalker
force-pushed
the
numeric-range-tree-1-find
branch
from
5a6d635 to
32360d6
Compare
![cursor[bot]](https://avatars.githubusercontent.com/in/1210556?s=60&v=4){kind=small}
LukeMathWalker
force-pushed
the
numeric-range-tree-1-find
branch
3 times, most recently
from
f67d0f6 to
0791d7f
Compare
LukeMathWalker
force-pushed
the
numeric-range-tree-1-rust
branch
from
e09782e to
06f9330
Compare
LukeMathWalker
force-pushed
the
numeric-range-tree-1-find
branch
from
0791d7f to
2724020
Compare
LukeMathWalker
force-pushed
the
numeric-range-tree-1-rust
branch
from
06f9330 to
601f53a
Compare
LukeMathWalker
force-pushed
the
numeric-range-tree-1-find
branch
2 times, most recently
from
45969d0 to
2ff1920
Compare
❌ Jit Scanner failed - Our team is investigatingJit Scanner failed - Our team has been notified and is working to resolve the issue. Please contact support if you have any questions. 💡 Need to bypass this check? Comment |
LukeMathWalker
force-pushed
the
numeric-range-tree-1-find
branch
6 times, most recently
from
c30c35f to
bcd192b
Compare
LukeMathWalker
changed the base branch from
numeric-range-tree-1-rust
to
master
LukeMathWalker
force-pushed
the
numeric-range-tree-1-find
branch
from
bcd192b to
5d457f6
Compare
LukeMathWalker
force-pushed
the
numeric-range-tree-1-find
branch
from
5d457f6 to
6bb03cf
Compare
|
| } | ||
| NumericRangeNode::Leaf(leaf) => { | ||
| let num_docs = leaf.range.num_docs(); | ||
| *total += if *total == 0 && filter.offset == 0 { |
There was a problem hiding this comment.
Why is the += 1 special case only applied when offset == 0? If the concern is overcounting for partially-overlapping ranges, wouldn't the same issue apply when offset > 0?
There was a problem hiding this comment.
Let's keep it as it is for now, aligning with the C version. We'll revise in the contex of the optimizer iterator rework (https://redislabs.atlassian.net/browse/MOD-13983).
2 participants
Describe the changes in the pull request
Find implementation for
NumericRangeTree.Stacked on top #8276.
Which additional issues this PR fixes
Main objects this PR modified
Mark if applicable
Release Notes
If a release note is required (bug fix / new feature / enhancement), describe the user impact of this PR in the title.
Note
Medium Risk
Adds a new public read-path (
NumericRangeTree::find) whose traversal/pruning and pagination semantics directly affect query correctness and performance. Includes new overlap/containment helpers and invariant checks, but regressions could still surface under edge-case filters or large trees.Overview
Implements the numeric range tree read path by adding
NumericRangeTree::find, which traverses the tree using containment/overlap pruning and returns ranges in ascending/descending order, with support forNumericFilterpagination viaoffset/limit.Adds
NumericRange::contained_in/overlapshelpers and (underunittest) newfind-specific invariant checks (overlap, ordering/non-overlap, and limit sufficiency). ExposesNumericFilterfrom the crate and adds integration + property tests covering large-tree queries, empty/no-overlap cases, ordering, and pagination behavior.Written by Cursor Bugbot for commit 6bb03cf. This will update automatically on new commits. Configure here.