Planner picks range scan over small IN-list lookup in JOIN + range query

# Planner picks range scan over small IN-list lookup in JOIN + range query

> ⚠️ **Disclaimer**: This report was drafted mainly by an AI assistant
> (Claude), with human oversight. The reproducer script and timings
> were produced and verified by the AI; the plan-diagnosis section is
> inference from timing behaviour rather than observed EXPLAIN output.
> Treat the wording and any speculative claims with appropriate
> scepticism, and please flag anything that looks off — I'd rather
> fix the report than have a maintainer chase a bad lead.

## Summary

A `SELECT DISTINCT p.id FROM parent p JOIN child c ON c.parent_id = p.id WHERE p.id IN (<13 ids>) AND c.value > 0` is ~100x slower than the equivalent `SELECT DISTINCT parent_id FROM child WHERE parent_id IN () AND value > 0` on identical data (warm: ~2.8s vs ~0.03s on 5k parent rows / 50k child rows; ~10s vs ~35ms on a production-shape dataset of ~38k / ~195k rows). The planner appears to drive the join from the large `child` table via the secondary index on `value` rather than from the 13 primary-key hits in `parent` and probing `child` via the `parent_id` index. An `EXISTS` rewrite is as fast as the subquery, confirming the issue is in the join plan's driving-side choice, not in any inherent cost of the join.

## Environment

- `dolt version 1.84.0` (client warns the latest is 1.86.2; I have not yet retested there — happy to do so if useful)
- Linux (Ubuntu 25.10, kernel 6.17.0 x86_64)
- MySQL-compatible mode, accessed via `mysql --protocol=TCP` (MariaDB 11.8 client); also reproduced via a MySQL driver (`mysql2`) against the same server
- Fresh Dolt database initialised with `dolt init`; single local `dolt sql-server`; no replication or clustering

## Schema

Two tables in a classic one-to-many relationship. The names `parent` and `child` are just placeholders — what matters is the shape.

```sql
CREATE TABLE parent (
id bigint NOT NULL AUTO_INCREMENT,
PRIMARY KEY (id)
);

CREATE TABLE child (
id bigint NOT NULL AUTO_INCREMENT,
parent_id bigint NOT NULL,
value int DEFAULT NULL,
PRIMARY KEY (id),
KEY index_child_on_parent_id (parent_id),
KEY index_child_on_value (value)
);
```

No composite index on `(parent_id, value)`. Adding such a composite does not fix the planner choice on the original query (it just masks it).

## Data

5,000 `parent` rows and 50,000 `child` rows (~10 children per parent), with ~90% of child rows having `value > 0` and the rest having `value = 0`. `parent_id` is sparse (drawn from a larger id space). Data is generated deterministically (`SEED = 20260423`) by the generator script below. The effect grows with table size: on a ~38k / ~195k dataset the ratio widens to ~300x.

## Reproducer

Three files are shown below in full:

1. `generate_data.py` — deterministic data generator (Python 3, stdlib only; writes `schema.sql`, `data.sql`, and `ids.txt` beside itself).
2. `repro.sh` — creates a fresh Dolt DB in `./dolt-db/`, starts `dolt sql-server` on port 3307, loads the data, runs the three queries cold + warm with `ANALYZE TABLE` beforehand, and tears the server down on exit.
3. The three SQL queries (also reproduced inline below).

To run:

```bash
mkdir dolt-repro && cd dolt-repro
# paste generate_data.py and repro.sh from below into this directory
chmod +x repro.sh
./repro.sh
```

### `generate_data.py`

