JSONSki: streaming semi-structured data with bit-parallel fast-forwarding

Pulling one field out of a gigabyte of JSON means reading the whole gigabyte, because you cannot know which parts to skip without parsing them and parsing them is the expensive thing you were trying to avoid; this paper (UC Riverside, best paper at ASPLOS 2022) breaks that circle by finding the end of an irrelevant object through counting braces in a 64-bit bitmap rather than by tokenising it, and ends up skipping over 95 percent of the input on every query it tries — 12.3 times faster than the streaming tool it replaces and 4.8 times faster than the fastest SIMD parser, in a third of the memory.

The argument in one glance

Problem

Reading a gigabyte to extract a few kilobytes

JSON is the format services exchange data in and document databases store data as, and a typical query wants one attribute buried somewhere in a much larger record. The standard approach parses the whole record into an in-memory tree and then walks it. That means an upfront delay before any answer appears, and a tree that can occupy several gigabytes. One measurement cited here has parsing dominating over 80 percent of query evaluation time in a common analytics stack.
What people did

Evaluate the query while you read, and never build the tree

The streaming approach fuses parsing and query evaluation into one pass. As characters arrive, it recognises tokens and structures, tracks how far the query has matched using a pair of stacks, and emits results the moment they are found. Nothing is stored, so memory stays flat regardless of record size and there is no upfront delay at all. This is the right shape for the problem, and it is what the state-of-the-art streaming tools do.
Why it fell short

It still has to look at every character

Streaming avoids building the tree but not reading the input. Every character must be examined to recognise each token and each syntactic structure, because the parser cannot know where an object ends without following it to the end. Yet enormous portions of the input are obviously irrelevant to any particular query. The trouble is a circle: to skip a segment you must know where it stops, to know where it stops you must parse it, and parsing it is the cost you were trying to avoid.
This paper's idea

Find the end of a structure without parsing it

This paper (UC Riverside — Lin Jiang and Zhijia Zhao, which won the best paper award at ASPLOS 2022) breaks the circle with a cheaper way to answer the only question skipping actually needs answered. Load 64 characters into a machine word, build a bitmap marking the braces, and locate the end of an object by COUNTING rather than by parsing. Then use what the query itself reveals about the data — a path implies the type of everything along it — to decide what to skip. Over 95 percent of the input goes unread on every query tested.

Why this problem is worth solving

The two established ways of processing this data both make a trade that streaming refuses, so it is worth being clear what each one buys.

The PREPROCESSING scheme reads the whole record first and builds something to query against — usually a parse tree, or in the faster tools a set of BITMAPS marking where the punctuation sits at each nesting level. Then it walks that structure to evaluate the query. This is what almost every JSON library does, and it costs an upfront delay before any answer emerges plus memory proportional to the input, which here means 2 to 3 gigabytes against a 1 gigabyte record. The STREAMING scheme instead fuses the two steps: it consumes characters as they arrive, tracks query progress on a stack as it descends through nesting levels, and emits matches immediately. Memory stays flat, there is no upfront delay, and the whole thing fits in cache. The catch is that it must still examine every character, because recognising each token and structure is how it knows where it is

The way out depends on a question much narrower than parsing, and on information the query was already carrying.

To skip an irrelevant object, a streaming parser needs exactly one fact: where that object ENDS. It does not need the tokens inside, the nesting, or the values — just the position of the matching close brace. That is a counting question, not a parsing question, and counting can be done on 64 characters at a time using bitwise operations. Deciding what to skip is separate, and the query supplies it. A path such as dollar-dot-place-dot-name says that place must be an OBJECT, since it has an attribute, so any array encountered at that level is irrelevant without reading it. JSON also guarantees an object cannot repeat an attribute name, so once a name matches, every remaining attribute of that object is dead. Neither fact requires looking at the data. Both were sitting in the query and the language definition the whole time

What people did before, and where it broke

Parse into a tree, then walk the tree. What nearly every JSON library does, and it is simple and general.
But you pay for the whole document before answering anything. An upfront delay, plus a tree occupying 2 to 3 gigabytes for a 1 gigabyte record, and the fastest such tool refuses records over 4 gigabytes entirely.
Use SIMD to build the structure faster. Recent parsers use wide instructions to locate the punctuation quickly, which genuinely speeds up the build.
But it is still a build, over the entire input. The bit-parallelism is spent finding metacharacters, and the resulting index still covers every byte, whether the query cares about it or not.
Stream instead: evaluate as you read. No tree, no upfront delay, flat memory, and everything stays in cache.
But every character still gets examined. Recognising tokens and structures is how the parser knows where it is, so the cost scales with the input rather than with the answer.
Filter out whole records before parsing them. A published technique discards records that lack substrings the query needs.
But it works between records, not inside one. If the query matches most records, it saves nothing, and it cannot help at all with a single large record.
The gap. Everyone was making the traversal cheaper. Nobody had asked whether most of the traversal could simply not happen, because the obvious way to find out what to skip is to parse it.

