The idea: the same answer from a much smaller tree

A query tree has the tables at its leaves and relational algebra operations at its inner nodes: σ (select rows), π (keep columns), × (Cartesian product) and ⋈ (join). It runs from the leaves up. Many different trees give the same answer, and the optimizer's job is to pick one whose intermediate results stay small. The page uses the book's query Q (Elmasri & Navathe, Section 19.1.2): the last names of employees born after 1957 who work on the project 'Aquarius'.

SELECT E.Lname
FROM   EMPLOYEE E, WORKS_ON W, PROJECT P
WHERE  P.Pname = 'Aquarius' AND P.Pnumber = W.Pno
  AND  E.Ssn = W.Essn AND E.Bdate > '1957-12-31';
Left: the canonical tree, pi Lname over one sigma with all four conditions over two Cartesian products of EMPLOYEE, WORKS_ON and PROJECT, making 30,000 and then 300,000 rows. Right: the tree MariaDB runs: sigma Pname on PROJECT gives 1 row, joined with WORKS_ON gives 30, joined with sigma Bdate on EMPLOYEE gives 10.
Same query, same 10 names: the canonical tree makes 300,000 rows on the way, the rewritten tree never more than 30.

The tables are small copies of the book's COMPANY data, the same as on a local MariaDB test server: EMPLOYEE has 100 rows (30 born after 1957), WORKS_ON 300 (each employee works on 3 projects), PROJECT 10 (one is 'Aquarius', with 30 workers). The answer is 10 names. The book prints the join as E.Essn=W.Ssn; the columns are really EMPLOYEE.Ssn and WORKS_ON.Essn, so the page uses E.Ssn = W.Essn.

Every number on the canvas tree is the number of rows that node would output if that tree were run as drawn. Every line of the MariaDB optimizer panel and of the EXPLAIN table is copied from MariaDB's own optimizer_trace, EXPLAIN and ANALYZE output for these tables.

(a) The canonical tree

The parser's first tree is the simplest one to build from SQL: a × of every table in FROM, one σ with the whole WHERE, and π for the SELECT list. Run as drawn, it pairs every employee with every WORKS_ON row and every project: 100 × 300 × 10 = 300,000 rows, to keep 10. That is the book's Fig. 19.2(a). No real system runs it, MariaDB included. In MariaDB's trace the comma list just becomes a list of inner joins with no ON conditions (expanded_query: … from employee E join works_on W join project P where …), and the rewrites below start from there.

1. Split the WHERE

The book's first rule is the cascade of σ: σc1 AND c2(R) ≡ σc1(σc2(R)), so each condition can move on its own. MariaDB does the same in condition_processing: it splits the WHERE at each AND and puts the column equalities into groups, multiple equal(p.Pnumber, w.Pno) and multiple equal(e.Ssn, w.Essn) (equality propagation). If several equalities share a column, they end up in one group, and any member can stand for another.

With P.Pnumber = 7 instead of the name, the constant joins the group: multiple equal(7, p.Pnumber, w.Pno). Now MariaDB knows W.Pno = 7 as well, although the query never says so (constant propagation), and it can use it to look W up directly. Demo: constant propagation, Pnumber = 7.

2. Equalities become joins

The book's rule 12 turns a σ on a join condition over a × into a join: σc(R × S) ≡ R ⋈c S. In MariaDB the equality groups become possible index lookups, listed in the trace as ref_optimizer_key_uses: "W's PRIMARY key column Essn can be found from e.Ssn", "P's PRIMARY key column Pnumber from w.Pno", and so on. Each next table is reached through one of them, so no × is left. On the canvas E × W (30,000 rows) becomes E ⋈ W (300 rows). This is the book's Fig. 19.2(d).

3. Join order by cost

The book's heuristic is to put the most restrictive selection first, without creating a ×: here the single 'Aquarius' row (Fig. 19.2(c)). MariaDB has no such fixed rule. It estimates the cost of join orders (considered_execution_plans) from row counts and the indexes it found, and keeps the cheapest one (best_join_order). Its plans are always left-deep: one table after another, each joined to the rows before it.

settingbest_join_orderwhy
Aquarius, index W_PNO on WORKS_ON(Pno)P, W, Ethe book's order: 1 row of P → 30 W rows by ref W_PNO → each E by eq_ref PRIMARY
Aquarius, no index on PnoE, W, Pstarting from P would scan all 300 W rows; from E each step has a key
Pnumber = 7P first, then W, E (index) or E, W (none)a primary key equal to a constant gives a const table: read once while optimizing, put first

