|
Hi Andreas,
I remember fixing something similar in MDEV-20424.
To analyze the issue, can you share the output of the optimizer trace.
Perform these queries
set optimizer_trace=1;
|
explain { your query }
|
select * from INFORMATION_SCHEMA.OPTIMIZER_TRACE;
|
and attach the output of the last query.
|
|
optimizer_trace.csv
I added the optimizer trace to this comment (generated via INTO OUTFILE).
|
|
After reading the other issue you referenced I tried the query with
set optimizer_use_condition_selectivity=1;
Then the problem does not occur / the PRIMARY index is chosen correctly. But already a value of optimizer_use_condition_selectivity=2 leads to the same flawed query plan.
|
|
Hi Andreas,
I can see you added the affected version as 10.4.11, can you please confirm that too , I think my fix for MDEV-20424 should fix that.
The irregularity that I see is
"rows_for_plan": 3141,\
|
"cost_for_plan": 27968,\
|
"selectivity": 5e-6,\
|
"rest_of_plan": [\
|
{\
|
"plan_prefix": [\
|
"o",\
|
"op",\
|
"p",\
|
"a",\
|
"v",\
|
"g"\
|
],\
|
"table": "g2",\
|
"best_access_path": {\
|
"considered_access_paths": [\
|
{\
|
"access_type": "eq_ref",\
|
"index": "PRIMARY",\
|
"rows": 1,\
|
"cost": 3141,\
|
"chosen": true\
|
},\
|
{\
|
"access_type": "scan",\
|
"resulting_rows": 179803,\
|
"cost": 11.558,\
|
"chosen": true\
|
}\
|
For eq_ref access the selectivity is not being taken into account. For the case with eq_ref access, the cost should have been 3141*selectivity.
|
|
Yes I am using 10.4.11 - I upgraded on the 13th of December, shortly after the last release.
|
|
One thing I do not understand is that the range optimizer shows this for table g2:
"table": "g2",
|
"range_analysis": {
|
"table_scan": {
|
"rows": 179803,
|
"cost": 36700
|
},
|
note the cost is 36700.
And then, in the join optimizer, we see:
"plan_prefix": [ "o", "op", "p", "a", "v", "g" ],
|
"table": "g2",
|
"best_access_path": {
|
{
|
"access_type": "scan",
|
"resulting_rows": 179803,
|
"cost": 11.558,
|
"chosen": true
|
}
|
and the cost is 11.558?
(following up the discussion on optimizer call: Could this be caused by some problem in selectivity computations? One could argue that this should not be the case: If one is doing a full table scan, the cost of doing the full table scan at least once will need to be paid, regardless of condition selectivity numbers)
|
|
https://gist.github.com/spetrunia/a7fce8a9b20cce54e918bb778abf8959 - mock dataset which seems to allow to demonstrate the problem. (optimizer trace lets one see relevant indexes and #rows table/range... note to self: we might want to print datatypes there)
|
|
Explain output looks like so:
+------+-------------+-------+--------+-------------------------------+-----------------------+---------+-------------------------------+--------+----------+---------------------------------------------------------------------+
|
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
|
+------+-------------+-------+--------+-------------------------------+-----------------------+---------+-------------------------------+--------+----------+---------------------------------------------------------------------+
|
| 1 | SIMPLE | o | ref | PRIMARY,order_shipment_status | order_shipment_status | 35 | const | 13150 | 100.00 | Using index condition; Using where; Using temporary; Using filesort |
|
| 1 | SIMPLE | op | ref | PRIMARY,product_id | PRIMARY | 4 | shop_aapo.o.order_id | 1 | 100.00 | |
|
| 1 | SIMPLE | p | eq_ref | PRIMARY | PRIMARY | 4 | shop_aapo.op.product_id | 1 | 100.00 | Using index |
|
| 1 | SIMPLE | a | ref | admin_id | admin_id | 10 | const,shop_aapo.op.product_id | 1 | 100.00 | Using where |
|
| 1 | SIMPLE | v | eq_ref | PRIMARY | PRIMARY | 4 | shop_aapo.op.product_id | 1 | 100.00 | |
|
| 1 | SIMPLE | g | eq_ref | PRIMARY,last_checked | PRIMARY | 4 | shop_aapo.op.product_id | 1 | 0.00 | Using where |
|
| 1 | SIMPLE | g2 | ALL | PRIMARY | NULL | NULL | NULL | 179952 | 100.00 | Using where; Using join buffer (flat, BNL join) |
|
+------+-------------+-------+--------+-------------------------------+-----------------------+---------+-------------------------------+--------+----------+---------------------------------------------------------------------+
|
|
|
Observations from debugging:
Very low record_count
for the plan prefix of ["o", "op", "p", "a", "v", "g"], best_access path is invoked with record_count=0.0656.
This is not a precise estimate. The query is using outer joins, so table g2 will receive incoming fanout of at least 1, regardless of how many rows are filtered out by table g).
Cost of eq_ref: prev_record_reads ignores selectivities of following tables?
For eq_ref, the cost is computed as follows:
records= 1.0; // as this is a unique key.
|
tmp= prev_record_reads(join_positions, idx, found_ref);
|
which gives
prev_record_reads()=1350.
|
This value comes from positions->records_read of table "o" (check its "rows" in the explain output).
(in the customer's trace output the values are a bit different (did I mix something up?) but the result is the same - cost of eq_ref access is #rows from table "o")
(TODO: this might be a problem but does this matter for the outcome of the optimization in this case?)
Cost of full table scan
Cost of using full table scan
matching_candidates_in_table()= 180K
s->scan_time() = 353 // or similar value, this is #pages
// in the clustered index from InnoDB
This part:
double cmp_time= (s->records - rnd_records)/(double) TIME_FOR_COMPARE;
|
is zero.
Then, cost is multiplied by record_count:
tmp= COST_MULT(record_count, COST_ADD(tmp,cmp_time));
|
which makes it even lower.
|
|
Looking at EXPLAIN EXTENDED output to see the outer join structure:
from
|
orders o
|
join orders_products op
|
join products p
|
left join admin_products_ausserhandel a on(a.product_id = op.product_id and a.admin_id = 16)
|
left join products_availability_sources_voigt v on(v.product_id = op.product_id)
|
left join products_availability_sources_galexis_oldschool g on(g.product_id = op.product_id and g.last_checked > 1576502395)
|
left join products_availability_sources_galexis_csv g2 on(g2.product_id = op.product_id and g2.outdated = 0)
|
Ok, no nested joins.
|
|
A sketch of the fix:
diff --git a/sql/sql_select.cc b/sql/sql_select.cc
|
index 337b1d5e02a..46e4d77d5a8 100644
|
--- a/sql/sql_select.cc
|
+++ b/sql/sql_select.cc
|
@@ -9522,6 +9522,11 @@ best_extension_by_limited_search(JOIN *join,
|
if (unlikely(thd->trace_started()) && pushdown_cond_selectivity < 1.0)
|
trace_one_table.add("selectivity", pushdown_cond_selectivity);
|
|
+ if (s->table->pos_in_table_list->on_expr)
|
+ {
|
+ if (pushdown_cond_selectivity < 1)
|
+ pushdown_cond_selectivity= 1;
|
+ }
|
double partial_join_cardinality= current_record_count *
|
pushdown_cond_selectivity;
|
if ( (search_depth > 1) && (remaining_tables & ~real_table_bit) & allowed_tables )
|
with this and my mock dataset, I get:
+------+-------------+-------+--------+-------------------------------+-----------------------+---------+-------------------------------+-------+----------+---------------------------------------------------------------------+
|
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
|
+------+-------------+-------+--------+-------------------------------+-----------------------+---------+-------------------------------+-------+----------+---------------------------------------------------------------------+
|
| 1 | SIMPLE | o | ref | PRIMARY,order_shipment_status | order_shipment_status | 35 | const | 13150 | 100.00 | Using index condition; Using where; Using temporary; Using filesort |
|
| 1 | SIMPLE | op | ref | PRIMARY,product_id | PRIMARY | 4 | shop_aapo.o.order_id | 1 | 100.00 | |
|
| 1 | SIMPLE | p | eq_ref | PRIMARY | PRIMARY | 4 | shop_aapo.op.product_id | 1 | 100.00 | Using index |
|
| 1 | SIMPLE | a | ref | admin_id | admin_id | 10 | const,shop_aapo.op.product_id | 1 | 100.00 | Using where |
|
| 1 | SIMPLE | v | eq_ref | PRIMARY | PRIMARY | 4 | shop_aapo.op.product_id | 1 | 100.00 | |
|
| 1 | SIMPLE | g | eq_ref | PRIMARY,last_checked | PRIMARY | 4 | shop_aapo.op.product_id | 1 | 0.00 | Using where |
|
| 1 | SIMPLE | g2 | eq_ref | PRIMARY | PRIMARY | 4 | shop_aapo.op.product_id | 1 | 100.00 | Using where |
|
+------+-------------+-------+--------+-------------------------------+-----------------------+---------+-------------------------------+-------+----------+---------------------------------------------------------------------+
|
Things that the above patch is missing:
- Handling for nested outer joins (with multiple tables on the inner side)
- Testcase
- (anything else?)
|
|
Here is a small test case to demonstrate the problem
create table t1(a int, b int,c int, primary key(a), key(b), key(c))engine=INNODB;
|
insert into t1 select seq, seq, seq from seq_1_to_100;
|
|
create table t2(a int, b int,c int, primary key(a), key(b), key(c))engine=INNODB;
|
insert into t2 select seq, seq, seq from seq_1_to_1000;
|
|
create table t3(a int, b int, primary key(a))engine=INNODB;
|
insert into t3 select seq, seq from seq_1_to_100;
|
MariaDB [test]> set optimizer_use_condition_selectivity=1;
|
Query OK, 0 rows affected (0.00 sec)
|
|
MariaDB [test]> EXPLAIN EXTENDED SELECT * FROM t1, t2, t3 WHERE t1.c= t2.c and t1.a = t3.a and t2.b < 10 AND t1.b < 5;
|
+------+-------------+-------+--------+---------------+---------+---------+-----------+------+----------+------------------------------------+
|
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
|
+------+-------------+-------+--------+---------------+---------+---------+-----------+------+----------+------------------------------------+
|
| 1 | SIMPLE | t1 | range | PRIMARY,b,c | b | 5 | NULL | 4 | 100.00 | Using index condition; Using where |
|
| 1 | SIMPLE | t2 | ref | b,c | c | 5 | test.t1.c | 1 | 100.00 | Using where |
|
| 1 | SIMPLE | t3 | eq_ref | PRIMARY | PRIMARY | 4 | test.t1.a | 1 | 100.00 | |
|
+------+-------------+-------+--------+---------------+---------+---------+-----------+------+----------+------------------------------------+
|
3 rows in set, 1 warning (0.00 sec)
|
|
MariaDB [test]> set optimizer_use_condition_selectivity=2;
|
Query OK, 0 rows affected (0.00 sec)
|
|
MariaDB [test]> EXPLAIN EXTENDED SELECT * FROM t1, t2, t3 WHERE t1.c= t2.c and t1.a = t3.a and t2.b < 10 AND t1.b < 5;
|
+------+-------------+-------+-------+---------------+------+---------+-----------+------+----------+-------------------------------------------------+
|
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
|
+------+-------------+-------+-------+---------------+------+---------+-----------+------+----------+-------------------------------------------------+
|
| 1 | SIMPLE | t1 | range | PRIMARY,b,c | b | 5 | NULL | 4 | 100.00 | Using index condition; Using where |
|
| 1 | SIMPLE | t2 | ref | b,c | c | 5 | test.t1.c | 1 | 0.90 | Using where |
|
| 1 | SIMPLE | t3 | ALL | PRIMARY | NULL | NULL | NULL | 100 | 100.00 | Using where; Using join buffer (flat, BNL join) |
|
+------+-------------+-------+-------+---------------+------+---------+-----------+------+----------+-------------------------------------------------+
|
3 rows in set, 1 warning (0.00 sec)
|
|
|
Observations for the above test case
Lets consider the plan t1, t2,t3 with optimizer_use_condition_selectivity > 1
records in prefix = 1 (default)
table t1 does a range scan, predicted records to be read is 4, selectivity = 100%
records in prefix= 4
t2 does a ref access, one match for each record in the prefix, selectivity= 0.0095137420718816069
records in prefix= 0.038054968287526428
t3 first tries eq_ref access=>
tmp = prev_record_reads(join_positions, idx, found_ref);
|
(lldb) p tmp
|
(double) $19 = 4
|
So this value 4 means the distinct number of eq_ref access one would perform. This is incorrect in our case because the number of records in the prefix is less than 4, we cannot get more matches than the records in the prefix.
The function prev_record_reads() tries to find the number of distinct ref access one would perform, but make sure that these are not greater than the records in the prefix
|
|
Made a small patch
http://lists.askmonty.org/pipermail/commits/2020-January/014134.html
Also after running the main suite there are 3 tests failing due to different query plans, these need to be fixed.
The tests are
main.join_outer_innodb main.subselect_sj2_mat main.subselect_mat main.subselect_sj_mat
|
|
The patch also fixes the test case that psergei made to reproduce the problem mentioned in the description.
|
|
Patch also adjusting the tests that were failing
http://lists.askmonty.org/pipermail/commits/2020-January/014138.html
|
|
I did a check with the latest selectivity tree:
MariaDB [test]> set optimizer_use_condition_selectivity=1;
|
Query OK, 0 rows affected (0.000 sec)
|
|
MariaDB [test]> EXPLAIN EXTENDED SELECT * FROM t1, t2, t3 WHERE t1.c= t2.c and t1.a = t3.a and t2.b < 10 AND t1.b < 5;
|
+------+-------------+-------+------------+---------------+---------+---------+-----------+--------+----------+------------------------------------+
|
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
|
+------+-------------+-------+------------+---------------+---------+---------+-----------+--------+----------+------------------------------------+
|
| 1 | SIMPLE | t1 | range | PRIMARY,b,c | b | 5 | NULL | 4 | 100.00 | Using index condition; Using where |
|
| 1 | SIMPLE | t2 | ref|filter | b,c | c|b | 5|5 | test.t1.c | 1 (1%) | 0.90 | Using where; Using rowid filter |
|
| 1 | SIMPLE | t3 | eq_ref | PRIMARY | PRIMARY | 4 | test.t1.a | 1 | 100.00 | |
|
+------+-------------+-------+------------+---------------+---------+---------+-----------+--------+----------+------------------------------------+
|
3 rows in set, 1 warning (0.001 sec)
|
|
MariaDB [test]> set optimizer_use_condition_selectivity=2;
|
Query OK, 0 rows affected (0.000 sec)
|
|
MariaDB [test]> EXPLAIN EXTENDED SELECT * FROM t1, t2, t3 WHERE t1.c= t2.c and t1.a = t3.a and t2.b < 10 AND t1.b < 5;
|
+------+-------------+-------+------------+---------------+---------+---------+-----------+--------+----------+------------------------------------+
|
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
|
+------+-------------+-------+------------+---------------+---------+---------+-----------+--------+----------+------------------------------------+
|
| 1 | SIMPLE | t1 | range | PRIMARY,b,c | b | 5 | NULL | 4 | 100.00 | Using index condition; Using where |
|
| 1 | SIMPLE | t2 | ref|filter | b,c | c|b | 5|5 | test.t1.c | 1 (1%) | 0.90 | Using where; Using rowid filter |
|
| 1 | SIMPLE | t3 | eq_ref | PRIMARY | PRIMARY | 4 | test.t1.a | 1 | 100.00 | |
|
+------+-------------+-------+------------+---------------+---------+---------+-----------+--------+----------+------------------------------------+
|
3 rows in set, 1 warning (0.001 sec)
|
At least this part seams to work correct in the new tree.
However the data set is so small it is hard to draw any conclusions from it.
|
|
Mock dataset requires a use of simplified query: (note: this is the query from the initial report with some irrelevant parts removed):
explain
|
SELECT
|
p.product_id,
|
SUM(op.quantity) AS quantity_sold,
|
COUNT(DISTINCT o.order_id) AS orders_number
|
FROM
|
shop_aapo.orders o,
|
shop_aapo.orders_products op,
|
(
|
(
|
(
|
shop_aapo.products p
|
LEFT JOIN shop_aapo.admin_products_ausserhandel a ON (a.product_id = p.product_id AND a.admin_id = 1)
|
)
|
LEFT JOIN shop_aapo.products_availability_sources_voigt v ON (p.product_id = v.product_id)
|
)
|
LEFT JOIN shop_aapo.products_availability_sources_galexis_oldschool g ON (p.product_id = g.product_id AND g.last_checked > 1576505788)
|
)
|
LEFT JOIN shop_aapo.products_availability_sources_galexis_csv g2 ON (g2.product_id = p.product_id AND g2.outdated = 0)
|
WHERE
|
o.order_id = op.order_id
|
AND op.product_id = p.product_id
|
AND o.order_status = "active"
|
AND (
|
v.product_status IN ("C","K","U","Z","S")
|
OR g.available_msg IN ("Ausser Handel","Fehlt beim Lieferanten")
|
OR g2.status_np IN (5,7)
|
OR g2.status_la IN (5,7)
|
)
|
AND (
|
a.product_id IS NULL
|
)
|
GROUP BY
|
p.product_id
|
HAVING
|
quantity_sold>5
|
AND orders_number>2
|
ORDER BY
|
quantity_sold DESC
|
LIMIT
|
0, 51;
|
The expected join order is "o,op,p,a,v,g,g2".
The difference is in the last line:
- in the version before the fix, table t2 will use a full table scan.
- in the fixed version, table g2 will use eq_ref access.
EXPLAIN output before the fix:
+------+-------------+-------+--------+-------------------------------+-----------------------+---------+-------------------------------+-------+-----------------------------------------------------------+
|
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
|
+------+-------------+-------+--------+-------------------------------+-----------------------+---------+-------------------------------+-------+-----------------------------------------------------------+
|
| 1 | SIMPLE | o | ref | PRIMARY,order_shipment_status | order_shipment_status | 35 | const | 14210 | Using where; Using index; Using temporary; Using filesort |
|
| 1 | SIMPLE | op | ref | PRIMARY,product_id | PRIMARY | 4 | shop_aapo.o.order_id | 1 | |
|
| 1 | SIMPLE | p | eq_ref | PRIMARY | PRIMARY | 4 | shop_aapo.op.product_id | 1 | Using index |
|
| 1 | SIMPLE | a | ref | admin_id | admin_id | 10 | const,shop_aapo.op.product_id | 1 | Using where; Using index |
|
| 1 | SIMPLE | v | eq_ref | PRIMARY | PRIMARY | 4 | shop_aapo.op.product_id | 1 | |
|
| 1 | SIMPLE | g | eq_ref | PRIMARY,last_checked | PRIMARY | 4 | shop_aapo.op.product_id | 1 | Using where |
|
| 1 | SIMPLE | g2 | ALL | PRIMARY | NULL | NULL | NULL | 8 | Using where; Using join buffer (flat, BNL join) |
|
+------+-------------+-------+--------+-------------------------------+-----------------------+---------+-------------------------------+-------+-----------------------------------------------------------+
|
EXPLAIN output after the fix:
+------+-------------+-------+--------+-------------------------------+-----------------------+---------+-------------------------------+-------+-----------------------------------------------------------+
|
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
|
+------+-------------+-------+--------+-------------------------------+-----------------------+---------+-------------------------------+-------+-----------------------------------------------------------+
|
| 1 | SIMPLE | o | ref | PRIMARY,order_shipment_status | order_shipment_status | 35 | const | 13150 | Using where; Using index; Using temporary; Using filesort |
|
| 1 | SIMPLE | op | ref | PRIMARY,product_id | PRIMARY | 4 | shop_aapo.o.order_id | 1 | |
|
| 1 | SIMPLE | p | eq_ref | PRIMARY | PRIMARY | 4 | shop_aapo.op.product_id | 1 | Using index |
|
| 1 | SIMPLE | a | ref | admin_id | admin_id | 10 | const,shop_aapo.op.product_id | 1 | Using where; Using index |
|
| 1 | SIMPLE | v | eq_ref | PRIMARY | PRIMARY | 4 | shop_aapo.op.product_id | 1 | |
|
| 1 | SIMPLE | g | eq_ref | PRIMARY,last_checked | PRIMARY | 4 | shop_aapo.op.product_id | 1 | Using where |
|
| 1 | SIMPLE | g2 | eq_ref | PRIMARY | PRIMARY | 4 | shop_aapo.op.product_id | 1 | Using where |
|
+------+-------------+-------+--------+-------------------------------+-----------------------+---------+-------------------------------+-------+-----------------------------------------------------------+
|
|
|
Tried with 11.0 tree, both with this tip cset:
commit d64cd6c004d6056ba2ab49bb0b1fa09babebe813 (HEAD -> bb-11.0, origin/bb-11.0)
|
Author: Monty <monty@mariadb.org>
|
Date: Fri Dec 2 17:18:50 2022 +0200
|
|
In best_access_path() change record_count to 1.0 if its less than 1.0.
|
|
In essence this means that we expect the user query to have at least
|
one matching row in the end.
|
and this:
commit 9595df9921dff28310652c9b65e6a5e4f0ba5bb4
|
Author: Monty <monty@mariadb.org>
|
Date: Mon Nov 28 15:02:34 2022 +0200
|
|
Changed some startup warnings to notes
|
|
- Changed 'WARNING' of type "You need to use --log-bin to make ... work"
|
to 'Note'
|
In both cases, the required join order is produced and the table g2 is using eq_ref access.
|
|
Was studying the available testcases on 11.0.
The testcase on the "mock dataset" is not a very good example actually as the last table (g2) has just one row (which means the cost of full scan isn't that different from that of ref access, although our formulas make it slightly higher)
The "small testcase" with t1,t2,t3 is better.
Why does bb-11.0 pick eq_ref there?
Two reasons (one intentional, one accidental):
The accidental reason is that full table scan is not considered due to this heuristics in best_access_path():
/*
|
Don't test table scan if it can't be better.
|
Prefer key lookup if we would use the same key for scanning.
|
...
|
*/
|
if ((best.records_read >= s->found_records ||
|
best.cost > s->read_time) && // (1)
|
The intentional reason is the change added by this commit:
commit 93ad4e1612744809a3ef9c5263636fc14bed1ddf
|
Author: Monty <monty@mariadb.org>
|
Date: Fri Dec 2 17:18:50 2022 +0200
|
|
In best_access_path() change record_count to 1.0 if its less than 1.0.
|
How does it help?
Background info: This bug requires the query plan to have these properties:
t1
|
t2 very_selective_condition
|
t3 [eq_]ref access on t3.key=t1.col
|
When considering access methods for table t3, the following will happen:
- ref access: the optimizer uses prev_record_reads() to estimate how many eq_ref lookups will be made for table t3. Note that the return value of prev_record_reads(t3.key=t1.col) is not affected by the very_selective_condition
 .
- full table scan: this will multiply the access cost by record_count.
very_selective_condition makes record_count very low (For the original example, it is incorrect as we're guaranteed to have at least one incoming row_combination due to outer join).
A very low record_count value is multiplied by the cost of full scan, and the result is cheaper than cost of eq_ref multiplied by prev_record_reads() return value.
The above mentioned patch,
93ad4e In best_access_path() change record_count to 1.0 if its less than 1.0.
|
will apparently fix this.
|
|
One other interesting observation.
In best_access_path(), if I look at the return value of prev_record_reads() and compare that with record_count, there are plenty of cases where prev_record_reads() > record_count. This doesn't look logical - how can number of different key values for ref access be bigger than the total number of incoming record combinations?
Capping the return value of prev_record_reads() to be no larger than record_count causes quite a few changes in the query plans.
|
mariadb_explain1.png
optimizer_trace.csv