feat: add stats and postings index sections with encoding abstraction by trevorwhitney · Pull Request #21442 · grafana/loki

trevorwhitney · 2026-04-07T17:52:49Z

Summary

Implement stats and postings section packages for index objects, enabling sort-schema-based storage locality
Introduce an encoding abstraction (SectionEncoder, ColumnReader, Section) so section packages can swap between encoding implementations at runtime. this was done to make it easier to switch to the new dataset APIs @rfratto is currently experimenting with if they come to fruition.
Wire new sections into the index builder pipeline with new calculation steps and builder methods
Sort schema is injectable (currently hardcoded to [service_name], designed for future per-tenant configuration) cc @shantanualsi
On-disk serialization is deferred — builders use in-memory round-trip for testing; Flush will be implemented in a followup PR

Commit-by-commit review guide

The bulk of the work is done if the first 3 commits:

feat(stats): add stats section package — Full section package: type definitions, builder (accumulate/sort/split), columnar encoder, reader, row reader, 12 tests.
feat(postings): add postings section package — Same pattern with nullable columns (label_value, bloom_filter), binary columns (stream_id_bitmap), and bitmap normalization. 14 tests.
feat(index): wire stats and postings into index builder pipeline — streamLabels context plumbing, AppendStat/AppendLabelPosting/AppendBloomPosting on indexobj.Builder, statsCalculation + labelPostingsCalculation + columnValuesCalculation bloom extension, injectable sort schema via shared constants.

Encoding abstraction

The section packages define a SectionEncoder function type that the builder receives at construction. The current implementation (ColumnarEncoder) builds columnar arrays directly using the existing pkg/columnar primitives. This was done with the hopes of being able to easily add a DatasetEncoder implementation if that investigation proves fruitful. Doing it this way the two can be swapped in via config — no changes to builders, readers, or calculation steps (though we will need to think about how to track the format/version changes in the objects themselves).

Builder (accumulate, sort, split) — encoding-agnostic
  → SectionEncoder (injected function)
    ├─ ColumnarEncoder (current, uses pkg/columnar)
    └─ DatasetEncoder  (future, uses pkg/dataset/array)
  → Section (encoding-agnostic)
    → ColumnReader interface
      → RowReader (uses columnar.Array — shared by both paths)

Design spec

Stats Section

Type: {Namespace: "github.com/grafana/loki", Kind: "stats", Version: 1}

One row per unique (object_path, section_index, label_value) in the sort schema.

Column	Type	Description
`object_path`	UTF8	Path to the logs data object
`section_index`	Int64	Section index within the data object
`run_id`	Int64	FNV-64a hash of `object_path`
`sort_schema`	UTF8	Comma-delimited sort key names
`service_name`	UTF8	Label value for the sort key
`min_timestamp`	Int64	Min timestamp (UnixNano)
`max_timestamp`	Int64	Max timestamp (UnixNano)
`row_count`	Int64	Log record count
`uncompressed_size`	Int64	Sum of `len(log.Line)`

Sort order: [service_name, min_timestamp]

Postings Section

Type: {Namespace: "github.com/grafana/loki", Kind: "postings", Version: 1}

One row per (kind, object_path, section_index, column_name, label_value) tuple.

Column	Type	Nullable	Description
`kind`	Int64	No	0=Bloom, 1=Label
`object_path`	UTF8	No	Path to the logs data object
`section_index`	Int64	No	Section index
`column_name`	UTF8	No	Indexed label/column name
`label_value`	UTF8	Yes	Label value (Kind=Label only)
`bloom_filter`	Binary	Yes	Bloom filter bytes (Kind=Bloom only)
`stream_id_bitmap`	Binary	No	LSB bit-packed bitmap (Arrow convention)
`uncompressed_size`	Int64	No	Sum of `len(log.Line)`
`min_timestamp`	Int64	No	Min timestamp (UnixNano)
`max_timestamp`	Int64	No	Max timestamp (UnixNano)

Sort order: [kind, column_name, label_value, min_timestamp]

Stream ID Bitmap

Uses source stream IDs from the data object (scoped per data object per tenant)
LSB numbering matching Arrow validity bitmaps: bitmap[N/8] & (1 << (N%8))
All bitmaps in a section normalized to the same length for correct bitwise operations

Section Splitting

Accumulate-sort-then-split: rows sorted globally, streamed into sections up to TargetSectionSize. Split points are size-based, not aligned to sort key boundaries.

Future work

