pingcap / pingcap/tidb

planner: Index Join cardinality estimation Issue because of filter re-estimates conditions already covered by range

Open
#64,649 0 comments 0 reactions 1 assignee Claimed by @qw4990 View on GitHub
epic/cardinality-estimation report/customer sig/planner type/enhancement
Dominant language
Go
Stars
40.5k
Forks
6.2k
PR merge metrics
PR metrics pending

Description

## Enhancement
Executed a LEFT JOIN query where the join condition and an additional filter on the inner table use a composite primary key (USER_ID, P_DATE):

```sql
-- Example SQL (anonymized for illustration)
EXPLAIN ANALYZE FORMAT='VERBOSE'
SELECT r.user_id
FROM APP.T_SRC_WORK r
LEFT JOIN APP.T_PART_FACT a
ON a.USER_ID = r.USER_ID
AND a.P_DATE = '20251118'
WHERE r.lat > '10.39406179877532'
AND r.lat < '10.549191119054242'
AND r.lon > '-67.06874897653084'
AND r.lon < '-66.73915913278084';
```

**Table schema (simplified):**
```sql
-- T_PART_FACT has a composite primary key
PRIMARY KEY (USER_ID, P_DATE)
```

For the Index Join inner side (table T_PART_FACT), the optimizer should recognize that:
1. TableRangeScan uses the range [user_id, '20251118'], which already includes the P_DATE equality
2. Selection should NOT re-estimate selectivity of P_DATE = '20251118' because it is guaranteed by the range
3. Estimated rows after Selection should be close to the real number (~1.2M)

Severe cardinality estimation error with **157x underestimation**:
```
+------------------------+----------+------------+-------+------------+-------------------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-------+----+
|id |estRows |estCost |actRows|task |access object |execution info |operator info |memory |disk|
+------------------------+----------+------------+-------+------------+-------------------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-------+----+
|IndexJoin_13 |1207740.07|627009980.26|1200239|root | |time:20.9s, loops:1174, RU:10942.104975, inner:{total:1m36.2s, concurrency:5, task:1170, construct:431.4ms, fetch:1m35.5s, build:292.6ms}, probe:220.9ms |left outer join, inner:TableReader_12, outer key:APP.T_SRC_WORK.user_id, inner key:APP.T_PART_FACT.user_id, equal cond:eq(APP.T_SRC_WORK.user_id, APP.T_PART_FACT.user_id) |1.63 MB|N/A |
│├─TableReader_33(Build) |1200237.92|26855188.30 |1200239|root | |time:154ms, loops:1175, cop_task: {num: 20, max: 0s, min: 0s, avg: 0s, p95: 0s, copr_cache_hit_ratio: 0.00} |data:ExchangeSender_32 |6.03 MB|N/A |
││ └─ExchangeSender_32 |1200237.92|107089200.80|1200239|mpp[tiflash]| |tiflash_task:{time:294.7ms, loops:19, threads:2} |ExchangeType:PassThrough |N/A |N/A |
││ └─Selection_31 |1200237.92|107089200.80|1200239|mpp[tiflash]| |tiflash_task:{time:72.7ms, loops:19, threads:2} |gt(APP.T_SRC_WORK.lat, 10.39406), gt(APP.T_SRC_WORK.lon, -67.06874), lt(APP.T_SRC_WORK.lat, 10.54919), lt(APP.T_SRC_WORK.lon, -66.73915) |N/A |N/A |
││ └─TableFullScan_30|1200239.00|95566906.40 |1200239|mpp[tiflash]|table:r |tiflash_task:{time:57.7ms, loops:19, threads:2} |pushed down filter:empty, keep order:false |N/A |N/A |
│└─TableReader_12(Probe) |7610.76 |28.84 |1200130|root |partition:P20251118|time:1m34.2s, loops:2344, cop_task:{num:3511, max:561.5ms, min:1ms, avg:26.8ms, p95:44.3ms, ...} |data:Selection_11 |N/A |N/A |
└─Selection_11 |7610.76 |432.17 |1200130|cop[tikv] | |tikv_task:{...} |eq(APP.T_PART_FACT.p_date, 2025-11-18 00:00:00.000000) |N/A |N/A |
└─TableRangeScan_10 |1200237.92|382.27 |1200130|cop[tikv] |table:a |tikv_task:{...} |range: decided by [eq(APP.T_PART_FACT.user_id, APP.T_SRC_WORK.user_id), eq(APP.T_PART_FACT.p_date, 2025-11-18 00:00:00.000000)], keep order:false |N/A |N/A |
+------------------------+----------+------------+-------+------------+-------------------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-------+----+
```

Simplified version:
```
+------------------------+----------+------------+-------+------------+-------------------+
|id |estRows |estCost |actRows|task |access object |
+------------------------+----------+------------+-------+------------+-------------------+
|IndexJoin_13 |1207740.07|627009980.26|1200239|root | |
|├─TableReader_33(Build) |1200237.92|26855188.30 |1200239|root | |
|│ └─TableFullScan_30 |1200239.00|95566906.40 |1200239|mpp[tiflash]|table:r |
|└─TableReader_12(Probe) |7610.76 |28.84 |1200130|root |partition:P20251118| ← Issue
| └─Selection_11 |7610.76 |432.17 |1200130|cop[tikv] | | ← Est: 7,610
| └─TableRangeScan_10 |1200237.92|382.27 |1200130|cop[tikv] |table:a | ← Actual: 1,200,130
+------------------------+----------+------------+-------+------------+-------------------+
```

**Operator details:**

```
TableRangeScan_10:
range: [
eq(APP.T_PART_FACT.user_id, APP.T_SRC_WORK.user_id),
eq(APP.T_PART_FACT.p_date, '2025-11-18')
]
↑ The range already enforces p_date

Selection_11:
eq(APP.T_PART_FACT.p_date, '2025-11-18')
↑ Re-applies the same condition and re-estimates selectivity
```

**Key observation:**
- `TableRangeScan_10` scanned 1,200,130 rows (correct, based on the range)
- `Selection_11` estimated only 7,610 rows (157x error)
- The condition `DATA_DATE = '20251118'` appears in **both** the range and the filter

### Root Cause Analysis

The issue occurs in the Index Join inner side estimation logic:

1. **Range construction** (`index_join_path.go`):
- The optimizer identifies p_date = '20251118' as an access condition
- Builds a composite range [user_id, '20251118']
- Correctly covers the date predicate

2. **Filter estimation** (`exhaust_physical_plans.go:constructDS2IndexScanTask`):
- The optimizer still keeps the same date predicate in filter conditions
- Calls Selectivity() on it again
- Treats the predicate as independent and un-applied
- Assumes uniform distribution (e.g., 1 / #dates)
- Produces 1200237.92 × (1/157) ≈ 7610.76

### Expected Behavior

The optimizer should:
1. Recognize when filter conditions are already guaranteed by the index range
2. Skip selectivity re-estimation for range-covered conditions

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.