The idea: price every access path, keep the cheapest

A one-table SELECT can usually be answered in several ways: read the whole table, or go down an index and fetch only the rows it points to. The optimizer lists every access path it can use, estimates the cost of each, and runs the cheapest. In MariaDB the path it picked is the type column of EXPLAIN: const, ref, range, index_merge or ALL. The page prices each path with the cost formulas of Elmasri & Navathe, section 19.4, counted in block accesses, on the book's EMPLOYEE file.

Cost in block accesses against the number of matching rows s. The full scan is a flat line at 2,000. A secondary index costs x + ⌈s/2500⌉ + s, a line rising from near 0. They cross at about 2,000 rows (20 % of the table). OP3 Dno = 5 at 80 rows costs 83, below the line; OP2 Dno > 5 at 5,000 rows costs 5,004, above it; Salary ranges of 1,500 rows (1,504) and 2,000 rows (2,004) sit just below and just above the crossing.
An index costs about one block per matching row, a scan costs b whatever matches: the index wins only below about 2,000 rows.

The book's EMPLOYEE file as a MariaDB table

Example 19.4.1 gives the catalog numbers. The page keeps them and turns the access paths into InnoDB indexes:

CREATE TABLE EMPLOYEE (
  Ssn CHAR(9) PRIMARY KEY, Fname VARCHAR(15), Lname VARCHAR(15),
  Salary INT, Dno INT, Sex CHAR(1),
  KEY EMP_SAL (Salary), KEY EMP_DNO (Dno), KEY EMP_SEX (Sex)
) ENGINE=InnoDB;
StatisticValue
rows r, blocks b, rows per block bfr10,000, 2,000, 5
PRIMARY (Ssn)x = 4 levels, one row per value
EMP_SAL (Salary)x = 3, 500 values, s = 20 rows per value
EMP_DNO (Dno)x = 2, bI1 = 4 leaf blocks, NDV = 125, s = 10,000 / 125 = 80
EMP_SEX (Sex)x = 1, NDV = 2, s = 5,000

Two changes are forced by InnoDB. The table is stored inside its primary key (the clustered index), so the book's secondary index on the key Ssn becomes PRIMARY, and the book's clustering index on Salary has to be an ordinary secondary index, EMP_SAL: InnoDB can cluster a table only on its primary key. A leaf block of an index holds r / bI1 = 10,000 / 4 = 2,500 entries; the page uses that for every index.

Access types and their cost

EXPLAIN typeBook methodWhenCost (block accesses)
ALLS1 linear searchalways possibleb = 2,000 (b / 2 for an equality on a key, S1b)
constS3a primary indexequality on the whole primary or unique keyx + 1
eq_refS3a, once per outer rowthe same lookup inside a joinx + 1 per outer row (see the join page)
refS6a secondary indexequality on a non-unique indexx + ⌈s/2500⌉ + s
rangeS6b<, >, BETWEEN, IN on an indexx + ⌈s/2500⌉ + s
index_mergeS7 (rowid intersection)AND or OR of conditions on different indexesthe index parts of every index + one block per fetched row

For a secondary index the formula is the index levels x, the leaf blocks of entries, and then one block per matching row, because the rows sit in different blocks. For s up to 2,500 it is the book's CS6a = x + 1 + s; for half the table it is CS6b = x + bI1/2 + r/2. The book's worked example drops the +1 and writes 82 for Dno = 5; the page shows 83. No decision changes.

OP1, Ssn = '123456789': const on PRIMARY costs 4 + 1 = 5 against 1,000 for a scan that stops at the match (Demo: OP1 key equality → const). OP3, Dno = 5: ref on EMP_DNO costs 2 + 1 + 80 = 83 against 2,000 (Demo: OP3 Dno = 5 → ref).

Why a big range loses to a full scan

OP2, Dno > 5: the book assumes half the rows match, s = 5,000. The range on EMP_DNO costs 2 + 2 + 5,000 = 5,004, more than the 2,000 blocks of the whole file, so MariaDB picks ALL even though an index exists (Demo: OP2 Dno > 5 → the full scan wins). The index reads 5,000 scattered rows, so it reads many blocks more than once; the scan reads each block once, in order.

Demo: widen a range until the full scan wins lowers v in Salary > v: 200 rows cost 204, 1,000 cost 1,004, 1,500 cost 1,504, and at 2,000 rows the range costs 2,004 and loses to the scan. MariaDB itself gives the same break-even on the user's test table (10,000 rows, a secondary index on Salary): in optimizer_trace, 1,500 rows give a range cost of 1.572 against a table scan cost of 1.723, so the index is used; 2,000 rows give 2.070, and the trace marks the range "chosen": false, "cause": "cost". Its cost unit is not a block, but the decision lands in the same place, at about 20 % of the table. A copy of the page's table on MariaDB 13.1 (10,000 rows, the same three secondary indexes and value counts) gives exactly the page's plans: range with Using index condition for Salary > 47500 (1,500 rows), ALL with Using where for Salary > 45000 (2,000 rows) and for Dno > 5.

AND: one index plus a filter, or index_merge intersect

