Module bloom 

Block-level “might contain this” filters.

Block names prune by time, which answers every question that has a time bound and none of the ones that do not. Two queries have no useful time bound at all, and both of them read every block on disk without a filter:

• “Every span of trace 0000…6eaa.” You do not know when the trace happened — that is why you are looking it up.
• “Any record with k8s.pod.name = api-7f9.” A predicate that matches nothing has no early exit: limit never fills, so the scan runs to the end of retention to prove a negative.

A sidecar per block, written next to the Arrow tables at publish and read before any of them, turns both into “open the blocks that can answer”. Measured on this machine, each query against its own corpus (section 11):

                                      blocks   rows scanned   time
4.1 GB / 25M spans / 84 blocks
every span of one trace, without         84      25,000,000   14.3 s
                         with             1         212,992    250 ms cold, 20 warm
6.4 GB / 25M logs / 69 blocks
absent attribute value,  without         69      24,961,024   10.4 s
                         with             0               0    71 ms cold, 5.7 warm

TRACE_IDX costs 65 KB per block, 0.13% of the data. ATTR_IDX is sized by the block’s distinct (key, value) pairs, so on that corpus it is 70 bytes per block and it grows only where pruning pays best.

Both go through a splitmix64 finalizer before Kirsch-Mitzenmacher double hashing, and that is not optional. W3C only requires a trace id to be non-zero, and plenty of real ones are structured rather than random: X-Ray puts an epoch in the first four bytes, a counter-derived id leaves whole bytes constant. The bit index is (h1 + i*h2) & mask, so it reads only the low bits of the halves; ids that vary in their middle bytes would map every trace in a block onto the same handful of bits and the filter would answer “maybe” to everything. Five ops per half buys immunity to that.

Everything here fails open. A short, corrupt or unrecognized file means “scan the block”, never “skip it” — a false positive costs one wasted block read, a false negative silently loses data from a correct query.

Structs

Filter

A filter checked out, with its header validated once.

Keys

A set of hashed keys, deduplicated so the filter is sized by what it holds.

Runs 🔒

Non-null values, with adjacent duplicates dropped.

Constants

ATTR_IDX

BITS_PER_KEY 🔒

Bits per inserted key. 10 with k=7 is the textbook ~0.8% false positive rate.

HAS_DOUBLE

Set in ATTR_IDX when the block holds at least one double-typed attribute.

HEADER 🔒

magic 4 | version 1 | k 1 | flags 1 | pad 1 | words 4 | crc32 4

K 🔒

MAGIC 🔒

MAX_KEYS 🔒

Beyond this many distinct keys the filter stops being a rounding error on the block — 1M keys is 1.25 MB — and a block that diverse prunes little anyway. Past it we write nothing, which the reader reads as “scan me”.

TRACE_IDX

Filenames inside a published block. Part of the on-disk format.

VERSION 🔒

Functions

attr_hash

Hash one (key, canonical value) pair for ATTR_IDX.

build

Build a filter over a FixedSizeBinary(16) column. None when there is nothing to index, in which case no file is written and the reader’s fail-open path scans the block.

encode 🔒

halves 🔒

may_contain

Could this block contain id? Anything unreadable answers yes.

mix 🔒

splitmix64’s finalizer: every input bit reaches every output bit.