stack-encrypt: size a probabilistic query's fetch with target_limit and Stats #1184

Background

ADR-0009 decision 5 sizes a fetch for a Probabilistic query: target_limit(want, stats) = want + Poisson_quantile(λ = p·N, confidence), where p is the mean of each stored filter's fill raised to b, the bits in the query filter. The statistics come from a declared prior or from a measured histogram of set-bit counts.

Problem

A caller who wants ten real matches from a Matches query has no way to know how many rows to ask for. A short needle against long stored text can need thousands of extra rows, and the library can say so before the query runs.

Proposal

• Stats with the row count, a fill source and a confidence (99% by default). Stats::declared(rows) uses the index's declared prior. Stats::measured(rows, histogram) takes (set bits, row count) buckets.
• A declared prior on the match configuration: MatchConfig::expected_tokens(), a default method returning no prior, so existing configurations keep compiling. The prior is not part of the index's identity and does not change a term.
• Limit with Rows(n) and Unbounded, and Probabilistic::target_limit(&self, want, &Stats) -> Limit. With no usable prior and no histogram the answer is Unbounded.
• p is the mean of (bits / m)^b over the histogram, never the mean fill raised to b. A declared prior uses 1 − e^(−k·n/m).
• A Poisson quantile that is exact for small λ and stays accurate and fast for large λ.
• ADR-0009's code matches what this ships.
• Tests: the worked table in ADR-0009 decision 5 reproduces, a mixed-length histogram gives the larger bound the ADR describes, the quantile matches reference values, and Unbounded is returned when nothing is known.

Related

• Depends on stack-encrypt: verify a Matches query's rows after decrypt (Probabilistic) #1183.
• Tracking: implement ADR-0009, operator-typed query terms for Stack Encrypt #1178: tracks ADR-0009.