Querying S3 without Parquet

Introduction

The last post dissected a Parquet file. After opening up the footer-at-the-end promise, the per-row-group min/max statistics and the Bloom filters, a question in the opposite direction remained. Is there a way to not use Parquet? Can the JSONL we already accumulate be queried efficiently as it is?

This post is an experiment. The material is synthetic data shaped like a notification delivery log. 2.5 million records a month, split into 30 daily JSONL files and uploaded to a real S3 bucket, 590MB in total. Assume roughly 200,000 users, and each leaves about 12 records a month. It mimics data like delivery logs, audit logs and event archives — written every day, queried rarely.

Now pull “user X’s deliveries last month” out of it. With no index, the only way is to download all 30 files and scan them. Measured, it took 15.7 seconds — and the same query took 115 seconds on another day. With 590MB on the wire, time is bandwidth, and bandwidth is out of our control. We read 2.5 million records to fetch 12 records, 3KB.

A database would solve this, but attaching one to an archive read a few times a month is overkill. Instead, S3 supports the Range header on GET. Any byte span of a file can be fetched, and at that moment S3 becomes a read-only remote disk. Which also means what a DB does on a disk — an index — can be built directly on top of it. So we built one after another and measured.

Range binary search

Daily files accumulate in delivery id order. Can a record be found with no index, on the strength of sorting alone?

The method is to move an in-memory binary search onto round trips. Fetch just 4KB at the midpoint with Range, parse the first complete record after a newline, and compare its id. Smaller than the target, drop the left half; larger, drop the right. When the remaining span narrows below 64KB, fetch that span whole and scan it.

Ten probes halving an 18MB daily file down to the target.

Measured: 0.81 seconds and 0.17MB transferred — 1/100 of the full scan. Grow the data fivefold and, on a log scale, 0.6 seconds merely becomes 0.8. The client code fits in 30 lines. Sorting itself is the index.

But see this trick for what it is. The knowledge that “this file is sorted by id” lives not in the file but in the client code. There is no metadata inside the file; outside knowledge is imitating metadata. This distinction follows us to the end of the post.

Binary search by key

The trick fails for user queries. user_id is scattered along the time axis, so an id-sorted file pins down no position at all. Can keys outside the sort order be found too?

In a DB this is where a secondary index goes. The same thing can be built on S3. On every append, record one line of [user_id, day, offset, length] from a byte counter, and at the daily close, sort by user_id and roll everything into a single sidecar file. The write-side cost is an O(1) record plus one batch sort.

The index file is itself a file sorted by user_id, so the Range binary search used on the data applies to the index again. Binary-search it by the key user_id to find the contiguous span holding the user’s 12 lines, then pinpoint-GET the data with each line’s (day, offset, length).

Scattered pointers become one contiguous span through sorting, and that span leads to the data — five steps.

Measured: 0.77 seconds, 24 requests, 175KB transferred — 1/3,400 of the full scan. A closed log is immutable, so no elaborate structure is needed. A sorted array is a finished index.

It is not free, of course. This index serves only equality lookups returning a few dozen rows, so it is useless for aggregation; every new query axis means building one more index; and if a single record is missed it can never be found, so completeness checking becomes the app’s responsibility. We settle this bill in the conclusion.

Updating the index more efficiently

Every trick so far presumes a “sorted, immutable file”. But data arrives daily. Inserting a new key into the middle of a sorted array shifts everything behind it — O(N) — and that price cannot be paid every day. Can sorting survive continuous updates? Databases hit this problem decades ago, and the answer forked in two.

B-tree

A B-tree keeps the ordering in place, at insertion time. With a disk page as a node holding hundreds of keys, even hundreds of millions of records make a wide, shallow tree only 3–4 levels deep. A lookup is one path: compare keys at the root, pick one child, descend. Range scans are cheap because the leaves form a linked list — find the start and scan sideways.

Key comparisons at the root picking one child, and the leaf linked list handling ranges.

The price of read optimization is paid by writes. The key’s value decides where it lands, so an insert is an in-place edit of a leaf page, and when a page fills, the split propagates to the parent. In-place edits turning into splits, splits into random I/O — here is the write side of the story.

LSM tree

An LSM tree gives up sorted insertion. Writes land only in an in-memory memtable; when it fills, the whole thing is sorted and streamed out sequentially as an immutable SSTable. Updates and deletes never touch old files either — a new value or a tombstone is simply laid on top. The scattered layers are merged back into one sorted run by background compaction. Instead of preserving order at insert, it re-earns order by rewriting.

