Details
Description
I originally commented on this bug: https://bugs.launchpad.net/maria/+bug/806894
but now I'm not so sure that is my issue.
With semijoin=on, I am seeing more than an order of magnitude of performance drop vs. in_to_exists.
I will upload my dataset to the ftp server and followup afterwards. For now, query is:
SELECT count(*)
FROM v
LEFT JOIN c
ON v.cid = c.cid
WHERE v.t >= '2012-01-31 05:00:00'
AND v.t <= '2012-02-08 07:59:59'
AND v.did = '208'
AND c.pid = '3124'
AND v.cid IN
( SELECT c.cid
FROM c
WHERE c.pid = '3124'
AND c.s = 0
AND
(
(
c.cid IN
( /*Inner query 1*/ SELECT v.cid
FROM v
WHERE v.did = 208
AND v.t >= '2012-01-31 05:00:00'
AND v.t <= '2012-02-08 07:59:59'
)
)
AND
(
c.cid IN
( /*Inner query 2*/ SELECT v.cid
FROM v
WHERE v.did = 208
AND v.t >= '2012-01-31 05:00:00'
AND v.t <= '2012-02-08 07:59:59'
)
)
AND
(
c.cid IN
( /*Inner query 3*/ SELECT v.cid
FROM v
WHERE v.did = 208
AND v.t >= '2012-01-31 05:00:00'
AND v.t <= '2012-02-08 07:59:59'
)
)
)
);
mysql> show variables like 'optimizer_switch'; +------------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+ | Variable_name | Value | +------------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+ | optimizer_switch | index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_merge_sort_intersection=on,index_condition_pushdown=on,derived_merge=on,derived_with_keys=on,firstmatch=on,loosescan=on,materialization=on,in_to_exists=on,semijoin=off,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on,mrr=on,mrr_cost_based=off,mrr_sort_keys=off,outer_join_with_cache=on,semijoin_with_cache=on,join_cache_incremental=on,join_cache_hashed=on,join_cache_bka=on,optimize_join_buffer_size=on,table_elimination=on | +------------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+ 1 row in set (0.02 sec) mysql> select version(); +----------------------+ | version() | +----------------------+ | 5.3.4-MariaDB-rc-log | +----------------------+ 1 row in set (0.00 sec)
(revno: 3411)
explain with no semijoin:
+----+--------------------+-------+-----------------+-----------------+---------+---------+------------+------+-----------------------------------------------------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+--------------------+-------+-----------------+-----------------+---------+---------+------------+------+-----------------------------------------------------------+ | 1 | PRIMARY | v | range | cid,did | did | 17 | NULL | 275 | Using where; Using index; Using temporary; Using filesort | | 1 | PRIMARY | c | eq_ref | PRIMARY | PRIMARY | 8 | test.v.cid | 1 | Using where | | 2 | DEPENDENT SUBQUERY | c | unique_subquery | PRIMARY | PRIMARY | 8 | func | 1 | Using where | | 5 | DEPENDENT SUBQUERY | v | index_subquery | PRIMARY,cid,did | cid | 16 | func,const | 1 | Using index; Using where | | 4 | DEPENDENT SUBQUERY | v | index_subquery | PRIMARY,cid,did | cid | 16 | func,const | 1 | Using index; Using where | | 3 | DEPENDENT SUBQUERY | v | index_subquery | PRIMARY,cid,did | cid | 16 | func,const | 1 | Using index; Using where | +----+--------------------+-------+-----------------+-----------------+---------+---------+------------+------+-----------------------------------------------------------+
result:
+----------+ | count(*) | +----------+ | 275 | +----------+ 1 row in set (0.01 sec)
explain w/ semijoin (set session optimizer_switch='semijoin=on')
+----+-------------+-------+--------+---------------+---------+---------+------------------+------+-------------------------------------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-------+--------+---------------+---------+---------+------------------+------+-------------------------------------------+ | 1 | PRIMARY | v | range | cid,did | did | 17 | NULL | 275 | Using where; Using index | | 1 | PRIMARY | v | ref | cid,did | cid | 16 | test.v.cid,const | 1 | Using where; Using index; Start temporary | | 1 | PRIMARY | v | ref | cid,did | cid | 16 | test.v.cid,const | 1 | Using where; Using index | | 1 | PRIMARY | v | ref | cid,did | cid | 16 | test.v.cid,const | 1 | Using where; Using index | | 1 | PRIMARY | c | eq_ref | PRIMARY | PRIMARY | 8 | test.v.cid | 1 | Using where | | 1 | PRIMARY | c | eq_ref | PRIMARY | PRIMARY | 8 | test.v.cid | 1 | Using where; End temporary | +----+-------------+-------+--------+---------------+---------+---------+------------------+------+-------------------------------------------+
result:
+----------+ | count(*) | +----------+ | 275 | +----------+ 1 row in set (0.51 sec)
A couple of things I found:
With semijoin off and more tables added as left joins in Inner query 1|2|3, the query takes approx the same times (or maybe linear increase). With semijoin on and more tables added as left joins to Inner query 1|2|3, query takes much more time (30s in my tests, so not linear)
On my server with flashcache ssds backed stores and much higher end CPU (Core i7), the semijoin query takes .49s. With aws instance with trashy ebs and 2006 era AMD processors, semijoin varient takes 2.5s. The CPU/IO does not affect query times with semijoin=off. The result is always fast (0.01s).
Gliffy Diagrams
Attachments
Issue Links
- is part of
-
MDEV-401 Better nested semi-join processing
-
- Open
-
Activity
- All
- Comments
- Work Log
- History
- Activity
- Transitions
full log for the above comments: queries, EXPLAIN outputs, counters
LPexportBug929732_bug929732-xpl.txt
Re: semijoin much slower than in_to_exists
Re: semijoin much slower than in_to_exists
== Observation about the dataset ==
- The subqueries have high fanout, it is 4x overall, 15x if one counts the
number of rows that need to be examined. - The real fanout is much higher than the estimate provided to the 1x.
== Analysis ==
Semi-join optimizer/run-time is incapable of processing nested subqueries. When
it encounters nested subuqeries it will flatten them. The original query of
this bug has this form:
v LEFT JOIN c SEMI JOIN (c2 SEMI JOIN v2
SEMI JOIN v3
SEMI JOIN v4)
Note the 2-level semi-join nesting. The nesting is eliminated: the query is
converted to
v LEFT JOIN c JOIN c2 SEMI JOIN (v2 JOIN v3 JOIN v4)
All subqueries are put together into one cross-product-join-subquery. Fanout
of this new subquery is a product of fanouts of each subqueries.
In some cases, it is not a problem. For instance, consider FirstMatch strategy
which is run on a dataset where the every table from the subquery immediately
produces a matching record (that is, the first row read from the table happens
to satisfy relevant part of the WHERE clause).
In this case, FirstMatch's execution short-cutting property will make
subquery's fanout irrelevant: only the first matching record will be read.
However, for the query in this bug, the plan was Duplicate Weedout:
+-----+------+-----------+----+-----------------------------------------+ |table|type |ref |rows|Extra | +-----+------+-----------+----+-----------------------------------------+ |v |range |NULL | 275|Using where; Using index | |v2 |ref |v.cid,const| 1|Using where; Using index; Start temporary| |v3 |ref |v.cid,const| 1|Using where; Using index | |v4 |ref |v.cid,const| 1|Using where; Using index | |c |eq_ref|v.cid | 1|Using where | |c2 |eq_ref|v.cid | 1|Using where; End temporary | +-----+------+-----------+----+-----------------------------------------+
the semi-join nest consists of tables (v2, v3, v4), and it is correlated with
table c because of the IN-equalities:
c2.cid=v2.cid AND c2.cid=v3.cid AND c2.cid=v4.cid
Duplicate Elimination operates on the join order of "v2,v3,v4,c,c2". Note that
the outer table is at the end. When the outer table is at the end, Duplicate
Elimination is unable to do any short-cutting, and so ends up reading many more records.
Re: semijoin much slower than in_to_exists
This is not easy to solve. Created https://mariadb.atlassian.net/browse/MDEV-401 to work on a solution.
Launchpad bug id: 929732
Re: semijoin much slower than materialization
The test data has been uploaded to the private FTP server, named bug_929732_fimbulvetr.sql.bz2