Pruning Segments in Amber: Ribbon, CQF, and SuRF

TL;DR. Segment pruning in Amber is a cascade: time first, then membership filters, then exact postings or a sidecar projection when it can answer the query without touching the row store. Ribbon is the natural default for exact membership. CQF adds multiplicity and updates; SuRF adds prefix and range semantics. Because Amber segments are append-only and sealed once, most of those extra capabilities are not free enough to justify their cost by default.

Step 1: prune by time

SparseIndex keeps [MinTS, MaxTS] for every segment. A time-bounded query can reject everything that does not overlap the requested interval before opening any index file.

// Lookup returns the segments whose span overlaps [from, to].
func (s *SparseIndex) Lookup(from, to int64) []SegmentTimeRange {
    result := make([]SegmentTimeRange, 0)
    for _, r := range s.ranges {
        if r.MaxTS < from || r.MinTS > to {
            continue // segment is outside the range
        }
        result = append(result, r)
    }
    return result
}

This is the cheapest pruning stage because the metadata is already in memory. There is no filter to build and no file to open: if the segment's time span cannot overlap the query, the segment is simply gone from the candidate set.

Step 2: membership checks by field

After time, the next question is whether a segment could contain the value we are looking for. Which sidecar index we build depends on field cardinality.

level, service, and host are low-cardinality fields, so they fit inverted bitmap indexes such as MultiFieldIndex.

trace_id is different. When most trace IDs have df = 1, a bitmap per value is mostly overhead. Instead Amber can use a RibbonFilter as the cheap negative test, followed by an exact posting list when the filter says the key might be present.

if !model.IsZeroTraceID(q.TraceID) {
    if ribbon, ok := e.logRibbon(seg.FileName); ok {
        if !ribbon.Contains(q.TraceID[:]) {
            return 0, nil // segment is definitely not a match
        }
    }
    if pl, ok := e.logPosting(seg.FileName); ok {
        ids := pl.Lookup(q.TraceID[:])
        if len(ids) == 0 {
            return 0, nil
        }
        // ...
    }
}

The same idea applies to full-text search: cheap membership structures can reject whole segments before the executor has to decompress and scan the underlying rows.

Step 3: skip decompression when a sidecar can answer the query

There is a second kind of pruning: sometimes a segment will definitely be read, but the full row store does not need to be read.

For trace-summary queries such as service, operation, or duration, Amber has a CoverIndex (.cidx). It is a columnar, strided projection of the fields needed by the query, stored in the same sorted order as the service posting list. That lets the executor answer the aggregation without decompressing the main row store.

So the cascade becomes:

time range
    ↓
membership filter
    ↓
exact posting / sidecar index
    ↓
row store only if still necessary

One seal pass for every sidecar

All of these sidecar indexes are built while the segment is sealed. The implementation originally built Bitmap, FTS, Ribbon, and FTSRibbon with separate scans of the same data. With several independent decodes of one segment — and especially with repeated tokenization and stemming for FTS — sealing started to compete with ingest.

The fix is to make one pass feed all the structures. For FTS, the Ribbon filter can reuse the tokens already produced while building the FTS index instead of tokenizing the same text again.

That makes the index family behave like projections over one seal pass, rather than five independent consumers fighting over the same CPU and memory bandwidth.

Ribbon Filter

Ribbon is the workhorse here because its job is narrow: answer one question cheaply — could this key be present?

It gives us the ideal shape for append-only sealed segments: a compact negative filter with no delete path, no update path, and no need to maintain a mutable structure after seal.

I use Ribbon with a small change to the window width tuned for this database. The important part is the role, not the exact parameter: it is the cheap gate in front of an exact posting list.

More background: part one and part two.

Counting Quotient Filter

CQF starts where Ribbon and Bloom stop. A membership filter can say “seen” or “not seen”; a Counting Quotient Filter also keeps a multiplicity count, and it can support insertion and deletion without rebuilding the whole structure.

The basic layout hashes a key and splits the hash into a quotient and a remainder:

func (qf *CountingQF) split(key []byte) (q0, r0 uint64) {
    h := hashKey(key) & maskBits(qf.q+qf.r)
    return h >> qf.r, h & maskBits(qf.r)
}

The table has 2^q slots. Instead of storing the full hash, each slot carries metadata bits describing whether a quotient has a run, whether the slot is occupied, and where a run ends.