One cycle from memtable writes through flush, layer buildup and compaction.

This time reads pay for optimal writes. A key lives “wherever it was written most recently”, so a lookup sweeps from the memtable down through the layers, with a per-file Bloom filter cutting the wasted stops. A read walking the layers and stopping the moment it finds the key.

Measuring both trees

We built both for real. The B-tree packs 4KB pages into a single file — 1 root, 3 internal, 785 leaf pages; one page read is one Range GET. The LSM has 30 daily SSTable runs plus a manifest holding each run’s Bloom filter and fence pointers. The target query is the same single user’s 12 records for the month, and all six paths were measured as the median of three runs, with results cross-checked for agreement.

Reads

The numbers say two things. First, a tree’s worth is round trips. The binary search’s 23 sequential round trips shrink to 3 — the depth of the tree — and time falls below half. Keep the upper levels in memory (what a real DB’s buffer pool always does) and only the single leaf round trip remains. Second, LSM read amplification is billed as request count. Checking all 30 runs without compaction costs 342 requests, and since S3 bills by count, not size, that is paying 15× for the same answer. Bloom filters ruled out the 21 days without the user at zero requests, and after compaction it lands at 13 requests.

We also built both trees keyed by id and measured single-record lookups: the B-tree at 0.12s and 2 requests with upper levels resident, the LSM at 0.13s and 2 requests. Notably, since id increases monotonically with time, per-run min/max alone picked the one SSTable — no Bloom filter even needed. Why time-series keys suit LSM shows up directly in the measurements.

Writes

The cost of folding in one day — 83,333 records. S3 objects can only be rewritten whole, so the B-tree kept each page as its own object and did a read-modify-write per page.

68,145 users were active that day, and they touched all 785 leaf pages. When keys scatter across the whole range, “in-place edit” is in place in name only — it is effectively a full rewrite with random round-trip costs added on. The LSM’s day, by contrast, is one sequential write, one PUT. On object storage, LSM wins structurally.

Append daily, sort at the close, merge monthly when needed — that design is an LSM with a one-day cycle. The daily close is the flush, the monthly merge is the compaction, the manifest is the Blooms and fences. There is a reason log-archive designers arrive at LSM without knowing LSM.

Comparing with Parquet

The same user query through Parquet and DuckDB takes 0.89 seconds — slightly slower than the index binary search, slower than the trees. But the round-trip structure is fundamentally different. Every index we built needed search round trips to find “where to read”. Parquet does not search: the metadata footer’s position is promised to be the end of the file. Read 30 files’ footers in one parallel round trip, pick the needed row groups by the footers’ min/max statistics, read just those chunks in a second parallel round trip — done.

One promise — the footer sits at the end — and the whole flow finishes in two parallel round trips, no search.

Lay the same query out along four paths and the sequential depths split into 3, 13, 5 and 2.

Even when times look alike, structure decides round-trip depth. Move to aggregation and the gap widens. A one-day status aggregation is Parquet 0.54 seconds versus JSONL 4.0; a full month is 6.6 versus 115. Range binary search, index binary search, B-tree, LSM — none of them can do anything here. They are all equality-lookup structures that only know “where the matching records are”; summarizing millions of rows collapses under one round trip per result. Parquet is column-oriented and fetches only the needed column chunks.

Wrapping up

Back to the opening question. JSONL can be queried as it is. A sorted file yields to Range binary search, an unsorted key to a sorted sidecar index, and updates to a B-tree or an LSM. Speed holds up too: 0.12 seconds for a single record beats Parquet’s 0.3–1.7.

The verdict is still Parquet. The difference is not speed but whether the app understands the index or the engine does. Every index we built is the app’s property. Add one query axis and the index, the backfill, the consistency checks and the query code all grow together. The moment a join is needed, an index is not enough — the app must write the executor too. Stitching a handful of rows with an index nested loop holds up, but a large join means one round trip per row or reinventing hash join. With Parquet, all of it belongs to the engine after one line in the closing batch: COPY ... ORDER BY user_id ... PARTITION_BY dt. The date partition acts as the primary index, the in-partition sort as the secondary, the row group size as the index granularity — baked into the format, with no separate index files.

So if you query on S3, use Parquet. Keep ingest and the archive in JSONL — append is simple and humans can read it — and bake a query copy into daily Parquet. The hand-built indexes and trees stay in reserve for the day some path gets a strict latency SLA. The primitive that sorting is an index holds on S3 too; the app just has no reason to carry it.