You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "kumarUjjawal (via GitHub)" <gi...@apache.org> on 2026/06/22 15:15:51 UTC
[PR] refactor: centralize TopK heap boundary handling [datafusion]
kumarUjjawal opened a new pull request, #23091:
URL: https://github.com/apache/datafusion/pull/23091
## Which issue does this PR close?
<!--
We generally require a GitHub issue to be filed for all bug fixes and enhancements and this helps us generate change logs for our releases. You can link an issue to this PR using the GitHub syntax. For example `Closes #123` indicates that this PR will close issue #123.
-->
- Closes #23073.
## Rationale for this change
TopK derives local heap-boundary data in multiple places. This refactor names that boundary and keeps full sort-key bytes, scalar threshold values, and prefix comparison tied to the same heap row.
<!--
Why are you proposing this change? If this is already explained clearly in the issue then this section is not needed.
Explaining clearly why changes are proposed helps reviewers understand your changes and offer better suggestions for fixes.
-->
## What changes are included in this PR?
- Add a private helper for the current local TopK heap boundary.
- Use it when updating dynamic filter thresholds.
- Use it for local prefix early-completion checks.
- Remove the old duplicate scalar threshold extraction path.
<!--
There is no need to duplicate the description in the issue here but it is sometimes worth providing a summary of the individual changes in this PR.
-->
## Are these changes tested?
Yes
<!--
We typically require tests for all PRs in order to:
1. Prevent the code from being accidentally broken by subsequent changes
2. Serve as another way to document the expected behavior of the code
If tests are not included in your PR, please explain why (for example, are they covered by existing tests)?
-->
## Are there any user-facing changes?
No
<!--
If there are user-facing changes then we may require documentation to be updated before approving the PR.
-->
<!--
If there are any breaking changes to public APIs, please add the `api change` label.
-->
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] refactor: centralize TopK heap boundary handling [datafusion]
Posted by "kosiew (via GitHub)" <gi...@apache.org>.
kosiew commented on code in PR #23091:
URL: https://github.com/apache/datafusion/pull/23091#discussion_r3457310431
##########
datafusion/physical-plan/src/topk/mod.rs:
##########
@@ -195,6 +195,67 @@ impl TopKThreshold {
}
}
+#[derive(Clone, Copy)]
+struct TopKHeapBoundaryRow<'a> {
+ row: &'a TopKRow,
+}
+
+impl<'a> TopKHeapBoundaryRow<'a> {
+ fn new(row: &'a TopKRow) -> Self {
+ Self { row }
+ }
+
+ fn full_sort_key_row(&self) -> &[u8] {
+ self.row.row()
+ }
+
+ fn is_more_selective_than(&self, current: Option<&TopKThreshold>) -> bool {
+ current
+ .map(|current| self.full_sort_key_row() < current.full_sort_key_row())
+ .unwrap_or(true)
+ }
+}
+
+#[derive(Clone, Copy)]
+struct TopKHeapBoundary<'a> {
+ row: &'a TopKRow,
+ batch: &'a RecordBatch,
+}
+
+impl<'a> TopKHeapBoundary<'a> {
+ fn new(row: &'a TopKRow, batch: &'a RecordBatch) -> Self {
+ Self { row, batch }
+ }
+
+ fn threshold_values(
+ &self,
+ sort_exprs: &[PhysicalSortExpr],
+ ) -> Result<Vec<ScalarValue>> {
+ let mut scalar_values = Vec::with_capacity(sort_exprs.len());
+ for sort_expr in sort_exprs {
+ let expr = Arc::clone(&sort_expr.expr);
Review Comment:
Small cleanup suggestion: since `expr` is only used for this one `evaluate` call, the `Arc` clone can be avoided.
This could be written directly as:
`let value = sort_expr.expr.evaluate(&batch_entry.batch.slice(self.row.index, 1))?;`
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] refactor: centralize TopK heap boundary handling [datafusion]
Posted by "geoffreyclaude (via GitHub)" <gi...@apache.org>.
geoffreyclaude commented on PR #23091:
URL: https://github.com/apache/datafusion/pull/23091#issuecomment-4771171711
Nice cleanup. I'm wondering if `TopKHeapBoundary` should hold both the heap row and the batch it points to, instead of having `threshold_values` take `&TopKHeap` and look back into `heap.store`.
That would make it clearer that the sort-key bytes, scalar values, and prefix row all come from the same row.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] refactor: centralize TopK heap boundary handling [datafusion]
Posted by "kumarUjjawal (via GitHub)" <gi...@apache.org>.
kumarUjjawal commented on PR #23091:
URL: https://github.com/apache/datafusion/pull/23091#issuecomment-4769862277
run benchmark topk_sorted_tpch
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] refactor: centralize TopK heap boundary handling [datafusion]
Posted by "kumarUjjawal (via GitHub)" <gi...@apache.org>.
kumarUjjawal commented on PR #23091:
URL: https://github.com/apache/datafusion/pull/23091#issuecomment-4775949269
> Nice cleanup. I'm wondering if `TopKHeapBoundary` should hold both the heap row and the batch it points to, instead of having `threshold_values` take `&TopKHeap` and look back into `heap.store`.
>
> That would make it clearer that the sort-key bytes, scalar values, and prefix row all come from the same row.
Thank you @geoffreyclaude for the feedback!
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] refactor: centralize TopK heap boundary handling [datafusion]
Posted by "kumarUjjawal (via GitHub)" <gi...@apache.org>.
kumarUjjawal commented on code in PR #23091:
URL: https://github.com/apache/datafusion/pull/23091#discussion_r3457382752
##########
datafusion/physical-plan/src/topk/mod.rs:
##########
@@ -195,6 +195,67 @@ impl TopKThreshold {
}
}
+#[derive(Clone, Copy)]
+struct TopKHeapBoundaryRow<'a> {
+ row: &'a TopKRow,
+}
+
+impl<'a> TopKHeapBoundaryRow<'a> {
+ fn new(row: &'a TopKRow) -> Self {
+ Self { row }
+ }
+
+ fn full_sort_key_row(&self) -> &[u8] {
+ self.row.row()
+ }
+
+ fn is_more_selective_than(&self, current: Option<&TopKThreshold>) -> bool {
+ current
+ .map(|current| self.full_sort_key_row() < current.full_sort_key_row())
+ .unwrap_or(true)
+ }
+}
+
+#[derive(Clone, Copy)]
+struct TopKHeapBoundary<'a> {
+ row: &'a TopKRow,
+ batch: &'a RecordBatch,
+}
+
+impl<'a> TopKHeapBoundary<'a> {
+ fn new(row: &'a TopKRow, batch: &'a RecordBatch) -> Self {
+ Self { row, batch }
+ }
+
+ fn threshold_values(
+ &self,
+ sort_exprs: &[PhysicalSortExpr],
+ ) -> Result<Vec<ScalarValue>> {
+ let mut scalar_values = Vec::with_capacity(sort_exprs.len());
+ for sort_expr in sort_exprs {
+ let expr = Arc::clone(&sort_expr.expr);
Review Comment:
Sounds good!
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] refactor: centralize TopK heap boundary handling [datafusion]
Posted by "kosiew (via GitHub)" <gi...@apache.org>.
kosiew merged PR #23091:
URL: https://github.com/apache/datafusion/pull/23091
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] refactor: centralize TopK heap boundary handling [datafusion]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #23091:
URL: https://github.com/apache/datafusion/pull/23091#issuecomment-4769897554
๐ค Benchmark running (GKE) | [trigger](https://github.com/apache/datafusion/pull/23091#issuecomment-4769862277)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB) | `Linux bench-c4769862277-612-tqlxx 6.12.68+ #1 SMP Sat May 2 07:49:07 UTC 2026 aarch64 GNU/Linux`
<details><summary>CPU Details (lscpu)</summary>
```
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
Comparing refactor/topk-heap-boundary (2a96e347846c549a7f3a5e68f7b3998542fc1528) to 9e68a86 (merge-base) [diff](https://github.com/apache/datafusion/compare/9e68a86ddcd1b9968331842406cc2f65263d784c..2a96e347846c549a7f3a5e68f7b3998542fc1528) using: topk_sorted_tpch
Results will be posted here when complete
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] refactor: centralize TopK heap boundary handling [datafusion]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #23091:
URL: https://github.com/apache/datafusion/pull/23091#issuecomment-4770044899
๐ค Benchmark completed (GKE) | [trigger](https://github.com/apache/datafusion/pull/23091#issuecomment-4769862277)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB)
<details><summary>CPU Details (lscpu)</summary>
```
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
<details><summary>Details</summary>
<p>
```
Comparing HEAD and refactor_topk-heap-boundary
--------------------
Benchmark run_topk_sorted_tpch.json
--------------------
โโโโโโโโโณโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโณโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโณโโโโโโโโโโโโโโโโ
โ Query โ HEAD โ refactor_topk-heap-boundary โ Change โ
โกโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโฉ
โ Q1 โ 2.24 / 2.94 ยฑ0.85 / 4.29 ms โ 2.16 / 2.68 ยฑ0.85 / 4.37 ms โ +1.10x faster โ
โ Q2 โ 2.33 / 2.47 ยฑ0.13 / 2.64 ms โ 2.37 / 2.49 ยฑ0.09 / 2.60 ms โ no change โ
โ Q3 โ 32.03 / 32.54 ยฑ0.40 / 32.94 ms โ 31.94 / 32.10 ยฑ0.20 / 32.47 ms โ no change โ
โ Q4 โ 2.66 / 2.78 ยฑ0.11 / 2.97 ms โ 2.64 / 2.73 ยฑ0.13 / 2.98 ms โ no change โ
โ Q5 โ 10.40 / 10.47 ยฑ0.09 / 10.65 ms โ 10.09 / 10.26 ยฑ0.12 / 10.43 ms โ no change โ
โ Q6 โ 17.65 / 17.89 ยฑ0.24 / 18.23 ms โ 17.44 / 17.72 ยฑ0.21 / 18.05 ms โ no change โ
โ Q7 โ 37.90 / 38.37 ยฑ0.45 / 39.00 ms โ 37.62 / 38.19 ยฑ0.54 / 39.08 ms โ no change โ
โ Q8 โ 3.49 / 3.88 ยฑ0.64 / 5.16 ms โ 3.42 / 3.82 ยฑ0.74 / 5.30 ms โ no change โ
โ Q9 โ 4.87 / 4.92 ยฑ0.04 / 4.98 ms โ 4.79 / 5.41 ยฑ1.14 / 7.68 ms โ 1.10x slower โ
โ Q10 โ 6.97 / 7.00 ยฑ0.02 / 7.03 ms โ 7.00 / 7.20 ยฑ0.32 / 7.84 ms โ no change โ
โ Q11 โ 3.82 / 3.92 ยฑ0.07 / 4.03 ms โ 3.79 / 3.86 ยฑ0.07 / 3.98 ms โ no change โ
โโโโโโโโโดโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโดโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโดโโโโโโโโโโโโโโโโ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโณโโโโโโโโโโโ
โ Benchmark Summary โ โ
โกโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโฉ
โ Total Time (HEAD) โ 127.18ms โ
โ Total Time (refactor_topk-heap-boundary) โ 126.46ms โ
โ Average Time (HEAD) โ 11.56ms โ
โ Average Time (refactor_topk-heap-boundary) โ 11.50ms โ
โ Queries Faster โ 1 โ
โ Queries Slower โ 1 โ
โ Queries with No Change โ 9 โ
โ Queries with Failure โ 0 โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโดโโโโโโโโโโโ
```
</p>
</details>
<details><summary>Resource Usage</summary>
**topk_sorted_tpch โ base (merge-base)**
| Metric | Value |
|--------|-------|
| Wall time | 5.0s |
| Peak memory | 260.0 KiB |
| Avg memory | 43.3 KiB |
| CPU user | 0.0s |
| CPU sys | 0.0s |
| Peak spill | 0 B |
**topk_sorted_tpch โ branch**
| Metric | Value |
|--------|-------|
| Wall time | 5.0s |
| Peak memory | 220.0 KiB |
| Avg memory | 36.7 KiB |
| CPU user | 0.0s |
| CPU sys | 0.0s |
| Peak spill | 0 B |
</details>
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org