MATCH_RECOGNIZE That Scales

Multi-step product funnels are sequence problems. A view, then a click, then a purchase, per user, in order, with missing steps and partial progress that still matter.

Simple funnels fit in joins. As the pattern gains more steps, optional steps, and incomplete funnels that still need to appear in the result, the SQL stops resembling the question.

SQL:2016 already named the primitive: MATCH_RECOGNIZE. The question is whether you can afford to run it.

One prospect hit that limit hard on Trino: the SQL was right, the engine was not fast enough for their funnels. On our side, we had been waiting for the DuckDB core team to land MATCH_RECOGNIZE. Eventually we stopped waiting and built the extension ourselves. Below we measure it against Trino on the same funnel suite. This is the same DuckDB bet we described earlier: use an engine we can extend when the standard primitive is missing, then make the workload fast enough to use in practice.

A two-step “view then click” funnel is the hello-world of product analytics. A self-join can find the first later click for each view:

DuckDB provides a better fit for this simple shape. ASOF LEFT JOIN finds the nearest later click and preserves views without a click:

Unlike the self-join, ASOF emits at most one right-side row per view, avoiding an intermediate row for every later click. That can cut intermediate cardinality dramatically when users have many later clicks.

But then, a full-fledged funnel query built from ASOF JOINs will most likely look like this:

Each extra step needs another CTE, select list, and join condition. This version is still manageable, but it is describing the matching algorithm rather than the funnel. Add preferred paths, optional fillers, or alternate steps, and the SQL becomes a pile of joins and null-handling that no longer reads like the question you asked.

MATCH_RECOGNIZE states the question directly:

PATTERN ((A B) | A) prefers a completed view→click pair, then falls back to a lone view. That is ordinary product-analytics language. It should not require a custom pipeline.

The usual implementation is a nondeterministic finite automaton (NFA) that explores candidate starts. In Trino 476, each candidate invokes Matcher.run(), which maintains preference-ordered branch threads; branching can copy capture and aggregation state, while thread-equivalence pruning removes some duplicate states within a run. The surrounding PatternRecognitionPartition retries the matcher from later candidate positions when the search mode requires it. When many rows can start a pattern and few (or none) can finish it, repeated candidate runs become expensive.

That is not a theoretical complaint. Relational engines that implement MATCH_RECOGNIZE with this style of NFA are known to struggle on historical analytical scans; join-prefilter research reports large speedups over baseline NFA evaluation in Trino and SQL Server for selective patterns. Separately, public Postgres-hackers measurements of Trino on a no-match A+ B+ C+ E workload show super-linear blowups as partition size grows.

We are treating Trino 476 as the production baseline most people reach for when they want SQL row-pattern recognition. The measurements below use the same SQL and data shapes; the implementation description above is limited to the per-candidate matcher behavior relevant to these workloads.

Same SQL. Different work per row.

The repeated-candidate exploration above is the cost model we designed against: ambiguous stars and alternations create branch work, and failed candidates still pay for their capture history and aggregation state. We are not claiming that Trino stores a partition-wide bag of every candidate start. The workloads below exercise the observed cost shape, including the Trino slowdowns and resource-limited runs described later.

Our extension refuses to make failed exploration the working set.

For the funnel-shaped SQL in this post, row-local DEFINE predicates such as event = 'view' are evaluated while rows sink into the operator, once per DuckDB vector batch, into compact per-row label masks. Matching then reads those bits; it does not re-enter the expression engine on every automaton step. PATTERN compiles to a small Thompson-style instruction program, with branch order encoding match preference.

Search itself is a lazy viability NFA backed by a shared viability matrix: the memoized answer to “from this row and this program counter, can a match still complete?” Every attempt in the partition reuses the same cells. Ambiguous choices do not each grow a private capture history. When a preferred start is viable, we replay that path once to fill first/last captures, then evaluate MEASURES. When nothing matches, the working set is still those memo cells plus an eval stack, not a stack of doomed capture clones.

When the compiled program is tiny (at most 64 instructions) and many rows can start a match, the same funnel path may switch at runtime to a bit-parallel NFA: pack program counters into a 64-bit word and advance them with a few word ops per row. Classic funnels (ONE ROW PER MATCH, skip past the last matched row, greedy *, row-local DEFINE) stay on this funnel path.

