Why Is Regex Search Slow at Scale?

Why does one fast operation become slow?

A regex engine is designed to match one string. It compiles the pattern once and then reads the input one character at a time, so a single log line or document field takes microseconds. Against a collection, the engine repeats that work for every document, and the total cost grows with the number of documents times the average field length. Even an engine built on automata, with no exponential backtracking and no ReDoS risk, has the same cost curve with a smaller constant.

Regex filters become the most expensive operator in a plan for that reason, and nobody has to do anything wrong for it to happen. The regex is fast. The scan over every document is slow.

Why do agents make it worse?

A person types an occasional regex and can wait for a scan. An agent issues many regex filters at once, because it uses regex for ordinary keyword search too, and it issues them while it explores, verifies, and refines an answer. Concurrent full scans compete to read and test the same body of text, so throughput stops growing almost as soon as concurrency starts. In TopK's measurement, throughput on the unindexed scan path grew almost nowhere from concurrency one to sixteen, and throughput on the indexed path grew almost thirteen times over the same range.

What makes it fast again?

The engine has to stop testing every document. Regexes written by agents usually contain literals, and even a pattern with optional sections or alternatives says that some characters must occur. An index over those characters can name a small candidate set, and the exact regex only has to check the candidates.

The rule that makes the two stages safe only goes one way. The index may return false positives, and the exact regex removes them. The index must never lose a real match, so the engine can skip any document that fails the index expression without checking it. How the index is built so that the rule holds is covered in how do you index text for regex search.

How much faster is it?

TopK measured the query path end to end on one of its clusters. The measurement compared sparse-gram candidate generation plus exact verification against an unindexed full scan. At concurrency sixteen, the indexed path delivered 55.3 times the throughput, 61 times lower average latency, and 51.2 times lower p99 latency (August 2026). The gap grows as concurrency grows, and high concurrency is how agent workloads run.

What does this look like in TopK?

The interface does not change. You write a regular expression as a filter, and the planner turns whatever literals it contains into a candidate plan before the exact regex runs.

from topk_sdk.query import select, field

docs = client.collection("logs").query(
    select("message").filter(
        field("message").regexp_match("error (reading|writing) file")
    ).limit(100)
)

Pass "i" as a second argument for a case-insensitive match. The query documentation covers the full filter syntax, and the fast regex search post walks through the design.