Optimizer fails to push aggregate functions through CROSS JOIN, causing full table scans instead of LIMITED SCAN on PRIMARY KEY
- Dominant language
- Go
- Stars
- 40.5k
- Forks
- 6.2k
- PR merge metrics
- PR metrics pending
Description
## Bug Report
Hi, TiDB developers, thanks for reading my report. I found a missed optimization in the optimizer.
When computing aggregate functions (`MAX/MIN`) from multiple tables in a `CROSS JOIN`, the optimizer materializes the full cartesian product before aggregation, losing the `LIMITED SCAN` optimization available on **`PRIMARY KEY`** indexes.
### 1. Minimal reproduce step (Required)
```sql
CREATE TEMPORARY TABLE digits (d INT);
INSERT INTO digits VALUES (0),(1),(2),(3),(4),(5),(6),(7),(8),(9);
CREATE TABLE t0(c0 INT PRIMARY KEY);
INSERT INTO t0
SELECT d1.d + d2.d*10 + d3.d*100 + d4.d*1000 + d5.d*10000 + d6.d*100000 AS num
FROM digits d1, digits d2, digits d3, digits d4, digits d5, digits d6
WHERE d1.d + d2.d*10 + d3.d*100 + d4.d*1000 + d5.d*10000 + d6.d*100000 <= 1000000;
CREATE TABLE t1 LIKE t0;
INSERT INTO t1 SELECT * FROM t0 LIMIT 1000;
-- positive case
SELECT MAX(t0.c0) FROM t0; -- 0.00 sec
EXPLAIN SELECT MAX(t0.c0) FROM t0;
+------------------------------+---------+-----------+---------------+---------------------------------+
| id | estRows | task | access object | operator info |
+------------------------------+---------+-----------+---------------+---------------------------------+
| StreamAgg_9 | 1.00 | root | | funcs:max(test.t0.c0)->Column#2 |
| └─Limit_13 | 1.00 | root | | offset:0, count:1 |
| └─TableReader_20 | 1.00 | root | | data:Limit_19 |
| └─Limit_19 | 1.00 | cop[tikv] | | offset:0, count:1 |
| └─TableFullScan_18 | 1.00 | cop[tikv] | table:t0 | keep order:true, desc |
+------------------------------+---------+-----------+---------------+---------------------------------+
-- negative case
SELECT MAX(t0.c0), MAX(t1.c0) FROM t0, t1; -- 24.37 sec
EXPLAIN SELECT MAX(t0.c0), MAX(t1.c0) FROM t0, t1;
+---------------------------------+----------------+-----------+---------------+------------------------------------------------------------------+
| id | estRows | task | access object | operator info |
+---------------------------------+----------------+-----------+---------------+------------------------------------------------------------------+
| HashAgg_9 | 1.00 | root | | funcs:max(test.t0.c0)->Column#3, funcs:max(test.t1.c0)->Column#4 |
| └─Projection_11 | 10000000000.00 | root | | test.t0.c0, test.t1.c0 |
| └─HashJoin_13 | 10000000000.00 | root | | CARTESIAN inner join |
| ├─TableReader_15(Build) | 10000.00 | root | | data:TableFullScan_14 |
| │ └─TableFullScan_14 | 10000.00 | cop[tikv] | table:t1 | keep order:false, stats:pseudo |
| └─TableReader_17(Probe) | 1000000.00 | root | | data:TableFullScan_16 |
| └─TableFullScan_16 | 1000000.00 | cop[tikv] | table:t0 | keep order:false |
+---------------------------------+----------------+-----------+---------------+------------------------------------------------------------------+
```
### 2. What did you expect to see? (Required)
This is a common optimization pattern. DBMSs, such as MySQL, MariaDB, and Percona, can handle this by pushing aggregates through cross joins. We expect TiDB to run such a query quickly as follows.
### 3. What did you see instead (Required)
```sql
SELECT MAX(t0.c0), MAX(t1.c0) FROM t0, t1; -- 24.37 sec
EXPLAIN SELECT MAX(t0.c0), MAX(t1.c0) FROM t0, t1;
+---------------------------------+----------------+-----------+---------------+------------------------------------------------------------------+
| id | estRows | task | access object | operator info |
+---------------------------------+----------------+-----------+---------------+------------------------------------------------------------------+
| HashAgg_9 | 1.00 | root | | funcs:max(test.t0.c0)->Column#3, funcs:max(test.t1.c0)->Column#4 |
| └─Projection_11 | 10000000000.00 | root | | test.t0.c0, test.t1.c0 |
| └─HashJoin_13 | 10000000000.00 | root | | CARTESIAN inner join |
| ├─TableReader_15(Build) | 10000.00 | root | | data:TableFullScan_14 |
| │ └─TableFullScan_14 | 10000.00 | cop[tikv] | table:t1 | keep order:false, stats:pseudo |
| └─TableReader_17(Probe) | 1000000.00 | root | | data:TableFullScan_16 |
| └─TableFullScan_16 | 1000000.00 | cop[tikv] | table:t0 | keep order:false |
+---------------------------------+----------------+-----------+---------------+------------------------------------------------------------------+
```
### 4. What is your TiDB version? (Required)
I tested such a case in TiDB-v8.5.6. Maybe it is an issue that exists in all the versions.
Contributor guide
Assessment
This issue has not been assessed yet.