VarBinBuilder: eagerly set IsSorted stat on offsets#6452
Merged
dimitarvdimitrov merged 15 commits intodevelopfrom Feb 16, 2026
Merged
VarBinBuilder: eagerly set IsSorted stat on offsets#6452dimitarvdimitrov merged 15 commits intodevelopfrom
dimitarvdimitrov merged 15 commits intodevelopfrom
Conversation
Contributor
|
Can also do this for runend varbinview if not |
Contributor
Author
i couldn't find where in the VarBinViewArrayBuilder we create runend offsets for VarBin(View) arrays. Can you point me pls? |
Contributor
|
varbinview: also maybe sequence array: |
Merging this PR will not alter performance
Comparing 
Footnotes
|
Contributor
Author
Contributor
There was a problem hiding this comment.
we need to be careful on validation cost on the release path
Contributor
Polar Signals Profiling ResultsLatest Run
Previous Runs (4)
Powered by Polar Signals Cloud |
Contributor
Benchmarks: PolarSignals ProfilingSummary
Detailed Results Table
|
Contributor
Benchmarks: TPC-H SF=1 on NVMESummary
Detailed Results Table
|
Contributor
Benchmarks: FineWeb NVMeSummary
Detailed Results Table
|
Contributor
Benchmarks: Random AccessSummary
Detailed Results Table
|
Contributor
Benchmarks: TPC-H SF=1 on S3Summary
Detailed Results Table
|
Contributor
Benchmarks: TPC-DS SF=1 on NVMESummary
Detailed Results Table
|
Contributor
Benchmarks: TPC-H SF=10 on NVMESummary
Detailed Results Table
|
Contributor
Benchmarks: FineWeb S3Summary
Detailed Results Table
|
Contributor
Benchmarks: Statistical and Population GeneticsSummary
Detailed Results Table
|
Contributor
Benchmarks: TPC-H SF=10 on S3Summary
Detailed Results Table
|
Contributor
Benchmarks: CompressionSummary
Detailed Results Table
|
Contributor
Benchmarks: Clickbench on NVMESummary
Detailed Results Table
|
26a0461 to
94ed345
Compare
Deploying vortex-bench with
|
| Latest commit: |
92faa3f
|
| Status: | ✅ Deploy successful! |
| Preview URL: | https://3950788a.vortex-93b.pages.dev |
| Branch Preview URL: | https://mitko-varbin-set-is-sorted-o.vortex-93b.pages.dev |
Contributor
There was a problem hiding this comment.
Did you need to add sortedness to the compressor
Contributor
Author
it already does it - vortex/encodings/runend/src/compress.rs Lines 76 to 77 in 1cd554b |
Contributor
Author
|
any idea why the benchmarks are failing? i'll rebase to try and fix it 
|
VarBinBuilder guarantees monotonically increasing offsets, but finish() wasn't setting the IsSorted stat. This caused an O(n) recomputation every time a deserialized VarBinArray was validated, which showed up as a hot path in production profiles. Signed-off-by: Dimitar Dimitrov <dimitar@spiraldb.com>
Signed-off-by: Dimitar Dimitrov <dimitar@spiraldb.com>
RunEndArray::validate didn't check that ends are strictly increasing, which is required for binary search to work correctly. Also caches IsSorted and IsStrictSorted on the ends after construction so downstream consumers don't recompute it. Signed-off-by: Dimitar Dimitrov <dimitar@spiraldb.com>
SequenceArray (A[i] = base + i * multiplier) can determine sortedness from the sign of the multiplier at construction time. Set both stats eagerly so we skip the kernel entirely. Signed-off-by: Dimitar Dimitrov <dimitar@spiraldb.com>
Signed-off-by: Dimitar Dimitrov <dimitar@spiraldb.com>
I, Dimitar Dimitrov <dimitar@spiraldb.com>, hereby add my Signed-off-by to this commit: 1445406 I, Dimitar Dimitrov <dimitar@spiraldb.com>, hereby add my Signed-off-by to this commit: b2b7817 I, Dimitar Dimitrov <dimitar@spiraldb.com>, hereby add my Signed-off-by to this commit: 5c932f3 I, Dimitar Dimitrov <dimitar@spiraldb.com>, hereby add my Signed-off-by to this commit: 2f5b11b I, Dimitar Dimitrov <dimitar@spiraldb.com>, hereby add my Signed-off-by to this commit: 8ae944c Signed-off-by: Dimitar Dimitrov <dimitar@spiraldb.com>
Signed-off-by: Dimitar Dimitrov <dimitar@spiraldb.com>
The reviewer removed the offset monotonicity validation from VarBinArray::try_new, so the test now expects construction to succeed. Signed-off-by: Dimitar Dimitrov <dimitar@spiraldb.com>
Signed-off-by: Dimitar Dimitrov <dimitar@spiraldb.com>
a6e603c to
6cd097d
Compare
I, Dimitar Dimitrov <dimitar@spiraldb.com>, hereby add my Signed-off-by to this commit: 6cbf9b0 I, Dimitar Dimitrov <dimitar@spiraldb.com>, hereby add my Signed-off-by to this commit: c5fbeb7 I, Dimitar Dimitrov <dimitar@spiraldb.com>, hereby add my Signed-off-by to this commit: 1cb2660 I, Dimitar Dimitrov <dimitar@spiraldb.com>, hereby add my Signed-off-by to this commit: e50a078 I, Dimitar Dimitrov <dimitar@spiraldb.com>, hereby add my Signed-off-by to this commit: 8cd19f4 Signed-off-by: Dimitar Dimitrov <dimitar@spiraldb.com>
Contributor
Author
|
@joseph-isaacs I think we addressed everything, can we merge this? |
a10y
added a commit
that referenced
this pull request
Feb 17, 2026
Fix for the issue found by fuzzer in [latest run](https://github.com/vortex-data/vortex/actions/runs/22098142659/job/63860475812) <img width="1222" height="892" alt="image" src="https://github.com/user-attachments/assets/c159cdb9-1685-4c94-ad1f-ae6225a280e0" /> Seems like this snuck in on #6452 --------- Signed-off-by: Andrew Duffy <andrew@a10y.dev>
fastio
pushed a commit
to fastio/vortex
that referenced
this pull request
Mar 10, 2026
## Does this PR closes an open issue or discussion? no ## What this PR does? VarBinBuilder guarantees monotonically increasing offsets, but finish() wasn't setting the IsSorted stat. This caused an O(n) recomputation every time a deserialized VarBinArray was validated. ## How is this change tested? unit tests ## Are there any user-facing changes? VarBin arrays now persist stats for their offsets child array. Existing persisted arrays will still be verified as sorted upon reading from disk. --------- Signed-off-by: Dimitar Dimitrov <dimitar@spiraldb.com>
fastio
pushed a commit
to fastio/vortex
that referenced
this pull request
Mar 10, 2026
…6560) Fix for the issue found by fuzzer in [latest run](https://github.com/vortex-data/vortex/actions/runs/22098142659/job/63860475812) <img width="1222" height="892" alt="image" src="https://github.com/user-attachments/assets/c159cdb9-1685-4c94-ad1f-ae6225a280e0" /> Seems like this snuck in on vortex-data#6452 --------- Signed-off-by: Andrew Duffy <andrew@a10y.dev>
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
2 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.
Does this PR closes an open issue or discussion?
no
What this PR does?
VarBinBuilder guarantees monotonically increasing offsets, but finish() wasn't setting the IsSorted stat. This caused an O(n) recomputation every time a deserialized VarBinArray was validated.
How is this change tested?
unit tests
Are there any user-facing changes?
VarBin arrays now persist stats for their offsets child array. Existing persisted arrays will still be verified as sorted upon reading from disk.