An Index That Knows Where the Answer Cannot Be — Full Spectrum Part 2: 28.2x Over ripgrep on -E -v, and Level When Every Block Holds a Hit

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

Ask for the lines of a 3 GB OpenStreetMap XML file that do not match ^ +< and you get a single line back. The previous build still ran the regular expression over all 92 million of them. The index had removed the second read of the file, but inside that one read, every line was still being matched.

If the answer is one line, almost every megabyte of that file could have stayed closed. This post is about what you have to put in an index to be allowed to skip it.

Up front: 3.10 s down to 0.11 s on an inverted regex (28.2x over ripgrep), level when hits are everywhere, and the index grows 6.3%

A .uwvz (UwView Pro’s compression format plus index) now carries a dictionary of line shapes. Each line is reduced to a skeleton — runs of digits become 9, runs of letters become a, runs of bytes above 0x80 become u, punctuation and spaces stay — truncated at 160 bytes. The most common 65,534 skeletons get a number, and every 1 MB block stores the numbers of the lines that start in it. At query time the regular expression is applied to the dictionary, not to the text: a few tens of thousands of entries, about 5 ms on the 3 GB file. That yields a verdict per shape — always matches, never matches, cannot be decided from the shape — and any block with no hits and no undecided lines is never opened.

In the v1.9.0 full test run (Mac, 3 GB, hot cache), ^ +< with -E -v came out at 3.10 s for ripgrep against 0.11 s (28.2x). Isolating the mechanism by toggling the skeleton off on the same file takes the same query from 1.510 s to 0.062 s (24.4x).

The losses first. A query whose hits land in every block cannot skip anything. [0-9]{3}-[0-9]{4}" has hits in 703 of 724 blocks, so reading the per-block number arrays is pure overhead: 0.92x to 0.99x, slightly slower with the skeleton on (under 1.5x, so I call that level). The index grows 6.3% — 251.8 MB to 267.8 MB on the 3 GB file. And a .uwvz bundling 60,000 Linux kernel source files gets no skeleton at all: the shapes scatter into 4.085 million distinct values, the top 65,534 cover only 70.65% of lines, and the build threshold is 90%.

uvf and uvp are the search commands of UwView, which I make (uvf is the free build, uvp is the paid UwView Pro). The numbers here come from v1.9.0 “Full Spectrum” (released 14 October 2026, build 26.10.13.22), measured on a Mac (Apple M4, 10 cores, 32 GB, external USB SSD) on 13 October 2026. v1.9 carries the pet name “Full Spectrum” because Shift_JIS, EUC-JP and UTF-16 files are now stored as UTF-8 inside the index, so encoding and file type no longer change how fast a search runs.

The problem: an inverted match cannot use a “where is it” index

What the index held until now is where things are: which byte each line starts at, which literals appear in which block. Search for 東京 and every block without it is skipped unopened.

An inverted match does not invert along with it. The answer to -v '^ +<' is not “blocks that lack ^ +<” but “lines that do not match it” — and those lines live inside the blocks that do contain matches. Skip a block because it contains the pattern and you drop the non-matching lines hiding in it. The same hole opens for any regular expression with no mandatory literal to filter on, such as [0-9]{3}-[0-9]{4}" (I wrote about extracting those literals here). With no handle, both cases fall back to matching everything: 1.5 s for -E -v and 4.7 s for -E on 3 GB.

The idea: keep the shape of each line and the expression only has to run once

Huge logs and XML have far fewer kinds of line than lines. The same row repeats for millions of lines with different numbers and different words. So throw away what differs and keep the shape.

• runs of digits become 9
• runs of letters become a
• runs of bytes above 0x80 become u
• punctuation and whitespace stay as they are
• truncate at 160 bytes and mark the skeleton as partial

<tag k="highway" v="residential"/> turns into something like <a a="a" a="a"/>. Across the 92.24 million lines of the 3 GB file there are 1.395 million distinct skeletons, and the most common 65,534 of them cover 98.56% of all lines.

From there the use is forced. Run the query against 65,534 dictionary entries instead of 92 million lines. Label each shape “always matches”, “never matches” or “undecidable”, and the per-block number arrays tell you which blocks you have to open. Building that table took about 5 ms on the 3 GB file.

And the inverted query is simply the table read backwards: “always matches” becomes “always suppressed”, “never matches” becomes “always emitted”. The handle that would not invert now inverts for free.

The shape of it: a 65,534-entry dictionary and one number array per block

It lives in an optional section at the end of the .uwvz, with a directory and a magic marker, so older builds still read the body, the line index and the metadata exactly as before.

