src/scan/ScanMerge.bend

mylsm-lsm-store@0.6.0.0 · 55 lines · 0 definitions

1import Base
2
3# Describes which source heads advance and whether a visible record is emitted.
4type Decision is Data:
5  Finished{}
6  EmitBase{}
7  EmitDelta{}
8  EmitBoth{}
9  SkipDelta{}
10  SkipBoth{}
11
12# Emits a delta value or advances past a delta tombstone without a base head.
13def delta.without.base(live: Bool) -> Decision:
14  match live:
15    case True{}: EmitDelta{}
16    case False{}: SkipDelta{}
17
18# Emits an SST head when no newer delta head is available.
19def base.without.delta() -> Decision:
20  EmitBase{}
21
22# Applies ordering and tombstone precedence when both sources have a head.
23def both.live(live: Bool, order: Cmp) -> Decision:
24  match live:
25    case True{}:
26      match order:
27        case LT{}: EmitDelta{}
28        case EQ{}: EmitBoth{}
29        case GT{}: EmitBase{}
30    case False{}:
31      match order:
32        case LT{}: SkipDelta{}
33        case EQ{}: SkipBoth{}
34        case GT{}: EmitBase{}
35
36# Exposes the two-head comparison transition for the top-level selector.
37def both(live: Bool, order: Cmp) -> Decision:
38  both.live(live, order)
39
40# Selects the next merge transition for sorted SST and delta heads.
41def choose(
42  base_exists: Bool,
43  delta_exists: Bool,
44  delta_live: Bool,
45  order: Cmp
46) -> Decision:
47  match base_exists:
48    case True{}:
49      match delta_exists:
50        case True{}: both(delta_live, order)
51        case False{}: base.without.delta()
52    case False{}:
53      match delta_exists:
54        case True{}: delta.without.base(delta_live)
55        case False{}: Finished{}