Abhisheklearn12 commented on issue #25035: URL: https://github.com/apache/datafusion/issues/25035#issuecomment-5669281208
Sorry for the delayed follow-up, @adriangb, I was tied up with other work. I independently reproduced and traced the current evaluator at [`9082d6b10`](https://github.com/apache/datafusion/commit/9082d6b10c29b72d56bede3d8e353d9d61fde542). The association-sensitive slowdown is real. Accumulated-prefix selectivity is useful, but insufficient as the sole trigger. Evidence points to node-local state plus policy: binary parents discard compact state, while the 20% rule omits bytes copied and remaining work. My measurements reproduce the qualitative result; absolute timings and ratios differ. I have not selected A/B/C, implemented B/C, or reproduced the reported TPC-H, `predicate_eval`, prototype, or 510-SLT results. Benchmark: [immutable commit](https://github.com/Abhisheklearn12/datafusion/commit/290f57d24efe9cd3cb75bb78570cc68cd03cf988), SHA-256 `2f0338362241221bc8fbdf3f0cf96c913feb4307513ba167e80a0a6152fbd29c`. This benchmark commit is a reproducibility artifact only, not a proposed production change or PR. ### Reproduction and mechanism The target evaluates eight ordered SplitMix64-salted `Int32 > 0` conjuncts over 8,192 rows at roughly 70%, with 32 unreferenced `Int64` payload columns. Both use the same leaf definitions and order. Criterion used 1-second warmup, 3-second measurement, and 40 samples on an Intel i7-11700F, Linux 6.1, rustc 1.97.0, and Arrow 59.3.0. Criterion's slope point estimates were **172.681 µs** [95% CI: 172.151, 173.214] and **31.965 µs** [95% CI: 31.915, 32.017], a **5.40x** ratio. Three invocations gave 5.39x to 5.41x. Frequency was unpinned and targets sequential, so small differences are not meaningful. The mixed-RHS path is [`BinaryExpr::evaluate`](https://github.com/apache/datafusion/blob/9082d6b10c29b72d56bede3d8e353d9d61fde542/datafusion/physical-expr/src/expressions/binary.rs#L542-L611) -> [`check_short_circuit`](https://github.com/apache/datafusion/blob/9082d6b10c29b72d56bede3d8e353d9d61fde542/datafusion/physical-expr/src/expressions/binary.rs#L1188-L1272) -> Arrow [`filter_record_batch`](https://github.com/apache/arrow-rs/blob/59.3.0/arrow-select/src/filter.rs#L441-L463) -> RHS evaluation -> [`pre_selection_scatter`](https://github.com/apache/datafusion/blob/9082d6b10c29b72d56bede3d8e353d9d61fde542/datafusion/physical-expr/src/expressions/binary.rs#L1307-L1354). Each trigger filters the full batch and restores a full-length Boolean array because the selected RHS is mixed. The uniform-RHS shortcut does not apply, and compact state is not propagated upward. Exact prefix survivors: `5742 -> 3946 -> 2749 -> 1905 -> 1338 -> 889 -> 617 -> 425`. At 8,192 rows, mixed non-null arrays with 1 to 1,638 true rows qualify, so the last three left-deep parents trigger. Right-deep LHS values are individual approximately 70%-passing leaves and do not. Arrow `filter_record_batch` filters every column, including unreferenced payload. ### Controlled experiments | Control | Left | Right | L/R | |---|---:|---:|---:| | k=2, p=.70, width=32 | 7.356 µs | 7.349 µs | 1.00x | | k=8, p=.70, width=0 | 73.062 µs | 31.878 µs | 2.29x | | k=8, p=.70, width=32 | 172.681 µs | 31.965 µs | 5.40x | | k=8, p=.70, width=64 | 282.648 µs | 31.899 µs | 8.86x | | k=8, p=.90, no firing | 31.900 µs | 31.872 µs | 1.00x | | k=16, p=.70, width=32 | 380.918 µs | 68.728 µs | 5.54x | | k=8, p=.70, regex suffix | 146.079 µs | 375.879 µs | 0.39x | Width amplifies only the preselecting path; the no-fire control removes the gap. Regex reverses it, making left-deep 2.57x faster. This strongly argues against disabling preselection globally or treating right-deep as the fix. These Samply stack counts are inclusive and may overlap: | Profile | Samples | `filter_record_batch` | `pre_selection_scatter` | |---|---:|---:|---:| | Left | 7,948 | 4,937 (62.12%) | 1,263 (15.89%) | | Right | 8,031 | 1 (0.01%) | 2 (0.02%) | | Left p=.90 | 7,898 | 4 (0.05%) | 0 | #### Right-deep: `pre_selection_scatter` <img width="1455" height="486" alt="Image" src="https://github.com/user-attachments/assets/fc4b5d52-f47b-4acc-a258-7ce897f3886c"; /> #### Right-deep: `filter_record_batch` <img width="1454" height="497" alt="Image" src="https://github.com/user-attachments/assets/e6b2096a-c097-4dbf-b09c-e6e90ceb2900"; /> #### Left-deep: `filter_record_batch` <img width="1454" height="491" alt="Image" src="https://github.com/user-attachments/assets/294373f1-5802-46aa-821d-4301ca588bc6"; /> #### Left-deep: `pre_selection_scatter` <img width="1457" height="499" alt="Image" src="https://github.com/user-attachments/assets/5443fba4-7b4f-4632-93a9-6f216481235f"; /> ### Correctness constraints and next decision All 11 generated comparisons and 22 Criterion targets passed, alongside the targeted nullable/scalar association, short-circuit/scatter, physical-expression library (1,643 passed, 2 ignored), logical right-deep protobuf round-trip, and `simplify_inlist` tests. These validate current cases, not candidates. For Kleene value semantics, definite `FALSE` rows can retire, but `NULL` must remain active because `NULL AND FALSE = FALSE`. [`evaluate_selection`](https://github.com/apache/datafusion/blob/9082d6b10c29b72d56bede3d8e353d9d61fde542/datafusion/physical-expr-common/src/physical_expr.rs#L97-L180) guarantees that skipped rows cannot trigger errors. A changed active set can therefore alter rows evaluated, first observable error, and rows on which volatile expressions run. Git history points to [`4818966fa0` / #15694](https://github.com/apache/datafusion/commit/4818966fa0950a6a471d1ea9e4b8c5808878207e) as introducing partial-row filtering/scatter. Protobuf preserves an explicitly right-deep logical tree, while fully mergeable `InList` chains can simplify bottom-up. These findings narrow the serialization and `InList` objections to A, but A still changes global shape and does not address the evaluator’s state or cost policy. This motivates testing A as a control. B would carry one active-row mapping through the `AND` chain and restore full length once; C would gate compaction using its predicted benefit. I would test B, C, then B+C independently. Before prototyping, I would value alignment on: 1. Is evaluator-local `AND` flattening the right initial boundary, preserving stored shape, leaf order, serialization, display, optimizer behavior, and public API? 2. What observable contract must hold for fallible and volatile leaves: rows evaluated, evaluation count, and/or first observable error? 3. Should B and C remain independently switchable, and which cheap signals may C use: survivor ratio, estimated bytes, remaining conjuncts, or coarse expression cost? 4. What correctness and performance criteria should define acceptance? Should `OR` remain unchanged, and should selection-aware `FilterExec` integration be considered only if the `BinaryExpr` boundary is insufficient? After alignment, I will establish correctness, then compare baseline, B, C, and B+C with interleaved same-binary runs and profiles. Only then would I run 31 `predicate_eval` cases with validation, TPC-H Q06 and the full suite with A/A drift controls, and repository-wide checks before proposing a production fix. I would genuinely appreciate your feedback on the semantic contract and evaluator boundary :) -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