• Dictionary: the top 65,534 skeletons by frequency get a number; 65535 means “other”.
• Number arrays: per block, the numbers of the lines starting in it, as u16, compressed with zstd.
• Build conditions: the top 65,534 shapes cover at least 90% of lines, the file is UTF-8, and line endings include LF. An existing .uwvz can be upgraded with uvp <file> --skeleton.
• Blocks opened: only those holding lines to emit or lines marked undecidable. Inside an opened block, lines that will not be emitted are skipped by counting newlines in bulk, and the regular expression runs only on the undecidable ones.

Block size also dropped from 4 MB to 1 MB in this release, which makes the skip decision finer-grained. That is the subject of the next part of this series.

The part that nearly killed it: 1.4% of lines were in every block

The first version of this barely worked at all.

The lines that missed the dictionary — the 1.4% outside the top 65,534 shapes — turned out to be spread across every block. A line with no number is undecidable, so even -E -v '^ +<' with its single hit still had to open 672 of 724 blocks. Less than a tenth of the file was being skipped.

The fix was to spend part of the budget differently. When the shape count exceeds 65,534, 8,192 of the slots are reserved for the first 16 characters of a skeleton, treated as a partial shape, and every line that misses the dictionary gets one of those instead. The 3 GB dictionary became 57,380 full skeletons plus the prefixes, and with the prefixes 100.00% of lines carry a number. Blocks opened went from 672 to 1, which is where the 24.4x above comes from.

The 90% build threshold is still measured without the prefixes. They are a safety net for precision, and letting them count would make the decision to build the index too easy.

The numbers against ripgrep (v1.9.0 full test run, 3 GB)

Against ripgrep 15.2.0, same patterns, hit counts verified equal. Cold means the page cache was purged with ten seconds of settling; hot is the run straight after.

• Only the first row is the skeleton working. One hit in the whole file means the dictionary pass rules out nearly every block before anything is read.
• That row carries a caveat from the harness itself: it flagged ripgrep’s hot run as not having warmed properly (cold 3.57, hot 3.10, almost identical). Comparing cold to cold gives 3.57 s against 0.18 s, 19.8x — the order of magnitude holds either way.
• The 3.85x on =" with -v is not the skeleton. That query emits 7.7 million lines and lines without =" sit in every block, so nothing is skipped; the gain is the index itself, which only has to read 251.8 MB. The next table shows the skeleton contributing nothing there.

The numbers with the skeleton on and off (the mechanism alone)

Setting UVP_SKELETON=0 searches the same .uwvz without using the section. These are measured on a development build (1.8.3.3), because the v1.9.0 test run has no skeleton-off condition. 3 GB, hot, median of three, output discarded to /dev/null.

Three regimes, and they are easy to tell apart:

1. Decidable by shape, few hits (-E -v '^ +<'): 24.4x. Almost nothing gets read.
2. Decidable by shape, many hits (-E '^ +<'): 1.98x. All 92 million lines are emitted, so writing them out becomes the ceiling.
3. Not decidable by shape (the other five): 0.92x to 0.99x, slightly slower, because the number arrays are read for no benefit.

A 1 GB plain-text file (10 million lines) behaves the same way: -E -v '^ +<' goes 0.240 s to 0.032 s (7.5x), everything else 1.00x to 1.45x.

What it costs

1. Queries that cannot skip get slightly slower. The bottom five rows above. [0-9]{3}-[0-9]{4}" has hits in 703 of 724 blocks and lines without =" exist in all of them, so the per-block arrays are read for nothing. Four to eight percent is inside what I call level, but it is not an improvement. For plain strings without -v there is now a cut-off: if more than half the blocks would be opened, the skeleton is not used and the old SIMD byte scan runs instead. The equivalent cut-off on the regex path is not implemented yet.

2. The index grows 6.3%. The section is 15.2 MB on the 3 GB file (251.8 MB to 267.8 MB) and takes 3.4 s to add; on the 1 GB plain file it is +2.6%. For a tool that advertises its storage footprint, that belongs in the open.

3. Bundles of many small files get no skeleton. On 60,000 Linux kernel source files the shapes scatter into 4.085 million values and the top 65,534 cover 70.65% of lines, below the 90% threshold. Source code varies line by line; this mechanism pays off on logs, XML and CSV, where the same shape repeats for millions of lines, and not on everything.

4. There is no way to time the matching apart from the writing. uvp‘s -c only exists after -uniq, so there is no count-only mode (the count goes to stderr). Every figure above discards output to /dev/null.

Correctness: 1.2 million randomised pairs, zero mismatches, byte-identical output

