Multi-root grep still decomposes the regex once per root after 66c0641d, plus a quadratic delta-posting insert

[iceteaSA]

Two findings in the search index. The first is the half of a redundancy that 66c0641d didn't cover — flagging it because you're evidently in this code right now and the other half already shipped.

Line numbers against 83fe3bd5.

---

1. decompose_regex still runs per root

66c0641d hoisted build_path_filters out of the per-root loop — correct, and it removed one of two identical recomputations. The other is still there.

search_grep_profiled_with_filters decomposes the pattern on every call:

// search_index.rs:1713-1724
let query = match pattern {
    CompiledPattern::Regex { case_insensitive: true, .. } => {
        decompose_regex(&format!("(?i:{raw_pattern})"))
    }
    _ => decompose_regex(&raw_pattern),
};

and execute_profiled_with_filters calls it once per root:

// grep_executor.rs:336
let (result, mut query) = snapshot.search_grep_profiled_with_filters(
    pattern, filters, &root.search_root, max_results, params.path_exclusion,
);

The returned query is used for timing accumulation (query.post_filter += scope_elapsed) rather than being threaded into the next root, so for an R-root grep the same regex HIR is parsed and decomposed into trigrams R times. decompose_regex is a pure function of the pattern — identical output every iteration.

• Trigger: any multi-root grep. Cost scales with root count × pattern complexity.
• Severity: P2, same class and same loop as the filter hoist you just did.
• Fix direction: decompose once alongside the build_path_filters call you already hoisted, and pass the prebuilt RegexQuery into each root's search — the plumbing added in 66c0641d is most of the way there.

2. Delta posting insert re-sorts the whole list when file ids arrive out of order

// search_index.rs:881-885, inside the per-file indexing loop
if postings.len() > 1
    && postings[postings.len() - 2].file_id > postings[postings.len() - 1].file_id
{
    postings.sort_unstable_by_key(|p| p.file_id);
}

The guard only detects the out-of-order case; when it fires it sorts the entire growing posting list. If files are indexed in an order not aligned with file_id allocation, every insert re-sorts, giving O(n² log n) over a single trigram's list.

apply_git_diff_updates is the concrete path — it iterates --name-status output in git's ordering and calls update_file per line, which has no relationship to file_id order.

• Trigger: refresh via git-diff updates on a trigram shared by many files. Doesn't bite when insertion order happens to be sorted, which is why it's latent.
• Severity: P3.
• Fix direction: set a per-trigram dirty flag and sort once at read/query time, or insert at a binary-searched position instead of append-then-sort.

---

Provenance and limits. Both came out of a read-only sweep; I verified each against upstream/main before filing — the decompose_regex call sites, the fact that 66c0641d hoisted only the filters, and the sort inside the per-file loop. No measurements — I haven't profiled either, and #2 in particular may never bite if real-world insertion order is usually sorted. The claims are structural.

One nearby finding I checked and am not filing: I suspected the remote embedding path sent whole batches without sub-batching, but entries_for_chunks_with_reuse already chunks by max_batch_size (step_by(batch_size), default 64), so that one is refuted. Mentioning it only so the absence isn't read as an oversight.

[ualtinok]

Both findings fixed on main. Finding 1: the regex decomposition is now hoisted beside the filter build from 66c0641 and the prebuilt query threads into each root's search — measured 1.97x on a 4-root grep (50.1µs → 25.5µs per op median). Finding 2: the delta insert now places postings at a binary-searched position instead of append-then-full-sort — measured 50.1x at 1,024 out-of-order postings on a shared trigram (2.76ms → 55µs), with byte-identical differential coverage for the multi-root path and out-of-order refreshes, mutation-tested. Your 'may never bite' instinct on #2 was half right: it never bites on mtime-ordered walks, but git-diff refresh order bites it hard — worth having fixed. One follow-on your report indirectly caught: stabilizing the parity harness around these paths exposed an equal-mtime tiebreak that ordered by absolute path (divergent across harness projects, Linux-only ties) — fixed with a root-relative tie key in the same arc. Thanks for the precise line-pinned reports, as ever.