We tried to speed up random trace_id lookups with a bloom filter and found it sped some queries up 29× while making others slower, and which one you get depends entirely on how your IDs are generated.
TL;DR:
- Looking up a random trace_id across 170 index files in object storage took 2,584ms. Tantivy prunes files by min/max term, but a random 16-byte ID is scattered across the whole 128-bit space, so every file's range is [0, 2¹²⁸], nothing prunes, and all 170 files get opened. On object storage every one of those is a network round trip, and that's where the 2.6s goes.
- A bloom filter is the obvious fix. The non-obvious part is where you put it. Per-file blooms = 170 small reads, which object storage punishes hardest, so it barely beats doing nothing.
- The trick: every file's bloom uses the same block count, so a query value maps to the same block index in every file. Store blooms block-major instead of file-major, and "block 7 across all 170 files" becomes one contiguous 5,440-byte row. One range request, 170 checks, ~170× fewer round trips. Lookup dropped to 89ms.
- But this makes time-ordered IDs slower. A UUIDv7 already range-prunes for free in 154ms; the bloom layer adds ~42ms and Tantivy still does its 154ms on the survivor, netting ~196ms of pure overhead. UUIDv4 wins by 29×, UUIDv7 loses by 1.3×.
- So we don't auto-detect fields to bloom (sampling would guess wrong half the time). Operators opt in per field, only when all three hold: high cardinality, random distribution, many files per hour.
- One design choice I'd defend: every bloom failure mode degrades to "keep the file." It can be slow; it can never drop a row.
We wrote up the full thing with diagrams and the SBBF details on our blog, happy to take questions here.
Disclaimer: I am one of the maintainers at OpenObserve (open-source observability, written in Rust) and the writer is our founding engineer. This is our own benchmark, single querier, S3 backend, no disk cache. Happy to share the test setup so anyone can poke at it.