DEV Community: amru195704

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

amru195704 — Tue, 27 Oct 2026 10:47:03 +0000

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:

Run the regular expression against the dictionary — tens of thousands of entries, about 5 ms.
Label every shape always matches, never matches, or undecidable.
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

Storing Legacy Encodings as UTF-8 Inside the Index: 5.4x to 38.8x Over ripgrep -E, and the Line-Number Bug That Nearly Stopped It

amru195704 — Thu, 22 Oct 2026 04:57:37 +0000

The decode ran on every query.

I build a search tool for very large text files, and one of its two commands keeps a persistent index. On a 3 GB Shift-JIS file, that index removed the second read of the file but not the second decode — every query still turned 3 GB of CP932 bytes into characters before it could decide anything.

This post is about moving the index to UTF-8: what it bought, what it cost, and the one decoding detail that quietly corrupted line numbers until we caught it.

Up front: the numbers

Measured on a Mac (Apple M4, 10 cores, 32 GB, external USB SSD), on OpenStreetMap XML (2,892 MB) converted with iconv to each encoding, against ripgrep 15.2.0 with -E <encoding> so it decodes the same text. Cold means the page cache was purged and ten seconds elapsed; hot is the run straight after. Two runs combined:

File	ripgrep -E (s)	index-based search (s)	ratio
Shift-JIS 2,887 MB, plain string	4.44	0.48	9.25x
Shift-JIS, `-i`	4.79	0.79	6.06x
Shift-JIS, regex	4.69	0.81	5.79x
Shift-JIS, inverted match	6.53	1.20	5.44x
EUC-JP 2,887 MB (range over 7 patterns)	—	—	5.38x to 23.26x
UTF-16LE 5,765 MB (range over 7 patterns)	—	—	8.06x to 38.79x

And the loss, which matters more than the wins: the pass that builds the index is slower than ripgrep — 4.93 s vs 3.35 s on Shift-JIS, 5.01 s vs 3.32 s on EUC-JP, 7.76 s vs 6.53 s on UTF-16LE. For a file you search once, rg -E is the right tool and nothing here changes that.

Output was compared against ripgrep on 7 patterns across 3 encodings — 21 queries, byte-identical, same exit codes.

Why the index kept the source encoding in the first place

Not an oversight. The index records the byte offset of every line in the source file, and several features depend on those offsets lining up: opening the original file in the viewer and injecting an index a CLI run produced, and restoring the original file from the index.

Convert the text and every offset moves. A two-byte Shift-JIS character is three bytes in UTF-8, so line 400,000 no longer begins at the same byte. An index with shifted offsets injected into a view of the source file shows the wrong lines.

So the change was not "call a converter". It was: convert, and then make sure a converted index can never reach a code path that expects source offsets. In practice that meant giving the converted format its own version number, refusing to read older ones, and making the verification step (length plus timestamp, with the header timestamp written as 0) fail by construction for every injection path. The converted index is always opened standalone.

The part that is useful without my tool: three things that bite when you move text to UTF-8

This is the section I would have wanted to read before starting.

1. A naive decoder can eat your newlines. The default CP932 decoder in .NET treats 0x82 0x0A — the lead byte of a two-byte character followed by a line feed — as one character, and the newline disappears. Decode a damaged or truncated Shift-JIS file as a single stream and you silently end up with fewer lines than the file has, with every line number after that point wrong. Our fix: when the newline count of a decoded region does not match the source, decode that region line by line. If you are writing anything that reports line numbers, test with a file whose last character is cut in half.

2. "Round-trips cleanly" is not one property, it is two. Character-identical and byte-identical are different promises. Characters with two code points — the NEC-selected IBM extensions in CP932, where the same glyph exists at ED40 and FA5C — come back with whichever one your decoder normalises to. We ended up promising character-identical only, and saying so in the help text. Dropping the byte-comparison pass on the way in also took index construction from 9.67 s to 5.33 s, so the weaker promise paid for itself. If someone downstream verifies archives by hash, they need to know which promise they have.

3. Replacement characters are a UI decision, not a correctness one. The spec said use U+FFFD for undecodable bytes. But the viewer already displayed "・" for them, because that is what the platform decoder does. Storing U+FFFD in the index would have changed search output for existing users. We stored "・" instead, and the output stayed byte-identical to the previous release. Pick whichever you like, but pick it once, and make the decode path and the display path agree.

A fourth, smaller one: UTF-16 at scale found a latent bug. Searching a 6 GB UTF-16 file in its original encoding failed with Specified argument was out of the range, because the carry-over bytes of a character split across a read boundary could exceed the read window. Files up to about 1,000 MB were fine, which is exactly why it survived so long. If you buffer-and-decode, write a test at a size larger than your buffer arithmetic assumes.

What the conversion actually bought

On a hot cache, the per-query numbers for the Shift-JIS file land on top of the numbers for the same content stored as UTF-8: 0.15 s vs 0.15 s for a plain string, 0.33 s vs 0.34 s case-insensitive, 0.30 s vs 0.32 s for a regex, 0.53 s vs 0.54 s for an inverted match.

That is the whole point, stated as a general rule: an index can absorb the per-query transformation, not just the per-query read. Decoding, newline counting, normalisation, case folding — these are not reads, they are "turning bytes into characters", and most of them can be done once at build time and stored.

The price is that your offsets stop matching the source. Which is a design problem, not a performance one: either you collapse to a single path, or you support both and test the product of every combination. I wrote the option to keep the source encoding, then deleted it, for exactly that reason.

What still does not work

EUC-JP supplementary kanji (JIS X 0212) are not decoded; they come back as "・".
Restoring to the original encoding got slower first: 7.88 s against 3.44 s for the previous build, which never converted at all — the old build 2.29x faster. Rebuilt as 8 MB chunks decompressed and converted in parallel and written in order, with chunk boundaries aligned to UTF-8 character boundaries (each chunk reads three extra bytes ahead; continuation bytes at the head belong to the previous chunk). That brought it to 1.03 s hot; in the release measurement it was 3.52 s cold, which includes writing 3 GB to disk.
Everything above is measured on one machine. The Windows and Linux builds pass the same correctness tests, but I do not 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-fs01-sjis-utf8-index-en/
Source: https://github.com/amru195704/UwView