Supporting Descendants in SIMD-Accelerated JSONPath

To pull values out of huge JSON files fast, the best tools scan the raw bytes with SIMD and skip over the parts that don't matter — but the leading one cannot handle descendant queries that reach elements at any depth, because it needs to know each element's type in advance; this work from Warsaw and Lille builds rsonpath, which splits the engine into a fast byte-skipping scanner and a separate query automaton with a compact stack, supporting descendants and full wildcards with no slowdown and often making queries an order of magnitude faster.

The argument in one glance

Problem

The fastest JSON query engines cannot reach elements at any depth

Querying huge JSON at speed means streaming the raw bytes with SIMD and skipping over irrelevant parts. But the state-of-the-art SIMD engine cannot support the descendant selector, which matches elements at any depth, and its wildcard is incomplete — because it relies on knowing in advance whether a selector acts on an object or a list, which descendants break.
What people did

Build a tree, or use the fast engine with its limits

One option is to parse the document into an in-memory tree and query that; another is to use the fast SIMD streaming engine but live without descendants and full wildcards, rewriting queries around the missing features.
Why it fell short

Trees are too big, and the fast engine excludes many queries

Building a tree is infeasible at scale — it eats enormous memory and parsing dominates the runtime. The fast SIMD engine, meanwhile, excludes descendant queries entirely and makes many natural queries hard or impossible to express, since you would need to know the exact depth and every label on the path.
This paper's idea

Split the engine: a byte-skipping scanner and a compact automaton (rsonpath)

rsonpath supports child, wildcard, descendant, and labels without any advance knowledge of element types. It separates a fast branchless SIMD classifier — which emits only the events the query currently needs and fast-forwards over the rest — from a depth-stack automaton that runs the query logic with a sparse stack kept as shallow as possible. It supports descendants with no performance loss (in fact 10 to 20 percent faster) and lets descendant rewrites speed up natural queries by up to an order of magnitude.

Why this problem is worth solving

Querying big JSON is common, and the obvious approach collapses at scale.

JSON represents data as nested objects (named fields) and arrays (ordered lists) down to atomic values like strings and numbers. JSONPath is the popular language for querying it: a query is a path made of selectors. A child selector names a field to step into; a wildcard steps into every child; a descendant selector reaches elements at any depth below the current point; and labels are the field names being matched. To answer such a query, the classic approach is to parse the whole document into an in-memory tree — a Document Object Model — and walk it. That is fine for small inputs, but for large datasets it is hopeless: the tree takes enormous amounts of memory, and merely building it can consume most of the query time — parsing can be up to 90 percent of the work in such an application — even though the query itself touches only a small portion of the data. When there are terabytes to query, the only feasible approach is a streaming algorithm that scans the input once with a minimal memory footprint, never materializing the whole tree.

The fastest streaming engines skip cleverly, but the leading one leaves out the most useful feature.

Modern processors offer SIMD — Single Instruction, Multiple Data — which applies one operation to many bytes at once, and this has transformed JSON processing: the simdjson parser reads gigabytes per second. For querying, the state of the art, JSONSki, goes even faster on suitable queries by using SIMD to fast-forward — to leap over stretches of the document that are irrelevant to the query without examining them byte by byte. The catch is what JSONSki cannot do. It has no support for the descendant selector, and its wildcard is only partial, stepping into every element of an array but not into every field of an object. The root cause is an assumption: JSONSki relies on knowing in advance whether a given selector is operating on an object or a list. That advance knowledge is precisely what a descendant selector destroys, since a descendant can match things at many depths and structures at once. Yet descendants are exactly what real queries want — they let you fetch, say, every value of a url property anywhere in a document without knowing its depth or path, or explore deep, irregular documents such as program syntax trees exported as JSON. Without descendants and full wildcards, those queries are infeasible or explode into unwieldy alternatives.

What people did before, and where it broke

Parse the document into an in-memory tree and query it. Build the full Document Object Model, then walk it to answer any query. Where it broke. At scale the tree consumes enormous memory and parsing dominates the runtime, even though the query touches only a fraction of the data.
Use general streaming query tools. Tools like JsonSurfer stream the document with low memory and support rich queries including descendants. Where it broke. They are slow — around 200 megabytes per second, an order of magnitude short of what SIMD engines achieve.
Use the fast SIMD engine within its limits. Use JSONSki’s SIMD fast-forwarding, and rewrite queries to avoid the unsupported descendant and full-wildcard features. Where it broke. Many natural queries cannot be expressed without descendants, or blow up into enumerations of every depth and label, because JSONSki needs to know each selector’s element type in advance.
The gap. No engine offered SIMD-speed streaming while supporting descendants and idiomatic wildcards without assuming element types in advance. Building exactly that is what rsonpath does.