A mechanism that decides “this cannot match” and then declines to read the text will silently lose answers if that decision is ever wrong once. So this got the heavier half of the work.

• Randomised cross-check: 1,500 lines × 800 patterns = 1.2 million pairs, comparing the skeleton verdict against actually running the regular expression on the text. Zero mismatches. Lines mixed digits, letters, Japanese, full-width digits, punctuation, control characters and invalid UTF-8; patterns included case-insensitive ones.
• Byte-identical output: verified with the skeleton on and off across 18 patterns (including -v, -i, -E) × LF / CRLF with BOM / bundled .uwvz / files whose shape count overflows into the prefix slots. Lines over 64 KB and over 1 MB, and lines spanning block boundaries, are included. The 1,027 tests in Pro.Core pass as well.

Several judgements deliberately fall on the undecidable side:

• \d matches full-width digits (the .NET default). For a pattern containing \d, a shape containing u that does not match is sent to “undecidable” rather than “never matches”. [0-9] is ASCII-only and decides cleanly.
• Lines over 64 KB are “other”. uvp only matches the first 64 KB of a line, so the skeleton must not claim more than that.
• A small purpose-built parser decides whether a pattern is safe, and anything ambiguous is rejected (meaning: skip the skeleton). The dictionary pass uses the non-backtracking engine so that nested quantifiers like (\d*)* stay time-bounded.

The general version: an index of where the answer cannot be

The obvious index records where things are. That cannot be inverted, which is why it does nothing for -v or for a regex with no mandatory literal. What worked was holding a summary that can say “the answer is not in this chunk”. Line shapes are far smaller than lines — 92 million collapse to 65,534 — and crucially, a pattern written for the real lines can be applied to the summary unchanged.

Three questions decide whether this shape of index is worth building. Is the summary set small enough that you can afford to evaluate the query against all of it (if not, you are back to looking things up — the kernel bundle fails here). Is the undecidable fraction small, since those fall back to reading the original, and 1.4% of lines appearing in every block was enough to neutralise the whole thing. Does it fail safe, because a wrong “cannot match” removes answers without any error; pushing doubt into “undecidable” is always safe, and 1.2 million randomised pairs exist to prove that the safe side really is safe.

How this looks in uvp

uvp japan.osm '^ +<' -E -v            # inverted regex, where the skeleton pays off
uvp japan.osm '^ +<' -E               # the matching lines
uvp japan.osm '[0-9]{3}-[0-9]{4}"' -E # no mandatory literal, skeleton cannot skip
uvp japan.osm.uwvz --skeleton         # add the section to an existing .uwvz
uvp japan.osm -info                   # whether the skeleton section is present
UVP_SKELETON=0 uvp japan.osm '^ +<' -E -v  # search without it (for cross-checks)
UVP_SKELETON_TRACE=1 uvp japan.osm '^ +<' -E -v  # table build time and blocks opened
uvf japan.osm '^ +<' -E -v            # the free build keeps no index and reads each time

Exit codes follow grep: 0 for hits, 1 for no hits, 2 for an error or an incomplete result. The free build is on GitHub Releases (brew install --cask amru195704/uwview/uwview on macOS, Scoop on Windows, Snap on Linux).

Links

• Part 1: storing Shift-JIS, EUC-JP and UTF-16 as UTF-8 inside the index: https://uvp.y42u.net/en/blog/uwview-fs01-sjis-utf8-index-en/
• The v1.9.0 “Full Spectrum” release post: https://uvp.y42u.net/en/blog/uwview-v190-full-spectrum-en/
• Extracting a mandatory literal from a regular expression: https://uvp.y42u.net/en/blog/uwview-fl04-regex-required-literal-en/
• Where ripgrep wins: https://uvp.y42u.net/en/blog/uwview-wf14-where-ripgrep-wins-en/
• Counting newlines was 40% of a cached query: https://uvp.y42u.net/en/blog/uwview-wf12-newline-hot-en/
• Where the previous series landed (many files, seven formats, zip, pbf): https://uvp.y42u.net/en/blog/uwview-wf15-wide-field-recap-en/
• All measured data (benchmark list): https://uvp.y42u.net/en/benchmarks-en/
• Source code (GitHub): https://github.com/amru195704/UwView

And if your logs are millions of near-identical lines and you want the second query to be fast, try UwView Pro: a persistent index, search over the compressed cache, and roughly 1/9 of the original size (all platforms; one-time purchase or monthly plan, with a 14-day trial).

From the developer: a full list of my apps, Kindle books and public projects is on GitHub: amru195704.