pingcap / pingcap/tidb

Index Scan Incorrectly Substituted for `ORDER BY (-c0) DESC`, Misplacing `NULL` Rows Relative to Explicit Sort

Open
#69,480 3 comments 0 reactions 0 assignees View on GitHub
affects-7.5 affects-8.1 affects-8.5 contribution severity/critical sig/planner type/bug
Dominant language
Go
Stars
40.5k
Forks
6.2k
PR merge metrics
PR metrics pending

Description

## Bug Report

Please answer these questions before submitting your issue. Thanks!

### 1. Minimal Reproduce Step (Required)

```sql
DROP DATABASE IF EXISTS test_repro;
CREATE DATABASE test_repro;
USE test_repro;

CREATE TABLE source (
vp_rowid BIGINT NOT NULL AUTO_INCREMENT PRIMARY KEY,
c0 DOUBLE UNSIGNED ZEROFILL DEFAULT NULL
) ENGINE=InnoDB;

INSERT INTO source (c0) VALUES
(NULL),
(0.30446792022164715),
(0.7041492922748734),
(0.8527053518765303);

ALTER TABLE source
ADD KEY i0 (c0),
ADD UNIQUE KEY i2 (c0),
ADD KEY i5 (c0),
ADD KEY i6 (c0),
ADD KEY i7 (c0),
ADD KEY i1 (c0);

CREATE TABLE l (vp_rowid BIGINT NOT NULL PRIMARY KEY, c0 DOUBLE UNSIGNED ZEROFILL DEFAULT NULL) ENGINE=InnoDB;
CREATE TABLE r (vp_rowid BIGINT NOT NULL PRIMARY KEY) ENGINE=InnoDB;

INSERT INTO l (vp_rowid, c0) SELECT vp_rowid, c0 FROM source;
INSERT INTO r (vp_rowid) SELECT vp_rowid FROM source;

-- Single‑table query (index scan, no explicit Sort)
SELECT vp_rowid FROM source
WHERE '2018-04-13'
ORDER BY (-c0) DESC, vp_rowid;

-- Join/rewrite query (explicit Sort at root)
SELECT vp_rowid FROM (
SELECT l.vp_rowid AS vp_rowid, l.c0 AS c0
FROM l JOIN LATERAL (
SELECT * FROM r rr WHERE rr.vp_rowid = l.vp_rowid
) r ON TRUE
) source2
WHERE '2018-04-13'
ORDER BY (-c0) DESC, vp_rowid;
```

### 2. What Did You Expect to See? (Required)

Both queries should return the rows in identical order. The ordering `ORDER BY (-c0) DESC, vp_rowid` implies:

- For non‑`NULL` `c0`, `-c0` is negative; descending order means larger (less negative) values first, so smaller `c0` values appear earlier.
- `NULL` values result in `-NULL = NULL`. In SQL standard (and MySQL default), `ORDER BY ... DESC` places `NULL` values first or last depending on the sort specification. Here, `DESC` typically puts `NULL` first. The presence of `vp_rowid` as a secondary key does not alter the grouping of `NULL`s.

The join query performs an explicit `Sort` at the root layer and produces order: `2, 3, 4, 1` (`NULL` last). The single‑table query should also produce `2, 3, 4, 1`, or at least a consistent placement of `NULL`. `NULL`s should be placed consistently.

### 3. What Did You See Instead? (Required)

- Single‑table query: returns rows in order `1, 2, 3, 4` (`NULL` first).
- Join/rewrite query: returns rows in order `2, 3, 4, 1` (`NULL` last).

The placement of the `NULL` row differs, violating the expected deterministic result.

### 4. What Is Your TiDB Version? (Required)

Version: TiDB‑v9.0.0

### 5. Execution Plan Differences

**Single‑table query (wrong)** — `Sort` eliminated, replaced by an ordered index scan:

| id | task | operator | info |
|----|------|----------|------|
| Projection | root | | `source.vp_rowid` |
| └─IndexReader | root | | `index:IndexFullScan` |
|   └─IndexFullScan | cop[tikv] | index:`i0(c0)` | `keep order:true` |

The optimizer replaces `ORDER BY (-c0) DESC, vp_rowid` with a scan of index `i0(c0)` that returns rows in ascending order of `c0`, relying on the monotonicity of `-c0` to derive the desired descending order.

**Join query (correct)** — Explicit `Sort` at root:

| id | task | operator | info |
|----|------|----------|------|
| Projection | root | | `l.vp_rowid` |
| └─Sort | root | | `Column#7:desc, l.vp_rowid` |
|   └─Projection | root | | `unaryminus(l.c0)→Column#7` |
|     └─IndexJoin | root | | inner join `l↔r` on `vp_rowid` |

Here the expression `-c0` is computed and stored in `Column#7`, and a true `Sort` is performed.

### 6. Root Cause

The optimizer attempts to eliminate the `Sort` by using an ordered index scan. For `ORDER BY (-c0) DESC`, it recognizes that `-c0` is a monotonic decreasing function of `c0`. It incorrectly concludes that scanning index `i0(c0)` in ascending order (which is the default `IndexFullScan` with `keep order:true`) is equivalent to sorting by `(-c0) DESC`.

However, this equivalence breaks for `NULL` values:

- `-NULL = NULL`, which is not order‑comparable with other numeric values.
- The index `i0(c0)` stores `NULL` as a distinct smallest value. When scanning the index in ascending order, `NULL` appears first.
- The expected behaviour of `ORDER BY (-c0) DESC` (as performed by the explicit `Sort`) places `NULL` last, because `NULL` is treated as larger than any non‑`NULL` value when `DESC` is specified (or, depending on implementation, last by default).

Because the optimizer substitutes the index scan for the `Sort` without correctly accounting for the special `NULL` ordering behaviour of the expression `-c0`, the result order becomes inconsistent with the explicit `Sort` plan, leading to different results between the single‑table and join queries.

Contributor guide

Open the contributing guide

Research direction

Start by tracing the optimizer rule that replaces Sort with an IndexFullScan using keep order:true for ORDER BY (-c0) DESC, and compare it with the explicit Sort plan shown in the report. Reproduce both SQL queries with the supplied schema and verify that index substitution preserves the explicit sort's NULL placement, with identical row order in both plans.

Written by the indexing model from the issue text.

Assessment

Tech stack
go, sql
Domain
databases
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
48/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.