[MDEV-83] Cost-based choice for the pushdown of subqueries to joined tables Created: 2012-01-11  Updated: 2015-10-30

Status: Stalled
Project: MariaDB Server
Component/s: None
Fix Version/s: None

Type: Task Priority: Minor
Reporter: Igor Babaev Assignee: Unassigned
Resolution: Unresolved Votes: 2
Labels: optimizer

Issue Links:
Blocks
is blocked by MDEV-4145 Take into account the selectivity of ... Closed
is blocked by MDEV-5123 Remove duplicated conditions pushed b... Closed
PartOf
includes MDEV-387 Move the optimization of subqueries e... Closed
includes MDEV-4612 SQ pushdown: Server crashes in make_j... Closed
includes MDEV-5524 Fix "Subqueries: n" in EXPLAIN for co... Open
Relates
relates to MDEV-383 Evaluate subquery predicates earlier ... Open
relates to MDEV-4612 SQ pushdown: Server crashes in make_j... Closed
relates to MDEV-4648 SQ pushdown: Wrong result (missing ro... Closed
relates to MDEV-4657 SQ pushdown: Valgrind warnings (Condi... Closed
relates to MDEV-4659 SQ pushdown: Valgrind warnings (Condi... Closed
relates to MDEV-5178 Valgrind warnings (Conditional jump o... Closed
relates to MDEV-5201 Assertion `!(*exec_tab) || (*exec_tab... Closed
relates to MDEV-5203 Different results with record_cond_st... Closed
relates to MDEV-5470 Cost-based subquery item pushdown mus... Open
Sub-Tasks:
Key
 Summary
 Type
 Status
 Assignee
MDEV-4407 SQ pushdown: Wrong result (extra rows... Technical task Closed Timour Katchaounov  
MDEV-4408 SQ pushdown: Assertion `cache != __nu... Technical task Closed Timour Katchaounov  

 Description   

Contents:

  1. Problem description
  2. High-level design
    1. Main assumptions in this task
    2. General idea
    3. Detailed design
  3. Low-level design
  4. Testing

Problem description

If the evaluation of a dependent single-row subquery is performed always after accessing the last table the subquery depends on the total query execution time may happen to be suboptimal. We can see it in the report for LP bug #914569 .

With default settings (optimizer_switch='semijoin=on,materialization=on') for Q20 of the DBT-3 

select sql_calc_found_rows
 
       s_name, s_address
 
from supplier, nation
 
where s_suppkey in (select ps_suppkey from partsupp
 
                    where ps_partkey in (select p_partkey from part
 
                                         where p_name like 'forest%')
 
                          and ps_availqty >
 
                              (select 0.5 * sum(l_quantity)
 
                               from lineitem
 
                               where l_partkey = ps_partkey
 
                                     and l_suppkey = ps_suppkey
 
                                     and l_shipdate >= date('1994-01-01')
 
                                     and l_shipdate < date('1994-01-01') +
 
                                         interval '1' year ))
 
and s_nationkey = n_nationkey
 
and n_name = 'CANADA'
 
order by s_name
 
limit 10;

the 5.3 optimizer chooses the following plan for the database dbt3x10_myisam
(a myisam DBT-3 database of scale factor 10):

+----+--------------------+----------+--------+--------------------------------------+---------------+---------+------------------------------------+------+----------------------------------------------+
 
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
 
+----+--------------------+----------+--------+--------------------------------------+---------------+---------+------------------------------------+------+----------------------------------------------+
 
| 1 | PRIMARY | nation | ALL | PRIMARY | NULL | NULL | NULL | 25 | Using where; Using temporary; Using filesort |
 
| 1 | PRIMARY | supplier | ref | PRIMARY,i_s_nationkey | i_s_nationkey | 5 | dbt3x10_myisam.nation.n_nationkey | 4000 | |
 
| 1 | PRIMARY | partsupp | ref | PRIMARY,i_ps_partkey,i_ps_suppkey | i_ps_suppkey | 4 | dbt3x10_myisam.supplier.s_suppkey | 80 | Using where |
 
| 1 | PRIMARY | part | eq_ref | PRIMARY | PRIMARY | 4 | dbt3x10_myisam.partsupp.ps_partkey | 1 | Using where; FirstMatch(supplier) |
 
| 4 | DEPENDENT SUBQUERY | lineitem | ref | i_l_shipdate,i_l_partkey,i_l_suppkey | i_l_partkey | 5 | dbt3x10_myisam.partsupp.ps_partkey | 30 | Using where |
 
+----+--------------------+----------+--------+--------------------------------------+---------------+---------+------------------------------------+------+--------------------------------------------+

The execution by this plan takes significantly more time ( almost 4 times more) then the execution by the plan:

+----+--------------------+----------+-----------------+--------------------------------------+--------------+---------+-------------------------------------+--------+-----------------------------+
 
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
 
+----+--------------------+----------+-----------------+--------------------------------------+--------------+---------+-------------------------------------+--------+-----------------------------+
 
| 1 | PRIMARY | supplier | ALL | i_s_nationkey | NULL | NULL | NULL | 100000 | Using where; Using filesort |
 
| 1 | PRIMARY | nation | eq_ref | PRIMARY | PRIMARY | 4 | dbt3x10_myisam.supplier.s_nationkey | 1 | Using where |
 
| 2 | DEPENDENT SUBQUERY | partsupp | index_subquery | i_ps_suppkey | i_ps_suppkey | 4 | func | 80 | Using where |
 
| 4 | DEPENDENT SUBQUERY | lineitem | ref | i_l_shipdate,i_l_partkey,i_l_suppkey | i_l_partkey | 5 | dbt3x10_myisam.partsupp.ps_partkey | 30 | Using where |
 
| 3 | DEPENDENT SUBQUERY | part | unique_subquery | PRIMARY | PRIMARY | 4 | func | 1 | Using where |
 
+----+--------------------+----------+-----------------+--------------------------------------+--------------+---------+-------------------------------------+--------+-----------------------------+

that is chosen with the settings optimizer_switch='semijoin=off,materialization=off'.

The main difference in these two plans is that with the first execution plan the dependent subquery:

(select 0.5 * sum(l_quantity)
 
 from lineitem
 
 where l_partkey = ps_partkey
 
   and l_suppkey = ps_suppkey
 
   and l_shipdate >= date('1994-01-01')
 
   and l_shipdate < date('1994-01-01') + interval '1' year ))

is evaluated before the table part is accessed while many rows where (p_name like 'forest%') is not true are filtered out and evaluation of the dependent subquery is not needed for them.

The main goal of this task is to implement a cost based decision whether the subquery predicate should be pushed to the table partsupp or to the table part.

High-level design

Main assumptions in this task

  • It is not possible to estimate the selectivity of a subquery
    predicate during optimization.
  • It is possible to estimate the cost of a subquery (mdev-402).
  • While currently we can estimate only the selectivity of predicates for which
    there exists suitable indexes, the task will assume that it will be possible
    to estimate selectivity of most predicates based on the work in mwl#248.
    Until mwl#248 can be used, predicate selectivity is estimated through
    quick_condition_rows when there is an index (mdev-446).

General idea

The goal of this task is to minimize the number of executions of subqueries in
a join plan. Since join conditions are pushed to the earliest possible
table in the join plan, an expensive condition may be re-attached to any
table later in the plan (but not earlier) in order to minimize the number of
times it is executed.

  • The pushdown of subquery predicates is decided for each complete join plan
    during join optimization.
  • For each complete join plan, we find the partial join with the least
    cardinality.
  • Depending on table dependencies, a subquery can be pushed to a join
    no earlier than a certain position in the plan. We search the partial
    join with the least cardinality after the first position where the
    subquery can be pushed. The subquery is marked with the number of this
    optimal join position.
  • The total cost of the plan is updated taking into account that size of
    the partial join result, and the subquery cost.
  • After join optimization, but before the predicate pushdown phase, each
    subquery is set to depend on the table that is accessed by the partial
    join with least cardinality.
  • The predicate pushdown phase automatically pushes the subquery to the
    right partial join, because it is already marked to depend on it.

 Comments   
Comment by Sergei Petrunia [ 2012-11-26 ]

Discussion results:

We've implemented a solution which worked this way:

S1. choose join plan
S2. attach subquery predicates in a way that minimizes the total cost to execute them.

This solution doesn't work for us, because step S1 chooses the wrong query plan. We need a solution where costs of subquery predicate evaluation affect the join plan choice.

There are two possible solutions:

== Early-opt-1 ==

  • when join optimizer builds a complete join plan, check where the predicates can be attached. Adjust costs appropriately.
  • That is, the task is:

"given a complete join plan, attach subquery predicates in a way that minimizes their cost" —

note that any two complete join plans are not prefixes/suffixes of each other. Hence, the task needs to be done from scratch.

We need to handle best plans. That means, we'll need to store two subquery attachments at a time:

1. The one for the best known query plan so far (the plan itself is in join->best_positions)
2. The one for the "incumbent" query plan (the plan itself is in join->positions).

After join optimization is done, we can put the attachment info into Item_subselect items (and let make_join_select() attach them appropriately).

Note: "attachement" here means the table that the subquery predicate depends on, in addition to the tables that it depends on syntactically.

Conclusion: Early-opt-1 is much easier than Early-opt-2.

== Early-opt-2 ==

  • Track subquery predicate attachment "on-the-fly". That is, for each partial join plan, figure where the subqueries should be attached.
  • In other words: as soon as join prefix allows to evaluate a subquery predicate, the predicate is included in the join prefix, and its costs are counted in join prefix cost.
  • This will face the same challenges as semi-join optimization does. Suppose, we've had a join prefix {t1, t2}

    , and generated optimal subquery predicate attachment OPT_SUBQ_t1t2. Now, we add t3. We need to generate new optimal subquery predicate attachment OPT_SUBQ_t1t2t3. One likely further action is to back track, ie. remove t3 from the join prefix, where we will need to restore OPT_SUBQ_t1t2.

== Real-subquery-location problem ==
A related, but different problem. Suppose the condition has form

func(tbl1, subquery(tbl2, tbl3))

then

  • the subquery itself is dependent on {tbl2, tbl3}
  • however, it can only be evaluated when {tbl1, tbl2, tbl3}

    are available.

Q: doesn't subquery cache make it irrelevant?
Practically, we will observe difference of this kind:

a join order of tbl2, tbl3, tbl1
we think subquery is attached to tbl3
actually it is attached to tbl1.

However, due to subquery cache, subquery will be executed #rows(tbl2) * #rows(tbl3) times.

Hence, Real-suquery-location-problem can be ignored for now.

Comment by Sergei Petrunia [ 2012-11-26 ]

Decision:

  • Use Early-opt-1.
  • Before coding, check with manual cost calculations that the target example (Q20) will be handled as desired.
Comment by Timour Katchaounov (Inactive) [ 2013-03-15 ]

Benchmark results with the prototype implementation of mdev-83 merged with mwl#253:

== DBT3 SF 30 Facebook1, cold data ==
 
 
 
== MariaDB 10.0-MDEV-83 + MWL253, DBT3 SF30, SEMI-JOIN + OPTIMAL PUSHDOWN
 
+------+--------------------+----------+--------+----------------------------------------------------------+---------------------+---------+---------------------------------------------------+----------------+----------+----------------------------------------------+
 
| id   | select_type        | table    | type   | possible_keys                                            | key                 | key_len | ref                                               | rows           | filtered | Extra                                        |
 
+------+--------------------+----------+--------+----------------------------------------------------------+---------------------+---------+---------------------------------------------------+----------------+----------+----------------------------------------------+
 
|    1 | PRIMARY            | nation   | ALL    | PRIMARY                                                  | NULL                | NULL    | NULL                                              |             25 |     4.00 | Using where; Using temporary; Using filesort |
 
|    1 | PRIMARY            | supplier | ref    | PRIMARY,i_s_nationkey                                    | i_s_nationkey       | 5       | dbt3.nation.n_nationkey                           |          12000 |   100.00 |                                              |
 
|    1 | PRIMARY            | partsupp | ref    | PRIMARY,i_ps_partkey,i_ps_suppkey                        | i_ps_suppkey        | 4       | dbt3.supplier.s_suppkey                           |             80 |   100.00 |                                              |
 
|    1 | PRIMARY            | part     | eq_ref | PRIMARY                                                  | PRIMARY             | 4       | dbt3.partsupp.ps_partkey                          | 26356106085562 |     0.00 | Using where; FirstMatch(supplier)            |
 
|    4 | DEPENDENT SUBQUERY | lineitem | ref    | i_l_shipdate,i_l_suppkey_partkey,i_l_partkey,i_l_suppkey | i_l_suppkey_partkey | 10      | dbt3.partsupp.ps_partkey,dbt3.partsupp.ps_suppkey |              7 |   100.00 | Using where                                  |
 
+------+--------------------+----------+--------+----------------------------------------------------------+---------------------+---------+---------------------------------------------------+----------------+----------+----------------------------------------------+
 
(24 min 5.84 sec)
 
 
 
== MariaDB 10.0-MDEV-83 + MWL253, DBT3 SF30 IN-EXISTS (semijoin=off,materialization=off)
 
+------+--------------------+----------+-----------------+----------------------------------------------------------+---------------------+---------+---------------------------------------------------+-------+----------+----------------------------------------------+
 
| id   | select_type        | table    | type            | possible_keys                                            | key                 | key_len | ref                                               | rows  | filtered | Extra                                        |
 
+------+--------------------+----------+-----------------+----------------------------------------------------------+---------------------+---------+---------------------------------------------------+-------+----------+----------------------------------------------+
 
|    1 | PRIMARY            | nation   | ALL             | PRIMARY                                                  | NULL                | NULL    | NULL                                              |    25 |     4.00 | Using where; Using temporary; Using filesort |
 
|    1 | PRIMARY            | supplier | ref             | i_s_nationkey                                            | i_s_nationkey       | 5       | dbt3.nation.n_nationkey                           | 12000 |   100.00 | Using where                                  |
 
|    2 | DEPENDENT SUBQUERY | partsupp | index_subquery  | i_ps_suppkey                                             | i_ps_suppkey        | 4       | func                                              |    80 |   100.00 | Using where                                  |
 
|    4 | DEPENDENT SUBQUERY | lineitem | ref             | i_l_shipdate,i_l_suppkey_partkey,i_l_partkey,i_l_suppkey | i_l_suppkey_partkey | 10      | dbt3.partsupp.ps_partkey,dbt3.partsupp.ps_suppkey |     7 |   100.00 | Using where                                  |
 
|    3 | DEPENDENT SUBQUERY | part     | unique_subquery | PRIMARY                                                  | PRIMARY             | 4       | func                                              |    23 |     4.17 | Using where                                  |
 
+------+--------------------+----------+-----------------+----------------------------------------------------------+---------------------+---------+---------------------------------------------------+-------+----------+----------------------------------------------+
 
(26 min 9.44 sec)
 
+------+--------------------+----------+-----------------+----------------------------------------------------------+---------------------+---------+---------------------------------------------------+----------------+----------+----------------------------------------------+
 
| id   | select_type        | table    | type            | possible_keys                                            | key                 | key_len | ref                                               | rows           | filtered | Extra                                        |
 
+------+--------------------+----------+-----------------+----------------------------------------------------------+---------------------+---------+---------------------------------------------------+----------------+----------+----------------------------------------------+
 
|    1 | PRIMARY            | nation   | ALL             | PRIMARY                                                  | NULL                | NULL    | NULL                                              |             25 |     4.00 | Using where; Using temporary; Using filesort |
 
|    1 | PRIMARY            | supplier | ref             | i_s_nationkey                                            | i_s_nationkey       | 5       | dbt3.nation.n_nationkey                           |          12000 |   100.00 | Using where                                  |
 
|    2 | DEPENDENT SUBQUERY | partsupp | index_subquery  | i_ps_suppkey                                             | i_ps_suppkey        | 4       | func                                              |             80 |   100.00 | Using where                                  |
 
|    4 | DEPENDENT SUBQUERY | lineitem | ref             | i_l_shipdate,i_l_suppkey_partkey,i_l_partkey,i_l_suppkey | i_l_suppkey_partkey | 10      | dbt3.partsupp.ps_partkey,dbt3.partsupp.ps_suppkey |              7 |   100.00 | Using where                                  |
 
|    3 | DEPENDENT SUBQUERY | part     | unique_subquery | PRIMARY                                                  | PRIMARY             | 4       | func                                              | 26356106085562 |     0.00 | Using where                                  |
 
+------+--------------------+----------+-----------------+----------------------------------------------------------+---------------------+---------+---------------------------------------------------+----------------+----------+----------------------------------------------+
 
(24 min 13.82 sec)
 
 
 
== MariaDB 10.0-MDEV-83 + MWL253, DBT3 SF30, SEMI-JOIN (no pushdown)
 
+------+--------------------+----------+--------+----------------------------------------------------------+---------------------+---------+---------------------------------------------------+-------+----------+----------------------------------------------+
 
| id   | select_type        | table    | type   | possible_keys                                            | key                 | key_len | ref                                               | rows  | filtered | Extra                                        |
 
+------+--------------------+----------+--------+----------------------------------------------------------+---------------------+---------+---------------------------------------------------+-------+----------+----------------------------------------------+
 
|    1 | PRIMARY            | nation   | ALL    | PRIMARY                                                  | NULL                | NULL    | NULL                                              |    25 |     4.00 | Using where; Using temporary; Using filesort |
 
|    1 | PRIMARY            | supplier | ref    | PRIMARY,i_s_nationkey                                    | i_s_nationkey       | 5       | dbt3.nation.n_nationkey                           | 12000 |   100.00 |                                              |
 
|    1 | PRIMARY            | partsupp | ref    | PRIMARY,i_ps_partkey,i_ps_suppkey                        | i_ps_suppkey        | 4       | dbt3.supplier.s_suppkey                           |    80 |   100.00 |                                              |
 
|    1 | PRIMARY            | part     | eq_ref | PRIMARY                                                  | PRIMARY             | 4       | dbt3.partsupp.ps_partkey                          |    23 |     4.17 | Using where; FirstMatch(supplier)            |
 
|    4 | DEPENDENT SUBQUERY | lineitem | ref    | i_l_shipdate,i_l_suppkey_partkey,i_l_partkey,i_l_suppkey | i_l_suppkey_partkey | 10      | dbt3.partsupp.ps_partkey,dbt3.partsupp.ps_suppkey |     7 |   100.00 | Using where                                  |
 
+------+--------------------+----------+--------+----------------------------------------------------------+---------------------+---------+---------------------------------------------------+-------+----------+----------------------------------------------+
 
(2 hours 4 min 20.71 sec)
 
 
 
== MySQL 5.6.10, DBT3 SF30, default plan
 
+----+--------------------+----------+--------+----------------------------------------------------------+---------------------+---------+---------------------------------------------------+------+----------+----------------------------------------------+
 
| id | select_type        | table    | type   | possible_keys                                            | key                 | key_len | ref                                               | rows | filtered | Extra                                        |
 
+----+--------------------+----------+--------+----------------------------------------------------------+---------------------+---------+---------------------------------------------------+------+----------+----------------------------------------------+
 
|  1 | PRIMARY            | nation   | ALL    | PRIMARY                                                  | NULL                | NULL    | NULL                                              |   25 |   100.00 | Using where; Using temporary; Using filesort |
 
|  1 | PRIMARY            | supplier | ref    | PRIMARY,i_s_nationkey                                    | i_s_nationkey       | 5       | dbt3.nation.n_nationkey                           | 2104 |   100.00 | NULL                                         |
 
|  1 | PRIMARY            | partsupp | ref    | PRIMARY,i_ps_partkey,i_ps_suppkey                        | i_ps_suppkey        | 4       | dbt3.supplier.s_suppkey                           |   33 |   100.00 | Using where                                  |
 
|  1 | PRIMARY            | part     | eq_ref | PRIMARY                                                  | PRIMARY             | 4       | dbt3.partsupp.ps_partkey                          |    1 |   100.00 | Using where; FirstMatch(supplier)            |
 
|  4 | DEPENDENT SUBQUERY | lineitem | ref    | i_l_shipdate,i_l_suppkey_partkey,i_l_partkey,i_l_suppkey | i_l_suppkey_partkey | 10      | dbt3.partsupp.ps_partkey,dbt3.partsupp.ps_suppkey |    3 |   100.00 | Using where                                  |
 
+----+--------------------+----------+--------+----------------------------------------------------------+---------------------+---------+---------------------------------------------------+------+----------+----------------------------------------------+
 
(2 hours 4 min 21.30 sec)
 
 
 
== MySQL 5.6.10, DBT3 SF30, IN-EXISTS (semijoin=off,materialization=off)
 
+----+--------------------+----------+-----------------+----------------------------------------------------------+---------------------+---------+---------------------------------------------------+------+----------+----------------------------------------------+
 
| id | select_type        | table    | type            | possible_keys                                            | key                 | key_len | ref                                               | rows | filtered | Extra                                        |
 
+----+--------------------+----------+-----------------+----------------------------------------------------------+---------------------+---------+---------------------------------------------------+------+----------+----------------------------------------------+
 
|  1 | PRIMARY            | nation   | ALL             | PRIMARY                                                  | NULL                | NULL    | NULL                                              |   25 |   100.00 | Using where; Using temporary; Using filesort |
 
|  1 | PRIMARY            | supplier | ref             | i_s_nationkey                                            | i_s_nationkey       | 5       | dbt3.nation.n_nationkey                           | 2104 |   100.00 | Using where                                  |
 
|  2 | DEPENDENT SUBQUERY | partsupp | index_subquery  | i_ps_suppkey                                             | i_ps_suppkey        | 4       | func                                              |   20 |   100.00 | Using where                                  |
 
|  4 | DEPENDENT SUBQUERY | lineitem | ref             | i_l_shipdate,i_l_suppkey_partkey,i_l_partkey,i_l_suppkey | i_l_suppkey_partkey | 10      | dbt3.partsupp.ps_partkey,dbt3.partsupp.ps_suppkey |    3 |   100.00 | Using where                                  |
 
|  3 | DEPENDENT SUBQUERY | part     | unique_subquery | PRIMARY                                                  | PRIMARY             | 4       | func                                              |    1 |   100.00 | Using where                                  |
 
+----+--------------------+----------+-----------------+----------------------------------------------------------+---------------------+---------+---------------------------------------------------+------+----------+----------------------------------------------+
 
(24 min 1.92 sec)
 
 
 
 
 
 
 
== DBT3 SF 10 Desktop machine (16 GB RAM), SSD, cold data ==
 
 
 
== MariaDB 10.0-MDEV-83 + MWL253, DBT3 SF10, SEMI-JOIN + OPTIMAL PUSHDOWN
 
+------+--------------------+----------+--------+----------------------------------------------------------+---------------------+---------+---------------------------------------------------+----------------+----------+----------------------------------------------+
 
| id   | select_type        | table    | type   | possible_keys                                            | key                 | key_len | ref                                               | rows           | filtered | Extra                                        |
 
+------+--------------------+----------+--------+----------------------------------------------------------+---------------------+---------+---------------------------------------------------+----------------+----------+----------------------------------------------+
 
|    1 | PRIMARY            | nation   | ALL    | PRIMARY                                                  | NULL                | NULL    | NULL                                              |             25 |     4.00 | Using where; Using temporary; Using filesort |
 
|    1 | PRIMARY            | supplier | ref    | PRIMARY,i_s_nationkey                                    | i_s_nationkey       | 5       | dbt3.nation.n_nationkey                           |           4000 |   100.00 |                                              |
 
|    1 | PRIMARY            | partsupp | ref    | PRIMARY,i_ps_partkey,i_ps_suppkey                        | i_ps_suppkey        | 4       | dbt3.supplier.s_suppkey                           |             80 |   100.00 |                                              |
 
|    1 | PRIMARY            | part     | eq_ref | PRIMARY                                                  | PRIMARY             | 4       | dbt3.partsupp.ps_partkey                          | 26356106085562 |     0.00 | Using where; FirstMatch(supplier)            |
 
|    4 | DEPENDENT SUBQUERY | lineitem | ref    | i_l_shipdate,i_l_suppkey_partkey,i_l_partkey,i_l_suppkey | i_l_suppkey_partkey | 10      | dbt3.partsupp.ps_partkey,dbt3.partsupp.ps_suppkey |              7 |   100.00 | Using where                                  |
 
+------+--------------------+----------+--------+----------------------------------------------------------+---------------------+---------+---------------------------------------------------+----------------+----------+----------------------------------------------+
 
(42.67 sec)
 
 
 
== MariaDB 10.0-MDEV-83 + MWL253, DBT3 SF10, IN-EXISTS
 
+------+--------------------+----------+-----------------+----------------------------------------------------------+---------------------+---------+---------------------------------------------------+------+----------+----------------------------------------------+
 
| id   | select_type        | table    | type            | possible_keys                                            | key                 | key_len | ref                                               | rows | filtered | Extra                                        |
 
+------+--------------------+----------+-----------------+----------------------------------------------------------+---------------------+---------+---------------------------------------------------+------+----------+----------------------------------------------+
 
|    1 | PRIMARY            | nation   | ALL             | PRIMARY                                                  | NULL                | NULL    | NULL                                              |   25 |     4.00 | Using where; Using temporary; Using filesort |
 
|    1 | PRIMARY            | supplier | ref             | i_s_nationkey                                            | i_s_nationkey       | 5       | dbt3.nation.n_nationkey                           | 4000 |   100.00 | Using where                                  |
 
|    2 | DEPENDENT SUBQUERY | partsupp | index_subquery  | i_ps_suppkey                                             | i_ps_suppkey        | 4       | func                                              |   80 |   100.00 | Using where                                  |
 
|    4 | DEPENDENT SUBQUERY | lineitem | ref             | i_l_shipdate,i_l_suppkey_partkey,i_l_partkey,i_l_suppkey | i_l_suppkey_partkey | 10      | dbt3.partsupp.ps_partkey,dbt3.partsupp.ps_suppkey |    7 |   100.00 | Using where                                  |
 
|    3 | DEPENDENT SUBQUERY | part     | unique_subquery | PRIMARY                                                  | PRIMARY             | 4       | func                                              |   23 |     4.17 | Using where                                  |
 
+------+--------------------+----------+-----------------+----------------------------------------------------------+---------------------+---------+---------------------------------------------------+------+----------+----------------------------------------------+
 
(49.81 sec)
 
 
 
== MariaDB 10.0-MDEV-83 + MWL253, DBT3 SF10, SEMIJOIN (no pushdown)
 
+------+--------------------+----------+--------+----------------------------------------------------------+---------------------+---------+---------------------------------------------------+------+----------+----------------------------------------------+
 
| id   | select_type        | table    | type   | possible_keys                                            | key                 | key_len | ref                                               | rows | filtered | Extra                                        |
 
+------+--------------------+----------+--------+----------------------------------------------------------+---------------------+---------+---------------------------------------------------+------+----------+----------------------------------------------+
 
|    1 | PRIMARY            | nation   | ALL    | PRIMARY                                                  | NULL                | NULL    | NULL                                              |   25 |     4.00 | Using where; Using temporary; Using filesort |
 
|    1 | PRIMARY            | supplier | ref    | PRIMARY,i_s_nationkey                                    | i_s_nationkey       | 5       | dbt3.nation.n_nationkey                           | 4000 |   100.00 |                                              |
 
|    1 | PRIMARY            | partsupp | ref    | PRIMARY,i_ps_partkey,i_ps_suppkey                        | i_ps_suppkey        | 4       | dbt3.supplier.s_suppkey                           |   80 |   100.00 | Using where                                  |
 
|    1 | PRIMARY            | part     | eq_ref | PRIMARY                                                  | PRIMARY             | 4       | dbt3.partsupp.ps_partkey                          |   23 |     4.17 | Using where; FirstMatch(supplier)            |
 
|    4 | DEPENDENT SUBQUERY | lineitem | ref    | i_l_shipdate,i_l_suppkey_partkey,i_l_partkey,i_l_suppkey | i_l_suppkey_partkey | 10      | dbt3.partsupp.ps_partkey,dbt3.partsupp.ps_suppkey |    7 |   100.00 | Using where                                  |
 
+------+--------------------+----------+--------+----------------------------------------------------------+---------------------+---------+---------------------------------------------------+------+----------+----------------------------------------------+
 
(3 min 18.53 sec)
 
 
 
== MySQL 5.6.9-rc DBT3 SF10, default plan
 
+----+--------------------+-------------+--------+----------------------------------------------------------+---------------------+---------+---------------------------------------------------+---------+----------+-----------------------------+
 
| id | select_type        | table       | type   | possible_keys                                            | key                 | key_len | ref                                               | rows    | filtered | Extra                       |
 
+----+--------------------+-------------+--------+----------------------------------------------------------+---------------------+---------+---------------------------------------------------+---------+----------+-----------------------------+
 
|  1 | PRIMARY            | supplier    | ALL    | PRIMARY,i_s_nationkey                                    | NULL                | NULL    | NULL                                              |  101199 |   100.00 | Using where; Using filesort |
 
|  1 | PRIMARY            | nation      | eq_ref | PRIMARY                                                  | PRIMARY             | 4       | dbt3.supplier.s_nationkey                         |       1 |   100.00 | Using where                 |
 
|  1 | PRIMARY            | <subquery2> | eq_ref | <auto_key>                                               | <auto_key>          | 4       | dbt3.supplier.s_suppkey                           |       1 |   100.00 | NULL                        |
 
|  2 | MATERIALIZED       | part        | ALL    | PRIMARY                                                  | NULL                | NULL    | NULL                                              | 1996869 |   100.00 | Using where                 |
 
|  2 | MATERIALIZED       | partsupp    | ref    | PRIMARY,i_ps_partkey,i_ps_suppkey                        | PRIMARY             | 4       | dbt3.part.p_partkey                               |       2 |   100.00 | Using where                 |
 
|  4 | DEPENDENT SUBQUERY | lineitem    | ref    | i_l_shipdate,i_l_suppkey_partkey,i_l_partkey,i_l_suppkey | i_l_suppkey_partkey | 10      | dbt3.partsupp.ps_partkey,dbt3.partsupp.ps_suppkey |       3 |   100.00 | Using where                 |
 
+----+--------------------+-------------+--------+----------------------------------------------------------+---------------------+---------+---------------------------------------------------+---------+----------+-----------------------------+
 
(4 min 14.36 sec)
 
 
 
 
 
 
 
== MariaDB 10.0-MDEV-83 + MWL253, DBT3 SF1 laptop
 
 
 
At this scale I couldn't produce the desired plan.
 
+------+--------------------+-------------+--------+----------------------------------------------------------+---------------------+---------+---------------------------------------------------+--------+----------+----------------------------------------------+
 
| id   | select_type        | table       | type   | possible_keys                                            | key                 | key_len | ref                                               | rows   | filtered | Extra                                        |
 
+------+--------------------+-------------+--------+----------------------------------------------------------+---------------------+---------+---------------------------------------------------+--------+----------+----------------------------------------------+
 
|    1 | PRIMARY            | nation      | ALL    | PRIMARY                                                  | NULL                | NULL    | NULL                                              |     25 |     4.00 | Using where; Using temporary; Using filesort |
 
|    1 | PRIMARY            | supplier    | ref    | PRIMARY,i_s_nationkey                                    | i_s_nationkey       | 5       | dbt3.nation.n_nationkey                           |    400 |   100.00 |                                              |
 
|    1 | PRIMARY            | <subquery2> | eq_ref | distinct_key                                             | distinct_key        | 4       | func                                              |      1 |   100.00 |                                              |
 
|    2 | MATERIALIZED       | part        | ALL    | PRIMARY                                                  | NULL                | NULL    | NULL                                              | 200000 |     4.17 | Using where                                  |
 
|    2 | MATERIALIZED       | partsupp    | ref    | PRIMARY,i_ps_partkey,i_ps_suppkey                        | PRIMARY             | 4       | dbt3.part.p_partkey                               |      4 |   100.00 | Using where                                  |
 
|    4 | DEPENDENT SUBQUERY | lineitem    | ref    | i_l_shipdate,i_l_suppkey_partkey,i_l_partkey,i_l_suppkey | i_l_suppkey_partkey | 10      | dbt3.partsupp.ps_partkey,dbt3.partsupp.ps_suppkey |      7 |   100.00 | Using where                                  |
 
+------+--------------------+-------------+--------+----------------------------------------------------------+---------------------+---------+---------------------------------------------------+--------+----------+----------------------------------------------+

Comment by Timour Katchaounov (Inactive) [ 2013-03-20 ]

Tests with additional indexes: i_p_name on part(p_name), i_n_name on nation(n_name).

The MariaDB tests use the following optimizer settings:
optimizer_switch='index_condition_pushdown=on'
optimizer_switch='mrr=on'
optimizer_switch='mrr_cost_based=off'
optimizer_switch='mrr_sort_keys=on'
join_cache_level = 6

In addition we test the effect of mrr_sort_keys, and in-to-exists.

MySQL's settings are:
index_condition_pushdown=on,mrr=on,mrr_cost_based=off,block_nested_loop=on,batched_key_access=on,materialization=on,semijoin=on,loosescan=on,firstmatch=on,subquery_materialization_cost_based=on,use_index_extensions=on
persistent InnoDB statistics, 64-page sampling

== DBT3 SF 30 Facebook1, cold data ==

== MariaDB 10.0-MDEV-83 + MWL253, SEMI-JOIN + OPTIMAL PUSHDOWN
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

id select_type table type possible_keys key key_len ref rows filtered Extra

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

1 PRIMARY nation ref PRIMARY,i_n_name i_n_name 26 const 1 4.00 Using where; Using index; Using temporary; Using filesort
1 PRIMARY supplier ref PRIMARY,i_s_nationkey i_s_nationkey 5 dbt3.nation.n_nationkey 12000 100.00 Using join buffer (flat, BKA join); Key-ordered Rowid-ordered scan
1 PRIMARY partsupp ref PRIMARY,i_ps_partkey,i_ps_suppkey i_ps_suppkey 4 dbt3.supplier.s_suppkey 80 100.00 Using join buffer (incremental, BKA join); Key-ordered Rowid-ordered scan
1 PRIMARY part eq_ref PRIMARY,i_p_name PRIMARY 4 dbt3.partsupp.ps_partkey 1 2.32 Using where; FirstMatch(supplier); Using join buffer (incremental, BKA join); Key-ordered scan
4 DEPENDENT SUBQUERY lineitem ref i_l_shipdate,i_l_suppkey_partkey,i_l_partkey,i_l_suppkey i_l_suppkey_partkey 10 dbt3.partsupp.ps_partkey,dbt3.partsupp.ps_suppkey 7 30.31 Using where

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
(6 min 48.32 sec)
set optimizer_switch='mrr_sort_keys=off';
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

id select_type table type possible_keys key key_len ref rows filtered Extra

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

1 PRIMARY nation ref PRIMARY,i_n_name i_n_name 26 const 1 4.00 Using where; Using index; Using temporary; Using filesort
1 PRIMARY supplier ref PRIMARY,i_s_nationkey i_s_nationkey 5 dbt3.nation.n_nationkey 12000 100.00 Using join buffer (flat, BKA join); Rowid-ordered scan
1 PRIMARY partsupp ref PRIMARY,i_ps_partkey,i_ps_suppkey i_ps_suppkey 4 dbt3.supplier.s_suppkey 80 100.00  
1 PRIMARY part eq_ref PRIMARY,i_p_name PRIMARY 4 dbt3.partsupp.ps_partkey 1 2.32 Using where; FirstMatch(supplier)
4 DEPENDENT SUBQUERY lineitem ref i_l_shipdate,i_l_suppkey_partkey,i_l_partkey,i_l_suppkey i_l_suppkey_partkey 10 dbt3.partsupp.ps_partkey,dbt3.partsupp.ps_suppkey 7 30.31 Using where

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
(24 min 2.13 sec)

== MariaDB 10.0-MDEV-83 + MWL253, DBT3 SF30 IN-EXISTS (semijoin=off,materialization=off)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

id select_type table type possible_keys key key_len ref rows filtered Extra

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

1 PRIMARY nation ref PRIMARY,i_n_name i_n_name 26 const 1 4.00 Using where; Using index; Using temporary; Using filesort
1 PRIMARY supplier ref i_s_nationkey i_s_nationkey 5 dbt3.nation.n_nationkey 12000 100.00 Using where; Using join buffer (flat, BKA join); Key-ordered Rowid-ordered scan
2 DEPENDENT SUBQUERY partsupp index_subquery i_ps_suppkey i_ps_suppkey 4 func 80 100.00 Using where
4 DEPENDENT SUBQUERY lineitem ref i_l_shipdate,i_l_suppkey_partkey,i_l_partkey,i_l_suppkey i_l_suppkey_partkey 10 dbt3.partsupp.ps_partkey,dbt3.partsupp.ps_suppkey 7 30.31 Using where
3 DEPENDENT SUBQUERY part unique_subquery PRIMARY,i_p_name PRIMARY 4 func 1 2.32 Using where

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
(23 min 52.71 sec)

== MySQL 5.6.10, DBT3 SF30, default plan
– with XL's settings, and persistent InnoDB statistics, 64-page sampling
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

id select_type table type possible_keys key key_len ref rows filtered Extra

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

1 PRIMARY nation ref PRIMARY,i_n_name i_n_name 26 const 1 100.00 Using where; Using index; Using temporary; Using filesort
1 PRIMARY supplier ref PRIMARY,i_s_nationkey i_s_nationkey 5 dbt3.nation.n_nationkey 6176 100.00 Using index condition; Using join buffer (Batched Key Access)
1 PRIMARY <subquery2> eq_ref <auto_key> <auto_key> 4 dbt3.supplier.s_suppkey 1 100.00 NULL
2 MATERIALIZED part range PRIMARY,i_p_name i_p_name 58 NULL 139430 100.00 Using where; Using index
2 MATERIALIZED partsupp ref PRIMARY,i_ps_partkey,i_ps_suppkey PRIMARY 4 dbt3.part.p_partkey 1 100.00 Using where
4 DEPENDENT SUBQUERY lineitem ref i_l_shipdate,i_l_suppkey_partkey,i_l_partkey,i_l_suppkey i_l_suppkey_partkey 10 dbt3.partsupp.ps_partkey,dbt3.partsupp.ps_suppkey 3 100.00 Using where

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
(2 hours 9 min 3.49 sec)

== MySQL 5.6.10, DBT3 SF30, IN-EXISTS (semijoin=off,materialization=off)
– with XL's settings
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

id select_type table type possible_keys key key_len ref rows filtered Extra

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

1 PRIMARY nation ref PRIMARY,i_n_name i_n_name 26 const 1 100.00 Using where; Using index; Using temporary; Using filesort
1 PRIMARY supplier ref i_s_nationkey i_s_nationkey 5 dbt3.nation.n_nationkey 6176 100.00 Using where; Using join buffer (Batched Key Access)
2 DEPENDENT SUBQUERY partsupp index_subquery i_ps_suppkey i_ps_suppkey 4 func 43 100.00 Using where
4 DEPENDENT SUBQUERY lineitem ref i_l_shipdate,i_l_suppkey_partkey,i_l_partkey,i_l_suppkey i_l_suppkey_partkey 10 dbt3.partsupp.ps_partkey,dbt3.partsupp.ps_suppkey 3 100.00 Using where
3 DEPENDENT SUBQUERY part unique_subquery PRIMARY,i_p_name PRIMARY 4 func 1 100.00 Using where

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
(24 min 13.00 sec)

== DBT3 SF 10 Facebook1, cold data ==

== MariaDB 10.0-MDEV-83 + MWL253, SEMI-JOIN + OPTIMAL PUSHDOWN
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

id select_type table type possible_keys key key_len ref rows filtered Extra

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

1 PRIMARY nation ref PRIMARY,i_n_name i_n_name 26 const 1 4.00 Using where; Using index; Using temporary; Using filesort
1 PRIMARY supplier ref PRIMARY,i_s_nationkey i_s_nationkey 5 dbt3.nation.n_nationkey 4000 100.00 Using join buffer (flat, BKA join); Key-ordered Rowid-ordered scan
1 PRIMARY partsupp ref PRIMARY,i_ps_partkey,i_ps_suppkey i_ps_suppkey 4 dbt3.supplier.s_suppkey 80 100.00 Using join buffer (incremental, BKA join); Key-ordered Rowid-ordered scan
1 PRIMARY part eq_ref PRIMARY,i_p_name PRIMARY 4 dbt3.partsupp.ps_partkey 1 2.42 Using where; FirstMatch(supplier); Using join buffer (incremental, BKA join); Key-ordered scan
4 DEPENDENT SUBQUERY lineitem ref i_l_shipdate,i_l_suppkey_partkey,i_l_partkey,i_l_suppkey i_l_suppkey_partkey 10 dbt3.partsupp.ps_partkey,dbt3.partsupp.ps_suppkey 7 30.72 Using where

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
(2 min 11.59 sec)

set optimizer_switch='mrr_sort_keys=off';
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

id select_type table type possible_keys key key_len ref rows filtered Extra

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

1 PRIMARY nation ref PRIMARY,i_n_name i_n_name 26 const 1 4.00 Using where; Using index; Using temporary; Using filesort
1 PRIMARY supplier ref PRIMARY,i_s_nationkey i_s_nationkey 5 dbt3.nation.n_nationkey 4000 100.00 Using join buffer (flat, BKA join); Rowid-ordered scan
1 PRIMARY partsupp ref PRIMARY,i_ps_partkey,i_ps_suppkey i_ps_suppkey 4 dbt3.supplier.s_suppkey 80 100.00  
1 PRIMARY part eq_ref PRIMARY,i_p_name PRIMARY 4 dbt3.partsupp.ps_partkey 1 2.42 Using where; FirstMatch(supplier)
4 DEPENDENT SUBQUERY lineitem ref i_l_shipdate,i_l_suppkey_partkey,i_l_partkey,i_l_suppkey i_l_suppkey_partkey 10 dbt3.partsupp.ps_partkey,dbt3.partsupp.ps_suppkey 7 30.72 Using where

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
(7 min 49.00 sec)

== MariaDB 10.0-MDEV-83 + MWL253, DBT3 SF30 IN-EXISTS (semijoin=off,materialization=off)
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

id select_type table type possible_keys key key_len ref rows filtered Extra

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

1 PRIMARY nation ref PRIMARY,i_n_name i_n_name 26 const 1 4.00 Using where; Using index; Using temporary; Using filesort
1 PRIMARY supplier ref i_s_nationkey i_s_nationkey 5 dbt3.nation.n_nationkey 4000 100.00 Using where; Using join buffer (flat, BKA join); Key-ordered Rowid-ordered scan
2 DEPENDENT SUBQUERY partsupp index_subquery i_ps_suppkey i_ps_suppkey 4 func 80 100.00 Using where
4 DEPENDENT SUBQUERY lineitem ref i_l_shipdate,i_l_suppkey_partkey,i_l_partkey,i_l_suppkey i_l_suppkey_partkey 10 dbt3.partsupp.ps_partkey,dbt3.partsupp.ps_suppkey 7 30.72 Using where
3 DEPENDENT SUBQUERY part unique_subquery PRIMARY,i_p_name PRIMARY 4 func 1 2.42 Using where

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
(7 min 48.83 sec)

== MySQL 5.6.10, DBT3 SF10, default plan
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

id select_type table type possible_keys key key_len ref rows filtered Extra

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

1 PRIMARY nation ref PRIMARY,i_n_name i_n_name 26 const 1 100.00 Using where; Using index; Using temporary; Using filesort
1 PRIMARY supplier ref PRIMARY,i_s_nationkey i_s_nationkey 5 dbt3.nation.n_nationkey 1984 100.00 Using index condition; Using join buffer (Batched Key Access)
1 PRIMARY <subquery2> eq_ref <auto_key> <auto_key> 4 dbt3.supplier.s_suppkey 1 100.00 NULL
2 MATERIALIZED part range PRIMARY,i_p_name i_p_name 58 NULL 48334 100.00 Using where; Using index
2 MATERIALIZED partsupp ref PRIMARY,i_ps_partkey,i_ps_suppkey PRIMARY 4 dbt3.part.p_partkey 1 100.00 Using where
4 DEPENDENT SUBQUERY lineitem ref i_l_shipdate,i_l_suppkey_partkey,i_l_partkey,i_l_suppkey i_l_suppkey_partkey 10 dbt3.partsupp.ps_partkey,dbt3.partsupp.ps_suppkey 3 100.00 Using where

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
(33 min 26.45 sec)

== MySQL 5.6.10, DBT3 SF10, IN-EXISTS (semijoin=off,materialization=off)
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

id select_type table type possible_keys key key_len ref rows filtered Extra

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

1 PRIMARY nation ref PRIMARY,i_n_name i_n_name 26 const 1 100.00 Using where; Using index; Using temporary; Using filesort
1 PRIMARY supplier ref i_s_nationkey i_s_nationkey 5 dbt3.nation.n_nationkey 1984 100.00 Using where; Using join buffer (Batched Key Access)
2 DEPENDENT SUBQUERY partsupp index_subquery i_ps_suppkey i_ps_suppkey 4 func 40 100.00 Using where
4 DEPENDENT SUBQUERY lineitem ref i_l_shipdate,i_l_suppkey_partkey,i_l_partkey,i_l_suppkey i_l_suppkey_partkey 10 dbt3.partsupp.ps_partkey,dbt3.partsupp.ps_suppkey 3 100.00 Using where
3 DEPENDENT SUBQUERY part unique_subquery PRIMARY,i_p_name PRIMARY 4 func 1 100.00 Using where

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
(8 min 9.90 sec)

Comment by Timour Katchaounov (Inactive) [ 2013-03-25 ]

Test SF 100 with additional indexes: i_p_name on part(p_name), i_n_name on nation(n_name).

The MariaDB tests use the following optimizer settings:
optimizer_switch='index_condition_pushdown=on'
optimizer_switch='mrr=on'
optimizer_switch='mrr_cost_based=off'
optimizer_switch='mrr_sort_keys=on'
join_cache_level = 6

In addition we test the effect of mrr_sort_keys, and in-to-exists.

MySQL's optimizer settings are:
index_condition_pushdown=on,mrr=on,mrr_cost_based=off,block_nested_loop=on,batched_key_access=on,materialization=on,semijoin=on,loosescan=on,firstmatch=on,subquery_materialization_cost_based=on,use_index_extensions=on

== DBT3 SF 100 Facebook1, cold data ==

== MariaDB 10.0-MDEV-83 + MWL253, SEMI-JOIN + OPTIMAL PUSHDOWN
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

id select_type table type possible_keys key key_len ref rows filtered Extra

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

1 PRIMARY nation ref PRIMARY,i_n_name i_n_name 26 const 1 4.00 Using where; Using index; Using temporary; Using filesort
1 PRIMARY supplier ref PRIMARY,i_s_nationkey i_s_nationkey 5 dbt3.nation.n_nationkey 40000 100.00 Using join buffer (flat, BKA join); Key-ordered Rowid-ordered scan
1 PRIMARY partsupp ref PRIMARY,i_ps_partkey,i_ps_suppkey i_ps_suppkey 4 dbt3.supplier.s_suppkey 80 100.00 Using join buffer (incremental, BKA join); Key-ordered Rowid-ordered scan
1 PRIMARY part eq_ref PRIMARY,i_p_name PRIMARY 4 dbt3.partsupp.ps_partkey 1 2.36 Using where; FirstMatch(supplier); Using join buffer (incremental, BKA join); Key-ordered scan
4 DEPENDENT SUBQUERY lineitem ref i_l_shipdate,i_l_suppkey_partkey,i_l_partkey,i_l_suppkey i_l_suppkey_partkey 10 dbt3.partsupp.ps_partkey,dbt3.partsupp.ps_suppkey 7 31.27 Using where

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
(25 min 47.89 sec)

== MariaDB 10.0-MDEV-83 + MWL253, DBT3 SF30 IN-EXISTS (semijoin=off,materialization=off)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

id select_type table type possible_keys key key_len ref rows filtered Extra

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

1 PRIMARY nation ref PRIMARY,i_n_name i_n_name 26 const 1 4.00 Using where; Using index; Using temporary; Using filesort
1 PRIMARY supplier ref i_s_nationkey i_s_nationkey 5 dbt3.nation.n_nationkey 40000 100.00 Using where; Using join buffer (flat, BKA join); Key-ordered Rowid-ordered scan
2 DEPENDENT SUBQUERY partsupp index_subquery i_ps_suppkey i_ps_suppkey 4 func 80 100.00 Using where
4 DEPENDENT SUBQUERY lineitem ref i_l_shipdate,i_l_suppkey_partkey,i_l_partkey,i_l_suppkey i_l_suppkey_partkey 10 dbt3.partsupp.ps_partkey,dbt3.partsupp.ps_suppkey 7 31.27 Using where
3 DEPENDENT SUBQUERY part unique_subquery PRIMARY,i_p_name PRIMARY 4 func 1 2.36 Using where

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
(3 hours 4 min 40.51 sec)

== MySQL 5.6.10, DBT3 SF1000, default plan
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

id select_type table type possible_keys key key_len ref rows filtered Extra

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

1 PRIMARY nation ref PRIMARY,i_n_name i_n_name 26 const 1 100.00 Using where; Using index; Using temporary; Using filesort
1 PRIMARY supplier ref PRIMARY,i_s_nationkey i_s_nationkey 5 dbt3.nation.n_nationkey 20545 100.00 Using index condition; Using join buffer (Batched Key Access)
1 PRIMARY <subquery2> eq_ref <auto_key> <auto_key> 4 dbt3.supplier.s_suppkey 1 100.00 NULL
2 MATERIALIZED part range PRIMARY,i_p_name i_p_name 58 NULL 472188 100.00 Using where; Using index
2 MATERIALIZED partsupp ref PRIMARY,i_ps_partkey,i_ps_suppkey PRIMARY 4 dbt3.part.p_partkey 1 100.00 Using where
4 DEPENDENT SUBQUERY lineitem ref i_l_shipdate,i_l_suppkey_partkey,i_l_partkey,i_l_suppkey i_l_suppkey_partkey 10 dbt3.partsupp.ps_partkey,dbt3.partsupp.ps_suppkey 3 100.00 Using where

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
(10 hours 11 min 20.92 sec)

== MySQL 5.6.10, DBT3 SF100, IN-EXISTS (semijoin=off,materialization=off)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

id select_type table type possible_keys key key_len ref rows filtered Extra

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

1 PRIMARY nation ref PRIMARY,i_n_name i_n_name 26 const 1 100.00 Using where; Using index; Using temporary; Using filesort
1 PRIMARY supplier ref i_s_nationkey i_s_nationkey 5 dbt3.nation.n_nationkey 20545 100.00 Using where; Using join buffer (Batched Key Access)
2 DEPENDENT SUBQUERY partsupp index_subquery i_ps_suppkey i_ps_suppkey 4 func 42 100.00 Using where
4 DEPENDENT SUBQUERY lineitem ref i_l_shipdate,i_l_suppkey_partkey,i_l_partkey,i_l_suppkey i_l_suppkey_partkey 10 dbt3.partsupp.ps_partkey,dbt3.partsupp.ps_suppkey 3 100.00 Using where
3 DEPENDENT SUBQUERY part unique_subquery PRIMARY,i_p_name PRIMARY 4 func 1 100.00 Using where

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
(2 hours 33 min 19.63 sec)

== MySQL 5.6.10, DBT3 SF100, SEMI-JOIN (materialization=off)
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

id select_type table type possible_keys key key_len ref rows filtered Extra

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

1 PRIMARY nation ref PRIMARY,i_n_name i_n_name 26 const 1 100.00 Using where; Using index; Using temporary; Using filesort; Start temporary
1 PRIMARY part range PRIMARY,i_p_name i_p_name 58 NULL 472188 100.00 Using where; Using index; Using join buffer (Block Nested Loop)
1 PRIMARY partsupp ref PRIMARY,i_ps_partkey,i_ps_suppkey PRIMARY 4 dbt3.part.p_partkey 1 100.00 Using where
1 PRIMARY supplier eq_ref PRIMARY,i_s_nationkey PRIMARY 4 dbt3.partsupp.ps_suppkey 1 100.00 Using where; End temporary
4 DEPENDENT SUBQUERY lineitem ref i_l_shipdate,i_l_suppkey_partkey,i_l_partkey,i_l_suppkey i_l_suppkey_partkey 10 dbt3.partsupp.ps_partkey,dbt3.partsupp.ps_suppkey 3 100.00 Using where

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
(10 hours 16 min 35.90 sec)

Comment by Timour Katchaounov (Inactive) [ 2013-06-03 ]

Fixed all known problems, submit for QA.

Comment by Sergei Golubchik [ 2013-08-19 ]

reassigned for a review

Comment by Timour Katchaounov (Inactive) [ 2013-09-18 ]

Found a problem in the pushdown logic, also found some redundant computations, that can be done during make_cond_for_table.

Comment by Timour Katchaounov (Inactive) [ 2013-09-18 ]

Found a bug in the pushdown logic, also found some redundant computations, that can be done during make_cond_for_table.

Comment by Timour Katchaounov (Inactive) [ 2013-12-09 ]

Remaining work:

  • Generalize the left and right limits where a condition can be moved in the presence of various semijoin plans.
    The main technical issue is how to determine what are the limits of a semijoin for each strategy.
  • Fix test show_explain: "Target is not running an EXPLAINable command".
  • Adjust several result files.
Comment by Sergei Petrunia [ 2013-12-27 ]

JOIN::static_pushdown_cost() creates List<Item> and calls push_back() for it. This can potentially allocate O(factorial(#tables)) memory on a MEM_ROOT. This is bad. (We probably could try living with this if it was necessary. But I think it isn't)

Comment by Sergei Petrunia [ 2013-12-28 ]

I am looking at POSITION::expensive_pred_cost

It is set to 0 from:

best_access_path()
Loose_scan_opt::save_to_position() // called form best_access_path

It is set to non-zero in JOIN::static_pushdown_cost(uint idx):

opt_pos->expensive_pred_cost+= cur_item_cost;

Now, consider the following scenario of join optmization:

A full join order is constructed: t1 t2 t3
JOIN::static_pushdown_cost() is called, opt_pos ==

{t1}, so
t1->expensive_pred_cost is set to non-zero.

optimization continues, and constructs this join order:

t1 t3 t2

Note that table t1 was not removed from the join order, so
join->positions[0].expensive_pred_cost is still non zero.

Again, static_pushdown_cost() is called, suppose opt_pos == {t1}

again, and we
will see that expensive_pred_cost now has two times the cost of the subquery
predicate.

Generated at Thu Feb 08 06:26:09 UTC 2024 using Jira 8.20.16#820016-sha1:9d11dbea5f4be3d4cc21f03a88dd11d8c8687422.