Background
Follow-up from PR review feedback on #22233 (review comment).
The IndexMerge executor performs K-way merges over postings and stats sections using the pkg/util/loser tournament tree (the same primitive sortmerge uses for log sections). During review, the question came up of whether the loser tree guarantees a stable ordering when two sequences compare equal — i.e. that ties are broken deterministically by sequence index.
Problem
@bboreham determined the loser tree is not stable. Per pkg/util/loser/tree.go#L113:
// If n.value < pos.value then pos loses.
// If they are equal, pos wins because n could be a sequence that ended, with value maxval.
Because equal values resolve in favour of pos, two sequences that compare equal will alternate rather than emerge in a stable, index-ordered sequence.
Proposed change
@bboreham noted it does not seem hard to make the tree stable: the loser tree already knows each sequence's index, so adding tie-breaking by index would be straightforward if the comparator were tri-state (i.e. returning less/equal/greater rather than the current boolean less). Since this copy of the loser tree lives inside Loki (rather than an upstream dependency), it is low-impact to try the change here.
Sketch
- Introduce a tri-state compare function (e.g.
cmp(a, b E) int) alongside or in place of the boolean less.
- In
replayGames/playGame, when two values compare equal, break the tie using the known sequence index so lower-indexed sequences win deterministically.
Why this matters
The IndexMerge executor currently relies on (ObjectPath, SectionIndex) being referenced by exactly one source index (last-wins on collisions, recorded via stats). A stable loser tree would let the executor depend on deterministic tie-breaking by index rather than the current alternating behaviour, simplifying reasoning about merge output ordering for any consumer that needs a total, stable order.
Acceptance criteria
Background
Follow-up from PR review feedback on #22233 (review comment).
The IndexMerge executor performs K-way merges over postings and stats sections using the
pkg/util/losertournament tree (the same primitivesortmergeuses for log sections). During review, the question came up of whether the loser tree guarantees a stable ordering when two sequences compare equal — i.e. that ties are broken deterministically by sequence index.Problem
@bboreham determined the loser tree is not stable. Per
pkg/util/loser/tree.go#L113:Because equal values resolve in favour of
pos, two sequences that compare equal will alternate rather than emerge in a stable, index-ordered sequence.Proposed change
@bboreham noted it does not seem hard to make the tree stable: the loser tree already knows each sequence's index, so adding tie-breaking by index would be straightforward if the comparator were tri-state (i.e. returning less/equal/greater rather than the current boolean
less). Since this copy of the loser tree lives inside Loki (rather than an upstream dependency), it is low-impact to try the change here.Sketch
cmp(a, b E) int) alongside or in place of the booleanless.replayGames/playGame, when two values compare equal, break the tie using the known sequence index so lower-indexed sequences win deterministically.Why this matters
The IndexMerge executor currently relies on
(ObjectPath, SectionIndex)being referenced by exactly one source index (last-wins on collisions, recorded via stats). A stable loser tree would let the executor depend on deterministic tie-breaking by index rather than the current alternating behaviour, simplifying reasoning about merge output ordering for any consumer that needs a total, stable order.Acceptance criteria
pkg/util/losersupports stable ordering: equal-keyed sequences emerge in deterministic (index) order.loserandsortmergecallers are unaffected (or updated as needed).