pingcap / pingcap/tidb

Optimizer fails to push aggregate functions through CROSS JOIN, causing full table scans instead of LIMITED SCAN on PRIMARY KEY

Open
#69,164 2 comments 0 reactions 0 assignees View on GitHub
contribution severity/moderate sig/planner type/bug
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.
Image

### 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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.