Fix Numeric Tree Balance - [MOD-8081, MOD-8082]#5185
Merged
Conversation
Contributor
Automated performance analysis summaryThis comment was automatically generated given there is performance data available. In summary:
You can check a comparison in detail via the grafana link Comparison between master and guyav-fix_numeric_tree.Time Period from 30 days ago. (environment used: oss-standalone)
|
Codecov ReportAll modified and coverable lines are covered by tests ✅
Additional details and impacted files@@ Coverage Diff @@
## master #5185 +/- ##
==========================================
+ Coverage 86.43% 86.50% +0.07%
==========================================
Files 192 192
Lines 34784 34683 -101
==========================================
- Hits 30066 30004 -62
+ Misses 4718 4679 -39 ☔ View full report in Codecov by Sentry. |
raz-mon
reviewed
Nov 10, 2024
Collaborator
raz-mon
left a comment
raz-mon
left a comment
There was a problem hiding this comment.
Very nice! 💪 🔥
Some nitpicks mainly.
Some more documentation on the faulty scenarios and the fixes in the general comment would be good.
alonre24
approved these changes
Nov 11, 2024
Contributor
|
Backport failed for Please cherry-pick the changes locally and resolve any conflicts. git fetch origin 2.8
git worktree add -d .worktree/backport-5185-to-2.8 origin/2.8
cd .worktree/backport-5185-to-2.8
git switch --create backport-5185-to-2.8
git cherry-pick -x 588468722680e3855f972f95580c299ae8bde2b1 |
Contributor
|
Backport failed for Please cherry-pick the changes locally and resolve any conflicts. git fetch origin 2.6
git worktree add -d .worktree/backport-5185-to-2.6 origin/2.6
cd .worktree/backport-5185-to-2.6
git switch --create backport-5185-to-2.6
git cherry-pick -x 588468722680e3855f972f95580c299ae8bde2b1 |
Contributor
|
Backport failed for Please cherry-pick the changes locally and resolve any conflicts. git fetch origin 2.10
git worktree add -d .worktree/backport-5185-to-2.10 origin/2.10
cd .worktree/backport-5185-to-2.10
git switch --create backport-5185-to-2.10
git cherry-pick -x 588468722680e3855f972f95580c299ae8bde2b1 |
Contributor
|
Backport failed for Please cherry-pick the changes locally and resolve any conflicts. git fetch origin 8.0
git worktree add -d .worktree/backport-5185-to-8.0 origin/8.0
cd .worktree/backport-5185-to-8.0
git switch --create backport-5185-to-8.0
git cherry-pick -x 588468722680e3855f972f95580c299ae8bde2b1 |
Collaborator
Author
|
/backport |
Contributor
|
Backport failed for Please cherry-pick the changes locally and resolve any conflicts. git fetch origin 2.8
git worktree add -d .worktree/backport-5185-to-2.8 origin/2.8
cd .worktree/backport-5185-to-2.8
git switch --create backport-5185-to-2.8
git cherry-pick -x 588468722680e3855f972f95580c299ae8bde2b1 |
Contributor
|
Backport failed for Please cherry-pick the changes locally and resolve any conflicts. git fetch origin 2.6
git worktree add -d .worktree/backport-5185-to-2.6 origin/2.6
cd .worktree/backport-5185-to-2.6
git switch --create backport-5185-to-2.6
git cherry-pick -x 588468722680e3855f972f95580c299ae8bde2b1 |
Contributor
|
Backport failed for Please cherry-pick the changes locally and resolve any conflicts. git fetch origin 2.10
git worktree add -d .worktree/backport-5185-to-2.10 origin/2.10
cd .worktree/backport-5185-to-2.10
git switch --create backport-5185-to-2.10
git cherry-pick -x 588468722680e3855f972f95580c299ae8bde2b1 |
Contributor
|
Backport failed for Please cherry-pick the changes locally and resolve any conflicts. git fetch origin 8.0
git worktree add -d .worktree/backport-5185-to-8.0 origin/8.0
cd .worktree/backport-5185-to-8.0
git switch --create backport-5185-to-8.0
git cherry-pick -x 588468722680e3855f972f95580c299ae8bde2b1 |
GuyAv46
added a commit
that referenced
this pull request
Nov 11, 2024
* add a failing test * fix maxDepth calculation (balance logic) * fix parent range depth logic * improve test and remove a print * fix test * comment fixes * tidy up * simplified test and address CR * code cleanup and address CR (cherry picked from commit 5884687)
GuyAv46
added a commit
that referenced
this pull request
Nov 11, 2024
* add a failing test * fix maxDepth calculation (balance logic) * fix parent range depth logic * improve test and remove a print * fix test * comment fixes * tidy up * simplified test and address CR * code cleanup and address CR (cherry picked from commit 5884687)
GuyAv46
added a commit
that referenced
this pull request
Nov 11, 2024
* add a failing test * fix maxDepth calculation (balance logic) * fix parent range depth logic * improve test and remove a print * fix test * comment fixes * tidy up * simplified test and address CR * code cleanup and address CR (cherry picked from commit 5884687)
GuyAv46
added a commit
that referenced
this pull request
Nov 11, 2024
* add a failing test * fix maxDepth calculation (balance logic) * fix parent range depth logic * improve test and remove a print * fix test * comment fixes * tidy up * simplified test and address CR * code cleanup and address CR (cherry picked from commit 5884687)
This was referenced Nov 11, 2024
github-merge-queue bot
pushed a commit
that referenced
this pull request
Nov 12, 2024
Fix Numeric Tree Balance - [MOD-8081, MOD-8082] (#5185) * add a failing test * fix maxDepth calculation (balance logic) * fix parent range depth logic * improve test and remove a print * fix test * comment fixes * tidy up * simplified test and address CR * code cleanup and address CR (cherry picked from commit 5884687)
github-merge-queue bot
pushed a commit
that referenced
this pull request
Nov 12, 2024
Fix Numeric Tree Balance - [MOD-8081, MOD-8082] (#5185) * add a failing test * fix maxDepth calculation (balance logic) * fix parent range depth logic * improve test and remove a print * fix test * comment fixes * tidy up * simplified test and address CR * code cleanup and address CR (cherry picked from commit 5884687)
github-merge-queue bot
pushed a commit
that referenced
this pull request
Nov 12, 2024
Fix Numeric Tree Balance - [MOD-8081, MOD-8082] (#5185) * add a failing test * fix maxDepth calculation (balance logic) * fix parent range depth logic * improve test and remove a print * fix test * comment fixes * tidy up * simplified test and address CR * code cleanup and address CR (cherry picked from commit 5884687)
github-merge-queue bot
pushed a commit
that referenced
this pull request
Nov 12, 2024
Fix Numeric Tree Balance - [MOD-8081, MOD-8082] (#5185) * add a failing test * fix maxDepth calculation (balance logic) * fix parent range depth logic * improve test and remove a print * fix test * comment fixes * tidy up * simplified test and address CR * code cleanup and address CR (cherry picked from commit 5884687)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
4 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Describe the changes in the pull request
Fixing 2 bugs in the numeric tree regarding the tree balancing
maxDepthvalue to become larger than both child subtrees, which can later yield sub-optimal tree balancing.maxDepthvalue has to grow by 1 (which is not true when the splitting leaf was not in the max depth), could cause the parent range to get released prematurely. (only when_NUMERIC_RANGES_PARENTSis set to2)Starting with this fix, we will also start balancing the root node to achieve a better tree.
Note:
This is a performance fix. Both bugs don't affect the correctness of any search.
Mark if applicable