Delete-free row-ID scans still filter every row
perfloop-oss/datafusion-ducklake · INEFFICIENT ALGORITHM
https://perfloop.ai/t/oss/case_3dt1xxfe9x
Verdict
VERIFIED · settled 2026-10-08 · merged as datafusion-contrib/datafusion-ducklake#368
What happened: The paired measurements met the required improvement.
Hypothesis
Delete-free row-ID reads still perform delete bookkeeping for every returned row. The scan already knows that its read group has no delete entries. This pass may consume material CPU on large, narrow scans. The saving from bypassing it has not been measured.
The benefiting operation is a full `SELECT rowid, id` collected through a `DuckLakeCatalog` with `with_row_lineage(true)`, over insert-only Parquet data with no visible inlined rows or deletes. At revision `27fc2edb17d5d9e1c36a351b793d45003759735d`, `docs/physical-row-positions.md:11-28` describes this positional-read workload, and lines 197-209 document large-file row-ID reads at five million rows, including full scans without a prunable predicate. The lifecycle example reads row IDs after inserts (`examples/rowid_lifecycle.rs:8-11,34`). These support the library workload and scale, not its production frequency. The profiled sequential `Int32` payload follows the supported delete-free shape in `tests/it/rowid_physical_position_tests.rs:69-107`; its cost share is not evidence for wide or poorly compressed tables.
`DuckLakeTable::scan` routes projected row IDs through `build_exec_for_files_with_rowid`. That builder omits delete-map entries for files without either delete source at `src/table.rs:3792-3795`, but still constructs `LazyDeleteFilterExec` at lines 3867-3876. This is the normal route for the named workload, not an error or fallback. `LazyDeleteFilterExec::execute` calls `apply` once per input batch. With an empty map, `BatchFilter::deleted` always returns an empty set. Every successfully processed batch therefore performs one empty-set check and one keep-mask insertion per row, with per-row reference-count bookkeeping, although every row survives. `RowLineageExec` has already constructed the row IDs; the filter must still drop its internal file-ID and position columns. These counts describe completed batches, not invocations that fail validation or scans stopped early by a limit.
CPU receipt `call_Zz0A2HN3m5gGGAxOoQHM5uLB` ran the public SQLite writer and 32 fresh, fully collected five-million-row queries with eight scan partitions. Its short 250 Hz capture contains 656 ms of sampled CPU, including setup and validation. Go pprof reports 288 ms flat, or 43.9% of that receipt's CPU, in the generic `AndThen::poll_next` filter-stream frame, and 28 ms, or 4.3%, in conversion of `Vec<bool>` to `BooleanArray`. The binding is the stream closure at `src/lazy_delete_filter.rs:332-336`, which invokes `apply`; the polling-frame share is not an exact removable-work share. A separate one-query replay exposed `LazyDeleteFilterExec: files=0`, eight file groups, five million returned rows, and passing row-ID comparisons. Arrow 59.2's all-true filter uses slices, so payload copying is not the proposed saving. This is a medium-confidence CPU lead.
The required Case check is an A/B of the same public SQL collection over the retained five-million-row insert-only fixture, using fresh execution plans and identical scan configuration. It should measure query CPU and elapsed time separately from setup, and confirm or reject a reproducible CPU reduction attributable to eliminating the row loop and mask construction. Identical rows, row IDs, schemas, and hidden-column removal are required. Empty batches, limits, and real file or inlined deletes are regression controls, not benefiting workloads. Decoding, row-ID construction, and output collection remain; neither a fixed gain nor a production-wide effect is established. The current-status document explicitly covers this node (`docs/physical-row-positions.md:3-7,68-83`), and the change requires no new public API.
Change to test: When the scan's delete map is empty, project the kept columns without building or evaluating a per-row delete mask. Preserve existing column validation, output schema and row counts, row order, physical row IDs, and plan properties; leave lazy delete loading and filtering unchanged when the map is nonempty.
Where it lives
perfloop-oss/datafusion-ducklake · src/table.rs
Evidence
5M-row SQLite SELECT rowid, id full scan · 10 sample pairs
| metric | baseline | candidate | paired median change | confidence range | required | result |
|---|---|---|---|---|---|---|
query_cpu_ns |
112500000 |
45468750 |
−60.4% (−67968750) |
−72500000 to −65312500 |
< −5625000 |
PASSED |
query_cpu_ns_per_row |
22.5 |
9.094 |
−60.4% (−13.59) |
−14.5 to −13.06 |
< −1.125 |
PASSED |
query_elapsed_ns |
41777826 |
17904831 |
−57.2% (−23887974) |
−24342214 to −22726815 |
≤ 2088891 |
PASSED |
Checks: 4 of 4 passed. Verification: no defect found.