Zero cardinality estimation lead to disastrous join ordering (on parquet tpch q21) #11638
Description
What happens?
Executing tpch q21 on parquet files results in joining the two largest tables (lineitem and orders) at the very beginning due to the join's CE is 0.
Here is the EXPLAIN plan
┌─────────────────────────────┐
│┌───────────────────────────┐│
││ Physical Plan ││
│└───────────────────────────┘│
└─────────────────────────────┘
┌─────────────────────┐
│ TOP_N │
│ ─ ─ ─ ─ ─ ─ ─ ─ │
│ Top 100 │
│ ─ ─ ─ ─ ─ ─ ─ ─ │
│ count_star() DESC │
│ supplier.s_name ASC │
└──────────┬──────────┘
┌──────────┴──────────┐
│ HASH_GROUP_BY │
│ ─ ─ ─ ─ ─ ─ ─ ─ │
│ #0 │
│ count_star() │
└──────────┬──────────┘
┌──────────┴──────────┐
│ PROJECTION │
│ ─ ─ ─ ─ ─ ─ ─ ─ │
│ s_name │
└──────────┬──────────┘
┌──────────┴──────────┐
│ PROJECTION │
│ ─ ─ ─ ─ ─ ─ ─ ─ │
│__internal_compress_i│
│ ntegral_utinyint(#0,│
│ 0) │
│__internal_compress_i│
│ntegral_usmallint(#1,│
│ 1) │
│__internal_compress_i│
│ ntegral_utinyint(#2,│
│ 0) │
│ #3 │
│ #4 │
└──────────┬──────────┘
┌──────────┴──────────┐
│ RIGHT_DELIM_JOIN │
│ ─ ─ ─ ─ ─ ─ ─ ─ │
│ RIGHT_ANTI │
│ l_orderkey IS NOT │
│ DISTINCT FROM l... ├─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│ l_suppkey IS NOT │ │
│ DISTINCT FROM l... │ │
│ ─ ─ ─ ─ ─ ─ ─ ─ │ │
│ EC: 6001215 │ │
└──────────┬──────────┘ │
┌──────────┴──────────┐ ┌──────────┴──────────┐
│ RIGHT_DELIM_JOIN │ │ HASH_JOIN │
│ ─ ─ ─ ─ ─ ─ ─ ─ │ │ ─ ─ ─ ─ ─ ─ ─ ─ │
│ RIGHT_SEMI │ │ RIGHT_ANTI │
│ l_orderkey IS NOT │ │ l_orderkey IS NOT │
│ DISTINCT FROM l... ├────────────────────────────────────────────────────────────────────────────────┐ │ DISTINCT FROM l... ├──────────────────────────────────┐
│ l_suppkey IS NOT │ │ │ l_suppkey IS NOT │ │
│ DISTINCT FROM l... │ │ │ DISTINCT FROM l... │ │
│ ─ ─ ─ ─ ─ ─ ─ ─ │ │ │ ─ ─ ─ ─ ─ ─ ─ ─ │ │
│ EC: 6001215 │ │ │ EC: 6001215 │ │
└──────────┬──────────┘ │ └──────────┬──────────┘ │
┌──────────┴──────────┐ ┌──────────┴──────────┐ ┌──────────┴──────────┐ ┌──────────┴──────────┐
│ HASH_JOIN │ │ HASH_JOIN │ │ PROJECTION │ │ DUMMY_SCAN │
│ ─ ─ ─ ─ ─ ─ ─ ─ │ │ ─ ─ ─ ─ ─ ─ ─ ─ │ │ ─ ─ ─ ─ ─ ─ ─ ─ │ │ │
│ INNER │ │ RIGHT_SEMI │ │ l_orderkey │ │ │
│ n_nationkey = │ │ l_orderkey IS NOT │ │ l_suppkey │ │ │
│ s_nationkey │ │ DISTINCT FROM l... │ │ │ │ │
│ ─ ─ ─ ─ ─ ─ ─ ─ ├───────────┐ │ l_suppkey IS NOT ├──────────────────────────────────┐ │ │ │ │
│ Build Min: 0 │ │ │ DISTINCT FROM l... │ │ │ │ │ │
│ Build Max: 24 │ │ │ ─ ─ ─ ─ ─ ─ ─ ─ │ │ │ │ │ │
│ ─ ─ ─ ─ ─ ─ ─ ─ │ │ │ EC: 6001215 │ │ │ │ │ │
│ EC: 0 │ │ │ │ │ │ │ │ │
└──────────┬──────────┘ │ └──────────┬──────────┘ │ └──────────┬──────────┘ └─────────────────────┘
┌──────────┴──────────┐┌──────────┴──────────┐ ┌──────────┴──────────┐ ┌──────────┴──────────┐┌──────────┴──────────┐
│ READ_PARQUET ││ HASH_JOIN │ │ PROJECTION │ │ DUMMY_SCAN ││ HASH_JOIN │
│ ─ ─ ─ ─ ─ ─ ─ ─ ││ ─ ─ ─ ─ ─ ─ ─ ─ │ │ ─ ─ ─ ─ ─ ─ ─ ─ │ │ ││ ─ ─ ─ ─ ─ ─ ─ ─ │
│ n_nationkey ││ INNER │ │ l_orderkey │ │ ││ INNER │
│ ─ ─ ─ ─ ─ ─ ─ ─ ││s_suppkey = l_suppkey│ │ l_suppkey │ │ ││ l_orderkey = │
│Filters: n_name=SAUDI││ ─ ─ ─ ─ ─ ─ ─ ─ ├───────────┐ │ │ │ ││ l_orderkey ├───────────┐
│ ARABIA AND n_name IS││ Build Min: 1 │ │ │ │ │ ││ l_suppkey != │ │
│ NOT NULL ││ Build Max: 10000 │ │ │ │ │ ││ l_suppkey │ │
│ ─ ─ ─ ─ ─ ─ ─ ─ ││ ─ ─ ─ ─ ─ ─ ─ ─ │ │ │ │ │ ││ ─ ─ ─ ─ ─ ─ ─ ─ │ │
│ EC: 5 ││ EC: 0 │ │ │ │ │ ││ EC: 1200243 │ │
└─────────────────────┘└──────────┬──────────┘ │ └──────────┬──────────┘ └─────────────────────┘└──────────┬──────────┘ │
┌──────────┴──────────┐┌──────────┴──────────┐ ┌──────────┴──────────┐ ┌──────────┴──────────┐┌──────────┴──────────┐
│ READ_PARQUET ││ HASH_JOIN │ │ HASH_JOIN │ │ FILTER ││ DELIM_SCAN │
│ ─ ─ ─ ─ ─ ─ ─ ─ ││ ─ ─ ─ ─ ─ ─ ─ ─ │ │ ─ ─ ─ ─ ─ ─ ─ ─ │ │ ─ ─ ─ ─ ─ ─ ─ ─ ││ │
│ s_suppkey ││ INNER │ │ INNER │ │ (l_receiptdate > ││ │
│ s_nationkey ││ l_orderkey = │ │ l_orderkey = │ │ l_commitdate) ││ │
│ s_name ││ o_orderkey ├───────────┐ │ l_orderkey ├───────────┐ │ ─ ─ ─ ─ ─ ─ ─ ─ ││ │
│ ─ ─ ─ ─ ─ ─ ─ ─ ││ ─ ─ ─ ─ ─ ─ ─ ─ │ │ │ l_suppkey != │ │ │ EC: 6001215 ││ │
│ EC: 10000 ││ EC: 0 │ │ │ l_suppkey │ │ │ ││ │
│ ││ │ │ │ ─ ─ ─ ─ ─ ─ ─ ─ │ │ │ ││ │
│ ││ │ │ │ EC: 6001215 │ │ │ ││ │
└─────────────────────┘└──────────┬──────────┘ │ └──────────┬──────────┘ │ └──────────┬──────────┘└─────────────────────┘
┌──────────┴──────────┐┌──────────┴──────────┐┌──────────┴──────────┐┌──────────┴──────────┐ ┌──────────┴──────────┐
│ FILTER ││ READ_PARQUET ││ READ_PARQUET ││ DELIM_SCAN │ │ READ_PARQUET │
│ ─ ─ ─ ─ ─ ─ ─ ─ ││ ─ ─ ─ ─ ─ ─ ─ ─ ││ ─ ─ ─ ─ ─ ─ ─ ─ ││ │ │ ─ ─ ─ ─ ─ ─ ─ ─ │
│ (l_receiptdate > ││ o_orderkey ││ l_orderkey ││ │ │ l_orderkey │
│ l_commitdate) ││ ─ ─ ─ ─ ─ ─ ─ ─ ││ l_suppkey ││ │ │ l_suppkey │
│ ─ ─ ─ ─ ─ ─ ─ ─ ││Filters: o_orderstatu││ ─ ─ ─ ─ ─ ─ ─ ─ ││ │ │ l_receiptdate │
│ EC: 1200243 ││s=F AND o_orderstatus││ EC: 6001215 ││ │ │ l_commitdate │
│ ││ IS NOT NULL ││ ││ │ │ ─ ─ ─ ─ ─ ─ ─ ─ │
│ ││ ─ ─ ─ ─ ─ ─ ─ ─ ││ ││ │ │ EC: 6001215 │
│ ││ EC: 300000 ││ ││ │ │ │
└──────────┬──────────┘└─────────────────────┘└─────────────────────┘└─────────────────────┘ └─────────────────────┘
┌──────────┴──────────┐
│ READ_PARQUET │
│ ─ ─ ─ ─ ─ ─ ─ ─ │
│ l_suppkey │
│ l_orderkey │
│ l_receiptdate │
│ l_commitdate │
│ ─ ─ ─ ─ ─ ─ ─ ─ │
│ EC: 1200243 │
└─────────────────────┘
To Reproduce
TPC-H Q21
The query is exact the same with the benchmark one with all tables are parquet files instead of native storage.
Minimal Reproducible
Since the cause of the wrong join order is due to the 0 cardinality estimation of joining the two largest table, here is a simpler example to reproduce the 0 EC of join using the spark-store.parquet under the parquet-testing dir.
Basically, I found that as long as there is a filter that compares two columns in the same relation (store.s_rec_start_date <= store.s_rec_end_date in the simple example and l1.l_receiptdate > l1.l_commitdate in tpch q21), the join EC will be 0. This won't happen if both tables are native tables through.
create table test (id INTEGER, date DATE);
insert into test VALUES (1, '1997-03-13'),(2, '1997-03-03'),(3, '1997-03-03');
-- q1
explain select s_store_id from read_parquet('data/parquet-testing/spark-store.parquet') store, test where store.s_store_sk = test.id and store.s_rec_start_date <= store.s_rec_end_date;
-- q2
explain select s_store_id from read_parquet('data/parquet-testing/spark-store.parquet') store, test where store.s_store_sk = test.id and store.s_rec_start_date <= '2030-01-01';
-- EXPLAIN q1
┌─────────────────────────────┐
│┌───────────────────────────┐│
││ Physical Plan ││
│└───────────────────────────┘│
└─────────────────────────────┘
┌───────────────────────────┐
│ PROJECTION │
│ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ │
│ s_store_id │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│ HASH_JOIN │
│ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ │
│ INNER │
│ id = s_store_sk │
│ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ├──────────────┐
│ Build Min: 1 │ │
│ Build Max: 3 │ │
│ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ │ │
│ EC: 0 │ │
└─────────────┬─────────────┘ │
┌─────────────┴─────────────┐┌─────────────┴─────────────┐
│ SEQ_SCAN ││ FILTER │
│ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ││ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ │
│ test ││ (s_rec_start_date <= │
│ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ││ s_rec_end_date) │
│ id ││ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ │
│ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ││ EC: 2 │
│ EC: 3 ││ │
└───────────────────────────┘└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│ READ_PARQUET │
│ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ │
│ s_store_sk │
│ s_rec_start_date │
│ s_rec_end_date │
│ s_store_id │
│ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ │
│ Filters: s_store_sk<=3 AND│
│ s_store_sk IS NOT NULL │
│ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ │
│ EC: 2 │
└───────────────────────────┘
-- EXPLAIN q2
┌─────────────────────────────┐
│┌───────────────────────────┐│
││ Physical Plan ││
│└───────────────────────────┘│
└─────────────────────────────┘
┌───────────────────────────┐
│ PROJECTION │
│ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ │
│ s_store_id │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│ HASH_JOIN │
│ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ │
│ INNER │
│ id = s_store_sk │
│ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ├──────────────┐
│ Build Min: 1 │ │
│ Build Max: 3 │ │
│ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ │ │
│ EC: 2 │ │
└─────────────┬─────────────┘ │
┌─────────────┴─────────────┐┌─────────────┴─────────────┐
│ SEQ_SCAN ││ READ_PARQUET │
│ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ││ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ │
│ test ││ s_store_sk │
│ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ││ s_store_id │
│ id ││ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ │
│ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ││ Filters: s_store_sk<=3 AND│
│ EC: 3 ││ s_store_sk IS NOT NULL │
│ ││ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ │
│ ││ EC: 2 │
└───────────────────────────┘└───────────────────────────┘
As shown above, the only difference between q1 and q2 is the predicate on the parquet file. q2 with single-column predicate results in reasonable EC, but q1 with two-column has 0 EC. Similarly, if I remove or change the predicate l1.l_receiptdate > l1.l_commitdate to another filter like l1.l_receiptdate > '1995-01-01', the EC will be non-zero and the join order will be reasonable.
I think the reason is due to the filter with two columns comparison are considered as join predicate in this case instead of predicate on base relations. I will put more details later.
OS:
tested both on macos m1, ubuntu x86
DuckDB Version:
latest main: e0c4d9c
DuckDB Client:
latest main: e0c4d9c
Full Name:
Xiaoying Wang
Affiliation:
Simon Fraser University
What is the latest build you tested with? If possible, we recommend testing with the latest nightly build.
I have tested with a source build
Did you include all relevant data sets for reproducing the issue?
Yes
Did you include all code required to reproduce the issue?
- Yes, I have
Did you include all relevant configuration (e.g., CPU architecture, Python version, Linux distribution) to reproduce the issue?
- Yes, I have