OP4 is Dno = 5 AND Salary > 30000 AND Sex = 'F'. The book prices each condition as the one used to find the rows and checks the other two in memory: Dno 82 (83 here), Salary 1,003 with its clustering index (a secondary EMP_SAL costs 3 + 2 + 5,000 = 5,005 here), Sex 5,001 (5,003), scan 2,000. It picks Dno. MariaDB picks the same plan: type ref, key EMP_DNO, rows 80, Extra: Using where (Demo: OP4 three ANDed conditions → ref + Using where).

MariaDB also tries the second half of the book's S7: read the rowids (here Ssn values) from two indexes, intersect the lists in memory, and fetch only the rows in both. That is index_merge with Using intersect(…). The plain intersect needs each index scan to return its rowids in primary-key order, which an equality on a secondary index does and a range does not: the optimizer trace marks Salary > 30000 "rowid_ordered": false, so it can't take part. It does try EMP_DNO with EMP_SEX, and drops EMP_SEX with "cause": "does not reduce cost": reading 4,999 Sex entries costs more than the 40 row fetches it saves. The book's model counts those entries as just 2 leaf blocks, so the page leaves this candidate out of OP4.

With two selective equalities the intersection pays off. For Dno = 5 AND Salary = 30000, EMP_SAL gives 20 Ssn values in 3 + 1 blocks, EMP_DNO gives 80 in 2 + 1, and about 80 × 20 / 10,000 = 0.16 rows are in both, so about 1 row is fetched: 4 + 3 + 1 = 8, against 24 for ref on EMP_SAL alone. MariaDB shows type index_merge, key EMP_SAL,EMP_DNO, rows 1, Using intersect(EMP_SAL,EMP_DNO); Using where (Demo: two equalities → index_merge intersect).

MariaDB also has a rowid filter for this case (optimizer_switch flag rowid_filter, on by default): it keeps ref on one index, builds a sorted list of the rowids that match a selective range on another index, and drops a row before fetching it when its rowid is not in the list. EXPLAIN then shows |filter after the type, both keys, and Using rowid filter.

OR: index_merge union, or a full scan

For Dno = 5 OR Salary = 30000 no single index finds all the rows, so without index merge the only plan is ALL. index_merge union reads both indexes, merges the two Ssn lists and fetches each row once: (2 + 1) + (3 + 1) + 100 = 107, with Using union(EMP_DNO,EMP_SAL). An OR is only as cheap as its biggest branch: Dno = 5 OR Sex = 'F' has to fetch 5,040 rows, 5,046 blocks, and loses to the scan (Demo: OR → index_merge union, or a full scan).

Left, intersect: EMP_SAL gives 20 Ssn values for Salary = 30000 and EMP_DNO gives 80 for Dno = 5; both lists are in Ssn order, the intersection keeps about 1, and 1 row is fetched: 4 + 3 + 1 = 8 blocks. Right, union: EMP_DNO gives 80 Ssn values and EMP_SAL gives 20 for Salary = 30000; the merged list has 100, and 100 rows are fetched: 3 + 4 + 100 = 107 blocks.
index_merge works on lists of rowids: intersect fetches only the rows in both lists, union fetches each row of either list once.

How index merge walks the lists, and the sort_union variant for ranges, are animated in MySQL Index Access Paths and EXPLAIN.

Book vs MariaDB

The book's modelMariaDB with InnoDB
A data file of blocks plus separate index files.The rows live in the leaves of the PRIMARY B+ tree. A primary-key lookup is a tree descent, with no extra data block.
A secondary index entry points at a block: one block per match.The entry holds the primary key, so each match is one more descent of PRIMARY. On the user's test table ANALYZE FORMAT=JSON reported r_engine_stats.pages_accessed = 44 for 20 rows found through EMP_SAL, and 45 for a full scan of all 10,000 rows.
Cost = block transfers from disk.Cost = an internal number mixing I/O and per-row CPU work; most pages come from the buffer pool.
s from a uniform assumption or a histogram.For an indexed range, the estimate comes from index dives (it is exact on the test table); other columns use mysql.column_stats and histograms.

To see it on a server: EXPLAIN SELECT … for the type, key and rows; ANALYZE SELECT … adds r_rows, the rows really read; SET optimizer_trace = 'enabled=on', run the query, then SELECT * FROM information_schema.OPTIMIZER_TRACE lists every candidate with its cost. See also How a Query Planner Picks a Plan for the same choice in PostgreSQL, and Clustered vs secondary index for the extra lookup a secondary index costs.

What the page leaves out

The book's S2 binary search, S3b hash-key lookup and S9 bitmap index have no InnoDB equivalent (InnoDB indexes are B+ trees; hash indexes exist only for MEMORY tables), and S10 functional indexes are only possible in MariaDB through an indexed virtual column. The page uses the book's block counts, not MariaDB's cost constants; it leaves out the index type (a full scan of an index in order, used for covering queries and ORDER BY), covering indexes, Index Condition Pushdown and Multi-Range Read, sort_union and sort_intersect, the rowid filter in action, eq_ref inside a join, and how the row estimates themselves are made.