Skip to content

Commit 63aa427

Browse files
zhuqi-lucaszhuqi-lucas
authored
Merge branch 'main' into asolimando/query-lifetime-stats-cache
2 parents c101751 + 3ed377a commit 63aa427

121 files changed

Lines changed: 7711 additions & 2458 deletions

File tree

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

‎.github/workflows/rust.yml‎

Lines changed: 4 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -700,10 +700,12 @@ jobs:
700700
rust-version: stable
701701
- name: Run sqllogictest
702702
# TODO: Right now several tests are failing in Substrait round-trip mode, so this
703-
# command cannot be run for all the .slt files. Run it for just one that works (limit.slt)
703+
# command cannot be run for all the .slt files. Run a supported subset
704704
# until most of the tickets in https://github.com/apache/datafusion/issues/16248 are addressed
705705
# and this command can be run without filters.
706-
run: cargo xtask ci step test substrait
706+
run: |
707+
cargo xtask ci step test substrait
708+
cargo xtask ci step test substrait-optimized
707709
708710
# Temporarily commenting out the Windows flow, the reason is enormously slow running build
709711
# Waiting for new Windows 2025 github runner

‎AGENTS.md‎

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -4,12 +4,19 @@
44

55
- [Quick Start Setup](docs/source/contributor-guide/development_environment.md#quick-start)
66
- [Testing Quick Start](docs/source/contributor-guide/testing.md#testing-quick-start)
7+
- [Open Contribution and Assigning tickets](docs/source/contributor-guide/index.md#open-contribution-and-assigning-tickets)
78
- [Choosing What Kind of Test to Write](docs/source/contributor-guide/testing.md#choosing-what-kind-of-test-to-write)
89
- [Before Submitting a PR](docs/source/contributor-guide/index.md#before-submitting-a-pr)
910
- [Reviewing Pull Requests](docs/source/contributor-guide/pr_review.md)
1011
- [Contributor Guide](docs/source/contributor-guide/index.md)
1112
- [Architecture Guide](docs/source/contributor-guide/architecture.md)
1213

14+
## Before Starting Work
15+
16+
Before you start work on an issue, you MUST follow the instructions in
17+
[Open Contribution and Assigning tickets](docs/source/contributor-guide/index.md#open-contribution-and-assigning-tickets). You must ensure duplicate work is not being created.
18+
Do not create multiple PRs if this is your first time contributing.
19+
1320
## Before Committing
1421

1522
Before committing any changes, you MUST follow the instructions in

‎benchmarks/sql_benchmarks/null_aware_join/benchmarks/q10.benchmark‎

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
name Q10
2+
group null_aware_join
3+
4+
load sql_benchmarks/null_aware_join/init/load.sql
5+
6+
# Correctness canary: the NOT IN result must match a reference count that does
7+
# not use NOT IN. It holds for every NAJ_ROWS. No key holds a NULL, so a row is
8+
# kept exactly when no subquery row equals its whole tuple.
9+
assert I
10+
SELECT count(*) = (
11+
SELECT count(*)
12+
FROM small_outer o
13+
WHERE NOT EXISTS (
14+
SELECT 1 FROM small_inner i WHERE i.id_n0 = o.id_n0 AND i.z = o.z
15+
)
16+
)
17+
FROM small_outer o
18+
WHERE (o.id_n0, o.z) NOT IN (SELECT i.id_n0, i.z FROM small_inner i);
19+
----
20+
true
21+
22+
expect_plan HashJoinExec
23+
24+
run
25+
-- Q10: uncorrelated multi-column NOT IN over nullable keys that hold no NULL.
26+
-- A tuple NOT IN always decides UNKNOWN per build row (the outer side), but
27+
-- without NULLs there is no candidate pair to check, so this is the floor for
28+
-- the multi-column shape.
29+
SELECT count(*)
30+
FROM small_outer o
31+
WHERE (o.id_n0, o.z) NOT IN (SELECT i.id_n0, i.z FROM small_inner i);
32+
33+
cleanup sql_benchmarks/null_aware_join/init/cleanup.sql

‎benchmarks/sql_benchmarks/null_aware_join/benchmarks/q11.benchmark‎

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
name Q11
2+
group null_aware_join
3+
4+
load sql_benchmarks/null_aware_join/init/load.sql
5+
6+
# Correctness canary: the NOT IN result must match a reference count that does
7+
# not use NOT IN. It holds for every NAJ_ROWS. The outer tuple holds no NULL, so
8+
# a subquery row makes it UNKNOWN or TRUE exactly when `z` matches and `id_n1`
9+
# is NULL or equal; the row is kept only when no such subquery row exists.
10+
assert I
11+
SELECT count(*) = (
12+
SELECT count(*)
13+
FROM small_outer o
14+
WHERE NOT EXISTS (
15+
SELECT 1 FROM small_inner i
16+
WHERE i.z = o.z AND (i.id_n1 IS NULL OR i.id_n1 = o.id_n0)
17+
)
18+
)
19+
FROM small_outer o
20+
WHERE (o.id_n0, o.z) NOT IN (SELECT i.id_n1, i.z FROM small_inner i);
21+
----
22+
true
23+
24+
expect_plan HashJoinExec
25+
26+
run
27+
-- Q11: uncorrelated multi-column NOT IN with 1% NULL in one subquery element.
28+
-- Each NULL-valued subquery row is paired with every outer row and the pair is
29+
-- kept as UNKNOWN only when the other element matches, so the cost grows with
30+
-- (outer rows) x (NULL-valued subquery rows). Compare with Q10 and Q12.
31+
SELECT count(*)
32+
FROM small_outer o
33+
WHERE (o.id_n0, o.z) NOT IN (SELECT i.id_n1, i.z FROM small_inner i);
34+
35+
cleanup sql_benchmarks/null_aware_join/init/cleanup.sql

‎benchmarks/sql_benchmarks/null_aware_join/benchmarks/q12.benchmark‎

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
name Q12
2+
group null_aware_join
3+
4+
load sql_benchmarks/null_aware_join/init/load.sql
5+
6+
# Correctness canary: the NOT IN result must match a reference count that does
7+
# not use NOT IN. It holds for every NAJ_ROWS. The subquery holds no NULL, so a
8+
# subquery row makes an outer tuple UNKNOWN or TRUE exactly when `z` matches and
9+
# the outer `id_n1` is NULL or equal; the row is kept only when no such
10+
# subquery row exists.
11+
assert I
12+
SELECT count(*) = (
13+
SELECT count(*)
14+
FROM small_outer o
15+
WHERE NOT EXISTS (
16+
SELECT 1 FROM small_inner i
17+
WHERE i.z = o.z AND (o.id_n1 IS NULL OR i.id_n0 = o.id_n1)
18+
)
19+
)
20+
FROM small_outer o
21+
WHERE (o.id_n1, o.z) NOT IN (SELECT i.id_n0, i.z FROM small_inner i);
22+
----
23+
true
24+
25+
expect_plan HashJoinExec
26+
27+
run
28+
-- Q12: uncorrelated multi-column NOT IN with 1% NULL in one outer element,
29+
-- the mirror of Q11. The outer side is the build side, so each NULL-valued
30+
-- build row is paired with every subquery row and kept as UNKNOWN only when
31+
-- the other element matches: the cost grows with (NULL-valued outer rows) x
32+
-- (subquery rows). Compare with Q10 and Q11.
33+
SELECT count(*)
34+
FROM small_outer o
35+
WHERE (o.id_n1, o.z) NOT IN (SELECT i.id_n0, i.z FROM small_inner i);
36+
37+
cleanup sql_benchmarks/null_aware_join/init/cleanup.sql

‎benchmarks/sql_benchmarks/null_aware_join/init/load.sql‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -14,7 +14,7 @@
1414
-- `id` is only ~half covered by the subquery side, so the anti join returns rows
1515
-- rather than degenerating to an empty or full result.
1616

17-
-- Small tables: used by the correlated queries (Q04-Q08), whose cost grows with
17+
-- Small tables: used by the correlated and multi-column queries (Q04-Q12), whose cost grows with
1818
-- the product of the two table sizes.
1919
CREATE TABLE small_outer AS
2020
SELECT

‎benchmarks/sql_benchmarks/null_aware_join/null_aware_join.suite‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
description = "Null-aware (NOT IN) hash join benchmarks: uncorrelated, non-equality-correlated, and equality-correlated NOT IN across NULL fractions, plus the positive IN shape that must not be null-aware"
1+
description = "Null-aware (NOT IN) hash join benchmarks: uncorrelated, non-equality-correlated, and equality-correlated NOT IN across NULL fractions, plus the positive IN shape that must not be null-aware, and multi-column (tuple) NOT IN with and without NULLs"
22

33
query_pattern = "q{QUERY_ID_PADDED}.benchmark"
44

@@ -8,7 +8,7 @@ short = "r"
88
env = "NAJ_ROWS"
99
default = "10000"
1010
values = ["10000", "..."]
11-
help = "Rows per table for the correlated queries (Q04-Q09). These evaluate the join filter over candidate build x probe pairs, so their cost grows with the square of this value."
11+
help = "Rows per table for the correlated and multi-column queries (Q04-Q12). These evaluate the join filter over candidate build x probe pairs, so their cost grows with the square of this value."
1212

1313
[[options]]
1414
name = "large-rows"

‎datafusion/common/benches/with_hashes.rs‎

Lines changed: 64 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -18,9 +18,10 @@
1818
//! Benchmarks for `with_hashes` function
1919
2020
use arrow::array::{
21-
Array, ArrayRef, ArrowPrimitiveType, DictionaryArray, GenericStringArray, Int32Array,
22-
Int64Array, ListArray, MapArray, NullBufferBuilder, OffsetSizeTrait, PrimitiveArray,
23-
RunArray, StringViewArray, StructArray, UnionArray, make_array,
21+
Array, ArrayRef, ArrowPrimitiveType, DictionaryArray, FixedSizeListArray,
22+
GenericStringArray, Int32Array, Int64Array, ListArray, ListViewArray, MapArray,
23+
NullArray, NullBufferBuilder, OffsetSizeTrait, PrimitiveArray, RunArray,
24+
StringViewArray, StructArray, UnionArray, make_array,
2425
};
2526
use arrow::buffer::{NullBuffer, OffsetBuffer, ScalarBuffer};
2627
use arrow::datatypes::{
@@ -127,6 +128,21 @@ fn criterion_benchmark(c: &mut Criterion) {
127128
array: create_run_array::<Int32Type>(BATCH_SIZE),
128129
supports_nulls: true,
129130
},
131+
BenchData {
132+
name: "null",
133+
array: Arc::new(NullArray::new(BATCH_SIZE)),
134+
supports_nulls: false,
135+
},
136+
BenchData {
137+
name: "list_view_array",
138+
array: list_view_array(BATCH_SIZE),
139+
supports_nulls: true,
140+
},
141+
BenchData {
142+
name: "fixed_size_list_array",
143+
array: fixed_size_list_array(BATCH_SIZE),
144+
supports_nulls: true,
145+
},
130146
];
131147

132148
for BenchData {
@@ -603,5 +619,49 @@ where
603619
)
604620
}
605621

606-
criterion_group!(benches, criterion_benchmark, sliced_array_benchmark);
622+
fn list_view_array(num_rows: usize) -> ArrayRef {
623+
let elements_per_row = 5;
624+
let values = primitive_array::<Int64Type>(num_rows * elements_per_row);
625+
let offsets: ScalarBuffer<i32> = (0..num_rows)
626+
.map(|i| (i * elements_per_row) as i32)
627+
.collect();
628+
let sizes: ScalarBuffer<i32> =
629+
(0..num_rows).map(|_| elements_per_row as i32).collect();
630+
Arc::new(ListViewArray::new(
631+
Arc::new(Field::new("item", DataType::Int64, true)),
632+
offsets,
633+
sizes,
634+
values,
635+
None,
636+
))
637+
}
638+
639+
fn fixed_size_list_array(num_rows: usize) -> ArrayRef {
640+
let list_size = 4;
641+
Arc::new(FixedSizeListArray::new(
642+
Arc::new(Field::new("item", DataType::Int64, true)),
643+
list_size as i32,
644+
primitive_array::<Int64Type>(num_rows * list_size),
645+
None,
646+
))
647+
}
648+
649+
/// Heterogeneous key columns
650+
fn mixed_columns_benchmark(c: &mut Criterion) {
651+
let pool = StringPool::new(100, 64);
652+
let int64 = primitive_array::<Int64Type>(BATCH_SIZE);
653+
let utf8 = pool.string_array::<i32>(BATCH_SIZE);
654+
let utf8_view = pool.string_view_array(BATCH_SIZE);
655+
let arrays = vec![int64, utf8, utf8_view];
656+
c.bench_function("mixed: 3 columns (int64, utf8, utf8_view)", |b| {
657+
do_hash_test(b, &arrays)
658+
});
659+
}
660+
661+
criterion_group!(
662+
benches,
663+
criterion_benchmark,
664+
sliced_array_benchmark,
665+
mixed_columns_benchmark
666+
);
607667
criterion_main!(benches);

‎datafusion/common/src/config.rs‎

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1809,7 +1809,9 @@ config_namespace! {
18091809
/// rule. When set to false, any rules that produce errors will cause the query to fail
18101810
pub skip_failed_rules: bool, default = false
18111811

1812-
/// Number of times that the optimizer will attempt to optimize the plan
1812+
/// The logical optimizer applies rules in order for up to `max_passes` passes,
1813+
/// stopping early if a pass leaves the plan unchanged or repeats an earlier plan.
1814+
/// The physical optimizer always runs in one pass.
18131815
pub max_passes: usize, default = 3
18141816

18151817
/// When set to true, the physical plan optimizer will run a top down

‎datafusion/core/src/physical_planner.rs‎

Lines changed: 16 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -41,7 +41,7 @@ use crate::physical_plan::explain::ExplainExec;
4141
use crate::physical_plan::filter::FilterExecBuilder;
4242
use crate::physical_plan::joins::utils as join_utils;
4343
use crate::physical_plan::joins::{
44-
AsOfJoinExec, AsOfMatchExpr, CrossJoinExec, HashJoinExec, NestedLoopJoinExec,
44+
AsOfJoinExec, AsOfMatchExpr, CrossJoinExec, HashJoinExecBuilder, NestedLoopJoinExec,
4545
PartitionMode, SortMergeJoinExec,
4646
};
4747
use crate::physical_plan::limit::{GlobalLimitExec, LocalLimitExec};
@@ -1377,6 +1377,7 @@ impl DefaultPhysicalPlanner {
13771377
join_type,
13781378
null_equality,
13791379
null_aware,
1380+
null_aware_value_keys,
13801381
schema: join_schema,
13811382
..
13821383
}) => {
@@ -1809,17 +1810,20 @@ impl DefaultPhysicalPlanner {
18091810
PartitionMode::CollectLeft
18101811
};
18111812

1812-
Arc::new(HashJoinExec::try_new(
1813-
physical_left,
1814-
physical_right,
1815-
join_on,
1816-
join_filter,
1817-
join_type,
1818-
None,
1819-
partition_mode,
1820-
*null_equality,
1821-
*null_aware,
1822-
)?)
1813+
Arc::new(
1814+
HashJoinExecBuilder::new(
1815+
physical_left,
1816+
physical_right,
1817+
join_on,
1818+
*join_type,
1819+
)
1820+
.with_filter(join_filter)
1821+
.with_partition_mode(partition_mode)
1822+
.with_null_equality(*null_equality)
1823+
.with_null_aware(*null_aware)
1824+
.with_null_aware_value_keys(*null_aware_value_keys)
1825+
.build()?,
1826+
)
18231827
};
18241828

18251829
// If plan was mutated previously then need to create the ExecutionPlan

0 commit comments

Comments
 (0)