How a parser learns to skip what it never read

Breaking the circle between knowing what to skip and having to parse it

Fuse parsing and query evaluation into one pass

Consume characters as they arrive, recognise tokens and structures, track how far the query has matched using a stack that mirrors the nesting, and emit results immediately. This is the existing streaming approach: no tree, flat memory, no upfront delay, and it is the foundation everything else builds on.
↓ →
Rewrite the streaming loop as recursive descent new

The prior design is a formal automaton with thirteen transition rules, which makes inserting ad-hoc skips awkward. Replace it with one function per grammar structure, calling each other recursively, so the nesting stack becomes the ordinary call stack and a skip is just an early jump inside a function.
↓ →
Read the query for information about the data new

A path expression implies the type of everything along it: an attribute that has attributes must be an object, one with an index range must be an array. Combined with the rule that a JSON object cannot repeat an attribute name, this identifies whole categories of irrelevant material before a single byte is examined.
↓ →
Enumerate what can be skipped, in five kinds new

Jump to the next attribute whose type the query wants. Jump over an attribute whose name failed to match. Emit a matched value without inspecting it. Jump to the end of the current object once a name has matched, since no second match is possible. And jump over array elements outside a requested index range.
↓ →
Build a partial bitmap from wherever you happen to be new

Streaming has no global view — only what it has already seen — so it cannot precompute an index. Instead, from the current position, mark the characters up to the next occurrence of one chosen punctuation mark in a single machine word, excluding any that appear inside strings. That short variable-length bitmap is the unit everything operates on.
↓ →
Find the end of a structure by counting, not parsing new

To leave an object, count close braces against the number of open braces still unmatched, word by word. When a word contains at least as many closes as there are outstanding opens, the object ends inside it, at a position the count identifies exactly. No tokens are recognised and no values are read.

Implemented in C++ using bitwise and SIMD instructions available on ordinary processors, evaluated on six real-world datasets of about 1 gigabyte each with twelve standard path queries.

The idea

The skip needs a much smaller answer than parsing provides. Everything turns on noticing that skipping an object requires knowing exactly one thing — where it ends — and that this is a counting problem rather than a parsing one. The paper proves the small fact that makes it work: if you know how many open braces are still unmatched, then scanning forward and tallying close braces tells you when you have left the object, and which close brace was the one that ended it. That tally runs over a bitmap of 64 characters at a time, so leaving a megabyte-long object costs a few thousand bitwise operations instead of a million character inspections. The values inside are never tokenised, the nesting is never tracked, the strings are never scanned except to mask out punctuation that appears inside them. This is the classic move of replacing an expensive general question with a cheap specific one that happens to be sufficient, and it is what dissolves the apparent circularity of needing to parse in order to know what not to parse. Finding that the question you actually have to answer is far narrower than the machinery you were using to answer it is the same ask-only-what-you-need discipline covered elsewhere on this site where a cheap sufficient test replaces a complete but costly analysis.

The query already described the data. The second half is almost free information that nobody had collected. A path expression is usually treated as something to match against, but it also constrains what the data must look like: an attribute that itself has attributes has to be an object, and one carrying an index range has to be an array. So the streamer knows, before reading anything, that an array appearing where the query wants an object is irrelevant in its entirety. The language definition contributes another constraint — a JSON object cannot contain the same attribute name twice — which means that the instant a name matches, every remaining attribute of that object is provably dead and can be jumped past wholesale. That single rule turns out to be the dominant source of skipping in five of the twelve queries evaluated, reaching 99.99 percent of the input in one of them. Neither constraint requires touching the data; both are consequences of things already written down. Extracting free constraints from a specification that was being read only as a thing to satisfy is the same the-spec-tells-you-more-than-you-asked move covered elsewhere on this site where a declaration written for one purpose turns out to license optimizations nobody was taking.

