SQLite recursive queries can follow several edge directions

An undirected graph stores an edge once, but traversal may need to follow it in either direction. A recursive SQL query needs to describe both steps. SQLite 3.34.0 allows the recursive part of a common table expression to contain multiple SELECT terms, making that description more direct. The December 1 release notes identify graph queries as a motivation for the change and note that SQL Server supports the same general capability.

The addition extends a facility SQLite already has. Recursive common table expressions can walk trees and graphs, beginning with an initial result and repeatedly deriving more rows. Before this release, the recursive part had to be one simple SELECT. A compound recursive part can now express several ways to derive the next rows without forcing them into that single term.

I value SQLite when a relational representation remains sufficient for the data an application needs. Graph-shaped relationships do not automatically require a separate service. This extension makes one useful traversal easier to express, while leaving the query author responsible for the rows that count as already visited.

Two recursive terms describe two directions

The WITH documentation at release demonstrates an undirected graph with an edge table and an index on each endpoint. Its query begins at one node and uses separate recursive SELECTs to follow the two directions. The following illustrative data makes that traversal concrete.

CREATE TABLE edge (aa INTEGER, bb INTEGER);
CREATE INDEX edge_aa ON edge (aa);
CREATE INDEX edge_bb ON edge (bb);

INSERT INTO edge VALUES (1, 2), (3, 2), (3, 4);

WITH RECURSIVE nodes(x) AS (
    SELECT 1
    UNION
    SELECT aa FROM edge JOIN nodes ON bb = x
    UNION
    SELECT bb FROM edge JOIN nodes ON aa = x
)
SELECT x FROM nodes ORDER BY x;

The initial SELECT supplies node 1. One recursive term follows an edge whose second endpoint matches the current node, and the other follows an edge whose first endpoint matches it. Together they reach nodes 1 through 4 in this example. The final ordering makes the displayed result explicit without making an assumption about the order of traversal.

The indexes match the two endpoint lookups. The documentation says they are not required but can help with larger graphs. Their role is understandable from the predicates, because each term searches a different endpoint column. The extension allows those searches to remain separate terms in the recursive definition.

This representation treats the edge as undirected by query policy. Storing a row with aa and bb does not itself force every query to traverse both directions. The recursive terms establish that interpretation. A directed traversal could use only the term corresponding to the intended direction.

Duplicate rows determine whether traversal terminates

The example uses UNION, which discards a row if an identical row has previously entered the recursive queue. That includes rows already extracted from the queue. UNION ALL instead admits repeated rows, so it has a different meaning for a graph with cycles. The documentation uses duplicate elimination to prevent infinite recursion in its undirected traversal.

The shape of the recursive row is therefore important. Here it contains only the node ID, so revisiting the same ID produces an identical row. If a query adds a depth column, reaching the same node at another depth produces a different row. Duplicate elimination on the complete row would no longer mean that the node itself has been visited only once.

That is a consequence of the documented row comparison, not a separate visited-node feature. The recursive CTE records the values the author puts in its result columns. An application that wants path information as well as reachability needs to account for that difference. Adding output detail can change termination behavior instead of merely enriching presentation.

There is also a memory tradeoff. The documentation explains that UNION needs to retain previously generated content to detect duplicates. Some UNION ALL queries can return rows and discard them without retaining that history. The appropriate operator follows the query's semantics, including whether revisits are valid and whether recursion has another stopping condition.

The recursive queue has explicit rules

SQLite describes the algorithm in terms of a queue. The initial terms add rows, then SQLite extracts one row and evaluates the recursive part as though that row were the recursive table. Newly generated rows enter the queue. The new compound form expands what that recursive evaluation can contain, while retaining this conceptual model.

All nonrecursive terms must precede the recursive terms. Each recursive SELECT must refer to the recursive table exactly once in its top-level FROM clause, and aggregate or window functions are not allowed in the recursive SELECTs. Multiple recursive terms must use the same UNION or UNION ALL operator that connects the initial and recursive parts.

The documentation also permits a recursive ORDER BY to control extraction from the queue and a LIMIT to bound rows admitted to the recursive table. Those clauses concern execution of recursion, while an outer ORDER BY controls presentation of the final result. In the example, only the final output order is needed to show the reached node IDs clearly.

Without a recursive ordering clause, the documentation leaves queue extraction order undefined. Its description of the current implementation as a FIFO is explicitly not a promise applications should depend on. A query that needs a traversal priority must express that priority in the recursive ordering.

I prefer the queue explanation because it makes these choices concrete. Multiple recursive terms describe alternative next steps, and the compound operator determines which resulting rows can enter the queue. Those are properties the SQL author can inspect before attributing a traversal result to unspecified graph behavior.

Transaction inspection also becomes more precise

The same release adds sqlite3_txn_state(). Its declaration and contract in the 3.34.0 header distinguish no pending transaction, a read transaction and a write transaction. The caller can ask about a named schema or pass a null schema name to obtain the highest state across the connection's schemas.

An invalid schema name returns -1, which is separate from the three valid states. The release also exposes transaction-state information through the command-line shell's .databases output. This gives both embedded callers and shell users a more specific description of connection activity, alongside the new ways to express recursive work within a SQL statement.