feat: Search compressed data without decompression

Compression saves space, but it usually makes your data opaque: to find anything you first
have to decompress the whole thing. MinLZ changes that. A MinLZ stream can carry a small
per-block search index that lets mz search find a byte sequence while skipping every block
that provably can't contain it — those blocks are never decompressed, and (with a sidecar) never
even read from disk.

The result: you keep your data compressed and searchable.

One number to set the scene: finding a specific string in a 10 GB CockroachDB log
(compressed to 578 MB) takes 0.14 s with mz search, reading about 133 MB. Decompressing
that log and piping it to grep — the usual way to search compressed data — takes ~5 s and
reads the whole file. zstd -dc | grep takes ~5 s, lz4 -dc | grep ~10 s. Scanning the raw
10 GB with rg takes ~8 s.

The search index is stored as skippable chunks: older MinLZ readers ignore them and the compressed
payload is byte-for-byte unchanged, so adding search is always backward-compatible.

Search indexes can be built while compressing or after the fact as sidecar streams,
allowing them to be used separately from the compressed data.

How it works (in 30 seconds)

Every block gets a tiny bloom-filter table: the byte-windows in the block are hashed and their
bits set. To search, mz search hashes the same-length windows of your pattern and checks each
block's table:

• any window bit missing → the pattern is definitely not in that block → skip it (no decode);
• all bits present → the block might match → decode and scan it.

Longer/rarer patterns produce more independent window checks, so blocks that don't contain them are
rejected with near-certainty. Tables can live inline in the .mz, or in a sidecar .mzs
file you build afterwards — handy for data you can't or don't want to re-compress.

This is why it matches with compression. Compressible data is very likely to produce
search indexes that are also useful, meaning there is a reasonable reduction in the
search table compared to the raw data.

For full details: SEARCH.md (usage & tuning) and SPEC_SEARCH.md (wire format).

When to use it — and when not

We will use the command-line tool mz search to demonstrate, but everything is available via the Go API.

This is a specialized tool. It is dramatic when it fits and pointless when it doesn't, so read this
part first.

Reach for mz search when:

• You search for literal byte strings — IDs, error codes, request paths, hostnames, JSON keys,
  hashes. (Not regex. See below.)
• The pattern is reasonably selective — it appears in a minority of blocks. Rare → huge win.
• The data is large, archived, or remote and you'd rather not materialize the whole thing.
• You search the same corpus repeatedly — build the index once, query many times.
• You are I/O-bound: on object storage or a cold cache, skipped blocks issue zero reads.
• You need to confirm a string is absent ("is this error anywhere in 10 GB?") — the fastest case
  of all.

Don't bother when:

• You need regex, case-insensitive, or fuzzy matching. mz search is literal bytes only.
• The pattern is very common or shorter than the index's match length — little or nothing
  gets skipped, and you pay a small table-check tax on top of a full decode.
• It's a one-shot scan of small data that's already in RAM and you have ripgrep — rg is
  superb there and hard to beat.

Rule of thumb: the speed-up scales with how much the query lets MinLZ skip. Rare string →
100× faster. String in every record → no faster at all.

Quick start

You need an index. Either add one while compressing:

mz c -search file.log            # writes file.log.mz — still a normal, decodable .mz

…or add one to an existing .mz after the fact (this decodes each block and builds fresh tables;
the original data is untouched):

mz sidecar build file.log.mz     # writes file.log.mz.mzs alongside it

Then search. The sidecar is auto-detected:

mz search "connection refused" file.log.mz        # prints  <offset>:<line>
mz search -c "connection refused" file.log.mz      # count matching lines
mz search -q "connection refused" file.log.mz      # exit code only (0=found, 1=not)
mz search -v -c "connection refused" file.log.mz    # + timing and skip stats

Line output is streamOffset:line, e.g.:

1976076142:{"tag":"cockroach.dev","channel":"DEV","severity":"ERROR",...}

-v shows you exactly what happened — here, "find all warnings" in the 10 GB log:

λ mz search -v -c '"severity":"WARNING"' cockroach.node1.log.mz
cockroach.node1.log.mz: using sidecar cockroach.node1.log.mz.mzs
cockroach.node1.log.mz: search info: matchLen=6 baseTableSize=23 (8388608 entries) no-prefix
92
cockroach.node1.log.mz took 231ms 45483.2 MB/s
Blocks total: 1253, skipped: 1238 (98.8%), deferred: 1245 (99.4%, 1238 skipped)
Blocks searched: 15 (1.2%), false positive: 7 (46.7%)
Table total: 139345225 bytes, avg 111209 bytes/table, 1.33% of 10506623721 uncompressed

