Documentation
¶
Overview ¶
Package bloom is a token bloom filter for full-text pruning: a compact, approximate set of the terms present in a column block (e.g. every token across a log part's bodies). A query token that tests **absent** is definitely not in the block, so the reader skips the whole block; a token that tests present may be a false positive, so the engine re-checks the exact predicate per row. The filter never reports a false negative — a token that was [Filter.Add]ed always [Filter.Test]s present — which is what makes block-skipping safe.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func SafeTokens ¶ added in v0.30.0
SafeTokens appends to dst the tokens that are provably present in *any* value a `contains lit` predicate matches, and returns the extended slice. It is the query-side companion to Tokenize: an embedder that lowers a substring/regexp filter to a required literal feeds that literal here, sets the result as a fetch condition's token hint, and the per-part token bloom then prunes any part whose bloom lacks one of these tokens — without ever pruning a part that holds a real match.
The safety rule. The bloom holds whole tokens (maximal alphanumeric runs). A value containing lit as a substring may glue extra alphanumerics onto lit's first/last token — "GET" occurs inside "xGETy", whose token is "xgety", not "get" — so lit's edge tokens are NOT guaranteed to be whole tokens of the value, and testing them would wrongly prune a match. SafeTokens therefore drops the leading and trailing partial token (the run of alphanumerics touching each edge) before tokenizing, keeping only interior tokens that a separator bounds on both sides within lit. Every returned token T satisfies: a value that contains lit contains T as a whole token, i.e. T ∈ Tokenize(value). The extraction under-approximates by design — a single-word literal yields no tokens (no pruning, a full scan, still correct) rather than an unsafe one.
leftPinned/rightPinned tell SafeTokens an edge cannot be extended, so its edge token is safe to keep: set them when an anchor (^, $), a word boundary (\b), or an exact-equality match guarantees the value does not glue an alphanumeric onto that side of lit. With both pinned lit is matched exactly, so every token of lit is safe.
func Tokenize ¶
Tokenize splits s into lowercased tokens — maximal runs of ASCII letters/digits — appending each to dst and returning the extended slice. Non-alphanumeric bytes are separators. Each token is a freshly allocated, lowercased copy (it does not alias s). It is the tokenization used both to fill a body bloom at flush and to derive a query's required tokens, so the two agree.
Types ¶
type Filter ¶
type Filter struct {
// contains filtered or unexported fields
}
Filter is a bit-array bloom filter with k hash probes derived from one 128-bit hash by double-hashing (Kirsch–Mitzenmacher). The zero value is not usable; build one with New.
func Decode ¶
Decode parses a filter encoded by Filter.Encode, returning it and the number of bytes consumed. It is fully bounds-checked and verifies the trailing CRC.
func New ¶
New returns a filter sized for n expected items at false-positive rate p (0 < p < 1), using the standard m = -n·ln p / (ln2)² and k = (m/n)·ln2, with m rounded up to a multiple of 64 and both m and k clamped to at least their minimums.
Source Files