How rsonpath works

From materializing a tree to a byte-skipping scanner feeding a compact automaton

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

Separate the fast branchless scanning from the branchy query logic. rsonpath is built as two decoupled modules: a classifier that consumes the raw JSON stream and, using branchless SIMD code, emits only the events that matter to the query — structural symbols and relevant labels — and an automaton that consumes those events and runs the heavily-branching query logic. Because every automaton step is costly, having the classifier emit only necessary events lets the automaton skip most of the raw input, and the clean split lets each part be built for its own kind of work. Peeling the fast, regular, high-volume path away from the slow, branch-heavy control logic, so the common case runs unobstructed, is the same architectural move the direct-storage-access work covered elsewhere on this site makes, separating the fast data path that carries the bulk of the traffic from the slow control path that only sets things up.

Look only for what you need right now, and skip straight to it. The automaton cares about different symbols in different states, so rsonpath makes the classifier state-driven: it toggles which symbols it recognizes to match the automaton’s current need, cutting the automaton’s workload and letting the classifier pick an algorithm tuned to that character set. For a descendant query it goes further, using a SIMD substring search to leap directly from one shallowest occurrence of the target label to the next, ignoring everything between. Refusing to spend work on anything the current step does not require, and jumping directly to the next thing that does, is the same discipline the redundant-writeback work covered elsewhere on this site follows, doing nothing at all in the common case where the operation would accomplish nothing and acting only when there is something that genuinely must be done.

Keep the traversal state as small as possible. Queries that mix child and descendant selectors naturally call for a pushdown automaton with a stack, but a full stack is costly to maintain, while stackless alternatives cannot handle every such query. rsonpath introduces depth-stack automata, which are as expressive as pushdown automata but use a sparse stack representation that keeps the stack depth to the bare minimum needed. Traversing tree-structured data with a compact, carefully-minimized representation of where you are, rather than a heavyweight bookkeeping of the whole path, is the same efficiency the traversal-synthesis work covered elsewhere on this site pursues, planning how to walk a nested structure so that the state carried through the traversal stays as lean as the query allows.

Following a descendant query through rsonpath

Answering a query for every url value at any depth

A trace of how rsonpath streams a descendant query, following the paper's design; the query asks for a label anywhere in the document.

Step 1 of 5

Stream the raw bytes, do not build a tree

The query asks for every url field anywhere in a huge JSON document. Materializing a tree is infeasible, so rsonpath streams the raw bytes once with minimal memory.

Descendant means the label can appear at any depth or path.

Why it works

Most of the document is irrelevant. Because a typical query touches only a small fraction of a large JSON document → an engine that examines every byte wastes almost all of its work → so fast-forwarding over the irrelevant regions is where the speed comes from.
Streaming avoids the cost of building a tree. Because parsing a document into an in-memory tree can consume most of the query time and enormous memory → skipping the tree and processing the raw stream removes that cost → so querying at terabyte scale becomes feasible.
Splitting branchless scanning from branchy logic fits the hardware. Because SIMD excels at uniform branchless work while query logic is full of branches → running each in its own module lets the fast scanner feed the slow logic only what it needs → so both parts run near their best.
A sparse stack keeps the automaton cheap. Because tracking arbitrary child-and-descendant nesting needs a stack, yet a full stack is costly → a sparse depth-stack keeps only the minimal necessary depth → so the automaton handles general queries without paying full pushdown cost.
Descendants unlock a faster skip. Because a descendant query looks for a label anywhere below the current point → the engine can use SIMD substring search to jump straight to the next occurrence of that label → so rewriting a query with descendants often makes it dramatically faster, not just shorter to write.

What it costs (trade-offs and scope)