```python
#!/usr/bin/env python3
"""
Deterministic synthetic data generator for the Dolt planner-regression
reproducer.

Writes schema.sql, data.sql, and ids.txt beside itself.

Data shape (tunable at the top of this file):
- N_PARENT parent rows
- N_CHILD child rows (~10 per parent on average)
- ~90% of child rows have value > 0; the rest have value = 0
- parent_ids are sparse (not 1..N_PARENT)
"""
import os
import random
import sys

N_PARENT = 5000
N_CHILD = 50000
ZERO_VALUE_FRACTION = 0.10 # ~10% of rows have value = 0
SEED = 20260423

HERE = os.path.dirname(os.path.abspath(__file__))
SCHEMA_PATH = os.path.join(HERE, "schema.sql")
DATA_PATH = os.path.join(HERE, "data.sql")

BATCH = 1000

def main():
rng = random.Random(SEED)

# Sparse parent ids: pick N_PARENT distinct ids from a larger space.
id_space = N_PARENT * 8
parent_ids = rng.sample(range(1, id_space + 1), N_PARENT)
parent_ids.sort()

# Assign a child count per parent. Mean ~10, min 1.
per_parent = []
remaining = N_CHILD
for i, _ in enumerate(parent_ids):
left = len(parent_ids) - i
mean = max(1.0, remaining / max(1, left))
k = max(1, int(rng.gauss(mean, max(1.0, mean / 2))))
k = min(k, 25)
k = min(k, remaining - (left - 1))
k = max(1, k)
per_parent.append(k)
remaining -= k
if remaining > 0:
per_parent[-1] += remaining

assert sum(per_parent) == N_CHILD
assert len(per_parent) == N_PARENT

with open(SCHEMA_PATH, "w") as f:
f.write(SCHEMA)

with open(DATA_PATH, "w") as f:
f.write("-- Generated by generate_data.py. Do not edit by hand.\n")
f.write("SET autocommit = 1;\n\n")

f.write("-- parent\n")
for i in range(0, len(parent_ids), BATCH):
chunk = parent_ids[i:i + BATCH]
values = ",".join(f"({pid})" for pid in chunk)
f.write(f"INSERT INTO parent (id) VALUES {values};\n")

f.write("\n-- child\n")
child_id = 1
buf = []
for pid, n in zip(parent_ids, per_parent):
for _ in range(n):
value = 0 if rng.random() < ZERO_VALUE_FRACTION else rng.randint(1, 20000)
buf.append(f"({child_id},{pid},{value})")
child_id += 1
if len(buf) >= BATCH:
f.write(
"INSERT INTO child (id, parent_id, value) "
"VALUES " + ",".join(buf) + ";\n"
)
buf.clear()
if buf:
f.write(
"INSERT INTO child (id, parent_id, value) "
"VALUES " + ",".join(buf) + ";\n"
)

# Emit a representative IN-list of 13 parent ids for the queries.
sample_ids = rng.sample(parent_ids, 13)
sample_ids.sort()
with open(os.path.join(HERE, "ids.txt"), "w") as f:
f.write(",".join(str(i) for i in sample_ids) + "\n")

print(f"wrote {SCHEMA_PATH}")
print(f"wrote {DATA_PATH}")
print(f"parent={N_PARENT} child={N_CHILD} "
f"zero_values~{ZERO_VALUE_FRACTION:.0%}")
print(f"sample IN-list (13): {sample_ids}")

SCHEMA = """DROP TABLE IF EXISTS child;
DROP TABLE IF EXISTS parent;

CREATE TABLE parent (
id bigint NOT NULL AUTO_INCREMENT,
PRIMARY KEY (id)
);

CREATE TABLE child (
id bigint NOT NULL AUTO_INCREMENT,
parent_id bigint NOT NULL,
value int DEFAULT NULL,
PRIMARY KEY (id),
KEY index_child_on_parent_id (parent_id),
KEY index_child_on_value (value)
);
"""

if __name__ == "__main__":
try:
main()
except Exception as e:
print(f"error: {e}", file=sys.stderr)
sys.exit(1)
```

### `repro.sh`

