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 Bits ¶ added in v0.33.0
Bits returns the bit count New would allocate for n items at rate p, so a caller can price a filter (its bytes are Bits/8 plus a small header) before deciding how carefully to count n.
func CountTokens ¶ added in v0.33.0
CountTokens returns how many tokens s yields, without producing any. Sizing a filter from it and then filling the filter from a Scanner over the same input costs no token materialization.
func Hashes ¶ added in v0.33.0
Hashes returns the pair of hashes identifying item, for use with Filter.AddHashes. It is the hash Filter.Add and Filter.Test derive their probes from, so a caller that caches these reproduces exactly the same filter.
func SafeTokens ¶ added in v0.29.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.
It allocates a token at a time, which suits the query side (a handful of tokens per predicate). A flush tokenizing whole columns should use Scanner instead, which yields the same tokens without allocating.
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.
func (*Filter) AddHashes ¶ added in v0.33.0
AddHashes records the item whose Hashes are h1, h2 — the same bits Filter.Add would set, for a caller that already hashed the item (e.g. a builder that hashes once and sizes the filter afterwards, rather than hashing the column twice).
type Scanner ¶ added in v0.33.0
type Scanner struct {
// contains filtered or unexported fields
}
Scanner walks the lowercased tokens of a byte slice — the same tokens Tokenize produces — without allocating per token. A token that is already lowercase aliases the input; one holding uppercase is folded into the scanner's reusable buffer. Either way the returned slice is valid only until the next call to Scanner.Next or Scanner.Reset, so a caller that retains a token must copy it.
The zero value is ready to use. Reuse one scanner across values so the fold buffer is kept. Not safe for concurrent use.
type Sketch ¶ added in v0.33.0
type Sketch struct {
// contains filtered or unexported fields
}
Sketch estimates how many *distinct* items a stream contains, in constant space (HyperLogLog). A bloom filter must be sized by its distinct item count: sizing by the number of occurrences over-allocates by the average repetition factor, which for tokenized log text is one to two orders of magnitude (the same words recur in every row). The zero value is ready to use; Sketch.Reset re-arms it.
func (*Sketch) AddHash ¶ added in v0.33.0
AddHash records an item by its hash, for a caller that already hashed it (e.g. through Hashes). Any well-distributed 64-bit hash works, as long as one item always yields one hash.
Source Files