Indexing Where the Answer Cannot Be: Skipping Blocks on an Inverted Regex, 3.10 s to 0.11 s

Out of 92,239,125 lines, exactly one was a hit.

I build a search tool for very large text files, and one of its two commands keeps a persistent index. Asking it for the lines of a 3 GB OpenStreetMap XML file that do not match ^ +< returns a single line — and the build before this one still ran the regular expression over all 92 million of them to find it.

This post is about the index we added to avoid that, what it bought, and the fairly large class of queries it does nothing for.

Why a normal index cannot help here

An inverted index — the ordinary "which chunks contain this token" kind — answers one question: where is it? Search for a literal and every chunk without it can stay closed.

That does not invert. The answer to -v '^ +<' is not "chunks without ^ +<"; it is "lines that do not match it", and those lines sit inside the very chunks that do contain matches. Skip a chunk because the pattern occurs in it and you silently drop the non-matching lines living there.

The same hole opens for any regular expression with no mandatory literal to prefilter on — [0-9]{3}-[0-9]{4}" has nothing you can look up. Both cases degrade to scanning everything: 1.5 s for the inverted regex and 4.7 s for the plain one over 3 GB, even with the file already decompressed and indexed.

The idea: index the shape of each line

Huge machine-generated files have far fewer kinds of line than lines. The same row repeats for millions of lines with different numbers and different words in it. So throw away what differs:

• runs of digits become 9
• runs of letters become a
• runs of bytes above 0x80 become u
• punctuation and whitespace are kept as-is
• truncate at 160 bytes and flag the skeleton as partial

<tag k="highway" v="residential"/> becomes <a a="a" a="a"/>.

Across 92.24 million lines there are 1.395 million distinct skeletons, and the most common 65,534 cover 98.56% of all lines. Number those, store the per-block arrays of line numbers (u16, zstd-compressed) in the index, and the query becomes:

1. Run the regular expression against the dictionary — tens of thousands of entries, about 5 ms.
2. Label every shape always matches, never matches, or undecidable.
3. Open only the blocks that hold lines to emit or lines marked undecidable.

Inverting is now free: you read the same table backwards. The 1 MB blocks that cannot possibly contain an answer are never decompressed.

The numbers

Mac (Apple M4, 10 cores, 32 GB, external USB SSD), 3 GB OpenStreetMap XML, hot cache, against ripgrep 15.2.0 with hit counts verified equal.

Query	Hits	ripgrep (s)	index-based (s)	ratio
^ +< inverted regex	1	3.10	0.11	28.18x
=" inverted literal	7,698,790	2.08	0.54	3.85x
[0-9]{3}-[0-9]{4}" regex	14,951	2.35	0.42	5.60x

Only the first row is the skeleton working. The other two come from the index itself and are unchanged by it — which the isolated measurement makes obvious. Toggling the mechanism off on the same file (development build, median of three, output to /dev/null):

Query	off (s)	on (s)	direction
^ +< inverted regex	1.510	0.062	24.4x faster with it on
^ +< regex	4.721	2.378	1.98x faster with it on
=" inverted literal	0.518	0.522	level, marginally slower with it on
[0-9]{3}-[0-9]{4}" regex	0.405	0.420	level, marginally slower with it on
\d+\.\d{6,} regex	0.393	0.413	level, marginally slower with it on
=" plain string	2.815	2.896	level, marginally slower with it on

Three regimes. Decidable by shape with few hits: 24x. Decidable with many hits: 1.98x, because writing 92 million lines becomes the ceiling. Not decidable: 0.92x to 0.99x — slightly slower, since the per-block arrays get read for nothing. [0-9]{3}-[0-9]{4}" has hits in 703 of 724 blocks; there is nothing to skip.

One caveat on the first table: the harness flagged ripgrep's hot run on the inverted regex as not having warmed properly (cold 3.57 s, hot 3.10 s, nearly identical). Cold against cold is 3.57 s to 0.18 s, 19.8x. The order of magnitude survives either reading.

The part that is useful without my tool: three things that decide whether a summary index pays off

This generalises past my file format, and the failures were more instructive than the wins.

1. Is the summary set small enough to evaluate the whole query against? The entire trick is that you can take a pattern written for the real data and apply it, unchanged, to the summary — but only if the summary is small enough to scan exhaustively per query. 65,534 entries at ~5 ms, fine. We also tried this on a bundle of 60,000 Linux kernel source files: the shapes scattered into 4.085 million distinct values, the top 65,534 covered only 70.65% of lines, and we now refuse to build the index below a 90% coverage threshold. Source code does not repeat its line shapes. Logs, XML and CSV do.

2. How small is the undecidable fraction, and where does it live? This nearly killed the whole thing. Lines that missed the dictionary — just 1.4% of them — turned out to be spread across every block. Undecidable means "go read the original", so a single stray line per block keeps that block open. The inverted regex with its one hit still opened 672 of 724 blocks: less than a tenth skipped, for a 6.3% larger index. 1.4% sounds negligible; distribution is what matters, not the percentage.

The fix was to spend part of the budget on precision instead of coverage: when the shape count overflows, reserve 8,192 of the slots for 16-character prefixes of a skeleton, and give every dictionary-miss one of those. Coverage of the numbering went to 100.00%, blocks opened went 672 → 1, and that is where the 24.4x came from. Note what that means in general: an exact index of 98.6% of your data can be worth less than an approximate index of 100% of it.

3. Does it fail safe, and have you proved that? A summary that wrongly says "cannot match" does not produce an error — it produces a quietly incomplete answer, which is the worst failure mode a search tool has. Everything ambiguous has to fall to "undecidable", which is always safe because it just costs a read. Concretely, that meant: \d matches full-width digits in .NET, so a shape containing u that doesn't match goes to undecidable rather than never-matches; lines over 64 KB become "other" because the matcher only looks at the first 64 KB; and a small purpose-built parser decides whether a pattern is even eligible, rejecting anything it isn't sure about.

Proving it took a randomised cross-check: 1,500 lines × 800 patterns = 1.2 million pairs, comparing the shape verdict against running the regex on the actual text, with invalid UTF-8, control characters and full-width digits in the corpus. Zero mismatches. Plus byte-for-byte output comparison with the mechanism on and off across 18 patterns, CRLF and BOM variants, bundled archives, and lines spanning block boundaries. If you build something that decides not to read data, budget more time for this than for the optimisation itself.

What it costs

• The index grows 6.3% (251.8 MB → 267.8 MB on the 3 GB file), and 3.4 s to build the section.
• Queries that cannot skip get 1% to 8% slower. For plain strings there is now a cut-off — if more than half the blocks would be opened, don't bother — but the equivalent on the regex path isn't implemented yet.
• Everything above is one machine. The Windows and Linux builds pass the same correctness tests; I don't compare seconds across operating systems.

I make this tool — uvf is the free build, uvp is the paid one — so treat the ratios as the author's own measurements and the method as the part worth checking.

• Full write-up with every pattern and timing: https://uvp.y42u.net/en/blog/uwview-fs02-line-skeleton-en/
• Source: https://github.com/amru195704/UwView