src/Sstable.bend
mylsm-lsm-store@0.6.0.0 · 536 lines · 0 definitions
1import Base
2import mylsm-lsm-store@0.6.0.0/src/Keys.bend as Keys
3import mylsm-lsm-store@0.6.0.0/src/MemTable.bend as MemTable
4import mylsm-lsm-store@0.6.0.0/src/BitTree.bend as BitTree
5import mylsm-lsm-store@0.6.0.0/src/SortedRun.bend as SortedRun
6
7# SSTables (Task 4): immutable strict sorted runs with BitTree Bloom filters.
8# `build` canonicalizes newest-first raw entries; `from_sorted_unique` trusts an
9# already strict, unique run and deliberately performs no sorting.
10
11# Represent Bloom data used by the SSTable indexes, filters, and lookup.
12type Bloom is Data:
13 Blm{bits: BitTree.BitTree, size: Nat}
14
15# Represent Table data used by the SSTable indexes, filters, and lookup.
16type Table is Data:
17 Tbl{
18 entries: List<&2, MemTable.Entry>,
19 filter: Bloom,
20 nbits: Nat,
21 smallest: Maybe<&2, String>,
22 largest: Maybe<&2, String>,
23 count: Nat,
24 chunks: List<&2, List<&2, MemTable.Entry>>,
25 blocks: List<&2, String>
26 }
27
28# Handle the block entries for the SSTable indexes, filters, and lookup.
29def block_entries() -> Nat:
30 64n
31
32# Handle the chunk go for the SSTable indexes, filters, and lookup.
33def chunk_go(
34 fuel: Nat,
35 +entries: List<&2, MemTable.Entry>,
36 +cur: List<&2, MemTable.Entry>,
37 room: Nat,
38 acc: List<&2, List<&2, MemTable.Entry>>
39) -> List<&2, List<&2, MemTable.Entry>>:
40 match fuel:
41 case 0n:
42 List.reverse(&2, List<&2, MemTable.Entry>, Con{List.reverse(&2, MemTable.Entry, cur), acc})
43 case 1n+f:
44 match entries:
45 case Nil{}:
46 List.reverse(&2, List<&2, MemTable.Entry>, Con{List.reverse(&2, MemTable.Entry, cur), acc})
47 case Con{e, t}:
48 match room:
49 case 0n:
50 chunk_go(f, t, Con{e, Nil{}}, Nat.sub(block_entries(), 1n), Con{List.reverse(&2, MemTable.Entry, cur), acc})
51 case 1n+r:
52 chunk_go(f, t, Con{e, cur}, r, acc)
53
54# Handle chunk in the SSTable indexes, filters, and lookup.
55def chunk(+entries: List<&2, MemTable.Entry>) -> List<&2, List<&2, MemTable.Entry>>:
56 match entries:
57 case Nil{}:
58 Nil{}
59 case Con{e, t}:
60 chunk_go(List.length(&2, MemTable.Entry, entries), t, Con{e, Nil{}}, Nat.sub(block_entries(), 1n), Nil{})
61
62# Handle the chunk head key for the SSTable indexes, filters, and lookup.
63def chunk_head_key(+xs: List<&2, MemTable.Entry>) -> Maybe<&2, String>:
64 match xs:
65 case Nil{}:
66 None{}
67 case Con{MemTable.Entry{key, val}, t}:
68 Some{key}
69
70# Handle the block cons acc for the SSTable indexes, filters, and lookup.
71def block_cons_acc(head: Maybe<&2, String>, acc: List<&2, String>) -> List<&2, String>:
72 match head:
73 case None{}:
74 acc
75 case Some{k}:
76 Con{k, acc}
77
78# Handle the block keys for the SSTable indexes, filters, and lookup.
79def block_keys(+chunks: List<&2, List<&2, MemTable.Entry>>, acc: List<&2, String>) -> List<&2, String>:
80 match chunks:
81 case Nil{}:
82 List.reverse(&2, String, acc)
83 case Con{c, t}:
84 block_keys(t, block_cons_acc(chunk_head_key(c), acc))
85
86# Represent Metadata data used by the SSTable indexes, filters, and lookup.
87type Metadata is Data:
88 Meta{smallest: Maybe<&2, String>, largest: Maybe<&2, String>, count: Nat}
89
90# --- Bloom allocator (Monkey-style: smaller/upper levels get more bits) ---
91# Closed form pinned here; Dayan-exact coefficients are tuning follow-up.
92def bloom_bits(level: Nat, est_keys: Nat) -> Nat:
93 match level:
94 case 0n:
95 Nat.mul(est_keys, 20n)
96 case 1n+m:
97 match m:
98 case 0n:
99 Nat.mul(est_keys, 10n)
100 case 1n+p:
101 Nat.mul(est_keys, 5n)
102
103# --- Local byte hash (kept stable for on-disk/rebuild compatibility) ---
104def bhash(str: String, acc: U32) -> U32:
105 match str:
106 case SNil{}:
107 acc
108 case SCon{c, t}:
109 bhash(t, U32.add(U32.mul(acc, 31), Char.to_u32(c)))
110
111# --- U32->Nat bridges that stay checker-tractable ---
112# The Bend checker does not share across sequentially-chained U32.mul terms:
113# `U32.to_nat` applied to a hash accumulated over 4+ bytes diverges in
114# `{==}` elaboration (runtime is unaffected). The bridges below therefore
115# never materialize a chained U32 as a Nat: each `to_nat` covers at most two
116# U32 ops (shift+mask on the ORIGINAL word — parallel, shared), and all
117# accumulation happens in small-Nat land. Both are EXACT (no semantic
118# change): bytes are the base-256 digits of the word (Horner), so
119# u32_to_nat_exact(w) == U32.to_nat(w) and bhash_n computes the same mod.
120def u32_byte(+word: U32, shift: Nat) -> Nat:
121 U32.to_nat(U32.and(U32.shrn(word, shift), 255))
122
123# Encode or decode a 32-bit word for to nat exact for the SSTable indexes, filters, and lookup.
124def u32_to_nat_exact(+word: U32) -> Nat:
125 +b0 = u32_byte(word, 24n)
126 +b1 = u32_byte(word, 16n)
127 +b2 = u32_byte(word, 8n)
128 +b3 = u32_byte(word, 0n)
129 Nat.add(Nat.mul(b0, Nat.mul(Nat.mul(256n, 256n), 256n)), Nat.add(Nat.mul(b1, Nat.mul(256n, 256n)), Nat.add(Nat.mul(b2, 256n), b3)))
130
131# Handle bhash n pos in the SSTable indexes, filters, and lookup.
132def bhash_n_pos(+str: String, +seed: U32, +mod: Nat) -> Nat:
133 +w = bhash(str, seed)
134 +a0 = Nat.mod(u32_byte(w, 24n), mod)
135 +a1 = Nat.mod(Nat.add(Nat.mul(a0, 256n), u32_byte(w, 16n)), mod)
136 +a2 = Nat.mod(Nat.add(Nat.mul(a1, 256n), u32_byte(w, 8n)), mod)
137 Nat.mod(Nat.add(Nat.mul(a2, 256n), u32_byte(w, 0n)), mod)
138
139# Handle bhash n in the SSTable indexes, filters, and lookup.
140def bhash_n(str: String, seed: U32, mod: Nat) -> Nat:
141 match mod:
142 case 0n:
143 0n
144 case 1n+p:
145 bhash_n_pos(str, seed, mod)
146
147# BitTree stores whole U32 words while Bloom.size preserves the exact logical
148# bit count selected by bloom_bits.
149def bit_words(num: Nat) -> Nat:
150 match num:
151 case 0n:
152 0n
153 case 1n+m:
154 Nat.add(1n, Nat.div(m, 32n))
155
156# Handle bit data for new for the SSTable indexes, filters, and lookup.
157def bits_new(+num: Nat) -> BitTree.BitTree:
158 BitTree.new(bit_words(num))
159
160# Handle bit set in the SSTable indexes, filters, and lookup.
161def bit_set(idx: Nat, bits: BitTree.BitTree) -> BitTree.BitTree:
162 BitTree.set(bits, idx)
163
164# Handle bit get in the SSTable indexes, filters, and lookup.
165def bit_get(idx: Nat, bits: BitTree.BitTree) -> Bool:
166 BitTree.test(bits, idx)
167
168# Handle Bloom filter data for new for the SSTable indexes, filters, and lookup.
169def bloom_new(+num: Nat) -> Bloom:
170 Blm{bits_new(num), num}
171
172# Handle Bloom filter data for well formed for the SSTable indexes, filters, and lookup.
173def bloom_well_formed(bloom: Bloom) -> Bool:
174 match bloom:
175 case Blm{+bits, +size}:
176 Bool.and(
177 BitTree.well_formed(bits),
178 Bool.and(
179 Nat.is_eq(BitTree.word_count(bits), bit_words(size)),
180 Nat.is_le(size, BitTree.bit_count(bits))))
181
182# Handle Bloom filter data for add for the SSTable indexes, filters, and lookup.
183def bloom_add(bloom: Bloom, +key: String) -> Bloom:
184 match bloom:
185 case Blm{bits, +size}:
186 Blm{bit_set(bhash_n(key, 17, size), bit_set(bhash_n(key, 257, size), bits)), size}
187
188# Handle both in the SSTable indexes, filters, and lookup.
189def both(lhs: Bool, rhs: Bool) -> Bool:
190 match lhs:
191 case True{}:
192 rhs
193 case False{}:
194 False{}
195
196# Handle Bloom filter data for test for the SSTable indexes, filters, and lookup.
197def bloom_test(bloom: Bloom, +key: String) -> Bool:
198 match bloom:
199 case Blm{+bits, +size}:
200 both(bit_get(bhash_n(key, 17, size), bits), bit_get(bhash_n(key, 257, size), bits))
201
202# Return the table bits for the SSTable indexes, filters, and lookup.
203def table_bits(tab: Table) -> Nat:
204 match tab:
205 case Tbl{entries, filter, nbits, smallest, largest, count, chunks, blocks}:
206 nbits
207
208# Handle the optional value for present for the SSTable indexes, filters, and lookup.
209def maybe_present(tab: Table, +key: String) -> Bool:
210 match tab:
211 case Tbl{entries, filter, nbits, smallest, largest, count, chunks, blocks}:
212 bloom_test(filter, key)
213
214# --- Parallel probe counters (Task 1): sequential leaf, two-way fork, `!` gate ---
215# Single probe as 0/1 for counting.
216def probe_hit_if(present: Bool) -> Nat:
217 match present:
218 case True{}:
219 1n
220 case False{}:
221 0n
222
223# Count matching probes sequentially.
224def probe_hit(+tab: Table, +key: String) -> Nat:
225 probe_hit_if(maybe_present(tab, key))
226
227# Sequential probe count over a probe list.
228def probe_count_seq(+probes: List<&2, String>, +tab: Table) -> Nat:
229 match probes:
230 case Nil{}:
231 0n
232 case Con{+q, t}:
233 Nat.add(probe_count_seq(t, tab), probe_hit(tab, q))
234
235# Two-way parallel probe count; halves share no state.
236def probe_count_par(+probes: List<&2, String>, +tab: Table) -> Nat:
237 +half = Nat.div(List.length(&2, String, probes), 2n)
238 left right = probe_count_seq(List.take(&2, String, probes, half), tab) probe_count_seq(List.drop(&2, String, probes, half), tab)
239 Nat.add(left, right)
240
241# --- Canonicalization and construction ---
242def bloom_of(entries: List<&2, MemTable.Entry>, +blm: Bloom) -> Bloom:
243 match entries:
244 case Nil{}:
245 blm
246 case Con{e, t}:
247 match e:
248 case MemTable.Entry{key, val}:
249 bloom_of(t, bloom_add(blm, key))
250
251# Handle Bloom filter data for union trees for the SSTable indexes, filters, and lookup.
252def bloom_union_trees(+abits: BitTree.BitTree, +bbits: BitTree.BitTree, size: Nat) -> Bloom:
253 match abits:
254 case BitTree.BT{aroot, awords, acap, aheight}:
255 match bbits:
256 case BitTree.BT{broot, bwords, bcap, bheight}:
257 Blm{BitTree.BT{BitTree.union_bits(aroot, broot), awords, acap, aheight}, size}
258
259# Handle Bloom filter data for union for the SSTable indexes, filters, and lookup.
260def bloom_union(ba: Bloom, bb: Bloom) -> Bloom:
261 match ba:
262 case Blm{abits, asize}:
263 match bb:
264 case Blm{bbits, bsize}:
265 bloom_union_trees(abits, bbits, Nat.max(asize, bsize))
266
267# Handle Bloom filter data for of chunk for the SSTable indexes, filters, and lookup.
268def bloom_of_chunk(+chunk: List<&2, MemTable.Entry>, +nb: Nat) -> Bloom:
269 bloom_of(chunk, bloom_new(nb))
270
271# Two-half parallel build (spike 1): one spawn, one union. Sequential below.
272def bloom_of_par(+entries: List<&2, MemTable.Entry>, +nb: Nat) -> Bloom:
273 +half = Nat.div(List.length(&2, MemTable.Entry, entries), 2n)
274 left right = bloom_of_chunk(List.take(&2, MemTable.Entry, entries, half), nb) bloom_of_chunk(List.drop(&2, MemTable.Entry, entries, half), nb)
275 bloom_union(left, right)
276
277# --- Four-chunk parallel build (Task 2): two-level fork, three unions ---
278# Third chunk slice as take-after-drop.
279def chunk_third(+entries: List<&2, MemTable.Entry>, +skip: Nat, +take: Nat) -> List<&2, MemTable.Entry>:
280 List.take(&2, MemTable.Entry, List.drop(&2, MemTable.Entry, entries, skip), take)
281
282# Four-way chunk build with a two-level fork tree.
283def bloom_of_chunks(+entries: List<&2, MemTable.Entry>, +nb: Nat) -> Bloom:
284 +num = List.length(&2, MemTable.Entry, entries)
285 +q = Nat.div(num, 4n)
286 a b = bloom_of_chunk(List.take(&2, MemTable.Entry, entries, q), nb) bloom_of_chunk(chunk_third(entries, q, q), nb)
287 c d = bloom_of_chunk(chunk_third(entries, Nat.mul(q, 2n), q), nb) bloom_of_chunk(List.drop(&2, MemTable.Entry, entries, Nat.mul(q, 3n)), nb)
288 bloom_union(bloom_union(a, b), bloom_union(c, d))
289
290# --- Hybrid bloom (spike): parallel index collection, sequential assembly ---
291# Phase 1 emits a flat index list (two per key); joins concatenate, so no
292# chunk tree or union is ever built. Phase 2 folds the indexes into ONE tree
293# on the CPU. This removes the tree-allocation amplification that costs ~10%
294# at 1M scale in the chunk+union design, while keeping a fork tree that a
295# future `!` can ship once the GPU recovery crash is fixed upstream.
296# Both bit positions of one key as a flat two-element list.
297def key_idxs(+key: String, +size: Nat) -> List<&2, Nat>:
298 Con{bhash_n(key, 17, size), Con{bhash_n(key, 257, size), Nil{}}}
299
300# Sequential index collection over entries.
301def hash_idxs_seq(+entries: List<&2, MemTable.Entry>, +size: Nat) -> List<&2, Nat>:
302 match entries:
303 case Nil{}:
304 Nil{}
305 case Con{MemTable.Entry{key, val}, t}:
306 List.append(&2, Nat, key_idxs(key, size), hash_idxs_seq(t, size))
307
308# Balanced parallel index collection; reusable fuel bounds the fork depth.
309def hash_idxs_par_go(+fuel: Nat, +entries: List<&2, MemTable.Entry>, +size: Nat) -> List<&2, Nat>:
310 match fuel:
311 case 0n:
312 hash_idxs_seq(entries, size)
313 case 1n+f:
314 match entries:
315 case Nil{}:
316 Nil{}
317 case Con{MemTable.Entry{key, val}, Nil{}}:
318 key_idxs(key, size)
319 case Con{_, Con{_, _}}:
320 +half = Nat.div(List.length(&2, MemTable.Entry, entries), 2n)
321 left right = hash_idxs_par_go(f, List.take(&2, MemTable.Entry, entries, half), size) hash_idxs_par_go(f, List.drop(&2, MemTable.Entry, entries, half), size)
322 List.append(&2, Nat, left, right)
323
324# Parallel entry point; fuel covers the fork depth.
325def hash_idxs_par(+entries: List<&2, MemTable.Entry>, +size: Nat) -> List<&2, Nat>:
326 +fuel = List.length(&2, MemTable.Entry, entries)
327 hash_idxs_par_go(fuel, entries, size)
328
329# Sequential assembly of one filter from a flat index list.
330def bloom_set_all(+idxs: List<&2, Nat>, +blm: Bloom) -> Bloom:
331 match idxs:
332 case Nil{}:
333 blm
334 case Con{+i, t}:
335 match blm:
336 case Blm{bits, +size}:
337 bloom_set_all(t, Blm{bit_set(i, bits), size})
338
339# Hybrid build: parallel hashing, single-tree assembly.
340def bloom_of_hybrid(+entries: List<&2, MemTable.Entry>, +nb: Nat) -> Bloom:
341 bloom_set_all(hash_idxs_par(entries, nb), bloom_new(nb))
342
343# Size-gated entry point: sequential on both sides of the gate.
344# MEASURED VERDICT (2026-09-26, 1M interleaved A/B, Darwin arm64, Bend 2.0.28):
345# sequential median 225105 ms (4442 ops/s) vs 4-chunk 249150 ms (4014 ops/s)
346# vs hybrid 261746 ms — the parallel builds cost ~10% (fork/join plus
347# allocation overhead dominates; invisible at 100k, compounds over 244
348# flushes). Confirmed under two machine states (all arms shifted +15k ms on
349# the slow day; relative order unchanged). The parallel builds stay as
350# law-covered spikes; the `!` variants stay opt-in behind the GPU recovery
351# crash documented below.
352def bloom_pick(small: Bool, +entries: List<&2, MemTable.Entry>, +nb: Nat) -> Bloom:
353 match small:
354 case True{}:
355 bloom_of(entries, bloom_new(nb))
356 case False{}:
357 bloom_of(entries, bloom_new(nb))
358
359# Handle Bloom filter data for of auto for the SSTable indexes, filters, and lookup.
360def bloom_of_auto(+entries: List<&2, MemTable.Entry>, +nb: Nat) -> Bloom:
361 bloom_pick(Nat.is_lt(List.length(&2, MemTable.Entry, entries), 2048n), entries, nb)
362
363# Build table metadata for tail for the SSTable indexes, filters, and lookup.
364def metadata_tail(entries: List<&2, MemTable.Entry>, +first: String, last: String, +count: Nat) -> Metadata:
365 match entries:
366 case Nil{}:
367 Meta{Some{first}, Some{last}, count}
368 case Con{MemTable.Entry{key, val}, rest}:
369 metadata_tail(rest, first, key, Nat.add(count, 1n))
370
371# Handle metadata in the SSTable indexes, filters, and lookup.
372def metadata(entries: List<&2, MemTable.Entry>) -> Metadata:
373 match entries:
374 case Nil{}:
375 Meta{None{}, None{}, 0n}
376 case Con{MemTable.Entry{+key, val}, rest}:
377 metadata_tail(rest, key, key, 1n)
378
379# Handle from sorted unique est meta in the SSTable indexes, filters, and lookup.
380def from_sorted_unique_est_meta(+entries: List<&2, MemTable.Entry>, level: Nat, est_keys: Nat, meta: Metadata) -> Table:
381 match meta:
382 case Meta{smallest, largest, count}:
383 +nb = bloom_bits(level, est_keys)
384 Tbl{entries, bloom_of_auto(entries, nb), nb, smallest, largest, count, chunk(entries), block_keys(chunk(entries), Nil{})}
385
386# Handle from sorted unique meta in the SSTable indexes, filters, and lookup.
387def from_sorted_unique_meta(+entries: List<&2, MemTable.Entry>, level: Nat, meta: Metadata) -> Table:
388 match meta:
389 case Meta{smallest, largest, +count}:
390 +nb = bloom_bits(level, count)
391 Tbl{entries, bloom_of_auto(entries, nb), nb, smallest, largest, count, chunk(entries), block_keys(chunk(entries), Nil{})}
392
393# Handle from sorted unique in the SSTable indexes, filters, and lookup.
394def from_sorted_unique(+entries: List<&2, MemTable.Entry>, level: Nat) -> Table:
395 from_sorted_unique_meta(entries, level, metadata(entries))
396
397# Build sorted for the SSTable indexes, filters, and lookup.
398def build_sorted(+entries: List<&2, MemTable.Entry>, level: Nat, est_keys: Nat) -> Table:
399 from_sorted_unique_est_meta(entries, level, est_keys, metadata(entries))
400
401# Handle build in the SSTable indexes, filters, and lookup.
402def build(+entries: List<&2, MemTable.Entry>, level: Nat, est_keys: Nat) -> Table:
403 +effective = Nat.max(est_keys, List.length(&2, MemTable.Entry, entries))
404 build_sorted(SortedRun.sort_newest(entries), level, effective)
405
406# Metadata accessors keep clients independent of the Tbl field layout.
407def table_smallest(tab: Table) -> Maybe<&2, String>:
408 match tab:
409 case Tbl{entries, filter, nbits, smallest, largest, count, chunks, blocks}:
410 smallest
411
412# Return the table largest for the SSTable indexes, filters, and lookup.
413def table_largest(tab: Table) -> Maybe<&2, String>:
414 match tab:
415 case Tbl{entries, filter, nbits, smallest, largest, count, chunks, blocks}:
416 largest
417
418# Return the table count for the SSTable indexes, filters, and lookup.
419def table_count(tab: Table) -> Nat:
420 match tab:
421 case Tbl{entries, filter, nbits, smallest, largest, count, chunks, blocks}:
422 count
423
424# Open bridge: metadata is matched explicitly so the Bloom schedule projects
425# through `build` without relying on reduction of an open entry list.
426def table_bits_from_meta(
427 +entries: List<&2, MemTable.Entry>,
428 level: Nat,
429 est_keys: Nat,
430 meta: Metadata,
431) -> {table_bits(from_sorted_unique_est_meta(entries, level, est_keys, meta)) == bloom_bits(level, est_keys) : Nat}:
432 match meta:
433 case Meta{smallest, largest, count}:
434 {==}
435
436# Return the table bits build for the SSTable indexes, filters, and lookup.
437def table_bits_build(
438 +entries: List<&2, MemTable.Entry>,
439 level: Nat,
440 est_keys: Nat,
441) -> {table_bits(build(entries, level, est_keys)) == bloom_bits(level, Nat.max(est_keys, List.length(&2, MemTable.Entry, entries))) : Nat}:
442 +effective = Nat.max(est_keys, List.length(&2, MemTable.Entry, entries))
443 table_bits_from_meta(SortedRun.sort_newest(entries), level, effective, metadata(SortedRun.sort_newest(entries)))
444
445
446# Block-scoped lookup. Checker constraints (proven by scratch experiments):
447# multi-scrutinee matches follow declaration order, and only Nat answers flow
448# through match arms — so selection returns an index, picked up by chunk_at_go.
449def pick_ix(bt: List<&2, String>, ct: List<&2, List<&2, MemTable.Entry>>, ix: Nat, +key: String, order: Cmp) -> Nat:
450 match bt ct order:
451 case _ _ GT{}:
452 Nat.sub(ix, 1n)
453 case Nil{} _ _:
454 ix
455 case _ Nil{} _:
456 ix
457 case Con{b2, bt2} Con{d2, ct2} LT{}:
458 pick_ix(bt2, ct2, Nat.add(ix, 1n), key, Keys.cmp(b2, key))
459 case Con{b2, bt2} Con{d2, ct2} EQ{}:
460 ix
461
462# Handle the chunk at go for the SSTable indexes, filters, and lookup.
463def chunk_at_go(fuel: Nat, +chunks: List<&2, List<&2, MemTable.Entry>>, ix: Nat) -> List<&2, MemTable.Entry>:
464 match fuel chunks:
465 case 0n _:
466 Nil{}
467 case 1n+f Nil{}:
468 Nil{}
469 case 1n+f Con{c, t}:
470 match ix:
471 case 0n:
472 c
473 case 1n+p:
474 chunk_at_go(f, t, p)
475
476# Handle the chunk at for the SSTable indexes, filters, and lookup.
477def chunk_at(+chunks: List<&2, List<&2, MemTable.Entry>>, ix: Nat) -> List<&2, MemTable.Entry>:
478 chunk_at_go(List.length(&2, List<&2, MemTable.Entry>, chunks), chunks, ix)
479
480# Handle the block scan for the SSTable indexes, filters, and lookup.
481def block_scan(+chunk: List<&2, MemTable.Entry>, +key: String) -> Maybe<&2, String>:
482 MemTable.get(MemTable.MT{chunk}, key)
483
484# Handle the block pick for the SSTable indexes, filters, and lookup.
485def block_pick(
486 +chunks: List<&2, List<&2, MemTable.Entry>>,
487 +blocks: List<&2, String>,
488 +key: String
489) -> List<&2, MemTable.Entry>:
490 match chunks blocks:
491 case Nil{} _:
492 Nil{}
493 case _ Nil{}:
494 Nil{}
495 case Con{c, ct} Con{b, bt}:
496 chunk_at(chunks, pick_ix(bt, ct, 0n, key, Keys.cmp(b, key)))
497
498# Handle the block finish for the SSTable indexes, filters, and lookup.
499def block_finish(
500 picked: List<&2, MemTable.Entry>,
501 +entries: List<&2, MemTable.Entry>,
502 +key: String
503) -> Maybe<&2, String>:
504 match picked:
505 case Nil{}:
506 MemTable.get(MemTable.MT{entries}, key)
507 case Con{e, t}:
508 block_scan(Con{e, t}, key)
509
510# Resolve the hit for finish for the SSTable indexes, filters, and lookup.
511def hit_finish(
512 picked: List<&2, MemTable.Entry>,
513 +entries: List<&2, MemTable.Entry>,
514 +key: String
515) -> Maybe<&2, Maybe<&2, String>>:
516 match picked:
517 case Nil{}:
518 MemTable.get_hit(MemTable.MT{entries}, key)
519 case Con{e, t}:
520 MemTable.get_hit(MemTable.MT{Con{e, t}}, key)
521
522# Handle the block get hit for the SSTable indexes, filters, and lookup.
523def block_get_hit(tab: Table, +key: String) -> Maybe<&2, Maybe<&2, String>>:
524 match tab:
525 case Tbl{entries, filter, nbits, smallest, largest, count, chunks, blocks}:
526 hit_finish(block_pick(chunks, blocks, key), entries, key)
527
528# Handle the block get for the SSTable indexes, filters, and lookup.
529def block_get(tab: Table, +key: String) -> Maybe<&2, String>:
530 match tab:
531 case Tbl{entries, filter, nbits, smallest, largest, count, chunks, blocks}:
532 block_finish(block_pick(chunks, blocks, key), entries, key)
533
534# Handle lookup in the SSTable indexes, filters, and lookup.
535def lookup(tab: Table, +key: String) -> Maybe<&2, String>:
536 block_get(tab, key)