Deeply nested, ambiguous queries hurt. When a query nests descendants of the same repeating label (the paper’s example reaches for a type deep inside many nested inner elements), the query is highly ambiguous and the depth-stack grows deep, so performance drops sharply — only about four times faster than the slow baseline. The authors note no good implementation for such queries is known, even in theory.
The gain from descendants depends on document structure. Rewriting a query with descendants helps a lot when the target label is shallow and selective, but for some documents the descendant version makes rsonpath examine far more nodes than a child-based engine would (in one case about twelve times more), searching whole subtrees that hold no matches, so the gain can be negligible.
Low selectivity yields many short skips. When almost everything matches, the substring-search skipping degenerates into many short fast-forwards rather than a few long ones, so throughput is only mediocre — though still better than the deeply-ambiguous case.
Idiomatic wildcard can cost a skip. Supporting wildcards that step into object fields as well as array elements means some leaf-skipping optimizations no longer apply, which can make certain wildcard queries slower for both rsonpath and prior engines.
It targets a defined JSONPath fragment. The engine supports child, descendant, wildcard, and labels. Richer JSONPath features such as filters and arithmetic are outside the scope of this work.
The classifier-switching has to earn its keep. In principle a different specialized classifier is optimal for each automaton state, but switching has a cost, so rsonpath switches only when the expected benefit justifies it and otherwise relies on its flexible main classifier — a pragmatic limit on how finely it specializes.

The evaluation

Three streaming JSON query engines

Property	JsonSurfer	JSONSki	rsonpath
Streams with low memory	Yes	Yes	Yes
SIMD fast-forwarding
Descendant selector	Yes, slow
Wildcard into objects and arrays	Yes
Needs element type known in advance	No
Throughput			10 to 20 percent faster, above 10 GB/s with descendants

Three streaming JSON query engines, as compared in the paper. JsonSurfer is a general streaming engine that supports rich queries including descendants but runs at only about 200 megabytes per second. JSONSki is the SIMD-accelerated state of the art: fast, but it cannot express descendant selectors and its wildcard only steps into arrays, because it must know each selector's element type in advance. rsonpath, implemented in Rust, supports child, descendant, wildcard, and labels without that assumption, by separating a branchless SIMD classifier (which emits only currently-relevant events and uses SIMD substring search to skip to labels) from a depth-stack automaton with a sparse stack. The paper reports rsonpath matches or beats JSONSki on descendant-free queries (a 10 to 20 percent boost), and that rewriting natural queries with descendants can speed them up by up to an order of magnitude, exceeding 10 gigabytes per second on most tested queries. It is honest about limits: deeply nested ambiguous queries make the depth-stack grow and slow rsonpath down, and the benefit of a descendant rewrite depends on the document's structure.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

This paper closes a real and practical gap. The fastest way to query large JSON is to stream the raw bytes and use SIMD to fast-forward over irrelevant parts, but the leading engine of that kind, JSONSki, could not support the descendant selector — the very feature that makes JSONPath queries convenient, since it reaches elements at any depth without spelling out the path. rsonpath supports descendants and idiomatic wildcards without the advance knowledge of element types that blocked them, and it does so with a clean, reusable architecture: a fast branchless SIMD classifier that emits only the events a query currently needs, feeding a depth-stack automaton whose sparse stack stays as shallow as possible. The evaluation is convincing and, importantly, honest. On queries the old engine could already do, rsonpath is 10 to 20 percent faster, so descendant support costs nothing; and rewriting natural queries to use descendants can speed them up by up to an order of magnitude, mostly thanks to SIMD substring search that jumps straight to the next relevant label, reaching above 10 gigabytes per second on most tested queries. The authors are candid about where it struggles: deeply nested, ambiguous descendant queries make the stack grow and performance fall — a case they note has no good solution even in theory — and whether a descendant rewrite helps can depend on the document’s structure, sometimes making the engine search many subtrees that hold no matches. The engine also targets a defined JSONPath fragment rather than the full language with filters. The durable ideas are two: that on huge data the winning strategy is to touch as little of it as possible, and that separating fast branchless bulk processing from slow branchy logic is an abstraction that pays off well beyond JSON.

Background

Why touching as little data as possible is the recurring win

It helps to see rsonpath within a wider theme: whenever data is large, the biggest performance wins come from arranging never to look at most of it. Here the data is a terabyte-scale JSON stream and a query that touches only a sliver of it, so the whole design is organized around skipping — streaming instead of materializing a tree, fast-forwarding over irrelevant bytes with SIMD, and jumping straight to the next relevant label. The warehouse-scale memory-traffic work covered elsewhere on this site pursues the same instinct in the memory system, eliminating the data movement that carries nothing useful so that scarce bandwidth is spent only on transfers that matter. The common thread is that moving or examining data you did not need is pure overhead, and a system can often be redesigned so that the irrelevant majority is skipped rather than processed. rsonpath adds a second lesson worth carrying: the value of matching the shape of the work to the shape of the hardware. SIMD is superb at uniform, branchless scanning and poor at branchy decision-making, so the engine puts the branchless scanning in one module and the branchy query logic in another, and lets the fast one feed the slow one only what it must handle. As datasets keep growing faster than processors, both instincts — skip the irrelevant, and split work along the grain of the hardware — are likely to matter more, not less.