occupied[i] — some run for quotient i exists
used[i]     — slot i contains a remainder
runend[i]   — slot i is the end of a run

When several keys share the same quotient, their remainders form a contiguous sorted run. Lookup walks the cluster and skips complete runs until it reaches the run belonging to the target quotient.

func (qf *CountingQF) locate(qIdx uint64) uint64 {
    if !qf.isUsed(qIdx) {
        return qIdx
    }
    start := qf.findClusterStart(qIdx)
    runsBefore := 0
    for k := start; k < qIdx; k++ {
        if qf.isOccupied(k) {
            runsBefore++
        }
    }
    pos := start
    for runsBefore > 0 {
        for !qf.isRunEnd(pos) {
            pos++
        }
        pos++
        runsBefore--
    }
    return pos
}

I use two deliberate simplifications compared with the paper: three metadata bits per slot instead of the two bits derived through rank/select in RSQF, and a unary counter instead of escape coding. Both trade some memory efficiency for a simpler implementation and test surface.

The interesting part for Amber is not that CQF is more powerful. It is that those extra powers may simply be unnecessary for sealed segments. There is no ongoing delete/update workload after seal, so the mutable part of CQF is mostly wasted capability unless a future use case actually needs it.

Succinct Range Filter

Ribbon has another hard boundary: it is a membership filter, not a range filter. No amount of tuning its memory budget gives the original key order back.

SuRF takes the opposite approach. It builds a compressed prefix tree over the sorted key set, truncates branches as soon as keys become distinguishable, and stores the tree in a succinct representation. LOUDS encodes the topology; labels are stored separately, while rank/select operations navigate the structure.

That gives SuRF something a pure hash filter cannot provide: it preserves enough lexical order to support prefix and range checks.

Three SuRF variants

SuRF-Base keeps only the truncated tree. It is cheap, but membership false positives depend on where the tree was truncated.

SuRF-Hash stores a few additional hash bits at the leaves. It tightens membership false positives without storing the complete suffix.

SuRF-Real keeps the remaining key bytes instead of only a hash suffix. That enables range queries such as “all keys between X and Y”, in addition to membership checks.

In other words, a Ribbon or Bloom filter destroys key order because it stores only hashes. SuRF intentionally keeps part of the order. That is why it can cover prefix and range predicates that membership filters cannot represent.

Which one actually belongs in Amber?

This is where the workload matters more than the feature list.

Amber's segments are append-only and sealed once. After sealing, we do not need to delete entries or update a filter in place. That removes most of the reason to pay for CQF's dynamic capabilities.

Most of the fields we care about are also short, structured keys with moderate cardinality, where exact equality is the common operation. For that workload, Ribbon plus an exact posting list is a very clean fit.

SuRF is more interesting because it adds semantics, not just mutability. It becomes worth the complexity if the query layer actually starts asking for prefix or lexical range predicates. Until then, carrying a succinct trie around just in case is paying for capability we do not use.

FTS is the one place where I want to keep the pencil out. FTS works on tokens rather than the original lexical key space, so it is not obvious that SuRF's ordering buys us anything useful there. Maybe it will; there is no query that justifies it yet.

The pruning cascade

                 query
                   │
           ┌───────▼───────┐
           │   time range   │
           └───────┬───────┘
                   │
           ┌───────▼───────┐
           │ Ribbon / FTS   │
           │ membership     │
           └───────┬───────┘
                   │
          ┌────────▼────────┐
          │ posting / cidx  │
          │ exact lookup    │
          └────────┬────────┘
                   │
            ┌──────▼──────┐
            │ row store   │
            │ only if     │
            │ necessary   │
            └─────────────┘

The point is not to accumulate every index we can find. It is to put the cheapest, most decisive test first, and stop opening bytes as soon as the answer is already known.

So why CQF and SuRF at all?

CQF closes Ribbon's “static membership only” limitation by adding counts and updates. SuRF closes Ribbon's “membership only” limitation by preserving order for prefix and range checks.

Neither is automatically better for Amber. The segments are immutable after seal, and the current query workload mostly needs exact equality. That makes Ribbon the simpler default. CQF and SuRF are tools to bring in when the workload grows into the cases they are specifically good at.

That is the pattern I want for segment pruning in general: build the smallest filter that can make a decisive early exit, and do not pay for semantics that the query engine never asks for.