```bash
#!/usr/bin/env bash
# Reproducer for a Dolt query planner regression.
# Creates a fresh Dolt database in ./dolt-db/, loads synthetic data,
# and times the two queries. Background server is torn down on exit.
# Requires: dolt, python3, mysql client. Port 3307 must be free.

set -euo pipefail

HERE="$(cd "$(dirname "$0")" && pwd)"
DB_DIR="$HERE/dolt-db"
LOG_DIR="$HERE/logs"
DOLT_PORT="${DOLT_PORT:-3307}"

mkdir -p "$LOG_DIR"

cleanup() {
if [[ -n "${SERVER_PID:-}" ]] && kill -0 "$SERVER_PID" 2>/dev/null; then
kill -TERM "$SERVER_PID" 2>/dev/null || true
for _ in 1 2 3 4 5; do
kill -0 "$SERVER_PID" 2>/dev/null || return 0
sleep 0.3
done
kill -KILL "$SERVER_PID" 2>/dev/null || true
fi
}
trap cleanup EXIT INT TERM

if [[ ! -f "$HERE/schema.sql" || ! -f "$HERE/data.sql" || ! -f "$HERE/ids.txt" ]]; then
python3 "$HERE/generate_data.py"
fi
IDS="$(cat "$HERE/ids.txt")"

rm -rf "$DB_DIR" && mkdir -p "$DB_DIR"
(cd "$DB_DIR" && dolt init --name "repro" --email "repro@example.com" >/dev/null)

cd "$DB_DIR"
dolt sql-server --host 127.0.0.1 --port "$DOLT_PORT" \
> "$LOG_DIR/server.log" 2>&1 &
SERVER_PID=$!
cd "$HERE"

for _ in $(seq 1 60); do
mysql --protocol=TCP -h 127.0.0.1 -P "$DOLT_PORT" -u root \
-e "SELECT 1" >/dev/null 2>&1 && break
sleep 0.5
done

mysql_q() {
mysql --protocol=TCP -h 127.0.0.1 -P "$DOLT_PORT" -u root "$@" \
2> >(grep -v 'ssl-verify-server-cert' >&2)
}

DB_ACTUAL="$(mysql_q -N -B -e "SHOW DATABASES;" \
| grep -v -E '^(information_schema|mysql|performance_schema|dolt_cluster)$' \
| head -n 1)"

mysql_q "$DB_ACTUAL" < "$HERE/schema.sql"
mysql_q "$DB_ACTUAL" < "$HERE/data.sql"
mysql_q "$DB_ACTUAL" -e "ANALYZE TABLE parent, child;" || true

SLOW_SQL="SELECT DISTINCT p.id FROM parent p
JOIN child c ON c.parent_id = p.id
WHERE p.id IN ($IDS) AND c.value > 0;"

FAST_SQL="SELECT DISTINCT parent_id FROM child
WHERE parent_id IN ($IDS) AND value > 0;"

EXISTS_SQL="SELECT DISTINCT p.id FROM parent p
WHERE p.id IN ($IDS)
AND EXISTS (SELECT 1 FROM child c WHERE c.parent_id = p.id AND c.value > 0);"

run_timed() {
local label="$1" sql="$2"
local t_start t_end elapsed
t_start=$(date +%s.%N)
mysql_q "$DB_ACTUAL" -e "$sql" > "$LOG_DIR/${label}.out"
t_end=$(date +%s.%N)
elapsed=$(awk "BEGIN {printf \"%.3f\", $t_end - $t_start}")
printf "%-22s %8.3f s\n" "$label" "$elapsed"
echo "$elapsed" > "$LOG_DIR/${label}.elapsed"
}

echo && echo "=== cold ==="
run_timed "slow_join" "$SLOW_SQL"
run_timed "fast_subquery" "$FAST_SQL"
run_timed "exists_rewrite" "$EXISTS_SQL"

echo && echo "=== warm ==="
run_timed "slow_join_warm" "$SLOW_SQL"
run_timed "fast_subquery_warm" "$FAST_SQL"
run_timed "exists_rewrite_warm" "$EXISTS_SQL"

slow=$(cat "$LOG_DIR/slow_join_warm.elapsed")
fast=$(cat "$LOG_DIR/fast_subquery_warm.elapsed")
ratio=$(awk "BEGIN {if ($fast>0) printf \"%.1f\", $slow/$fast; else print \"inf\"}")
echo && echo "ratio (slow/fast, warm): ${ratio}x"
```

### The queries