Dataset API encoder — Add encode_dataset.go implementations when pkg/dataset/array lands (from Robert's branch). The encoding abstraction is already in place.
Section storage format — On-disk serialization for persisting sections to index objects.
Query path integration — Wire postings reads into the metastore.
Configurable sort schema — Per-tenant configuration (injection point exists in calculation steps).

…, and reader

…ncoder, and reader

…lculation pipeline

trevorwhitney · 2026-04-07T21:47:00Z

@cursor please review

cursor · 2026-04-07T21:47:09Z

Excellent! The review document has been created. Now let me create a concise summary message for the user:

PR Review Complete ✅

I've completed a comprehensive review of your PR implementing stats and postings index sections with encoding abstraction. Here's my assessment:

Overall: APPROVED ✅

The implementation is excellent - well-architected, thoroughly tested, and production-ready for the in-memory round-trip phase.

Key Findings

Strengths:

Encoding Abstraction: Clean design that makes swapping implementations trivial
Test Coverage: 40 tests total across all packages, all passing
Code Quality: Follows Go best practices, proper error handling, good documentation
Architecture: Clear separation of concerns between builder, encoder, and reader layers

Test Results:

✅ pkg/dataobj/sections/stats: 12/12 tests pass (0.007s)
✅ pkg/dataobj/sections/postings: 14/14 tests pass (0.004s)  
✅ pkg/dataobj/index: 10/10 tests pass (0.727s)
✅ pkg/dataobj/index/indexobj: 4/4 tests pass (0.364s)

Detailed Review Areas

Stats Section ✅
- Correct sort implementation (label values → timestamp)
- Size-based section splitting works correctly
- Dynamic label columns handled elegantly
- Excellent test coverage including edge cases
Postings Section ✅
- Nullable column handling is correct
- Bitmap normalization ensures bitwise ops will work
- LSB bit ordering matches Arrow convention
- Sort order [Kind, ColumnName, LabelValue, MinTimestamp] verified
Index Integration ✅
- Stats calculation uses composite keys to avoid ambiguity
- Label postings builds bitmaps correctly with auto-resize
- Builder integration is clean with lazy initialization
- Deferred serialization approach is intentional and correct

Minor Suggestions (Non-blocking)

Sort Schema Parsing: Consider extracting to shared helper (duplicated in 2 places)
TODO Clarification: Add note that TODOs wait for on-disk flush implementation
Size Estimation: Document the 6*8 bytes calculation more explicitly

No Critical Issues Found

No memory leaks, race conditions, or panics
No incorrect error handling or security concerns
All edge cases properly tested

Commit Structure

The commit-by-commit approach is excellent:

Stats section package
Postings section package
Multi-key sort schema support
Index builder integration
Linter fixes

Each commit is self-contained and reviewable independently.

Full detailed review saved to: /workspace/PR_REVIEW.md

The PR is ready to merge! The encoding abstraction provides a solid foundation for adding the Dataset encoder when Robert's work lands, and the deferred on-disk serialization is the right approach for this phase.

cla-assistant · 2026-04-07T21:53:18Z

All committers have signed the CLA.

cla-assistant · 2026-04-07T21:53:22Z

Thank you for your submission! We really appreciate it. Like many open source projects, we ask that you all sign our Contributor License Agreement before we can accept your contribution.
1 out of 2 committers have signed the CLA.

✅ trevorwhitney
❌ cursoragent
_{You have signed the CLA already but the status is still pending? Let us recheck it.}

…ocations Clamp RowReader.Read output to destination buffer size in both stats and postings sections to prevent out-of-bounds writes when callers pass a buffer smaller than the section row count. Hoist strings.Builder out of the per-record loop in statsCalculation and defer labelMap allocation to the new-aggregate branch to reduce GC pressure in the hot path.

rfratto

Good start! I didn't look at the stats section because I imagine I'd have the same feedback for it that I had with the postings section.

rfratto · 2026-04-08T12:32:58Z

+//
+// Flush writes are done via [Builder.Flush], which encodes all accumulated
+// rows into a set of [Section] values that can be read back via a [Reader].
+type Builder struct {


This type should implement the dataobj.SectionBuilder interface to fully wire up properly (the Flush method doesn't match).

I think this will change where/how we wire up the encoder, so in my mind it makes most sense to do this in the next PR when implement serialization. I'll add a TODO to track this.

- Use SHA-224 for stats run ID instead of FNV-1a for consistency with data object key generation - Replace strings.Builder with FNV-64a hash for stats composite key to avoid per-record allocations (strings.Builder.Reset discards memory) - Create label postings for all stream label key/value pairs, not just sort schema keys, so all indexed labels are queryable - Add Name() to logsIndexCalculation interface for per-step metrics - Add calculator step duration histogram metric - Add benchmark for label postings ProcessBatch - Simplify column_values ProcessBatch with single early-return guard - Add SectionBuilder TODOs to postings and stats builders - Wire calculator metrics registration into index builder

rfratto

LGTM!

rfratto · 2026-04-10T14:52:14Z

 	objectPath     string
 	sectionIdx     int64
 	streamIDLookup map[int64]int64
+	streamLabels   map[int64]labels.Labels // source stream ID -> labels


Can we add a TODO here to monitor memory usage? This is going to be a shared object-scoped map. Streams sections are usually small enough that it shouldn't be a problem, but if it is we'll need to find a different approach here.

rfratto · 2026-04-10T15:00:24Z

+	for k := range c.postingsByKey {
+		keys = append(keys, k)
+	}
+	sort.Slice(keys, func(i, j int) bool {


nit: slices.SortFunc is the "modern" way to do this (and faster)

rfratto · 2026-04-10T15:26:48Z

+	"github.com/grafana/loki/v3/pkg/memory"
+)
+
+type labelPostingsCalculation struct {


Can we add a doc comment here explaining that this is section-scoped? Ditto for all the other ones.

rfratto · 2026-04-10T15:38:16Z

+	return nil
+}
+
+func writeHashKey(h hash.Hash64, i int, key, value string) error {


Can you write a benchmark for this? Since this is on the hot path and h is an interface, I think this will be kind of slow.

If it is slow, you can fix it by passing in a *bytes.Buffer, writing your key into that, then passing the buffer into h.Write (and resetting the buffer between calls).

that was a good call, ~3x faster with zero allocations.

rfratto · 2026-04-10T15:59:29Z

+	// Compute run-ID from object path using SHA-224.
+	// We take the first 8 bytes as an int64.
+	sum := sha256.Sum224([]byte(calcCtx.objectPath))
+	runID := int64(binary.BigEndian.Uint64(sum[:8]))


I know I mentioned that we should store a run ID to make it easier to easily know how to group sections by whether they follow the sort schema, but I think we should take this out in favour of trying to group things at run time by looking at the stats section.

This will particularly be helpful if we get a set of sections that already happen to be sorted and so they can be implicitly merged into an existing "run" without needing compaction to generate a new run ID first.

rfratto · 2026-04-10T16:01:43Z

+
+// Append adds a [Posting] row to the builder.
+func (b *Builder) Append(p Posting) {
+	b.rows = append(b.rows, p)


I'm worried about the memory overhead of accumulating all postings for the lifetime of the builder, but I think we can revisit this once you implement serialization.

rfratto · 2026-04-10T16:04:31Z

+// [Kind, ColumnName, LabelValue, MinTimestamp]. All comparisons are
+// lexicographic. Nil LabelValue sorts as empty string so Bloom entries come
+// before Label entries for the same column_name.
+func comparePostings(a, b Posting) bool {


Can we have an ultimate tiebreaker if all other things match? You can use comparison object paths + section indexes.

for posterity, I decided not to do this as the dataobj and section should be guaranteed to be the same here. I did add a final tie breaker per @rfratto's suggestion of max timestamp, so if min timestamps are equal the posting with the smaller max timestamp comes first.

rfratto · 2026-04-10T16:06:20Z

+	ObjectPath       string
+	SectionIndex     int64
+	ColumnName       string
+	LabelValue       *string // nil for Bloom postings


A pointer to a string feels odd to me. I know this is for blooms, but can we leave this as a string and then have the encoder encode a NULL for this column (regardless of what might be in LabelValue)?

rfratto · 2026-04-10T16:07:13Z

+	)
+
+	for i, r := range b.rows {
+		rowSize := 5*8 + len(r.ObjectPath) + len(r.ColumnName) + len(r.BloomFilter) + len(r.StreamIDBitmap) // 5 int64 columns × 8 bytes + variable-length fields


This should probably be a helper method on Posting

rfratto · 2026-04-10T16:09:37Z

We're moving towards columnar reads across the board. Is now the time to switch this over to columnar reads so we don't have to refactor it later? (I'm ok with this being a follow up)

will do after serialization

- Replace sort.Slice with slices.SortFunc in label_postings_calculation and stats_calculation for idiomatic Go - Optimize writeHashKey by building composite key in bytes.Buffer before hashing, eliminating per-Write string-to-byte allocations (~3x faster) - Change Posting.LabelValue from *string to string; use empty string for Bloom postings and Kind check in encoder for null column writes - Add MaxTimestamp as final tie-breaker in postings and stats sort order - Extract Posting.Size() helper method for row size estimation - Remove unused readNullableStringColumn/extractNullableStringValues - Fix unused runIDs variable in stats row_reader

pull-request-size Bot added the size/XXL label Apr 7, 2026

trevorwhitney added 2 commits April 7, 2026 12:05

feat(stats): add stats section package with builder, columnar encoder…

bccae96

…, and reader

feat(postings): add postings section package with builder, columnar e…

4407b76

…ncoder, and reader

trevorwhitney force-pushed the twhitney/new-index-sections branch 8 times, most recently from 87d3d3e to f246574 Compare April 7, 2026 19:51

feat(index): wire stats and postings into index builder pipeline

771ff3e

trevorwhitney force-pushed the twhitney/new-index-sections branch 7 times, most recently from 26eccd6 to 06133b0 Compare April 7, 2026 21:26

refactor(stats): support multi-key sort schemas in Stat struct and ca…

bb7b8b6

…lculation pipeline

trevorwhitney force-pushed the twhitney/new-index-sections branch from 06133b0 to bb7b8b6 Compare April 7, 2026 21:32

chore: rename to make linter happy

520aa28

Merge branch 'main' into twhitney/new-index-sections

0b05cad

trevorwhitney force-pushed the twhitney/new-index-sections branch from 7754a7b to 0b05cad Compare April 7, 2026 21:55

trevorwhitney marked this pull request as ready for review April 7, 2026 21:59

trevorwhitney requested a review from a team as a code owner April 7, 2026 21:59

trevorwhitney added 3 commits April 7, 2026 15:59

Merge branch 'main' into twhitney/new-index-sections

4b44977

Merge branch 'main' into twhitney/new-index-sections

57194b4

rfratto reviewed Apr 8, 2026

View reviewed changes

trevorwhitney added 3 commits April 9, 2026 14:10

chore: use natural sort and sh224

5da41f9

chore: add metrics and benchmark for batch process time

7d26490

rfratto approved these changes Apr 10, 2026

View reviewed changes

trevorwhitney merged commit 8553815 into main Apr 10, 2026
88 checks passed

trevorwhitney deleted the twhitney/new-index-sections branch April 10, 2026 23:00

trevorwhitney mentioned this pull request Apr 16, 2026

feat: On-disk serialization for postings and stats index sections #21591

Merged

This was referenced Apr 20, 2026

chore(k303): release 3.8.0 #21622

Closed

chore(k304): release 3.8.0 #21711

Closed

loki-gh-app Bot mentioned this pull request May 4, 2026

chore(k305): release 3.8.0 #21760

Closed

loki-gh-app Bot mentioned this pull request May 11, 2026

chore(k306): release 3.8.0 #21802

Closed

This was referenced May 20, 2026

chore(k307): release 3.8.0 #21968

Closed

chore(k308): release 3.8.0 #22007

Closed

loki-gh-app Bot mentioned this pull request Jun 1, 2026

chore(k309): release 3.8.0 #22136

Closed

This was referenced Jun 8, 2026

chore(k310): Release 3.8.0 #22294

Merged

chore(k310): Release 3.8.0 (backport main) #22303

Merged

chore(k310): Release 3.9.0 #22317

Closed

chore(k311): Release 3.9.0 #22415

Open

loki-gh-app Bot mentioned this pull request Jun 22, 2026

chore(k312): Release 3.9.0 #22492

Open

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

feat: add stats and postings index sections with encoding abstraction - #21442

feat: add stats and postings index sections with encoding abstraction#21442
trevorwhitney merged 13 commits into
mainfrom
twhitney/new-index-sections

trevorwhitney commented Apr 7, 2026 •

edited

Loading

trevorwhitney commented Apr 7, 2026

cursor Bot commented Apr 7, 2026 •

edited

Loading

cla-assistant Bot commented Apr 7, 2026 •

edited

Loading

cla-assistant Bot commented Apr 7, 2026

rfratto left a comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

rfratto Apr 8, 2026

trevorwhitney Apr 9, 2026

rfratto left a comment

rfratto Apr 10, 2026

rfratto Apr 10, 2026

rfratto Apr 10, 2026

rfratto Apr 10, 2026

trevorwhitney Apr 10, 2026

rfratto Apr 10, 2026

rfratto Apr 10, 2026

rfratto Apr 10, 2026

trevorwhitney Apr 10, 2026

rfratto Apr 10, 2026

rfratto Apr 10, 2026

rfratto Apr 10, 2026

trevorwhitney Apr 10, 2026

Uh oh!

Labels

2 participants

Uh oh!

Conversation

trevorwhitney commented Apr 7, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Summary

Commit-by-commit review guide

Encoding abstraction

Stats Section

Postings Section

Stream ID Bitmap

Section Splitting

Future work

trevorwhitney commented Apr 7, 2026

cursor Bot commented Apr 7, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

PR Review Complete ✅

Overall: APPROVED ✅

Key Findings

Detailed Review Areas

Minor Suggestions (Non-blocking)

No Critical Issues Found

Commit Structure

cla-assistant Bot commented Apr 7, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

cla-assistant Bot commented Apr 7, 2026

rfratto left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Choose a reason for hiding this comment

rfratto left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Uh oh!

Labels

2 participants

trevorwhitney commented Apr 7, 2026 •

edited

Loading

cursor Bot commented Apr 7, 2026 •

edited

Loading

cla-assistant Bot commented Apr 7, 2026 •

edited

Loading