Receipts
Every number below is computed in your browser from New York City 311 requests. Click one to see the requests it came from.
Loading the engine.
| borough | requests | mean hours |
|---|
Where it came from
The plan behind the table, one step per line. The sentences are generated from the plan by the engine, not written by me, so they can't drift from what it does.
The plan as JSON
The requests
What if some of them are wrong?
A trace says which rows went into a number. It doesn't say which of them matter. For the selected number, the engine works out what it would be without each request, all at once, and ranks the requests by how far they move it.
requests that move it most.
For a count, every request moves the number by exactly one, so there is nothing to rank. Switch to the mean or the median above.
The data checks itself
A receipt is only worth something if the data it points to is the data that was published. So the engine doesn't take the snapshot's word for it. Before it will run anything, it decodes the files and re-derives every hash from the bytes: each block of 65,536 rows, each column, the text dictionaries, the side tables and the manifest. It also checks the sort order that row numbers depend on.
A flip that breaks the compressed data, or points a value past its dictionary, is caught while decoding, and the reader says where. Every read is bounds checked, so a broken file gives an error, never a crash. A flip that decodes cleanly changes a value, and the hash of that column's chunk no longer matches.
How it works
I built Receipts to answer one question about any number derived from public data: which rows is it made of, and what happens to it if some of them are wrong? It has four parts.
Snapshots. A command line tool pages through the city's Socrata API, keeps the raw responses, and builds a typed, sorted, compressed Arrow file. Every chunk, column and file is hashed with BLAKE3, and the hashes roll up into one snapshot hash. Cleaning only changes how a value is stored. It never decides a value is wrong. Judgements like "a request can't close before it opens" belong in the plan, where you can see them and turn them off, as the checkbox above does.
Plans. A plan is a list of steps: scan, filter, map, aggregate, sort, limit. The engine checks names and types before running, explains any error in a sentence, and hashes each step together with its inputs, so two plans that share a prefix share hashes.
Lineage. The operators already know which input rows produce each output row. A filter knows which rows it kept, an aggregate knows its groups. I keep those mappings instead of throwing them away. That costs four bytes per row for each filter, sort or aggregate and nothing for scans and maps, and a trace becomes a few array lookups. A property test runs random plans on random tables against a slow reference interpreter that carries a set of source rows through every operator, and the two must agree exactly.
Counterfactuals. This was the hardest part to get exactly right. The fast way to remove a row from a mean is to subtract it from the sum. With floating point, that answer can differ in the last bits from a fresh run, because addition order matters. So the engine recomputes only the groups that lost a row, from their remaining rows in the original order, with the same aggregate code the executor uses. When that shortcut isn't valid, for example when a limit runs before the aggregate and removing a row pulls another one in, it re-runs the plan. Both paths give the same bits as a full re-run, and a property test checks that.
About this demo
The page loads one month of real data so it stays quick on a phone. The full project is built for two years of requests, about 7.1 million rows (benchmarks). This page uses the single threaded build, because GitHub Pages can't send the headers that browser threads need.
Prior work
Tracing a derived value back to its source rows is an old database problem. Cui, Widom and Wiener worked it out for relational views in Tracing the lineage of view data in a warehousing environment (ACM TODS, 2000). Asking what a result becomes when source rows are removed is deletion propagation, studied by Buneman, Khanna and Tan in On propagation of deletions and annotations through views (PODS 2002). Snapshots use the Arrow IPC file format and BLAKE3 hashing.
Source on GitHub. Data from NYC Open Data, under the city's terms of use. Set in ET Book; layout after Tufte CSS.