The IN-list in the queries below is one possible output of the generator (13 `parent_id`s sampled from the 5000 generated). The effect holds for any 13-id subset; `repro.sh` inlines whatever `generate_data.py` wrote to `ids.txt`.

Slow query (the join):

```sql
SELECT DISTINCT p.id
FROM parent p
JOIN child c ON c.parent_id = p.id
WHERE p.id IN (190, 3099, 4089, 8533, 9669, 16565, 24393,
25122, 26197, 27316, 29768, 29819, 39221)
AND c.value > 0;
```

Fast query (the subquery — same result set):

```sql
SELECT DISTINCT parent_id
FROM child
WHERE parent_id IN (190, 3099, 4089, 8533, 9669, 16565, 24393,
25122, 26197, 27316, 29768, 29819, 39221)
AND value > 0;
```

EXISTS rewrite (also fast):

```sql
SELECT DISTINCT p.id
FROM parent p
WHERE p.id IN (190, 3099, ..., 39221)
AND EXISTS (SELECT 1 FROM child c
WHERE c.parent_id = p.id AND c.value > 0);
```

Timings observed on Dolt 1.84.0, after `ANALYZE TABLE parent, child`, averaged across three runs on the synthetic data:

| Query | Cold | Warm |
|--------------------------|---------|---------|
| slow_join (JOIN) | ~2.87s | ~2.82s |
| fast_subquery | ~0.03s | ~0.03s |
| exists_rewrite | ~0.03s | ~0.03s |

Warm ratio slow/fast: **~97x** on 5k/50k. On a larger ~38k parent / ~195k child dataset (same schema, same generation strategy, same distribution) the ratio widens to **~285x** (~10s vs ~35ms warm). The bug scales with table size, consistent with the hypothesis that the slow plan range-scans `child`.

## Expected vs. actual plan

**Expected:** drive from the IN-list on `parent.id` (13 primary-key lookups), then for each parent row probe `child` via `index_child_on_parent_id`, and apply `value > 0` as a residual filter on the ~130 matching rows. Estimated work: 13 PK lookups + ~130 index probes — should complete in low tens of ms.

**Apparent actual (inferred from timing):** drive the join from `child`, using `index_child_on_value` to scan the `value > 0` slice (~45k of 50k rows), then hash/nested-loop-join against `parent` and apply `p.id IN (...)`. That the timing scales with `|child where value>0|` rather than with `|IN-list|` is the smoking gun. The `EXISTS` rewrite proves the planner *can* choose the expected shape — it just doesn't for the semantically equivalent INNER JOIN + DISTINCT form.

### Secondary finding: `EXPLAIN` returns an empty plan

`EXPLAIN` on either query returns a single NULL-filled row rather than a plan tree:

```
mysql> EXPLAIN SELECT DISTINCT p.id
-> FROM parent p JOIN child c ON c.parent_id = p.id
-> WHERE p.id IN (190, ..., 39221) AND c.value > 0;
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------+
| 1 | SELECT | NULL | NULL | NULL | NULL | NULL | NULL | NULL | NULL | 0 | NULL |
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------+
```

This is also the case for the fast subquery. Without a plan tree it is hard to confirm the driving-side hypothesis above; `EXPLAIN FORMAT=TREE` / `EXPLAIN ANALYZE` would help diagnosis. Happy to capture additional diagnostics if there is a verbose-planner flag I have missed.

## Workaround

Rewriting to the subquery form avoids the regression:

```sql
SELECT DISTINCT parent_id
FROM child
WHERE parent_id IN (...)
AND value > 0;
```

The `EXISTS` rewrite is an equally effective workaround when the join is structurally necessary (i.e. when columns from the parent row are actually needed in the projection).

## Why it matters

The regression is silent: the query is legal, returns correct results, and uses the indexes one would expect to exist — it just picks the wrong driving side. Because the runtime scales with the size of the range-predicate's selection (`value > 0` matches ~90% of rows in the reproducer), it gets worse as the child table grows. Any application doing ` JOIN WHERE parent.id IN (...) AND child. ` against a Dolt database may hit this without realising — the query shape is common in ORM-generated SQL.