A technique does not survive the move from batch to streaming unchanged. Bit-parallelism was already being used on this problem, by well-known parsers, but always to build a complete index over the whole document before querying it. The paper is explicit that this cannot simply be carried across, because a streaming processor has no global view: it knows only what it has already consumed, so it cannot construct bitmaps between the start and end of an object it has not yet seen the end of. Two consequences follow. The abstraction changes — instead of complete per-level bitmaps, the unit becomes a partial bitmap of variable length running from wherever you are to the next occurrence of one chosen punctuation mark. And the algorithms multiply, because with complete indices a skip is a single lookup, whereas with partial context each of the five kinds of skip needs its own tailored procedure. The authors also had to abandon the existing formal streaming automaton for a recursive-descent design, purely because ad-hoc skips are easy to insert into recursive functions and awkward to express as transition rules. Rebuilding a technique around the information a new setting withholds, rather than porting it and hoping, is the same redesign-for-the-new-constraint discipline covered elsewhere on this site where moving a workload to a platform with different guarantees requires changing the algorithm rather than the packaging.

Skipping through a tweet

Evaluating one path query over a gigabyte of JSON without reading most of it

Following the paper worked example, a query for the name of the place attribute in a stream of geo-referenced tweets.

Step 1 of 5

Read the query and learn about the data

The path asks for the name inside place. Because place has an attribute, place must be an object — so anything that is not an object at that level cannot possibly match, whatever it contains. The first attribute in the record is an array of coordinates, and it is dismissed on type alone, without any of its contents being examined.

the same inference works the other way: an attribute carrying an index range must be an array
only the innermost level of a path escapes this inference, since a leaf could be of any type

Why it works

Skipping a structure needs only its end position, not its contents → that is a counting question answerable over a 64-character bitmap → so leaving a large object costs bitwise operations proportional to its length divided by 64 rather than character inspections proportional to its length.
A path expression implies the type of every attribute along it → material of the wrong type can be dismissed before it is examined → eliminating entire branches on information the query was already carrying.
JSON forbids an object from repeating an attribute name → once a name matches, the rest of that object provably cannot match → which is the largest single source of skipping in five of the twelve queries measured.
Streaming never materialises an index or a tree → memory stays flat at roughly the input buffer size → giving about 1 gigabyte against 2 to 3, and continuing to work at 72 gigabytes where the alternatives fail.
Skips are ad-hoc and varied by nature → expressing the parser as recursive functions rather than transition rules makes each one a local early exit → so five distinct families of skip fit into the design without complicating it.

What it costs (trade-offs and scope)

What you skip, you do not validate. A conventional parser checks the whole document is well formed. Fast-forwarded segments get bracket pairing but not full syntactic validation, which is a real semantic difference, not just a speed one.
No support for descendant search. The query operator that matches at any depth is unimplemented, and the authors note it would limit skipping anyway, since descendant types cannot be inferred from the path.
On a single large record it loses to a parallel competitor. Lacking speculative execution, one thread of this system runs 48 percent slower than the index builder using 16 threads, though it still beats the 16-thread streaming tool by 28 percent.
The skip mix is wildly query-dependent. Every query skips over 95 percent overall, but which mechanism does the work swings from 0.01 percent to 99.99 percent between queries, and one family contributes meaningfully only at low selectivity.
Two of twelve results are extreme outliers. In two queries all matches happen to appear early in the stream, so almost everything is skipped and the time drops to about 0.01 seconds, which flatters the averages.

The evaluation

Six real datasets — tweets, two product catalogues, map directions, a postcode lookup and Wikipedia entities — each normalised to about 1 gigabyte, with nesting depths from 4 to 12, and twelve path queries spanning wildcards, index ranges and varying selectivity. Comparisons cover both processing schemes and both parallelism strategies: a character-by-character streaming tool, a plain tree parser, a SIMD tree parser, and an index builder that also uses SIMD and speculation. Each dataset is tested both as one large record and as a sequence of small ones, since only the latter exposes parallelism across records.

Property	Build a parse tree first	Build structural indices first	Stream and skip
When the first answer appears
Memory for a 1 gigabyte record
How much input gets examined
Behaviour at 72 gigabytes
Parallelism available

On a single large record the streaming design runs 12.3 times faster than the character-by-character streaming tool, 4.8 times faster than the SIMD tree parser and 3.1 times faster than the index builder. On many small records with 16 threads it is 9.5 and 3.0 times faster than those two respectively, scaling 10.3 times across 16 cores. Every one of the twelve queries skips more than 95 percent of its input.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

