Label Index

The label index lets us quickly answer "which streams match {service=api,level=error}?"

Approach 1: Reverse index per label key:

label "service":
  "api"   -> [stream_1, stream_3, stream_7]
  "auth"  -> [stream_2, stream_5]

label "level":
  "info"  -> [stream_1, stream_2]
  "error" -> [stream_3, stream_5, stream_7]

label "env":
  "prod"  -> [stream_1, stream_3]
  "dev"   -> [stream_2, stream_5, stream_7]

To resolve {service=api,level=error}:

• service=api: {1,3,7}
• level=error: {3,5,7}
• intersect: {3,7}

Sorted lists — intersection in O(n+m).

Approach 2: Bitmap index (Loki's choice for low-cardinality cases): each (key,value) → bitmap of stream IDs. Bitwise AND for intersection. Very fast.

Approach 3: Inverted index per token (Elasticsearch). Powerful but expensive — hence Loki abandoned it.

Regex/glob match labels: {service=~"api|web"} — iterate all "service" values, OR matching ones together.

Time range: another index (stream_id, time_range) → list of chunks. Combine with label match: "for each matching stream, find chunks overlapping [t1, t2]".

def find_chunks(label_filter, t_start, t_end):
    streams = match_labels(label_filter)
    chunks = []
    for s in streams:
        chunks.extend(c for c in chunks_of(s) if c.overlaps(t_start, t_end))
    return chunks