Repository navigation
Commit 4bb9f8d
Prune hash join probe side via a build-side key range bitmap (apache#25602)
## 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 apache#123` indicates that this PR will close issue apache#123.
-->
- Closes apache#25291.
- Alternative to apache#25292.
## Rationale for this change
<!--
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.
Please explain the problem you are trying to solve in terms of the
user-visible
behavior, rather than the implementation.
For example, "The code in `foo.rs` doesn't handle nulls" is a symptom of
the
implementation. "COUNT(DISTINCT) returns wrong results when the column
contains
nulls" is the user-visible problem.
-->
Avoid scanning redundant files/row-groups/pages in the probe side of
hash joins, based on the values dictated by the build side.
## What changes are included in this PR?
<!--
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.
-->
- wiring up PushdownStrategy::Map/HashTableLookupExpr to carry a
representation of the build side values from a hash join, through
- `KeyRangeBitmap` implementation, which maps the build-side values
array into a finite-sized bitmap bucket, and can answer probing
questions for certain ranges
- extend `build_predicate_expression` to build the associated pruning
expression from `HashTableLookupExpr` using the new
`KeyRangeBitmapPruningExpr`, which implements `PhysicalExpr` on top of
`KeyRangeBitmap`
- also extend `build_predicate_expression` so that it now pushes down
pruning for `CaseExprs`, since that also unlocks the partitioned
hash-join scenario this pr targets
## What is the testing strategy for this PR?
<!--
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
Briefly describe how this PR is tested, and point to the specific tests
you added. For example: 'This new feature is covered by the
`sqllogictest` cases added in `foo.slt`'.
If this PR does not add tests, explain why. For example, if the change
is already covered by existing tests, please mention it.
You should also check the `codecov` bot reply on this PR to confirm the
changed code is exercised.
-->
A number of unit tests added, and one SLT added.
Also verified on the query shape that motivated the original issue
```sql
> copy (select i as k, random() as v from generate_series(0, 1999999) t(i))
to '/tmp/fact.parquet'
stored as parquet options ('format.max_row_group_size' '1000');
+---------+
| count |
+---------+
| 2000000 |
+---------+
1 row(s) fetched.
Elapsed 0.093 seconds.
> create external table fact stored as parquet location '/tmp/fact.parquet';
0 row(s) fetched.
Elapsed 0.008 seconds.
> create table dim as
select i as k from generate_series(0, 1999999) t(i) where i % 10000 < 200;
0 row(s) fetched.
Elapsed 0.014 seconds.
> select count(*), sum(v) from fact join dim on fact.k = dim.k;
select count(*), sum(v) from fact join dim on fact.k = dim.k;
select count(*), sum(v) from fact join dim on fact.k = dim.k;
select count(*), sum(v) from fact join dim on fact.k = dim.k;
+----------+--------------------+
| count(*) | sum(fact.v) |
+----------+--------------------+
| 40000 | 20121.308621485692 |
+----------+--------------------+
1 row(s) fetched.
Elapsed 0.031 seconds.
+----------+--------------------+
| count(*) | sum(fact.v) |
+----------+--------------------+
| 40000 | 20121.308621485692 |
+----------+--------------------+
1 row(s) fetched.
Elapsed 0.017 seconds.
+----------+-------------------+
| count(*) | sum(fact.v) |
+----------+-------------------+
| 40000 | 20121.30862148569 |
+----------+-------------------+
1 row(s) fetched.
Elapsed 0.011 seconds.
+----------+-------------------+
| count(*) | sum(fact.v) |
+----------+-------------------+
| 40000 | 20121.30862148569 |
+----------+-------------------+
1 row(s) fetched.
Elapsed 0.011 seconds.
> explain analyze select count(*), sum(v) from fact join dim on fact.k = dim.k;
...
| | DataSourceExec: file_groups={12 groups: [[tmp/fact.parquet:0..1927333], [tmp/fact.parquet:1927333..3854666], [tmp/fact.parquet:3854666..5781999], [tmp/fact.parquet:5781999..7709332], [tmp/fact.parquet:7709332..9636665], ...]}, projection=[k, v], output_ordering=[k@0 ASC NULLS LAST], file_type=parquet, predicate=DynamicFilter [ k@0 >= 0 AND k@0 <= 1990199 AND hash_lookup ], dynamic_rg_pruning=eligible, pruning_predicate=k_null_count@1 != row_count@2 AND k_max@0 >= 0 AND k_null_count@1 != row_count@2 AND k_min@3 <= 1990199 AND k_null_count@1 != row_count@2 AND KEY_RANGE_BITMAP(k_min@3, k_max@0, 20000/1048576 buckets), required_guarantees=[], metrics=[output_rows=200.0 K, elapsed_compute=9.65ms, output_bytes=25.0 MB, output_batches=200, files_ranges_pruned_statistics=12 total → 12 matched, row_groups_pruned_statistics=2.00 K total → 200 matched, row_groups_pruned_bloom_filter=200 total → 200 matched, page_index_pages_pruned=200 total → 200 matched, page_index_rows_pruned=200.0 K total → 200.0 K matched, limit_pruned_row_groups=0 total → 0 matched, batches_split=0, bytes_processed=22.1 MB, bytes_scanned=2.1 MB, file_open_errors=0, file_scan_errors=0, files_opened=12, files_processed=12, num_predicate_creation_errors=0, predicate_evaluation_errors=0, pushdown_rows_matched=0, pushdown_rows_pruned=0, row_groups_pruned_dynamic_filter=0, predicate_cache_inner_records=0, predicate_cache_records=0, bloom_filter_eval_time=64.23µs, metadata_load_time=345.27µs, page_index_eval_time=1.33ms, row_pushdown_eval_time=36ns, statistics_eval_time=896.06µs, time_elapsed_opening=6.99ms, time_elapsed_processing=24.90ms, time_elapsed_scanning_total=224.99ms, time_elapsed_scanning_until_data=25.01ms, output_rows_skew=1.19%, scan_efficiency_ratio=9.7% (2.24 M/23.13 M)] |
...
```
## Are there any user-facing changes?
<!--
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.
-->
---------
Co-authored-by: Claude Opus 5 (1M context) <[email protected]>
Co-authored-by: Jay Zhan <[email protected]>1 parent 348553b commit 4bb9f8d
14 files changed
Lines changed: 877 additions & 48 deletions
File tree
- datafusion
- physical-plan/src/joins
- hash_join
- exec/prepared
- proto/tests/cases/plans
- pruning
- src
- sqllogictest/test_files
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
40 | 40 | | |
41 | 41 | | |
42 | 42 | | |
| 43 | + | |
43 | 44 | | |
44 | 45 | | |
45 | 46 | | |
| |||
3318 | 3319 | | |
3319 | 3320 | | |
3320 | 3321 | | |
3321 | | - | |
| 3322 | + | |
| 3323 | + | |
| 3324 | + | |
| 3325 | + | |
3322 | 3326 | | |
3323 | 3327 | | |
3324 | 3328 | | |
| |||
3328 | 3332 | | |
3329 | 3333 | | |
3330 | 3334 | | |
3331 | | - | |
3332 | | - | |
3333 | | - | |
3334 | | - | |
3335 | | - | |
| 3335 | + | |
| 3336 | + | |
| 3337 | + | |
| 3338 | + | |
| 3339 | + | |
| 3340 | + | |
3336 | 3341 | | |
3337 | | - | |
| 3342 | + | |
| 3343 | + | |
| 3344 | + | |
| 3345 | + | |
3338 | 3346 | | |
3339 | | - | |
3340 | | - | |
3341 | 3347 | | |
3342 | 3348 | | |
3343 | | - | |
| 3349 | + | |
| 3350 | + | |
| 3351 | + | |
| 3352 | + | |
| 3353 | + | |
| 3354 | + | |
| 3355 | + | |
| 3356 | + | |
| 3357 | + | |
| 3358 | + | |
| 3359 | + | |
| 3360 | + | |
| 3361 | + | |
| 3362 | + | |
| 3363 | + | |
| 3364 | + | |
| 3365 | + | |
| 3366 | + | |
| 3367 | + | |
| 3368 | + | |
| 3369 | + | |
| 3370 | + | |
| 3371 | + | |
| 3372 | + | |
| 3373 | + | |
3344 | 3374 | | |
3345 | 3375 | | |
3346 | 3376 | | |
| |||
3519 | 3549 | | |
3520 | 3550 | | |
3521 | 3551 | | |
| 3552 | + | |
| 3553 | + | |
| 3554 | + | |
| 3555 | + | |
| 3556 | + | |
| 3557 | + | |
| 3558 | + | |
| 3559 | + | |
| 3560 | + | |
| 3561 | + | |
| 3562 | + | |
| 3563 | + | |
| 3564 | + | |
| 3565 | + | |
| 3566 | + | |
| 3567 | + | |
| 3568 | + | |
| 3569 | + | |
| 3570 | + | |
| 3571 | + | |
| 3572 | + | |
| 3573 | + | |
| 3574 | + | |
| 3575 | + | |
| 3576 | + | |
| 3577 | + | |
| 3578 | + | |
| 3579 | + | |
| 3580 | + | |
| 3581 | + | |
| 3582 | + | |
| 3583 | + | |
| 3584 | + | |
| 3585 | + | |
| 3586 | + | |
| 3587 | + | |
| 3588 | + | |
| 3589 | + | |
| 3590 | + | |
| 3591 | + | |
| 3592 | + | |
| 3593 | + | |
| 3594 | + | |
| 3595 | + | |
| 3596 | + | |
| 3597 | + | |
| 3598 | + | |
| 3599 | + | |
| 3600 | + | |
| 3601 | + | |
| 3602 | + | |
| 3603 | + | |
| 3604 | + | |
| 3605 | + | |
| 3606 | + | |
| 3607 | + | |
| 3608 | + | |
| 3609 | + | |
| 3610 | + | |
| 3611 | + | |
| 3612 | + | |
| 3613 | + | |
| 3614 | + | |
| 3615 | + | |
| 3616 | + | |
3522 | 3617 | | |
3523 | 3618 | | |
3524 | 3619 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
785 | 785 | | |
786 | 786 | | |
787 | 787 | | |
788 | | - | |
| 788 | + | |
| 789 | + | |
| 790 | + | |
789 | 791 | | |
790 | 792 | | |
791 | 793 | | |
| |||
795 | 797 | | |
796 | 798 | | |
797 | 799 | | |
798 | | - | |
799 | | - | |
800 | | - | |
| 800 | + | |
| 801 | + | |
| 802 | + | |
| 803 | + | |
| 804 | + | |
| 805 | + | |
801 | 806 | | |
802 | 807 | | |
803 | 808 | | |
| |||
888 | 893 | | |
889 | 894 | | |
890 | 895 | | |
891 | | - | |
| 896 | + | |
892 | 897 | | |
893 | 898 | | |
894 | 899 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
34 | 34 | | |
35 | 35 | | |
36 | 36 | | |
| 37 | + | |
37 | 38 | | |
38 | 39 | | |
39 | 40 | | |
| |||
284 | 285 | | |
285 | 286 | | |
286 | 287 | | |
| 288 | + | |
| 289 | + | |
287 | 290 | | |
288 | 291 | | |
289 | 292 | | |
| |||
293 | 296 | | |
294 | 297 | | |
295 | 298 | | |
| 299 | + | |
296 | 300 | | |
297 | 301 | | |
298 | 302 | | |
| |||
303 | 307 | | |
304 | 308 | | |
305 | 309 | | |
| 310 | + | |
306 | 311 | | |
307 | 312 | | |
308 | 313 | | |
309 | 314 | | |
310 | 315 | | |
311 | 316 | | |
| 317 | + | |
312 | 318 | | |
313 | 319 | | |
| 320 | + | |
| 321 | + | |
| 322 | + | |
| 323 | + | |
| 324 | + | |
314 | 325 | | |
315 | 326 | | |
316 | 327 | | |
| |||
363 | 374 | | |
364 | 375 | | |
365 | 376 | | |
366 | | - | |
367 | | - | |
368 | | - | |
369 | | - | |
370 | | - | |
371 | | - | |
| 377 | + | |
| 378 | + | |
| 379 | + | |
| 380 | + | |
| 381 | + | |
| 382 | + | |
| 383 | + | |
372 | 384 | | |
373 | 385 | | |
374 | 386 | | |
| |||
414 | 426 | | |
415 | 427 | | |
416 | 428 | | |
| 429 | + | |
417 | 430 | | |
418 | 431 | | |
419 | 432 | | |
| |||
460 | 473 | | |
461 | 474 | | |
462 | 475 | | |
| 476 | + | |
463 | 477 | | |
464 | 478 | | |
465 | 479 | | |
| |||
470 | 484 | | |
471 | 485 | | |
472 | 486 | | |
| 487 | + | |
| 488 | + | |
| 489 | + | |
| 490 | + | |
| 491 | + | |
| 492 | + | |
| 493 | + | |
| 494 | + | |
| 495 | + | |
| 496 | + | |
| 497 | + | |
| 498 | + | |
| 499 | + | |
| 500 | + | |
| 501 | + | |
| 502 | + | |
| 503 | + | |
| 504 | + | |
| 505 | + | |
| 506 | + | |
| 507 | + | |
| 508 | + | |
| 509 | + | |
| 510 | + | |
| 511 | + | |
| 512 | + | |
| 513 | + | |
| 514 | + | |
| 515 | + | |
| 516 | + | |
473 | 517 | | |
474 | 518 | | |
475 | 519 | | |
| |||
748 | 792 | | |
749 | 793 | | |
750 | 794 | | |
| 795 | + | |
751 | 796 | | |
752 | 797 | | |
753 | 798 | | |
754 | 799 | | |
755 | 800 | | |
756 | 801 | | |
757 | 802 | | |
| 803 | + | |
758 | 804 | | |
759 | 805 | | |
760 | 806 | | |
| |||
773 | 819 | | |
774 | 820 | | |
775 | 821 | | |
| 822 | + | |
776 | 823 | | |
777 | 824 | | |
778 | 825 | | |
779 | 826 | | |
780 | 827 | | |
781 | 828 | | |
782 | 829 | | |
| 830 | + | |
783 | 831 | | |
784 | 832 | | |
785 | 833 | | |
| |||
796 | 844 | | |
797 | 845 | | |
798 | 846 | | |
| 847 | + | |
799 | 848 | | |
800 | 849 | | |
801 | 850 | | |
802 | 851 | | |
803 | 852 | | |
804 | 853 | | |
805 | 854 | | |
| 855 | + | |
806 | 856 | | |
807 | 857 | | |
808 | 858 | | |
| |||
822 | 872 | | |
823 | 873 | | |
824 | 874 | | |
| 875 | + | |
825 | 876 | | |
826 | 877 | | |
827 | 878 | | |
828 | 879 | | |
829 | 880 | | |
830 | 881 | | |
831 | 882 | | |
| 883 | + | |
832 | 884 | | |
833 | 885 | | |
834 | 886 | | |
| |||
846 | 898 | | |
847 | 899 | | |
848 | 900 | | |
| 901 | + | |
849 | 902 | | |
850 | 903 | | |
851 | 904 | | |
852 | 905 | | |
853 | 906 | | |
854 | 907 | | |
855 | 908 | | |
| 909 | + | |
856 | 910 | | |
857 | 911 | | |
858 | 912 | | |
| |||
0 commit comments