Demo: no index on Pno, cost keeps E first shows that the order depends on the access paths, not on the query alone. How MariaDB searches the orders and what the cost formula is are the topics of the book's Sections 19.5 and 19.6.

4. Conditions pushed to their tables

The book moves each σ as far down the tree as its columns allow (Fig. 19.2(b)): σ Pname onto PROJECT, σ Bdate onto EMPLOYEE. MariaDB does this once the order is fixed (attaching_conditions_to_tables): each one-table condition is attached to that table, and EXPLAIN shows Using where there. A condition over several tables goes to the first table in the order at which all its columns are known. W gets attached_condition: null, because its join equality is already the index lookup that finds its rows.

MariaDB does steps 3 and 4 in the other order from the book: it chooses the order first and attaches the conditions after. The result is the same tree.

5. Only the columns that are needed

The book's last rewrite moves π down, so intermediate results keep only the columns used later (Fig. 19.2(e)). MariaDB has no π nodes inside the plan. It marks which columns of each table the query uses, and if one index holds all of them it reads only the index: EXPLAIN says Using index. Here W_PNO on (Pno) also stores the primary key Essn, which is everything Q needs from WORKS_ON. See Clustered vs Secondary Index for why a secondary index carries the primary key, and MySQL index access for covering indexes. π E.Lname is applied as each result row is sent.

Running the tree: a pipelined nested loop

The final tree is left-deep, and MariaDB runs it as a nested loop: read a row of the first table, check its attached condition, look up the matching rows of the second table, check, look up the third, and send the row as soon as all tables have matched. Then go back for the next row. Nothing is stored between the operators: each row is passed on as soon as it is made. The book calls this pipelined evaluation, as opposed to materialized evaluation, where each operation writes its result to a temporary table.

Time runs down. P scan: rows 1 to 6 fail Pname. Row 7 Aquarius passes. W_PNO lookup for Pno 7 gives Essn 3, then E lookup fails Bdate; Essn 6 fails; Essn 10 passes and Lname10 is sent to the client at once. The loop continues and finally reads P 10, W 30, E 30 rows and sends 10.
The first name reaches the client after 7 P rows, 3 W rows and 3 E rows have been read, long before the loop ends.

ANALYZE counts the real work per table: r_rows is the average number of rows read per loop, and r_filtered the percentage that passed the table's condition. For P → W → E they are 10 / 10.00, 30 / 100.00, 1.00 / 33.33. For E → W → P they are 100 / 30.00, 3.00 / 100.00, 1.00 / 11.11: 30 employees, 90 WORKS_ON rows and 90 PROJECT lookups to find the same 10 names. Demo: pipelined nested loop, row at a time and Demo: nested loop without the index run both. See Join Algorithms for nested loop, hash and merge joins in general.

The book's rules and what MariaDB does with them

book rulewhat it saysin MariaDB
1, 2: cascade and commute σsplit an AND into single σ, in any ordercondition_processing, multiple equal
4, 6: move σ past π, ⋈, ×a one-table σ can go to that tableattached_condition, Using where
5, 9: commute and regroup ⋈the joins can run in any ordercost-based best_join_order, left-deep only
12: σ over × is a ⋈a join condition turns × into ⋈ref_optimizer_key_uses, access types ref / eq_ref
3, 7: cascade π, move π past ⋈keep only the needed columns earlycolumns used per table, Using index
15: trivial conditionsa σ that is always true can gotrivial_condition_removal in the trace

For the cost-based planner of another database, see How a Query Planner Picks a Plan (PostgreSQL).

What the page leaves out

Query graphs (Fig. 19.1(c)) and the rules for set operations (∪, ∩, −; rules 8, 10, 11, 13, 14) are not shown. MariaDB's subquery rewrites (semi-joins, derived table merging), outer-join simplification and table elimination are left out, and so are join buffers (join_cache_level: block nested loop, BKA), which group rows instead of passing them one at a time; none is used in these plans. The cost model, histograms and optimizer_use_condition_selectivity are only named. Only a SELECT on three small tables is traced. The page leaves out the book's bushy and right-deep trees, because MariaDB builds only left-deep plans.