The most substantive limitation is not about speed. A parser normally validates that a document is well formed, and material that is fast-forwarded is by definition not examined — the implementation retains bracket pairing but not full syntactic checking, so this is a genuinely different guarantee from the tools it is compared against, and the paper says so rather than glossing it. The query language is also incomplete: the operator for matching at any depth is unimplemented, and the authors observe it would blunt the technique anyway, since the type inference that drives much of the skipping depends on knowing where in the path you are. On raw numbers, one gap is reported honestly: without speculative execution, a single thread of this system is 48 percent slower on one large record than the competing index builder running 16 speculative threads, though it still beats the 16-thread streaming tool by 28 percent, and the authors see no design obstacle to adding speculation. Read the aggregate skip ratios with care too. All twelve queries exceed 95 percent, but the contribution of each mechanism swings between 0.01 and 99.99 percent depending on the query, and one of the five families only matters when selectivity is low. Finally, two of the twelve queries happen to find all their matches near the start of the stream and finish in about 0.01 seconds, which pulls the reported means down.

Background

When the question you must answer is smaller than the machinery answering it

This paper sits in the site’s compilers and data-processing clusters and rhymes with several ideas covered elsewhere on this site. Its central move — replacing an expensive general operation with a cheap specific test that happens to be sufficient, here counting braces in a bitmap instead of tokenising an object — is the same cheap-oracle bargain the compiler consistency page makes when it replaces semantic reasoning with a diff, and the same reduction the sparse computation pages perform when they make skipping the empty parts a first-class operation rather than a special case. Its second insight, that a specification written to be satisfied also constrains what the data must look like and therefore licenses skipping, rhymes with the graph pattern mining pages, where knowing the pattern in advance avoids enumerating candidates that cannot possibly match. Its insistence that bit-parallelism could not simply be carried over from the batch setting, because a streaming processor has no global view and must work from partial context, is the same redesign-for-the-new-constraint argument the serverless graph processing page makes about porting a framework onto a platform with different guarantees. And its trade of complete validation for speed is a familiar shape from the approximation pages, where the honest question is always which guarantee was quietly given up.

If you remember only three things

1. A query over a large JSON record wants a small part of it, but both established approaches read all of it. Building a parse tree or a structural index costs an upfront delay and 2 to 3 gigabytes against a 1 gigabyte record, with one popular tool refusing records over 4 gigabytes. Streaming avoids the structure by fusing parsing with query evaluation, keeping memory flat and emitting matches immediately, but it still examines every character — because knowing where you are requires recognising every token. Large parts of the input are plainly irrelevant, yet identifying them seems to require the parsing you wanted to skip.
2. The circle breaks because skipping needs a much smaller answer than parsing gives. To pass over an irrelevant object you need only its end position, which is a counting question: given how many open braces are still unmatched, tally close braces 64 characters at a time in a bitmap until a word holds enough, and the count names the exact brace that closes it. Nothing inside is tokenised. What to skip comes free from the query, since a path implies the type of every attribute along it, and from the language itself, since a JSON object cannot repeat an attribute name — so the moment a name matches, the rest of that object is provably dead.
3. The result skips over 95 percent of the input on every one of twelve queries across six real datasets, running 12.3 times faster than the streaming tool it replaces, 4.8 times faster than the fastest SIMD parser and 3.1 times faster than the fastest index builder, in about a third of the memory, and still working at 72 gigabytes where the alternatives run out. The costs are real and stated: fast-forwarded material is not fully validated, the any-depth query operator is unimplemented, and without speculative execution a single thread loses to a 16-thread competitor on one large record by 48 percent.

Check yourself

Check your understanding

1. Skipping irrelevant parts of a JSON stream seems circular: to know where a segment ends you must parse it, and parsing is the cost you wanted to avoid. Predict how the circle is broken.
2. Deciding what to skip is separate from knowing where it ends. Predict where that decision comes from, given that the streamer has not read the data.
3. Existing SIMD-based JSON parsers already use bit-parallelism heavily. Predict why their technique could not simply be carried into the streaming setting.
4. The system reports skipping over 95 percent of the input on every query and beating every competitor on a single record. Predict what it gives up in exchange.

Sources

Lin Jiang and Zhijia Zhao. “JSONSki: Streaming Semi-structured Data with Bit-Parallel Fast-Forwarding.” ASPLOS 2022, Lausanne. University of California, Riverside. DOI 10.1145/3503222.3507719. The paper received a best paper award at the conference.
Full text of the paper was used for this explainer, including the background on preprocessing and streaming schemes in Section 2, the recursive-descent streaming model and the five groups of fast-forward opportunities in Section 3, the structural interval abstraction and the counting-based pairing algorithms in Section 4, and the performance, memory, fast-forward ratio and scalability measurements in Section 5.
The authors released their implementation publicly.