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.
## Funnels are sequences, not joins
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:
```sql
SELECT
v.event_id,
v.user_id,
v.ts AS view_ts,
min(c.ts) AS click_ts
FROM events AS v
LEFT JOIN events AS c
ON c.user_id = v.user_id
AND c.event = 'click'
AND c.ts > v.ts
WHERE v.event = 'view'
GROUP BY v.event_id, v.user_id, v.ts;
```
DuckDB provides a better fit for this simple shape. `ASOF LEFT JOIN` finds the nearest later click and preserves views without a click:
```sql
SELECT
v.event_id,
v.user_id,
v.ts AS view_ts,
c.ts AS click_ts
FROM events AS v
ASOF LEFT JOIN (
SELECT user_id, ts
FROM events
WHERE event = 'click'
) AS c
ON v.user_id = c.user_id
AND v.ts < c.ts
WHERE v.event = 'view';
```
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 JOIN`s will most likely look like this:
```sql
WITH
query_periods AS (
SELECT *
FROM (
VALUES (
0,
TIMESTAMPTZ '2026-01-01 00:00:00+00',
TIMESTAMPTZ '2026-01-31 23:59:59+00'
)
) AS periods(period_index, range_start, range_end)
),
candidate_events AS (
SELECT
periods.period_index,
e.identity_uuid AS agg_field,
e.timestamp AS candidate_time,
CASE WHEN e.event = 'view' THEN TRUE ELSE FALSE END AS matches_step_0,
CASE WHEN e.event = 'click' THEN TRUE ELSE FALSE END AS matches_step_1,
CASE WHEN e.event = 'purchase' THEN TRUE ELSE FALSE END AS matches_step_2
FROM events AS e
JOIN query_periods AS periods
ON e.timestamp BETWEEN periods.range_start AND periods.range_end
WHERE e.event IN ('view', 'click', 'purchase')
AND e.identity_uuid IS NOT NULL
),
segmented_events AS (
SELECT candidate_events.*, TRUE AS belongs_to_segment, 0 AS segment_index
FROM candidate_events
),
step0 AS (
SELECT
period_index,
segment_index,
agg_field,
candidate_time AS step0_time
FROM segmented_events
WHERE matches_step_0 AND belongs_to_segment
),
step1 AS (
SELECT
step0.period_index,
step0.segment_index,
step0.agg_field,
step0.step0_time,
e1.candidate_time AS step1_time
FROM step0
ASOF LEFT JOIN segmented_events AS e1
ON step0.period_index = e1.period_index
AND step0.segment_index = e1.segment_index
AND step0.agg_field = e1.agg_field
AND step0.step0_time <= e1.candidate_time
AND e1.matches_step_1
),
step2 AS (
SELECT
step1.period_index,
step1.segment_index,
step1.agg_field,
step1.step0_time,
step1.step1_time,
e2.candidate_time AS step2_time
FROM step1
ASOF LEFT JOIN segmented_events AS e2
ON step1.period_index = e2.period_index
AND step1.segment_index = e2.segment_index
AND step1.agg_field = e2.agg_field
AND step1.step1_time <= e2.candidate_time
AND e2.matches_step_2
)
SELECT
period_index,
segment_index,
count(DISTINCT agg_field) AS funnel_step_0,
count(DISTINCT CASE WHEN step1_time IS NOT NULL THEN agg_field END) AS funnel_step_1,
count(DISTINCT CASE WHEN step2_time IS NOT NULL THEN agg_field END) AS funnel_step_2
FROM step2
GROUP BY period_index, segment_index;
```
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:
```sql
SELECT count(*)
FROM events
MATCH_RECOGNIZE (
PARTITION BY user_id
ORDER BY ts
MEASURES
A.ts AS view_ts,
B.ts AS click_ts
ONE ROW PER MATCH
AFTER MATCH SKIP PAST LAST ROW
PATTERN ((A B) | A)
DEFINE
A AS event = 'view',
B AS event = 'click'
);
```
`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.
## Why engines make it expensive
The usual implementation is a nondeterministic finite automaton (NFA) that
explores candidate starts. In Trino 476, each candidate invokes
[`Matcher.run()`](https://github.com/trinodb/trino/blob/476/core/trino-main/src/main/java/io/trino/operator/window/matcher/Matcher.java),
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`](https://github.com/trinodb/trino/blob/476/core/trino-main/src/main/java/io/trino/operator/window/PatternRecognitionPartition.java)
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.
## What we built instead
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.
## Numbers: DuckDB extension vs Trino
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](https://github.com/trinodb/trino/releases/tag/476) and [DuckDB v1.5.5](https://github.com/duckdb/duckdb/tree/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.
### Primary funnel suite
Workload
Rows
DuckDB
Trino 476
Speedup
2-step ((A B) | A)
10M
0.28 s
6.67 s
24×
3-step view→click→purchase
10M
0.19 s
4.72 s
25×
Skew (one 4M user + many tiny)
5M
0.45 s
5.02 s
11×
No completion (A C* B), zero clicks
10M
0.24 s
2.71 s
11×
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.
2-step funnel scaling from 100k to 10M rows. Both engines grow roughly with
table size; DuckDB stays about an order of magnitude ahead across the sweep.
### Where Trino collapses
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:
Rows
DuckDB
Trino 476
Speedup
10k
0.66 s
14.6 s
22×
20k
2.58 s
52.0 s
20×
40k
9.1 s
618 s
68×
60k
17.9 s
OOM
—
80k
32.0 s
—
—
100k
53.4 s
—
—
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.)
Pathological no-match scaling (zero matches). Trino finishes 40k in ~10
minutes, then OOMs at 60k; DuckDB continues through 100k.
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.
## Honest limits
- 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.
## Getting the extension
We will publish this as a DuckDB community extension soon. If you need it in the meantime, email [support@altertable.ai](mailto:support@altertable.ai).
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.