Semijoin FirstMatch: stop looking after the first matchMySQL 8.4 • MariaDB 11.4

IN (subquery) asks does-it-exist, not how-many. Watch MySQL short-circuit the inner scan the moment one matching order appears — the naive-join and FirstMatch counters diverge.

Lesson familyJoin operator

Semijoin shape controls

About this example
Ready: press Next step, or Play to run it all
0.0s 0.0s

About this example

Example query this animation executes

SELECT c.customer_id, c.name
FROM   customers c
WHERE  c.customer_id IN (
  SELECT o.customer_id
  FROM   orders o
  WHERE  o.total > 1000
);

IN (subquery) asks does-it-exist, not how-many. MySQL rewrites it as a semijoin and runs the FirstMatch strategy: the moment the first order over $1000 is found for a customer, that customer is emitted and the inner scan short-circuits — the remaining orders for that customer are never read.

What you'll see in the animation

  • Left = the driving customers (outer rows). Orange = the customer currently being checked. Right = that customer's orders over $1000 (the inner rows the subquery scans).
  • Act 1 — naive inner join: for each customer, EVERY matching order arcs into the probe panel. Alice with 3 orders reads all 3. The 'rows read' counter climbs fast — most of that work is wasted for an IN check.
  • Act 2 — FirstMatch early-out: the same query as a semijoin. The FIRST matching order arcs in, the customer is emitted with a green check, and the inner scan STOPS. The skipped orders are drawn greyed-out — MySQL never reads them.
  • The two 'rows read' counters diverge — that divergence IS the lesson. Naive = outer_rows × matches; FirstMatch = outer_rows × 1 (one probe stops each inner scan).
  • Watch the phase label: it names the exact customer and order at every step ('Alice id=1 -> order #104 $1500 matches -> emit Alice, stop scanning her orders').
  • Next step checks one customer at a time, first with the plain join, then with FirstMatch; the simplified code beside the drawing highlights the lines each step runs.

FirstMatch cost model

Outer rows ?Rows from the driving (customers) side. The semijoin runs the existence check once per outer row.

—

Matching inner rows each ?Average orders over $1000 per customer. A plain join reads all of them; FirstMatch reads only until the first.

—

Rows read — naive join ?Inner rows a plain inner join would read: outer_rows × matches. All of it is wasted past the first match, because IN only needs existence.

—

Rows read — FirstMatch ?Inner rows FirstMatch reads: about outer_rows × 1. The inner scan short-circuits on the first match for each outer row.

—

Inner reads saved ?naive − FirstMatch. These are inner-row reads FirstMatch skips because IN asks does-it-exist, not how-many.

—

Complexity ?FirstMatch turns the inner cost per outer row from 'read all matches' into 'read until the first match' — roughly constant per outer row.

O(n · 1)

Inner rows read: naive join vs FirstMatch (log-log)

Learn more — FirstMatch among the four semijoin strategies

MySQL and MariaDB rewrite IN (SELECT …) and EXISTS (SELECT …) subqueries as semijoins — a join that keeps an outer row if at least one inner row matches, without duplicating the outer row for every match. That "at least one" is the whole point: the subquery asks does a matching row exist?, never how many?.

FirstMatch (this lesson) exploits exactly that. While scanning the inner side for the current outer row, the instant the first qualifying inner row is found, the outer row is emitted and the inner scan for that outer row stops. No further inner rows are read for that customer. It behaves like a nested loop with an early break the moment a match appears — which is why it is the cheapest strategy when each outer row has many matches you would otherwise read for nothing.

The other three strategies handle the cases FirstMatch can't:

  • LooseScan — walks the inner index and skips duplicate key values, feeding only distinct keys to the join. Needs a suitable index on the inner side.
  • Materialization — runs the subquery once into a temp table, then probes it per outer row. Good when the subquery result is small and reusable.
  • DuplicateWeedout — runs the full join, then removes duplicate outer rows via a temp table keyed on the outer rowid. The most general fallback — it always works.

FirstMatch is controlled by optimizer_switch='firstmatch=on' (enabled by default in MySQL 8.4 and MariaDB 11.4). The optimizer picks it when the outer row's existence check can be satisfied by the first inner match and reading the rest would be wasted work.

Practical takeaway: if EXPLAIN shows FirstMatch(customers) (or the JSON tree shows a semijoin with a first-match strategy), MySQL is already short-circuiting the inner scan for you. If instead you see the full inner side being read per outer row, an index on the inner join/filter column is what lets the optimizer keep the per-outer cost near 1.

Sources: MySQL 8.4 Reference Manual §10.2.2.1 "Optimizing IN and EXISTS Subquery Predicates with Semijoin Transformations"; MariaDB Knowledge Base "Semijoin Subquery Optimizations" / "FirstMatch Strategy". In the MySQL source a FirstMatch semijoin runs as NestedLoopIterator with the semijoin join type, which stops reading the inner side after the first row (sql/iterators/composite_iterators.cc); MariaDB jumps back to the outer table after the first match (do_firstmatch in sql/sql_select.cc).