Join optimization that takes into account the execution cost of expensive predicates

Currently MariaDB performs join ordering with the assumption that all predicates have the same cost. If a query contains expensive predicates, the join order found based on the assumption that all predicates have the same cost may be far from optimal. The reason for such suboptimal plans is that an expensive predicate may be attached to an intermediate JOIN with a big fanout. As a result the expensive predicate may be evaluated too many times.

In some cases it is possible to move the predicate later in the plan to a more selective JOIN without changing the join order. These cases will be addressed by mdev-83. However, in other cases there exist better join ordering that allows an expensive predicate to be moved earlier in the plan, to a more selective JOIN.

The goal of this task is to extend the JOIN optimizer to take into account the cost (and selectivity if possible) of expensive predicates when considering different JOIN orders.

This is an example that would benefit from the optimization (extracted from mdev-317):

CREATE TABLE t1 (a INT, KEY(a)) ENGINE=MyISAM;
INSERT INTO t1 VALUES
(0),(8),(1),(8),(9),(24),(6),(1),(6),(2),
(4),(8),(4),(4),(7),(4),(1),(9),(4),(8);
INSERT INTO t1 SELECT * FROM t1;

CREATE TABLE t2 (b INT, KEY(b)) ENGINE=MyISAM;
INSERT INTO t2 VALUES
(4),(8),(0),(0),(0),(7),(7),(5),(3),(188),
(4),(9),(6),(1),(5),(6),(2),(4),(231),(4),
(3),(3),(7),(6),(7),(9),(4),(4),(2),(1),(2),
(194),(2),(3),(8),(4),(9),(4),(5),(5),(9),
(3),(8),(0),(98),(3),(1),(0),(189),(8),(3),
(3),(9),(6),(8),(3),(9),(5),(9),(2),(2),(5),
(8),(6),(9),(0),(3),(6),(5),(8),(2),(120),
(25),(1),(3),(1),(3),(153),(5),(9),(1),(8),
(7),(6),(2),(4),(7),(3),(8),(4),(6),(1),(7),
(1),(0),(2),(7),(2),(1),(5);

CREATE TABLE t3 (c INT, KEY(c)) ENGINE=MyISAM;
INSERT INTO t3 VALUES
(7),(0),(9),(3),(4),(2),(5),(3),(1),(3),(6),
(7),(5),(1),(204),(224),(9),(5),(0),(3);
INSERT INTO t3 SELECT * FROM t3;

SET optimizer_prune_level = 1;

EXPLAIN
SELECT count FROM t1, t2, t3 AS t3_alias
WHERE b <= 236
AND EXISTS ( SELECT 1 FROM t3 WHERE c > t3_alias.c )
ORDER BY a LIMIT 1;

– worse plan
SET optimizer_prune_level = 0;

EXPLAIN
SELECT count FROM t1, t2, t3 AS t3_alias
WHERE b <= 236
AND EXISTS ( SELECT 1 FROM t3 WHERE c > t3_alias.c )
ORDER BY a LIMIT 1;

In the above example, optimizer pruning skips the optimal query plan with respect to the current cost model and search procedure, and finds the real optimal plan.