Repository navigation
Rebuild lists over only the elements valid lists reference - #10743
Conversation
Merging this PR will degrade performance by 10.11%4 warnings, 1 note
Warning Please fix the performance issues or acknowledge them on CodSpeed. Performance Changes
Tip Investigate this regression by commenting Comparing Footnotes
|
Signed-off-by: Matt Katz <[email protected]>
Signed-off-by: Matt Katz <[email protected]>
Signed-off-by: Matt Katz <[email protected]>
Signed-off-by: Matt Katz <[email protected]>
e37ff7a to
14aa30a
Compare
Signed-off-by: Matt Katz <[email protected]>
Signed-off-by: Matt Katz <[email protected]>
…th one bitmap Signed-off-by: Matt Katz <[email protected]>
| ctx: &mut ExecutionCtx, | ||
| ) -> VortexResult<ListViewArray> { | ||
| if self.is_empty() || !self.is_zero_copy_to_list() { | ||
| return self.rebuild(ListViewRebuildMode::MakeExact, ctx); |
There was a problem hiding this comment.
just have make exact remove nulls
Polar Signals Profiling ResultsLatest Run
Previous Runs (7)
Powered by Polar Signals Cloud |
Benchmarks: PolarSignals Profiling 📖Commits: PR datafusion / vortex-file-compressed / ns (1.004x ➖, 0↑ 0↓)
No file size changes detected. |
Benchmarks: FineWeb NVMe 📖Commits: PR How to read Verdict and Engines
datafusion / vortex-file-compressed / ns (0.977x ➖, 0↑ 0↓)
datafusion / parquet / ns (0.999x ➖, 0↑ 0↓)
duckdb / vortex-file-compressed / ns (1.017x ➖, 0↑ 1↓)
duckdb / parquet / ns (1.020x ➖, 0↑ 0↓)
No file size changes detected. |
Benchmarks: TPC-H SF=1 on NVME 📖Commits: PR How to read Verdict and Engines
datafusion / vortex-file-compressed / ns (0.993x ➖, 0↑ 0↓)
datafusion / parquet / ns (1.000x ➖, 0↑ 0↓)
duckdb / vortex-file-compressed / ns (0.988x ➖, 1↑ 0↓)
duckdb / parquet / ns (0.999x ➖, 0↑ 0↓)
No file size changes detected. |
Benchmarks: TPC-H SF=10 on NVME 📖Commits: PR How to read Verdict and Engines
datafusion / vortex-file-compressed / ns (0.995x ➖, 0↑ 0↓)
datafusion / parquet / ns (0.998x ➖, 0↑ 0↓)
duckdb / vortex-file-compressed / ns (0.992x ➖, 0↑ 0↓)
duckdb / parquet / ns (0.998x ➖, 0↑ 0↓)
No file size changes detected. |
Benchmarks: TPC-DS SF=1 on NVME 📖Commits: PR How to read Verdict and Engines
datafusion / vortex-file-compressed / ns (0.997x ➖, 0↑ 0↓)
datafusion / parquet / ns (1.000x ➖, 0↑ 0↓)
duckdb / vortex-file-compressed / ns (0.998x ➖, 0↑ 0↓)
duckdb / parquet / ns (0.991x ➖, 0↑ 0↓)
No file size changes detected. |
Benchmarks: Clickbench on NVME 📖Commits: PR How to read Verdict and Engines
datafusion / vortex-file-compressed / ns (0.996x ➖, 0↑ 0↓)
datafusion / parquet / ns (1.001x ➖, 0↑ 0↓)
duckdb / vortex-file-compressed / ns (1.002x ➖, 0↑ 0↓)
duckdb / parquet / ns (0.998x ➖, 0↑ 0↓)
No file size changes detected. |
Benchmarks: TPC-H SF=1 on S3 📖Commits: PR How to read Verdict and Engines
datafusion / vortex-file-compressed / ns (0.989x ➖, 1↑ 1↓)
datafusion / parquet / ns (1.024x ➖, 0↑ 1↓)
duckdb / vortex-file-compressed / ns (1.071x ➖, 0↑ 1↓)
duckdb / parquet / ns (1.104x ➖, 0↑ 1↓)
|
Signed-off-by: Matt Katz <[email protected]>
Signed-off-by: Matt Katz <[email protected]>
| /// [`ListViewArray`] that is also zero-copy to a [`ListArray`]. | ||
| /// | ||
| /// [`ListArray`]: crate::arrays::ListArray | ||
| MakeExact, |
There was a problem hiding this comment.
Essentially ListArray does not guarantee that null lists have length 0
Signed-off-by: Matt Katz <[email protected]>
| /// Null lists come out empty, the offsets start at 0, end at the length of the elements and | ||
| /// keep their type, and the validity is kept. An array with nothing to drop is returned as it | ||
| /// is. | ||
| pub fn compact(&self, ctx: &mut ExecutionCtx) -> VortexResult<ListArray> { |
There was a problem hiding this comment.
I think we have a canonical compact method?
There was a problem hiding this comment.
we dont want to have to rebuild to listview in order to compact
Issue: #9249
Summary
Adds
ListArray::compactand a list view rebuild mode,ListViewRebuildMode::MakeExactWithEmptyNulls. Both return the same lists over only the elements that valid lists reference: nothing before the first list, after the last, between lists or under a null list.A list column can hold elements that no valid list shows. Slicing keeps the parent's elements on both sides, and a null list may still cover elements. A function that only reads values does not care, but a function that can fail on an element, such as a checked
x + 1, must not see them: an overflow in an element under a null list would fail the whole batch.list_transform(#10503, stacked on this PR) is the first user; it applies its lambda to the rebuilt elements whenever the lambda can fail.For example:
How it works
ListArray[first offset, last offset)and the offsets are shifted down, without copying an element.ListViewRebuildMode::MakeExactWithEmptyNullsMakeExactonly trims the ends of a view that is already zero-copy to a list, so its null lists keep their elements. The new mode drops those too.MakeExact, which already copies only the valid lists' elements and leaves null lists empty.MakeExact's documentation now says both.Benchmark
list_transformwith a checkedx + 1over 100k lists (~800ki32elements, ~1/8 of the lists null), through #10503, exported to Arrow, median µs over three alternating runs of a local divan benchmark. "Before" is #10503 without this PR, which used the existing list view rebuild instead.array_transformTesting
rstestcases for both types: ends to drop, null lists holding elements or not, every list null, no lists, an empty valid list between null lists, overlapping and out-of-order views, views with and without the zero-copy flag.ArrayRef::ptr_eq), and a slicedListArraywhose validity starts mid-byte is rebuilt correctly.ListArrayand both kinds of view against a reference that gathers each valid list's elements, over five offset types, with non-nullable validity and validity arrays that start mid-byte.