Heavier SQL falls back to a complete matcher that can run navigation (PREV / NEXT), pattern aggregates, reluctant quantifiers, match-dependent DEFINE, or ALL ROWS PER MATCH. Correct, just not what the funnel numbers below are exercising.

The physical operator still has to sort and partition. DuckDB’s spill-capable sort keeps large partitions honest; we also prune sort payloads so row-local DEFINE columns do not ride through ordering when they are not needed afterward.

Hardware: Apple M4 Pro, 14 CPUs, 48 GB RAM. DuckDB: in-process release build of the extension, default threads=14. Trino: 476, single-node coordinator in Docker (Docker Desktop VM ~32 GiB, JVM -Xmx28G, task.concurrency=16 — Trino requires a power of two, so the nearest setting above 14). Same SQL shapes and synthetic generators for both engines. The tables are loaded before timing, but DuckDB samples include client-process startup and extension loading, while Trino samples use a persistent server plus a CLI client. Ratios are therefore end-to-end harness wall-clock comparisons, not isolated operator timings.

The recorded comparison uses Trino 476 and DuckDB v1.5.5.

We also checked that both engines return the same answers on these workloads: identical input cardinalities, identical count(*) of matches (for example 2.5M matches on the 10M-row 2-step funnel, 1.25M on the 10M-row 3-step and 5M-row skew funnels, and 0 on the no-completion / pathological no-match cases), plus matching measure rows on sampled 2-step outputs.

These are end-to-end query times, including the partitioning and sorting required by the operator. DuckDB processes the 10M-row funnels in a few hundred milliseconds, while Trino takes several seconds on the same single-machine setup.

The more interesting failure mode is a no-match pattern with greedy runs: the shape that makes active-run-style evaluation explore many doomed prefixes.

We ran PATTERN (A+ B+ C+ E) over a segmented A/B/C/D events table (no E ever appears, so both engines return zero matches), in the spirit of the public Trino-vs-Postgres row-pattern comparison. These tables are much smaller than the 10M-row funnel suite on purpose: Trino dies here in the tens of thousands of rows. One honesty note on our side: today + does not use the funnel path above, so this query runs on the complete fallback matcher, not the viability matrix. That still matters. The fallback uses preference-ordered backtracking with undo and failure memoization rather than a growing bag of capture-cloned active runs, and that is enough to survive where Trino does not:

From 10k to 20k rows, Trino’s time grew ~3.6× while the table only doubled. At 40k it still finished—but only after ~10 minutes, with resident memory already ~9 GiB on the 32 GiB Docker VM (the same scale exited 137 under an earlier ~8 GiB VM). We did not keep pushing Trino past that: the next scale (60k) is where we mark the collapse. DuckDB completed 40k in about nine seconds and kept scaling: ~18 s at 60k, ~32 s at 80k, ~53 s at 100k. (Rewriting the pattern as A A* B B* C C* E would use the funnel path instead; we kept A+ so the SQL matches the public comparison shape.)

That is the tax we did not want to inherit for funnel analytics. A pattern language is useless if “no match” is the expensive case. Product data is full of abandoned journeys.

• Funnel-shaped queries with greedy *, row-local DEFINE, ONE ROW PER MATCH, and skip-past-last-row use the funnel path above. Navigation, pattern aggregates, reluctant quantifiers, + / bounded quantifiers, match-dependent DEFINE, and ALL ROWS PER MATCH use the complete fallback: correct, heavier, still improving.
• The Trino numbers are single-node, not a tuned multi-worker cluster. That is the fair comparison for “can I run this query on a laptop-shaped analytical node,” which is how we use DuckDB. It is not a claim about Trino’s distributed scheduling.
• Docker’s memory ceiling (~32 GiB for the pathological re-run; JVM -Xmx28G) is part of the OOM story. Even with that budget, 40k took ~10 min (~9 GiB resident); we stop the Trino sweep at 60k rather than burn another half hour confirming the cliff.

We are also not claiming a complete SQL:2016 surface in every corner. Conformance tests lean on Trino 483 fixtures for the semantics we do implement.

We will publish this as a DuckDB community extension soon. If you need it in the meantime, email [email protected].

Funnels are sequence queries. MATCH_RECOGNIZE is the SQL for that. The remaining work is making the operator cheap enough that people stop rewriting the pattern as joins, and cheap enough that “no match” does not take the database down with it.