Details
-
Bug
-
Status: Confirmed (View Workflow)
-
Major
-
Resolution: Unresolved
-
12.3, 12.3.2
-
Related to performance
-
Description
Summary
I found a reproducible optimizer performance issue on MariaDB 12.3.2.
For an ORDER BY ... LIMIT query over a two-table inner join, the optimizer chooses a lower-cost but much slower join order. A forced t1 -> t0 plan is estimated as slightly more expensive, but runs about 40x faster.
The key point is that the query orders by t0.c0, while the join condition is t1.c0 = t0.c0. Therefore, on joined rows, ORDER BY t0.c0, t1.c3 is equivalent to ORDER BY t1.c0, t1.c3. When the query is rewritten to use t1.c0 in the ORDER BY, the optimizer automatically chooses the fast plan.
This suggests that equality-propagated ORDER BY keys are not used when costing/choosing the faster ORDER BY ... LIMIT join order.
Environment
MariaDB version: 12.3.2-MariaDB
|
|
|
Session settings used in the testcase:
|
|
|
optimizer_prune_level=0
|
optimizer_join_limit_pref_ratio=0
|
join_cache_level=0
|
|
|
optimizer_switch includes:
|
orderby_uses_equalities=on
|
The testcase also runs:
ANALYZE TABLE t0, t1; |
ANALYZE TABLE t0 PERSISTENT FOR ALL; |
ANALYZE TABLE t1 PERSISTENT FOR ALL; |
Testcase
I attached the full SQL testcase:
mariadb_order_limit_equality_key_costing.sql
|
It creates a database, two InnoDB tables, indexes, deterministic test data, and runs the relevant EXPLAIN FORMAT=JSON and ANALYZE FORMAT=JSON statements.
The data shape is:
t0 rows: 48000
|
t1 rows: 72000
|
|
|
NDV(t0.c0): 4000
|
NDV(t1.c0): 4000
|
|
|
t0 rows per c0 key: 12
|
t1 rows per c0 key: 18
|
|
|
Join rows before filter: 864000
|
Join rows after filter: 859680
|
Relevant indexes:
CREATE INDEX idx_t0_c0 ON t0(c0); |
CREATE INDEX idx_t0_c0_c1 ON t0(c0, c1); |
|
|
CREATE INDEX idx_t1_c0 ON t1(c0); |
CREATE INDEX idx_t1_c1 ON t1(c1); |
CREATE INDEX idx_t1_c3_c0_c2 ON t1(c3, c0, c2); |
Original query
SELECT t1.c2 AS ref0 |
FROM t1 INNER JOIN t0 ON t1.c0 = t0.c0 |
WHERE t0.c4 IS NOT NULL |
ORDER BY t0.c0 ASC, t1.c3 DESC |
LIMIT 3;
|
The optimizer chooses this plan:
t0 ALL scan -> t1 ref lookup -> temporary/filesort
|
Relevant part of EXPLAIN FORMAT=JSON:
{
|
"query_block": {
|
"cost": 901.9646724,
|
"filesort": {
|
"sort_key": "t0.c0, t1.c3 desc",
|
"temporary_table": {
|
"nested_loop": [
|
{
|
"table": {
|
"table_name": "t0",
|
"access_type": "ALL",
|
"rows": 48000,
|
"filtered": 99.5,
|
"attached_condition": "t0.c4 is not null and t0.c0 is not null"
|
}
|
},
|
{
|
"table": {
|
"table_name": "t1",
|
"access_type": "ref",
|
"key": "idx_t1_c0",
|
"ref": ["mariadb_order_limit_equality_key_costing.t0.c0"],
|
"loops": 47760,
|
"rows": 18
|
}
|
}
|
]
|
}
|
}
|
}
|
}
|
ANALYZE FORMAT=JSON shows that this plan takes about 2.6 seconds:
estimated cost: 901.96
|
actual runtime: 2615 ms
|
|
|
t0 actual rows: 48000
|
t1 actual loops: 47760
|
t1 actual rows per loop: 18
|
t1 pages accessed: 1817028
|
Faster forced plan
Forcing the join order to t1 -> t0 gives a slightly higher estimated cost, but runs much faster:
SELECT /*+ JOIN_ORDER(t1, t0) */ t1.c2 AS ref0 |
FROM t1 INNER JOIN t0 ON t1.c0 = t0.c0 |
WHERE t0.c4 IS NOT NULL |
ORDER BY t0.c0 ASC, t1.c3 DESC |
LIMIT 3;
|
Plan shape:
t1 index/read_sorted_file -> t0 ref lookup
|
Relevant part of EXPLAIN FORMAT=JSON:
{
|
"query_block": {
|
"cost": 928.9865715,
|
"nested_loop": [
|
{
|
"read_sorted_file": {
|
"filesort": {
|
"sort_key": "t0.c0, t1.c3 desc",
|
"table": {
|
"table_name": "t1",
|
"access_type": "index",
|
"key": "idx_t1_c3_c0_c2",
|
"used_key_parts": ["c3", "c0", "c2"],
|
"rows": 72000,
|
"using_index": true
|
}
|
}
|
}
|
},
|
{
|
"table": {
|
"table_name": "t0",
|
"access_type": "ref",
|
"key": "idx_t0_c0",
|
"ref": ["mariadb_order_limit_equality_key_costing.t1.c0"],
|
"loops": 72000,
|
"rows": 12,
|
"attached_condition": "t0.c4 is not null"
|
}
|
}
|
]
|
}
|
}
|
ANALYZE FORMAT=JSON shows:
estimated cost: 928.99
|
actual runtime: 65 ms
|
|
|
estimated t0 loops: 72000
|
actual t0 loops: 19
|
So the forced plan is estimated as if it would probe t0 72000 times, but in reality it probes t0 only 19 times because the sorted outer stream satisfies LIMIT 3 early.
This is the main cost-model mismatch.
STRAIGHT_JOIN control
Using STRAIGHT_JOIN gives the same fast plan without using a comment hint:
SELECT t1.c2 AS ref0 |
FROM t1 STRAIGHT_JOIN t0 ON t1.c0 = t0.c0 |
WHERE t0.c4 IS NOT NULL |
ORDER BY t0.c0 ASC, t1.c3 DESC |
LIMIT 3;
|
Observed result:
actual runtime: 62 ms
|
actual t0 loops: 19
|
So the issue is not specific to the JOIN_ORDER hint.
Equivalent ORDER BY rewrite
Because the join condition is:
t1.c0 = t0.c0
|
the original ordering:
ORDER BY t0.c0 ASC, t1.c3 DESC |
is equivalent on joined rows to:
ORDER BY t1.c0 ASC, t1.c3 DESC |
Running the rewritten query without any join-order hint:
SELECT t1.c2 AS ref0 |
FROM t1 INNER JOIN t0 ON t1.c0 = t0.c0 |
WHERE t0.c4 IS NOT NULL |
ORDER BY t1.c0 ASC, t1.c3 DESC |
LIMIT 3;
|
makes the optimizer choose the fast t1 -> t0 plan automatically:
t1 index/read_sorted_file -> t0 ref lookup
|
Observed result:
estimated cost: 928.99
|
actual runtime: 150 ms
|
actual t0 loops: 19
|
The first rows returned by the original ORDER BY and the rewritten ORDER BY are the same in the attached output.
This suggests that the optimizer can find the fast plan when the ORDER BY key is syntactically on t1, but does not use the equality t0.c0 = t1.c0 to see the same opportunity in the original query.
optimizer_join_limit_pref_ratio does not fix this
I also tested:
SET optimizer_join_limit_pref_ratio=1; |
and:
SET optimizer_join_limit_pref_ratio=100; |
Both still choose the original slower t0 -> t1 plan:
t0 ALL scan -> t1 ref lookup -> temporary/filesort
|
So this does not appear to be covered by the current optimizer_join_limit_pref_ratio behavior.
orderby_uses_equalities is already enabled
The session optimizer_switch includes:
orderby_uses_equalities=on
|
However, the original query still gets the slow t0 -> t1 plan. Therefore, this seems to be a missing or incomplete use of equality-propagated ORDER BY keys in this particular ORDER BY LIMIT join-order costing path.
LIMIT sweep
With LIMIT 300, the same pattern remains.
Default plan:
t0 ALL -> t1 ref -> temporary/filesort
|
runtime: about 2521 ms
|
t1 actual loops: 47760
|
Forced JOIN_ORDER(t1,t0) plan:
t1 index/read_sorted_file -> t0 ref
|
runtime: about 63 ms
|
actual t0 loops: 43
|
This supports that the faster plan benefits from ORDER BY LIMIT early stop, while the default plan still processes and sorts almost the whole join result.
Expected result
The optimizer should recognize that ORDER BY t0.c0, t1.c3 can be treated like ORDER BY t1.c0, t1.c3 for this inner join because t0.c0 = t1.c0.
It should consider/cost the t1 -> t0 sorted-outer plan with the LIMIT early-stop effect, instead of ranking it as more expensive than the much slower t0 -> t1 join-result-filesort plan.
Actual result
The optimizer chooses the lower-cost but much slower plan:
t0 ALL -> t1 ref -> temporary/filesort
|
cost: 901.96
|
runtime: about 2615 ms
|
The faster plan is costed higher:
t1 index/read_sorted_file -> t0 ref
|
cost: 928.99
|
runtime: about 65 ms
|
Related issues
This looks related to the ORDER BY LIMIT join-order optimization family, especially MDEV-8306 and MDEV-34720, but appears to be a narrower subcase involving equality-propagated ORDER BY keys.
Attachments
Issue Links
- relates to
-
MDEV-8306 Complete cost-based optimization for ORDER BY with LIMIT
-
- Stalled
-
-
-
- Stalled
-
-
-
- Closed
-