Join Order

Join Order

Join Order, Driving Tables, and STRAIGHT_JOIN

FROM order does not decide execution order: the optimizer reorders inner joins (an outer join still reads its preserved side first) to drive from the input that shrinks the rows earliest, which is only as good as its estimates:

A wrong driving table, forced right, then fixed with histogramsSQL

SELECT COUNT(*) INTO @n FROM customers AS c JOIN orders AS o ON o.customer_id = c.id
WHERE c.country = 'US' AND o.status = 'cancelled';
SELECT STRAIGHT_JOIN COUNT(*) INTO @n FROM orders AS o JOIN customers AS c
ON o.customer_id = c.id WHERE c.country = 'US' AND o.status = 'cancelled';
ANALYZE TABLE customers UPDATE HISTOGRAM ON country;
ANALYZE TABLE orders UPDATE HISTOGRAM ON status;
EXPLAIN SELECT COUNT(*) FROM customers AS c JOIN orders AS o ON o.customer_id = c.id
WHERE c.country = 'US' AND o.status = 'cancelled'\G

Output

Query OK, 1 row affected (0.753 sec)
Query OK, 1 row affected (0.149 sec)
+-------------------+-----------+----------+---------------------------------------------------
  -+
| Table             | Op        | Msg_type | Msg_text
  |
+-------------------+-----------+----------+---------------------------------------------------
  -+
| shop.customers    | histogram | status   | Histogram statistics created for column
  'country'. |
+-------------------+-----------+----------+---------------------------------------------------
  -+
1 row in set (7.037 sec)
+----------------+-----------+----------+---------------------------------------------------+
| Table          | Op        | Msg_type | Msg_text                                          |
+----------------+-----------+----------+---------------------------------------------------+
| shop.orders    | histogram | status   | Histogram statistics created for column 'status'. |
+----------------+-----------+----------+---------------------------------------------------+
1 row in set (24.485 sec)
*************************** 1. row ***************************
EXPLAIN: -> Aggregate: count(0)  (cost=68613 rows=1)
    -> Nested loop inner join  (cost=66056 rows=11102)
        -> Filter: (o.`status` = 'cancelled')  (cost=50315 rows=24704)
            -> Table scan on o  (cost=50315 rows=499223)
        -> Filter: (c.country = 'US')  (cost=0.537 rows=0.449)
            -> Single-row index lookup on c using PRIMARY (id = o.customer_id)  (cost=0.537
              rows=1)
1 row in set (0.001 sec)

Guessing 10% American customers (really 45%) and 25% cancelled orders (really 5%), the optimizer drove from customers and probed orders 44,938 times: 0.75 s, up to 2.6 s cold. STRAIGHT_JOIN forces the written order, and scanning orders first took 0.15 s. With histograms the estimates come within 1% (24,704 against 24,736) and the optimizer drives from orders unaided; the country histogram alone flipped the plan only in some runs.

A histogram has up to 1,024 buckets (default 100), singleton as here or equi-height; beyond histogram_generation_max_mem_size (20 MB) it samples (72% of status). It refreshes only when rerun or with AUTO UPDATE, is ignored where an index can answer, and appears in information_schema.COLUMN_STATISTICS. Fix statistics before hard-wiring an order that cannot adapt.

MENU