It looked at 15 of 1253 blocks and answered in a quarter of a second.

While the table cost of 1.33% is acceptable for most cases, it is possible to reduce
the size a lot by specializing the search index to a specific result.

If you know you'll always search a particular field, you can tell MinLZ to index only the bytes
that follow it. For example:

λ mz sidecar build -search.prefix='"severity":"' cockroach.node1.log.mz
Building sidecar: cockroach.node1.log.mz -> cockroach.node1.log.mz.mzs
Sidecar size: 50846 bytes

λ mz search -v -c '"severity":"WARNING"' cockroach.node1.log.mz
cockroach.node1.log.mz: using sidecar cockroach.node1.log.mz.mzs
cockroach.node1.log.mz: search info: matchLen=6 baseTableSize=23 (8388608 entries) long-prefix="\"severity\":\""
92
cockroach.node1.log.mz took 39ms 269400.6 MB/s
Blocks total: 1253, skipped: 1245 (99.4%), deferred: 0 (0.0%, 0 skipped)
Blocks searched: 8 (0.6%), false positive: 0 (0.0%)
Table total: 38859 bytes, avg 31 bytes/table, 0.00% of 10506623721 uncompressed

Even when considering the sidecar headers, the index is less than 0.0005% of the data.

Benchmarks

Setup: AMD Ryzen 9 9950X (16C/32T), 61.6 GB RAM, Windows 11, mz [dev]. Warm page cache, best
of 3 runs, literal (-F) patterns. grep's output is sent to a file so it performs a full count
scan (piping grep -c to /dev/null lets GNU grep quit at the first match — a common
benchmarking trap). Every file below is in cmd/mz/; the commands are copy-pasteable.

Flagship: 10 GB of CockroachDB logs

cockroach.node1.log is 10.5 GB of JSON log lines. It exists here in four forms: raw, MinLZ
(.mz, 578 MB), Zstandard (.zst, 508 MB) and LZ4 (.lz4, 954 MB). Building the MinLZ search
sidecar took 8.5 s and produced a 178 MB file (1.69% of the raw size).

(zstd/lz4 are decode-bound, so their time is the same regardless of the query or how many hits
there are.)

For selective queries mz search is ~30–60× faster than any approach that has to read the whole
stream — because it doesn't. It processes the 10 GB dataset at an effective 40–55 GB/s by
decompressing almost none of it. As the pattern gets more common the advantage shrinks, and for a
field present in every record ("severity":"INFO", 16.5 M hits, nothing to skip) it lands right
where plain decompress-and-grep does — no better, no worse:

Confirming a string is absent

This is the case mz search was born for. To prove a string isn't in a file, every other tool
must read the entire file. mz search checks each block's table, finds the pattern can't be there,
and skips it — so a "not found" over 10 GB comes back in 0.14 s instead of 5–10 s. If you're
scripting alert checks or grepping archives for an incident marker that's usually not present,
this is the difference between an instant answer and a coffee break.

Less I/O — the real lever for cold and remote data

The warm-cache times above actually understate the benefit, because they charge nothing for
reading the file. In the real world — cold cache, network storage, S3 — bytes read is what you pay
for. Here mz search reads the 178 MB index plus only the handful of candidate blocks; with a
sidecar, skipped blocks issue no reads at all:

<img width="1153" height="454" alt="bytes_read" src="https://github.com/user-attachments/assets/daad8731-01d6-4964-bfbf-...

What's Changed

• Re-enable level 1 repeats on amd64 by @klauspost in #37
• Bump the github-actions group with 2 updates by @dependabot[bot] in #36

Full Changelog: v1.1.0...v1.1.1

What's Changed

• Add faster compression mode for speed extremely sensitive applications by @klauspost in #30
• perf: Add arm64 decompression assembly by @klauspost in #29
• Simplify BMI use by @klauspost in #18
• Add nicer looking block debug print by @klauspost in #26
• Add -follow to decompression by @klauspost in #27
• Add block visualizer by @klauspost in #32

Full Changelog: V1.0.1...v1.1.0

What's Changed

• Fix Snappy/S2 block fallback max size by @klauspost in #15

Full Changelog: v1.0.0...v1.0.1

What's Changed

• Fix WriteTo bytes read count by @klauspost in #5
• Bump the github-actions group with 2 updates by @dependabot in #6
• Add v1.0.0 by @klauspost in #7
• More minor cleanup by @klauspost in #8

Full Changelog: v0.0.1...v1.0.0

Changelog

• 8a432db Add CI workflows (#1)
• 4663c50 Add final documentation touches (#4)
• f6fb18d Block benchmarks (#3)
• 3466702 Bump the github-actions group with 2 updates (#2)
• 989d22d Initial Commit