If you remember only three things

1. Querying large JSON at speed requires streaming: parsing the whole document into an in-memory tree is infeasible at scale because the tree eats enormous memory and parsing can be up to 90 percent of the runtime, while the query touches only a fraction of the data. The fastest streaming engines use SIMD to fast-forward over irrelevant parts of the document, but the state-of-the-art engine, JSONSki, cannot support the descendant selector (which reaches elements at any depth) and has only a partial wildcard, because it relies on knowing in advance whether each selector acts on an object or a list — the assumption descendants break. This excludes many natural, useful queries.
2. rsonpath, implemented in Rust, supports child, descendant, wildcard, and labels without any advance knowledge of element types. Its key structure is a separation between a fast branchless SIMD classifier — which consumes the raw stream and emits only the events the query currently needs, fast-forwarding over the rest — and a depth-stack automaton that runs the branchy query logic on those events. The classifier is state-driven, toggling which symbols it recognizes to match the automaton's current need, and for descendants it uses SIMD substring search to jump straight from one shallowest occurrence of a label to the next. The depth-stack automaton is as expressive as a pushdown automaton but uses a sparse stack kept as shallow as possible, giving the best of stackless and full-stack designs.
3. On queries the prior engine could already handle, rsonpath is 10 to 20 percent faster, so descendant support costs no performance; and reformulating natural queries with descendants can speed them up by up to an order of magnitude, exceeding 10 gigabytes per second on most tested queries, largely thanks to the SIMD substring-search skipping. The paper is honest about limits: deeply nested, ambiguous descendant queries make the depth-stack grow and slow the engine down (a case with no known good solution even in theory), the benefit of a descendant rewrite can depend on the document's structure, and the engine targets a defined JSONPath fragment rather than the full language. The durable lessons are that on huge data the winning move is to touch as little of it as possible, and that separating branchless SIMD scanning from branchy query logic is an abstraction useful well beyond JSON.

Check yourself

Check your understanding

1. Why is streaming, rather than building an in-memory tree, the only feasible way to query large JSON?
2. Why could the state-of-the-art SIMD engine (JSONSki) not support descendant queries?
3. What is the core architectural idea of rsonpath?
4. The paper reports that rewriting a query with descendants sometimes helps enormously and sometimes barely at all. What explains the difference?

Sources

The paper is “Supporting Descendants in SIMD-Accelerated JSONPath” by Mateusz Gienieczko, Filip Murlak, and Charles Paperman, published at ASPLOS 2023, DOI 10.1145/3623278.3624754. The authors are at the University of Warsaw and the University of Lille.

This explainer is based on the full text of the paper, obtained as the open-access (CC-BY) author copy deposited in the HAL open archive (record hal-04398350). The problem framing (the ubiquity of JSON, the cost of building an in-memory Document Object Model for large data, the fraction of time spent parsing, and the need for streaming), the state of the art (simdjson’s SIMD parsing, JSONSki’s SIMD fast-forwarding, its lack of descendant support and partial wildcard, and its reliance on knowing element types in advance), the contribution (an engine for the JSONPath fragment with child, descendant, wildcard, and labels without advance type knowledge; the modular separation of a branchless SIMD classifier from a query automaton; the depth-stack automata with a sparse stack; the state-driven and multi-classifier design; and the SIMD substring-search skipping to labels), the Rust implementation named rsonpath, and the experimental findings (the 10 to 20 percent boost over the state of the art on descendant-free queries, the up-to-an-order-of-magnitude speedups from descendant rewrites, throughput above 10 gigabytes per second on most tested queries, the roughly 200 megabytes per second of the JsonSurfer baseline, and the honest limitations for deeply nested ambiguous queries and structure-dependent rewrites) are all drawn directly from the paper. Background explanations of JSON, JSONPath selectors, SIMD, streaming, and pushdown automata are standard and provided to make the paper’s contribution understandable.