Status: todo → in progress → done. Add a one-line takeaway when done.
#
Topic
Status
Takeaway
0
The Performance Toolbox
done
Benchmarks lie by default: my own cache_ladder measured its own cache footprint until the walker carried state; flamegraph showed 21% of HashMap lookup time is SipHash; DRAM ladder verified at ~1/5/100 ns.
2026-07-12 — restructure rollout: all 179 remaining reading guides across topics 00-25 and 27-32 rewritten as self-contained chapters (topic 26 was the pilot, previous entry), executed by 8 parallel agents (4 topics each) against the same spec: concept-first H1 titles replacing “Reading guide — …”, Sources blocks replaced by 2-4 sentence framing leads, one inline Rust-ish code sample of the core algorithm added where the guide lacked one (skips documented for pure surveys / guides already carrying equivalent code), all existing content kept (diagrams, line-anchor tables, questions, tie-backs), ## References appended with Papers (arXiv) + Code (GitHub) links carrying the old reading advice, filenames unchanged to avoid link churn; the 32 topic READMEs’ guide lists updated to the new titles; one agent (topics 16-19) hit context limits with 2 files left — reading-umbra-tidy-tuples.md (retitled “Umbra & copy-and-patch: the war on compile latency” + copy-and-patch memcpy/patch-holes sample + References) and reading-sqlite-vdbe.md (References) finished by hand; SUMMARY.md link titles regenerated centrally by script from the actual on-disk H1s rather than agent reports (179 updated); verification: zero old-style H1s, zero Sources blocks, zero guides missing References, fence-and-backtick-aware bare-angle-bracket scan across all 186 guides found one genuine hazard (HashMap<fd, handler> in topic 7’s ae guide, backticked), mdBook build green. The whole book now reads as chapters instead of pointers.
2026-07-12 — book-quality pass, three moves: (1) paper audit against dbscholar’s citation-PageRank ranking (rmarcus.info — pulled the underlying data.json, 11,867 SIGMOD/VLDB/CIDR/PODS papers) — resources/papers.md gains a “Modern systems & directions” section and 6 topic READMEs gain “Further references” (Kung-Robinson OCC ’81, Calcite, Spark SQL, Kipf/Neo/Bao learned optimization, Photon, Velox, GAMMA, Dremel, Lakehouse+Delta Lake, MillWheel, CockroachDB); (2) all ~/repos/... code references linkified to their GitHub repos (scripted, fence-aware: 143 links across 115 files) so the online book’s code pointers resolve; (3) restructure demo on topic 26 — all 7 reading guides rewritten as self-contained chapters: concept titles (“HyperLogLog: count distinct in 12 KB” not “Reading guide — …”), framing lead instead of a Sources block, an inline Rust code sample of each core algorithm (HLL add/merge + Ertl count skeleton, blocked-bloom 6-probe loop with golden-ratio remix, cuckoo kick loop with the XOR involution, PGM shrinking-cone add_point, roaring galloping intersect, BRIN one-sided range prune, Morton interleave64 magic masks), and a “## References” section at the bottom (papers with arXiv links, code with GitHub links); filenames kept (reading-*.md) to avoid link churn; SUMMARY.md + README titles updated; mdBook build verified locally (mdbook-mermaid install + build green). If the format lands, roll it out to the other 32 topics.
2026-07-12 — PLAN.md expansions backfilled into the four already-scaffolded topics (the plan-only commit 2fb095a now has matching study material): topic 7 gains “Bolt: the third answer” — RESP/pgwire/Bolt framing-typing-streaming table (Bolt’s PULL{n}/DISCARD = protocol-level backpressure, §4’s problem solved at the wire) + reading-bolt-packstream.md anchored on FalkorDB’s removed Bolt server read frozen via git show 0b11a00b3^:src/bolt/ (#2170, 2026-07-08): session-sequence ASCII with handshake bolt_api.c:803/version-clamp :845-864, RUN-executes-but-PULL-streams :467-482/:504-521 decoupling, PackStream marker nibbles bolt.c:11/:21/:36 + graph types Node 0x4E/Rel 0x52/Path 0x50 in the type system, why-was-it-removed as a question, M7 stretch = Bolt listener beside RESP; topic 13 gains “The query-language landscape” — 6-language table (Cypher/GQL/SQL-PGQ/SPARQL/Gremlin/Datalog) on model/matching/composability/pushdown + reading-query-languages.md (SIGMOD ’22 GQL+PGQ paper, count-2-paths-in-a-triangle under homomorphism/isomorphism/trail as the same-pattern-three-answers demo, family-tree mermaid, kuzu Cypher.g4 anchor, M13 rule: keep the AST GQL-shaped — quantified path patterns + explicit path-mode field); topic 20 gains “Parallelism: OpenMP inside SuiteSparse, rayon in Rust” — saxpy3’s costed static scheduling (coarse/fine tasks GB_AxB_saxpy3.c:22-48, nthreads-from-flopcount slice_balanced.c:418, parallel flopcount pass :219) vs rayon work-stealing (join/mod.rs:93 inline+push+steal, registry.rs:248 crossbeam_deque Stealer) + reading-openmp-vs-rayon.md with the static-vs-stealing trade table, no-native-Rust-GraphBLAS note (crates are FFI), new M20 checkbox: document each OpenMP→rayon mapping decision; topic 26 gains “Geo indexes: 2D keys through 1D indexes” — valkey GEO as geohash-in-a-zset (interleave64 geohash.c:52 → 52-bit Morton score, geohashEstimateStepsByRadius helper.c:64, 9-cell scan geo.c:375 + haversine verify = bloom’s candidate-then-verify control flow) + reading-geo-indexes.md (Z-order seams vs Hilbert, Guttman R-tree/GiST, S2 prefix-containment vs H3 hexagons, M26 mapping: Morton key through the existing sorted property index). SUMMARY.md gains the 4 new guides so they appear in the book.
2026-07-11 — topic 32 scaffolded (added to the plan this session, so the scaffold-all-topics run is complete again): study guide (the HTAP problem measured — bench lane 1 run: 1M-row store behind one coarse lock, fixed 2 s window per mode: writes alone = 11,438,647 writes at p99 333 ns; writes + a free-running full scanner = 69 writes with p99 7.49 seconds — not slowdown, starvation: std Mutex is unfair, the scanner re-wins the lock after each ~0.6 ms scan (3261 scans) and the parked writer never gets in; interference at its worst is zero writes, and the coarse lock is deliberate — mitigations ARE the topic; the freshness/isolation/cost trilemma triangle; the architecture-menu table HANA-delta+main / HyPer-fork() / TiFlash-learner / F1-Lightning-CDC / pg_duckdb-offload keyed on one-copy? freshness isolation; the changelog-is-the-glue mermaid tying topic 27’s thesis to every split design; the same-fold-four-costumes thread: topic 4 LSM minor compaction = HANA delta merge = TiFlash segmentMergeDelta = FalkorDB delta-matrix flush), 4 reading guides (TiDB VLDB ’20 — columnar-copy-as-Raft-LEARNER so the replica costs no write-quorum latency, freshness-is-a-WAIT with tiflash LearnerRead.cpp:35 doLearnerRead + :61 waitIndexTimeout as the anchor, one-planner-two-engines via tidb find_best_task.go:535/:1841/:1878 TiFlash-paths-retained-so-cost-not-topology-decides, learner-log vs CDC-changelog trade question; TiFlash DeltaTree — Segment.h:84 delta-over-stable ASCII with MemTableSet/DeltaValueSpace.h:65 as a-little-LSM-inside-the-delta, Delta/MinorCompaction.h why-compact-the-delta-at-all, DeltaIndex.h:27 as the structure that makes delta+stable merge reads cheap (the thing our scan_sum_a lacks), DeltaMergeStore.h:668 segmentMergeDelta with our merge_preserves_scans test as its correctness condition, MVCC-versions-in-both-layers GC question linking topic 31’s causal stability; HyPer ICDE ’11 + HANA SIGMOD Record ’12 paired as the one-copy family — fork() CoW-page ASCII (snapshot cost ∝ dirtied pages = MVCC-where-the-version-chain-is-the-page-table, GC is exit()), snapshot-ages-until-re-fork = lane 3’s apply interval in OS clothing, HANA delta+main = our replica.rs minus segmenting, HANA’s-trilemma-corner-is-exactly-what-lane-1-measures; F1 Lightning VLDB ’20 + Özcan SIGMOD ’17 survey — CDC-fed HTAP with zero OLTP changes, safe-timestamp = applied_lsn productionized (reads never wait, served stale-but-consistent at the max fully-applied ts — the opposite choice from doLearnerRead), Changepump ordering question = topic 27 changelog + topic 29 Spanner timestamps, the survey’s copies×engines quadrant with every cell trading the same three currencies), experiments crate compiles: row.rs PROVIDED (RowStore = rows + every-write-appended-to-log changelog + scan oracle + skewed_key + percentile — 2 provided tests pass) — replica.rs (ColumnarReplica delta+main: apply/scan_sum_a/merge_delta with delta-overrides-main + highest-lsn-per-key-wins + merge-preserves-scans-and-sorts contracts, freshness_is_visible via applied_lsn gap — TiFlash DeltaTree in miniature, 4 tests), learner.rs (read_wait over an apply schedule: first-batch-covering-read_index, Some(0) if already applied, None = waitIndexTimeout — doLearnerRead as arithmetic, 3 tests) are todo!() stubs — 7 tests fail as todo panics; htap_bench lane 1 RUN (table above; original fixed-200K-writes design serialized into minutes behind ~0.6 ms scan lock-holds — switched to fixed-2s-window per mode, making the writes-completed collapse the headline number), lanes 2 (scan row-vs-delta-heavy-vs-merged + freshness max-lsn-gap vs batch 1K/10K/100K) and 3 (learner-read wait distribution vs apply interval 1/10/100, 50K reads demanding lsn==now) armed behind catch_unwind; notes.md predicts lanes 2-3 + records the starvation surprise + the RwLock exercise; M32 log: Lightning-shaped not TiFlash-shaped (no consensus group until M15, decoupling = zero primary changes), M27’s changelog feeds a delta-matrix replica, router advertises applied_lsn safe timestamps + freshness-bound routing with read_wait-or-fallback, before-shot recorded: 69 writes/2s when analytics shares the copy, success = restoring the 11.4M with scans elsewhere. Cloned tiflash + tidb.
2026-07-11 — topic 31 scaffolded (the last topic): study guide (consensus-vs-CRDT as the same problem in opposite currencies — agree-on-an-order vs design-so-order-doesn’t-matter, 1-RTT vs 0-RTT, unavailable-in-minority vs available-under-any-partition; SEC via join-semilattice mermaid; CvRDT/CmRDT table with where-each-lives-in-this-crate; the zoo table clock/lww/counter/orset/rga/graph with the one idea per structure; LWW’s lie measured — lane 1 run: two replicas, 20K writes each, LWW map: 10 hot keys + sync-every-write loses 94.98% of writes, 1000 keys + sync-every-100 loses 88.34%, even 100K keys + rare sync loses 12.45% — “eventually consistent” without conflict semantics is not a semantics, priced; sequence-CRDT integration ASCII with the interleaving dragon; code-reading table across all five cloned repos), 4 reading guides (Shapiro SSS’11 + INRIA RR-7506 — SEC’s three clauses, the CvRDT⇔CmRDT equivalence proof, the catalog reading map ending at §4’s graphs where concurrent addEdge∥removeVertex is declared application-specific = the dangling-edge problem M31 inherits, causal-stability GC question; Kleppmann arc JSON-CRDT ’17 + move-op ’21 + Local-First Onward!’19 — ops-address-identities-not-paths with automerge op_set2/op.rs:52 succ as deletion-by-successor-ops, the concurrent-move duplicate/cycle problem and its undo/redo total-order fix, the does-move-survive-in-graphs M31 design question; sequence CRDTs in production — yrs block.rs:160 ID=our-Dot / :1302 Item with origin+right_origin=YATA’s pair vs RGA’s single parent / :1415 Item::integrate as the loop our rga.rs apply implements plus run-coalescing splits, diamond-types merge.rs:142 self-described “bastardization” + yjsspan.rs:29 INSERTED/NOT_INSERTED_YET retreat/advance = only-be-a-CRDT-at-merge-time, Loro/Fugue maximal-non-interleaving with the letter-soup demo, automerge-vs-loro bench as scratch-project exercise per deps convention; cr-sqlite as THE-database-goes-multi-master — crsql_as_crr clock-row-per-CELL diagram, local_writes/mod.rs:83-133 db_version bookkeeping = Lamport-clock spine, compare_values.rs version-tie-broken-by-VALUE-comparison = deterministic convergence with zero clock trust, changes_vtab.rs replication-endpoint-as-virtual-table, delete-wins-for-rows vs our add-wins-for-nodes tension question, the M31 change-feed schema design question), experiments crate compiles: clock.rs PROVIDED (Dot + VClock tick/covers/merge/partial_cmp-None-defines-concurrent, modeled on automerge clock.rs:109/:145) + lww.rs PROVIDED (register/map with (ts,replica) total order; merge counts its own discards so lane 1 can price the lie) — 6 provided tests pass — counter.rs (G/PN with semilattice-law tests + why-PN-is-two-G-Counters), orset.rs (add-wins over Dots: add-tags-fresh-dot / remove-kills-observed-dots, concurrent-add-beats-remove + remove-covers-all-observed-tags + seeded-permutation convergence), rga.rs (insert-after-parent + skip-larger-(counter,replica)-siblings + tombstones-still-anchor, idempotent apply, delete∥insert-after-it convergence), graph.rs (OR-Set nodes/edges + LwwMap props composition; dangling-edge-hidden-NOT-deleted test: edges()-filters-to-visible-endpoints, re-add-resurrects; props keyed by node id survive remove/re-add vs automerge’s key-by-creation-op as an exercise) are todo!() stubs — 18 tests fail as todo panics; crdt_bench lane 1 RUN (table above; also caught state-based-sync’s quadratic cost live — sync_every=1 ships the whole map per write, workload shrunk and the delta-CRDT motivation written into the bench comment), lanes 2-4 armed behind catch_unwind (OR-Set gossip storm + tombstone census, RGA 50K-char trace + tombstone bloat, graph dangling storm 100-removes∥500-edge-adds + resurrection count); notes.md flags lane 1’s honest caveat (counts merge-time discards only — locally-overwritten writes don’t show, so it’s a lower bound); M31 log: node/edge identity must be Dots not user ids (cr-sqlite’s auto-increment-PK trap), dangling policy locked hide-not-delete, props LWW-with-HLC (topic 29), anti-entropy v1 whole-state → v2 db_version-watermark deltas, deliverable = same workload through M15 Raft vs active-active with latency histogram + concrete-conflict table. All 32 topics scaffolded.
2026-07-10 — topic 30 scaffolded: study guide (the-shape-of-the-problem ASCII — regular append-mostly writes vs range+selector+aggregation reads; the baseline finding measured: delta+varint lands at a shape-blind 11.00 B/sample because raw f64 values dominate — whatever the codec does about timestamps is a rounding error until it attacks the value bytes, hence XOR; Gorilla→Prometheus/VM→IOx lineage mermaid with Monarch and BtrDB as the bracketing extremes; five-system table on codec / time organization / label index / out-of-order policy; TSDB=LSM-keyed-by-time thesis with retention=drop-the-oldest-level), 4 reading guides (Gorilla VLDB ’15 + prometheus chunkenc/xor.go — prediction-error framing with the dod/XOR ASCII, paper bucket table vs prometheus’s retuned 14/17/20 buckets (:195-208) as buckets-are-workload-parameters, writeVDelta :226 window reuse, :396 tDelta+=dod as the whole model in one line, no-random-access-by-design, entropy-floor bit accounting question; prometheus tsdb — full architecture ASCII head/WAL/2h-blocks/exponential compaction, head_append.go:436/:481/:688-693 as the exact head.rs contract (ErrOutOfOrderSample vs ErrTooOldSample), OutOfOrderTimeWindow head.go:168 quarantine design, MemPostings postings.go:60/:403 = topic 23’s inverted index with labels as terms, the two famous failure modes high-cardinality + churn; VictoriaMetrics + InfluxDB 3 paired as two-rebuttals — VM partition.go:75 rawRows→parts LSM-said-out-loud, nearest_delta2.go:15 byte-aligned varint batches with optionally-lossy precisionBits vs Gorilla’s exact bits, index_db.go:124 tagFilters cache + churn invalidation, vs IOx WAL→Arrow QueryableBuffer→Parquet-on-object-store (influxdb3_wal/lib.rs:75-98 SnapshotTracker, queryable_buffer.rs:41) as topic 28’s landing-zone applied to metrics, vertical-integration-vs-commodity-formats trade table, how-much-of-Gorilla’s-win-was-really-sorting question; Monarch VLDB ’20 + BtrDB FAST ’16 — monitoring-must-not-depend-on-what-it-monitors ⇒ RAM-first lazy durability, push-vs-pull, distribution-typed values as the schema cure for cardinality, query pushdown; BtrDB’s aggregate tree — min/mean/max/count per 64-way node ⇒ query cost ∝ pixels not samples, downsampling as the index structure itself, CoW versions), experiments crate compiles: gen (scrape jitter, gauge/counter/constant/random shapes, OOO arrivals, label sets with the unique-instance cardinality bomb) + bits (MSB-first BitWriter/Reader + sign_extend so the stub is the algorithm not bit plumbing) + baseline (zigzag varint delta) PROVIDED — 7 provided tests pass, lane 1 RUN (table above, decode ~270-330 Msamples/s — byte-aligned codecs have a real throughput edge over bit-packed Gorilla, the actual design axis is ratio-vs-decode-speed) — gorilla.rs (paper dod buckets + XOR leading/trailing windows; bit-exact roundtrip incl. bucket edges, constant ≤~2 bits/sample, gauge beats raw 3×, random must FAIL to compress >8 B/sample — the codec wins on regularity not magic), head.rs (in-order fast path + bounded OOO window + TooOld refusal + LWW merge flush that feeds the in-order-only encoder — prometheus semantics exactly), index.rs (MemPostings-style (name,value)→sorted-ids + shortest-list-first k-way intersect, brute-force oracle, cardinality-bomb-counted test) are todo!() stubs — 15 tests fail as todo panics; tsdb_bench lanes 2-4 (gorilla ratios per shape, OOO tax sweep 0-50%, selector latency at 100K series) armed behind catch_unwind; notes.md predicts all lanes; M30 log: history chunks per (entity, attribute), MATCH ... AT TIME t = latest_write_before ≤ t so M29’s MVCC read path generalizes to time-travel, storage split by age (custom hot chunks → M28 Parquet cold), Gorilla dod survives for changelog timestamps but property values need dictionary+RLE not XOR, BtrDB-shaped rollup tree over the M27 changelog for graph-evolution queries.
2026-07-10 — topic 29 scaffolded: study guide (the-problem-priced motivation table — measured conflict probability of the bank workload itself: 0.3% of 8-txn batches collide at zipf θ=0.5 but 29.9% at 0.9, 86.2% at 1.1, 99.6% at 1.3 — contention is the common case at real-workload skew; design-space mermaid rooted at textbook 2PC with the three escapes labeled on the edges — move-the-decision-into-the-data (Percolator), replicate-the-coordinator (Spanner), remove-runtime-agreement (Calvin), decompose+batch (FDB); one-table five-system summary keyed on concurrency control / clock / cross-shard atomicity / blocking window; Percolator-in-six-lines with THE-COMMIT-POINT marked), 4 reading guides (Percolator OSDI ’10 + TiKV — three-column-families ASCII (data/lock/write with write-CF-as-commit-index), lifecycle sequenceDiagram with the any-reader-resolves note, TiKV walk actions/prewrite.rs:37 (pessimistic_action + secondary_keys args as post-paper hardening) → commit.rs:64 with the :57 duplicate-commit-returns-Ok idempotency arm → check_txn_status.rs:92/:241 + MissingLockAction :458 as production resolve_lock → cleanup.rs:24 Rollback records our sim skips → latch.rs/scheduler.rs local-vs-distributed conflict split, txn_status_cache; Spanner OSDI ’12 + HLC OPODIS ’14 paired — bound-the-ERROR-vs-bound-the-SKEW fork diagram, commit-wait derivation, HLC rules + the l≤max-pt anti-Lamport-drift bound, uncertainty-interval restarts, CRDB walk hlc.go:38/:411/:471/:517 (UpdateAndCheckMaxOffset crashes the node — maxOffset is a promise) + txn_coord_sender.go:113 interceptor stack + txn_interceptor_committer.go:128 parallel commits with STAGING-is-implicitly-committed :195-205 as Percolator’s-resolve-idea-shaving-a-latency-round; Calvin SIGMOD ’12 — agree-on-inputs-not-outcomes diagram, sequencer/scheduler/executor layers, deterministic-locking-kills-both-deadlock-and-2PC, OLLP reconnaissance for dependent txns with the graph-traversals-are-the-ultimate-dependent-txn M29 question; FoundationDB SIGMOD ’21 — unbundled roles ASCII, ConflictSet.cpp:947 detectConflicts over the :224 SkipList as the-whole-SI-check-in-one-data-structure, CommitBatchContext :504 batch-is-the-unit, masterserver-is-barely-a-counter, ResolverBug.cpp injectable-wrong-answers as DST culture beyond crash injection, vs-Calvin and vs-Percolator design reads), experiments crate compiles: kv.rs PROVIDED (the three Percolator column families as HashMaps/BTreeMap, strictly-monotonic TSO, latest_write_before range scan, 2-shard cluster, Zipf transfer workload — 4 provided tests pass) — tpc.rs (2PC coordinator with 4-point CrashPoint injection + recovery-from-durable-state-only; blocking_window_demonstrated test names the flaw), percolator.rs (get/prewrite/commit_primary/commit_secondaries/resolve_lock with roll-forward-iff-primary-committed tests, no-lock-leak on failed prewrite, total-conserved-after-rollback), hlc.rs (send/recv rules; monotonic-under-backward-clocks, l-bounded-by-max-pt over 1000 skewed messages, concurrent-events-collide-without-node-id-tiebreak as an assert_eq teaching test) are todo!() stubs — 14 tests fail as todo panics; txn_bench lane 1 RUN (conflict table above), lanes 2 (abort rate vs θ + bank invariant) and 3 (20K-txn crash storm, crash every 100th cycling 4 points, blocked_aborts counts the blocking window empirically) armed behind catch_unwind; notes.md predicts lane 2/3 numbers before implementation; M29 log: shard by node id, cross-shard edge = prewrite both adjacency sides with primary on u, supernodes are the Zipf head — per-shard adjacency segments turn the WW hotspot into scatter-gather reads, every protocol step gets a kill point with no-dangling-half-edges as the invariant.
2026-07-10 — topic 28 scaffolded: study guide (the latency ladder measured and priced — local NVMe p50 0.10 ms vs raw S3 p50 14.17 / p99 112.99 ms = 140× median, 940× tail, and why everyone moved anyway: $/GB, 11-nines durability = replication-is-someone-else’s-problem, scale-to-zero; the 2008→Snowflake→Aurora→Socrates→Neon→SlateDB lineage mermaid; Neon’s four-box data flow with the safekeepers-commit-fast / pageserver-serves-pages split; five-system design-space table with what-crosses-the-network as the axis; WAL-rule-promoted-to-architecture rosetta linking topic 27’s Kafka thesis), 5 reading guides (Aurora SIGMOD ’17 — the-log-is-the-database, 6-copy 4/6 AZ+1 quorums over 10 GB protection groups, 35× network amplification killed, VDL-replaces-2PC question, commit=log-quorum-ack + recovery-without-REDO-at-compute; Socrates SIGMOD ’19 — durability≠availability as THE decomposition, XLOG landing zone vs page servers vs XStore mapped onto topic 5’s WAL lifecycle and onto Neon components, RBPEX = buffer pool made restart-durable; Snowflake SIGMOD ’16 + Building-a-DB-on-S3 SIGMOD ’08 paired — the prescient paper’s three blockers (eventual consistency/no CAS/request cost) vs what fixed each (strong consistency 2020, conditional PUT 2024, immutability routed around all three), micro-partitions as CoW-clone-by-file-list, min/max pruning = topic 26’s BRIN at cloud scale; Neon code walk — get_rel_page_at_lsn pgdatadir_mapping.rs:258 → Timeline::get :1227 → LayerMap::search layer_map.rs:448 as an LSM over (page, LSN), walredo.rs:173 = REDO on the read path in a sandboxed Postgres, branch_timeline_impl tenant.rs:4985 O(1) branches + the timeline.rs:4548 ancestor walk our stub reimplements, branch-aware GC retain-point question; SlateDB+Quickwit S3-first code walk — tablestore.rs:835 block-granular ranged GETs, cached_object_store part cache = our cache.rs in production form, fence.rs:105 CAS-epoch fencing = consensus outsourced to S3 conditional PUT, clone.rs:38 zero-copy clones, quickwit bundle hotcache footer + TimeoutAndRetryStorage :37 hedging with the AWS-recommends-it citation, pathology→countermeasure convergence table), experiments crate compiles: virtual-latency sim (charged-not-slept lognormal S3 with 2% 8× stragglers, NVMe, scripted Fixed model for exact contract tests) + block store + zipf + percentiles PROVIDED — 6 provided tests pass, tier_bench provided lanes RUN (numbers above) — LruBlockCache+TieredReader (touch-protects, 1/8-cache zipf hit-rate >50%, block-sharing hits), hedged_get (scripted 50ms-primary/1ms-backup/10ms-deadline ⇒ exactly 11ms, p99-halves-at-<10%-extra-GETs on straggler-heavy S3), BranchStore::get (parent-prefix visibility, sibling isolation, PITR historical branch points, 100-deep chains, branching-copies-nothing proven by version_count) are todo!() stubs — 13 tests fail as todo panics; notes.md predicts cache-fixes-the-median-hedging-fixes-the-tail and flags the O(n)-eviction-scan wall-time trap; M28 log: L0+WAL stay local (landing-zone lesson), manifest-CAS fencing not leases, branch at SST-list not page granularity, image-layer materialization deferred until ancestor walks profile hot.
2026-07-10 — topic 27 scaffolded: study guide (recompute-is-the-enemy with the priced motivation table — full recompute per 100-change batch: triangles 97.2 ms / wedge self-join 894.3 ms / re-BFS 24.7 ms vs µs-scale incremental targets; the one algebraic idea as a table — LINEAR ops stream deltas statelessly, BILINEAR joins need arranged inputs via Δ(A⋈B)=ΔA⋈B+A⋈ΔB+ΔA⋈ΔB, NONLINEAR distinct/aggregates need integrals; DBSP I→Q→D mermaid; timestamps/watermarks section: timely frontiers are proofs where Flink watermarks are heuristics; four-system comparison timely/DBSP/Materialize/RisingWave), 5 reading guides (Naiad+timely — could-result-in pointstamp protocol, MutableAntichain frontier.rs:380/update_iter :533, ChangeBatch :16 progress-updates-are-Z-set-shaped, worker.rs:235 step as the topic-7 event loop one layer up, the rosetta table frontier=vacuum-watermark; differential — consolidation.rs:24 = our from_updates verbatim, arrangements as LSM-of-batches with advance=compaction, join_traces join.rs:69 with the fuel/effort loop :348-395 as operator-level cooperative yielding, iterate.rs:192 Variable + bfs.rs:101-107 as the 40 lines our stub can’t do, why deletion-in-recursion needs lattice times; DBSP — Q^Δ=D∘Q∘I with the chain rule as the compositional bombshell, feldera anchors z1.rs:221/integrate.rs:85/differentiate.rs:38/join.rs:123-350/delta0.rs, nested-circuits-vs-lattice trade, the M27 mapping: delta matrix DP−DM=ΔA and wedges need NO new state because the integrals ARE the adjacency matrices; Materialize+RisingWave — dogs^3 delta_join.rs:47 + half_join :315/:402 avoiding intermediate arrangements, indexes-are-arrangements-are-memory, RisingWave Op enum stream_chunk.rs:45 as Z-set-weights-as-protocol, hash_join.rs:158 degree tables :269 as hand-rolled weight bookkeeping vs one consolidation rule, barrier checkpoints, single-writer-gets-the-hard-parts-free table; Kafka NetDB’11 — dumb-broker/smart-consumer, offset=LSN rosetta, log-compaction=arrangement-advance=LSM-GC same operation three communities, exactly-once = where-do-offsets-live, M27’s raw-log-vs-result-delta subscriber decision), experiments crate compiles: ZSet with consolidation + the distinct-is-not-linear load-bearing test, churn generator with set-semantics guard, full-recompute oracles (sorted-intersect triangles, hash join with weight multiplication, BFS) PROVIDED — 6 provided tests pass, ivm_bench baselines RUN (numbers above) — delta_join+IncrementalJoin (algebra-exact vs join(A+ΔA,B+ΔB)−join(A,B), 30-batch drift-free, deletes-retract), IncrementalTriangles (oracle-tracking under churn, K4-minus-edge=−2, <4K probes for 20 changes on 40K edges), SemiNaiveReach (insert-only BY DESIGN — deletion is differential’s lattice territory, documented; matches re-BFS per batch, ≤4 relaxations/edge EVER, intra-component edges free) are todo!() stubs — 9 tests fail as todo panics; notes.md flags the honest suspicion that IncrementalJoin’s Vec-merge state integration may dominate and re-derive why arrangements exist.
2026-07-10 — topic 26 scaffolded: study guide (indexes-are-bets framing with the measured motivation table — point-miss binary search 167 ns / BTreeMap 218 / HashSet 24 at 224 MB, vs blocked bloom’s ~15-25 ns at 12 MB target; three-families ASCII filters/sketches/learned; bloom math block with the reproduce-it FPR derivation; bloom→blocked→cuckoo→xor→ribbon lineage mermaid; HLL sparse-30-bytes-to-dense-12KB story; PGM ε-window thesis), 6 reading guides (bloom→ribbon over RocksDB code — FastLocalBloomImpl bloom_impl.h:144 golden-ratio probe remix vs LegacyBloomImpl :364, CacheLocalFpRate :42 as the Poisson-crowding honesty function, ribbon as banded GF(2) solve with StandardBanding ribbon_impl.h:471 / num_starts_=slots−kCoeffBits+1 :504 and the build-can-fail-vs-monotone question; cuckoo+xor — partial-key involution getAltHash cuckoo.c:122, RedisBloom’s LSM-of-subfilters growth CuckooFilter_InsertFP :256 vs the paper’s fail-at-MAX_KICKS, delete-a-false-positive-corrupts-someone-else contract, xor peeling 1.23× vs bloom 1.44× vs ribbon 1.10×; HLL — hllPatLen :467 / Ertl tau+sigma :1016/:1033 replacing HLL++’s empirical bias tables, ZERO/XZERO/VAL sparse opcodes :380 with promote-at-3KB-or-rank>32, merge-is-a-semilattice AVX2 :1116; learned indexes — Kraska RMI’s no-error-bound flaw, PGM_SUB/ADD_EPS pgm_index.hpp:32-33 + optimal hull PLA piecewise_linear_model.hpp:96/:154-190 vs our simpler shrinking cone, ALEX gapped arrays predict_position alex_nodes.h:1448 + exponential search :1462 with the degrades-in-space-vs-time-vs-write-amp scoreboard; roaring internals extending topic 23 — Store enum store/mod.rs:28-31, ARRAY_LIMIT=4096/RUN_MAX_SIZE=2048 as pure arithmetic container.rs:9-11, 3×3 pairwise kernel dispatch, three-adaptive-encodings table roaring/HLL-sparse/GIN-varbyte; postgres indexam as the classical baseline — _bt_search nbtsearch.c:100 + Lehman-Yao moveright :211, GIN varbyte ginCompressPostingList ginpostinglist.c:196 + pending-list-as-mini-LSM, BRIN bringetbitmap brin.c:301 as the one-sided filter that’s 10,000× smaller than bloom when clustering holds), experiments crate compiles: splitmix64/hash2/fastrange PROVIDED (avalanche + coverage tests pass), filter_bench motivation lanes RUN — binary search miss 167 ns ≈ 23 dependent misses, BTreeMap 218, HashSet 24 ns at 224 MB, hit≈miss 169 (the walk is the cost, not the compare) — BlockedBloom (no-FN + FPR<2.5%@10bpk + <4×-theory + halves-8→16 tests), CuckooFilter (no-FN at 90% load, FPR<1%@12-bit, delete-leaves-others-intact — the test bloom can never pass, graceful-full-failure), Hll (err<3% at 1K/100K/5M, merge registers EXACTLY equal union’s), and LearnedIndex (window ≤2ε+2 always contains true pos, uniform-1M <2K segments, ε holds on hostile powers-of-2+quadratic mix) are todo!() stubs — 15 contract tests fail as todo panics, notes.md has predict-before-measure table and the M26 call that learned indexes are NOT in scope (node IDs are dense — a plain array is already the perfect model).
2026-07-10 — topic 25 scaffolded: study guide (message-passing-is-SpMM with receipts — the message_and_aggregate table showing GCNConv = spmm(adj_t, x) at gcn_conv.py:273 and SAGEConv = spmm(..., reduce=mean) while GAT can’t fuse because attention recomputes the matrix values per forward; associativity-as-query-plan — (AX)W vs A(XW) swaps which term carries the big dimension, 90× on Cora; GraphRAG closed-loop mermaid graph→embeddings→M14 vector index→hybrid Cypher), 7 reading guides (node2vec KDD ’16 — second-order walk figure, p/q as BFS↔DFS knobs, the alias-table O(m·avg_deg) memory trap with rejection sampling as the fix, PyG Node2Vec.loss node2vec.py:135 as the SGNS reference; Kipf-Welling GCN — renormalization trick, gcn_norm anchors gcn_conv.py:45-71, GCN-forward-is-a-query thesis, oversmoothing as why-2-layers; GraphSAGE — sampling as a page budget (B·10·25 fan-out math), mean+lin_r≈concat, inductive-is-the-only-write-friendly-variant; GAT — SDDMM+softmax+SpMM kernel decomposition = topic 24’s masked SpGEMM, a_src/a_dst per-node split as factor-out-of-join, materialized-vs-computed view line running exactly between GCN and GAT; PyG message-passing machinery — 10-stop code walk, COO gather-scatter materializes an m×d temp (145 MB on our bench) vs CSR spmm’s zero temporaries = materialize-the-join vs pipeline-the-aggregate, message()-as-arbitrary-callable = Ligra’s F-with-CAS tradeoff third community; TransE — relations as translations, symmetric-relation collapse, link-prediction-is-an-ANN-query so M14 serves KG completion natively; GraphRAG-SDK with systems eyes — vector_store.py:344 queryNodes / :219 SET embedding write path, relationship_expansion’s ANN+k-MATCHes as the k+1-round-trip join to push down, multi_path’s client-side cosine rerank, router-as-planner-with-no-cost-model, four systems smells), experiments crate compiles: CSR + SBM generator (ground-truth labels; O(m) inter-block sampling not O(n²) Bernoulli) + ring-of-cliques + dense Mat/glorot/softmax + SpMM + row-norm adjacency + uniform walks + dense GCN oracle PROVIDED and run — SBM 16,384 vertices/566K edges: uniform walks 42.8 Msteps/s, SpMM 21.2 GFLOP/s = 81% of dense matmul’s 26.2 (64-wide feature rows amortize the gather — fat RHS forgives sparsity, the number that makes M25 plausible) — node2vec_walks (4 tests: degree-stationary dist, p=q=1 ≡ uniform, q orders exploration on ring-of-cliques, p orders backtrack rate), train_skipgram (SBM intra-block cosine must beat inter by 0.2), gcn_norm+gcn_forward (dense-oracle 1e-4, sorted rows, transform-before-aggregate) are todo!() stubs.
2026-07-10 — topic 24 scaffolded: study guide (per-source vs whole-graph algorithm map; frontier-world vs algebraic-world mermaid with the honest trade — per-vertex tricks like Afforest’s edge skipping vs LAGraph’s batched matrix frontiers and atomics-free bulk ops; rmat-vs-uniform baseline table making skew the headline), 6 reading guides (GAP arXiv:1508.03619 + gapbs anchors — sssp.cc:44’s redundant-relaxation-beats-bookkeeping bet, bc.cc:76 succ bitmap, cc.cc:69/:106/:129 Afforest’s three phases, tc.cc WorthRelabelling, and the 5-graph matrix as topic 22’s change-anything-different-number; Meyer-Sanders delta-stepping as the Dijkstra↔Bellman-Ford dial with gapbs thread-local-bins vs LAGr_SSSP’s MIN_PLUS tmasked vxm + three implementation traps; Brandes ’01 with the dependency-recurrence derivation exercise + gapbs-vs-LAGr_Betweenness table — the batched ns×n matrix frontier amortizes what frontier code cannot; Ligra PPoPP ’13 — edgeMapData ligra.h:235-272, the m/20 threshold :238, dense/sparse/denseForward, PageRank-degenerates-to-SpMV lesson, m/20 = Beamer α/β = dot-vs-saxpy; Louvain→Leiden Sci Rep ’19 — the disconnected-communities bug as topic 21’s greedy-destructive trap, refinement as egg’s keep-both-forms, ΔQ accumulator = SPA, aggregation = S·A·Sᵀ SpGEMM, determinism-needs-seeding for CALL algo.community; LAGraph analytics — FastSV7 mngp/hooking-as-one-mxv :102 + FASTSV_SAMPLES :335, TriangleCount’s six formulations with the :44 urand-flips-to-saxpy exception, PageRankGAP-vs-PageRank as benchmark-specs-fork-implementations, and FalkorDB’s proc_pagerank.c:197 already calling LAGr_PageRank = M24’s pattern exists, re-plumb it), experiments crate compiles: weighted CSR + RMAT/uniform generators + heap Dijkstra with pop counter + pull PageRank + degree-ordered triangle count + union-find CC + O(n³) definitional BC oracle PROVIDED and run — RMAT scale 16 vs uniform same n/m: 15,645,988 vs 5,428 triangles (2,883×) in 376/158 ms, PR 8-vs-6 iters (hubs slow L1 decay), Dijkstra 343K pops = 1.74×n stale-entry tax, 18,844 components at avg_deg 16 (RMAT’s leaf quadrant strands vertices) — delta_stepping (bucketed, extremes-must-still-be-exact test + relaxation counters), brandes (must match the O(n³) oracle exactly on n=128, then sample GAP-style), and afforest (partition-equal + <50%-of-m edges-inspected bound) are todo!() stubs; RMAT skew assertion needed scale-aware bounds (19.1% top-1% share at scale 12, 36.6% at 16).
2026-07-10 — topic 23 scaffolded: study guide (inverted-index anatomy ASCII — analyzer → FST term dict → TermInfo{doc_freq, postings_range} → 128-doc Δ-bitpacked blocks with {last_doc, max_score} skip data; write-path mermaid making Lucene-segments-are-an-LSM explicit — tiered LogMergePolicy works for text because queries fan out anyway; the two speed tricks: compression-with-random-access + score upper bounds), 6 reading guides + 2 cross-linked (Zobel-Moffat CSUR ’06 design-space map — TAAT vs DAAT, capped accumulators as 2006’s WAND, merge-based construction = LSM before Lucene; Robertson-Zaragoza BM25 derivation ladder — eliteness ⇒ tf saturation at K1+1 ⇒ the static ceiling WAND needs, mapped to tantivy bm25.rs:8-59 with the 1-byte-fieldnorm quantization question; Ding-Suel SIGIR ’11 block-max WAND with pivot diagram + four implementation traps (θ seeding, livelock-on-failed-refinement, k-boundary ties, docs-evaluated metric); Roaring — 4096 crossover derivation, kernel matrix, containers = GraphBLAS sparse↔bitmap lattice at 64K granularity; tantivy code walk — compression/mod.rs:3 128-blocks, skip.rs:93/:175/:186 SkipReader/block_max_score, term_info.rs:9-13, fst_termdict, block_wand_union.rs:8-24 find_pivot_doc, log_merge_policy.rs:20-24, 90-minute read order; RediSearch redisearch_rs Rust-rewrite — newly cloned — InvertedIndex core.rs:30/:75 chained varint IndexBlocks vs tantivy’s immutable bitpacked segments, Encoder-as-type-parameter monomorphizing 11 codecs, gc_marker/unique_id cursor validation ↔ delta-matrix wait, new-block-on-delta-overflow, and the finding that RediSearch has NO block-max WAND — scored unions walk everything), experiments crate compiles: zipf corpus (term id = rank, df(t0)=99.9%) + tf-counting index builder with per-128-block max-BM25 metadata + saturating-BM25 + exhaustive TAAT oracle PROVIDED and run — 100K docs/7.9M postings built in 335 ms, common∧rare [t0 t12000] top-10 walks 99,964 postings in 6.34 ms at ~32 ns/posting (hash accumulate dominates — Q1’s lesson again) while the rare term carries ~93% of the winning score = the WAND poster child measured, and vec two-pointer dense∧sparse AND costs O(|dense|) 52 µs for 172 hits = the roaring motivation measured — block-max wand_topk (recipe in doc comment, must match oracle top-k while scoring <25% of the postings) and mini-Roaring (array/bitmap containers, 3 density-crossing oracle tests) are todo!() stubs.
2026-07-10 — topic 22 scaffolded: study guide (OLTP↔OLAP benchmark map + the number-is-four-choices mermaid workload/data/harness/metric; choke points one-liner table — Q1 tiny-group agg = expression bench, Q6 2%-scan = the GB/s headline, Q9 = optimizer punisher, TPC-C = the D_NEXT_O_ID hot counter institutionalized; benchmarking-sins checklist linking topic 0’s fair-benchmarking guide), 4 new reading guides + 3 cross-linked existing ones (Boncz TPCTC ’13 choke-point taxonomy with duckdb dbgen/queries dir open + hidden messages — uniform data is why JOB exists, Q1’s 4-6 groups make hash-agg invisible; YCSB SoCC ’10 + go-ycsb zipfian.go:92-165 anchors — zetan/eta/alpha math, the two fast paths, scrambled-fnv rationale, coordinated-omission warning; OLTP-Bench VLDB ’13 + benchbase TPCC anchors — keying/think times :85-100, NURand C_LAST load-vs-run constants :94-116, why nobody runs TPC-C honestly = 12.86 tpmC/warehouse; DuckDB tpch extension — dbgen as streaming TABLE FUNCTION tpch_extension.cpp:17-99 with answers/ shipped next to queries/ = benchmark-as-oracle, run-real-TPC-H-here recipe), experiments crate compiles: dbgen-lite lineitem + row-at-a-time Q1/Q6 oracles + YCSB A-F driver over BTreeMap with ns-percentile Hist PROVIDED and run — Q1 oracle 5.6 GB/s effective (HashMap per row even at 6 groups: CP1.2 measured), Q6 branchy oracle 15.7 GB/s (2% selectivity = perfectly-predicted branch, the crater is hiding at 50%), YCSB uniform A-F 2.88/4.15/3.72/4.40/1.11/2.85 Mops/s with E’s scans 4× a point read — Zipfian/Scrambled generators (the actual YCSB math with head-frequency-vs-theory statistical contract tests) and q1_flat/q6_branchless columnar lanes are todo!() stubs; fixed a nearest-rank percentile off-by-one in the harness itself (harness bugs are results bugs).
2026-07-10 — topic 21 scaffolded: study guide (tool-per-guarantee table proptest→TLC→SMT→Lean with cost axis; e-graph = union-find + hashcons + congruence closure with egg’s deferred rebuild = delta-matrix wait = LSM compaction — batch the invariant repair; equality-saturation loop mermaid; TLA+ spec-as-math with the measured state counts; Z3 DPLL(T) diagram + the euf_egraph.h:23 comment where Z3 cites egg back; Perceus RC as the Arc::make_mut compiler pass), 5 reading guides (AWS CACM ’15 — 35-step S3 bug, exhaustively-testable-pseudo-code pitch, small-scope hypothesis; egg POPL ’21 with full source anchors — egraph.rs:970 add / :1147 union / :1416 rebuild / :1346 process_unions fixpoint, machine.rs Bind/Scan/Compare pattern VM = topic 19’s bytecode interpreter, extract.rs greedy find_best vs lp_extract, e-graph ≈ Cascades memo; Z3 TACAS ’08 + src/ast/euf anchors — backtracking trail + justifications = WAL for unions, e-matching triggers = index choice; Specifying Systems + Ongaro’s raft.tla — newly cloned — with the un-model-an-assumption exercise that re-derives terms; Beans + Perceus borrowed-vs-owned + reuse tokens with the proof-vs-TLC-vs-proptest calibration exercise), experiments crate compiles on egg 0.9: expr IR + hand-ordered fixpoint rewriter PROVIDED and run — ~30% cost reduction, ~2 µs/firing, and the planted trap measured: (a*2)/2 → strength-reduce fires before div-reassoc → stuck at (a<<1)/2 cost 5 where egg should reach cost 1 — egg_optimize is a todo!() stub with trap + never-worse-than-hand tests; TLA+ WalReplication spec written AND model-checked (tla2tools.jar downloaded, java 17): SyncCommit=TRUE → Durability holds over 1080 distinct states depth 14 in <1 s; SyncCommit=FALSE → TLC finds the 5-state data-loss trace Append→Commit→Crash→Failover after 123 states — the postgres synchronous_commit=off story, found exhaustively.
2026-07-10 — topic 20 scaffolded: study guide (format lattice hypersparse→sparse→bitmap→full with the actual switch tests from GB_convert_sparse_to_bitmap_test.c and GB_conform; one-mxm-four-engines mermaid — dot3 iterates the MASK so work ∝ nnz(M) vs saxpy3’s coarse/fine × Gustavson/hash task scheduler with its flopcount pre-pass = cudf size/retrieve five years early; push-vs-pull BFS as vxm-vs-mxv with LAGraph’s shipped α=8/β1=8/β2=512; delta matrices as LSM-over-matrices — DP=memtable, DM=tombstones, wait=minor compaction, delta_mxm’s (A*(M+DP))<!A*DM> fold), 6 reading guides (Davis TOMS ’19+’23 — zombies/pending as the library’s own deltas, iso matrices, 32-bit indices; SuiteSparse internals with saxpy3.c:22-60 scheduling-essay and hash>m/16⇒Gustavson anchors; Gustavson ’78 + Buluç-Gilbert — SPA design space, symbolic/numeric two-phase; Beamer SC ’12 direction-optimizing with the ICPP ’18 linear-algebra translation; LAGraph — BFS template switch block anchors, ANY_SECONDI parent-without-comparisons, six triangle-count formulations, PageRankGAP; FalkorDB delta_matrix with fresh eyes — header state-table as spec, transposed twin, transpose-as-masked-copy sync, over-masking question — LAGraph newly cloned), experiments crate compiles: CSR+RMAT/uniform/path generators, SpMV, hash-SpGEMM, scalar BFS, hypersparse PROVIDED and run — SpMV 16-19 GB/s single-thread (gather tax vs 30 GB/s streaming), hash SpGEMM ~60-75 Mflop/s (15 ns/flop = the accumulator cost the SPA stub should crush), hypersparse 50× index memory and 171× full-sweep on the 10M-nodes/100K-edges FalkorDB shape — dense-SPA Gustavson and push/pull/direction-optimizing BFS (with per-level trace + path-graph-never-pulls test) are todo!() stubs.
2026-07-10 — topic 19 scaffolded: study guide (the spectrum tree-walker → bytecode VM → copy-and-patch → IR JIT → LLVM as a compile-latency-vs-run-speed trade with each system placed on it; produce/consume compiles the PIPELINE not the operators — push inverts control so tuples stay in registers; three JIT grains compared — postgres per-query, Umbra per-pipeline with adaptive Flying-Start→LLVM tiering, GraphBLAS per-kernel-specialization cached forever; DuckDB’s deliberate no-JIT with the VLDB ’18 tie as the counter-argument; M19 = expressions only, gate on measured cost), 6 reading guides (Neumann VLDB ’11 pipelines/breakers + produce-consume inversion; SQLite VDBE — vdbe.c:1049 switch over 199 opcodes, register machine, OP_Yield coroutines as flattened-bytecode’s free resumability; Umbra Tidy Tuples single-pass IR + copy-and-patch musttail stencils; postgres llvmjit_expr.c opblocks-per-EEOP-step + the jit_above_cost estimate-gate failure taxonomy + deform-JIT-as-the-real-win; GraphBLAS jitifyer encodify-hash → PreJIT → memory table → dlopen → invoke-cc ladder with FalkorDB cache-warming implications; cranelift-jit-demo declare→define→finalize→transmute ladder + per-node CLIF emission table for the stub), experiments crate compiles on cranelift 0.116: Expr enum + seeded generator, AST interpreter, and column-at-a-time vectorized lane PROVIDED and run — interp ~2.1 ns/node flat, vectorized 6-12× over interp across depths 2-10 (topic 11’s number reproduced; both linear in nodes, no y-intercept until compile time adds one) — jit.rs compile() is a todo!() stub with bit-exact-vs-interpreter tests, jit_bench prints the three-way table with compile µs + e2e winner and survives the stub via catch_unwind.
2026-07-10 — topic 18 scaffolded: study guide (GPU-for-DB-people translation table — SIMT = topic 17’s predication in hardware, coalescing = columnar × 32, shared memory = cache blocking made explicit; the bus decides the architecture — Crystal’s regime A ship-per-query vs regime B device-resident, rewritten for Apple unified memory; libcudf size/retrieve two-phase + cooperative-groups probing = SwissTable at warp scale; Gunrock advance/filter + load-balance menu; CAGRA = HNSW with SIMT-hostile parts deleted by construction), 6 reading guides (Crystal SIGMOD ’20 tile model + fair-CPU-baseline lesson; wgpu compute examples ladder incl. the hello_compute doc-comment our bench proves; libcudf join size/retrieve + shared-mem-until-spill groupby with cuco/cooperative-groups anchors — newly cloned; Gunrock Essentials bfs.hxx enactor + advance.hxx thread/block/merge_path dispatch anchors — newly cloned; CAGRA ICDE ’24 + single-CTA kernel/shared-mem-hashmap/bitonic-topk anchors — cuvs newly cloned; Faiss GPU billion-scale paper — WarpSelect register k-select, memory-tier table), experiments crate compiles AND RUNS on Metal: GpuCtx + workgroup-reduction sum kernel PROVIDED with per-phase timings, gpu_bench crossover sweep run on Apple M3 Pro — CPU wins at every size up to 16M elements (~1.5 ms fixed dispatch floor, flat 16K→1M; even amortized the GPU reads the same unified memory at ~9 GB/s effective vs CPU 30 GB/s — regime B’s bandwidth ratio doesn’t exist for streaming ops on this machine, which IS the lesson), filter_count (one-atomicAdd-per-workgroup, WGSL skeleton provided) and l2_batch (one-invocation-per-target + row/column-major coalescing experiment) are todo!() stubs with exact-match/1e-3 tests, notes.md predicts where arithmetic intensity finally flips the verdict.
2026-07-10 — topic 17 scaffolded: study guide (ports×latency mental model — M-series 4 FMA ports × 3cy ⇒ ~12 independent chains, the four autovectorization failures, branchy/branchless/compress filter shapes with AVX-512 vpcompress vs NEON’s missing compress, vshrn movemask idiom, FastLanes interleaved layout), 7 reading guides (simdjson VLDB ’19 + arm64 nibble-LUT classification / PMULL prefix_xor quote parity / LUT-shuffle compress emulation / flatten_bits over-write-under-advance — newly cloned; polars-compute float_sum STRIPE=16 + pairwise-128 and simd_filter! with per-ISA compress + selectivity-adaptive scalar bit-iteration fallback; hashbrown Group×3 backends + memchr Vector — newly cloned — with the finding that hashbrown’s NEON group is 8 BYTES so vceq output already IS the bitmask, no vshrn, while memchr keeps 16 lanes and narrows; SimSIMD under its numkong rename — per-instruction latency/port tables in headers, f64-upcast accumulation, 4-target streaming states = M14’s scoring loop, and the FCMLA lesson: the specialized instruction measured 2.3× SLOWER than 4 plain FMAs; SIGMOD ’15 selective-store/load primitives + vertical hash probing + gather-costs-a-load-per-lane; FastLanes VLDB ’23 1024-lane transposed layout; Mojo SIMD[type,width] parametric-width ladder), experiments crate compiles: dot naive+unrolled-8 PROVIDED and run — 10.89 → 42.12 GB/s, 3.9× from accumulator count alone, zero intrinsics — wide-f32x4 and NEON vfmaq 4-accumulator rungs are todo!() stubs; filter branchy+branchless PROVIDED and swept — branchy craters 9× to 1.19 GB/s at 50% selectivity while branchless holds ~12.7 flat, the SIGMOD ’15 curve live — NEON count (vcltq+vsubq mask-accumulate) and LUT-compress compact (simdjson trick, f32 edition, all-16-masks test) are stubs; unpack4 scalar PROVIDED at 10.20 GB/s, NEON shift/mask stub; simd_bench catches stub panics so baselines always print.
2026-07-10 — topic 16 scaffolded: study guide (every technique = generator + oracle table, DST determinism boundary diagram, PQS/TLP/NoREC comparison, Jepsen/elle, Z3-as-search-engine), 6 reading guides (turso testing/simulator with clock/io/file fault-injection anchors + interaction-plan properties + doublecheck + structured fuzz targets; FDB simulation + BUGGIFY + Antithesis determinism-boundary table; SQLancer oracle base classes — newly cloned — PQS check()/rectification, TLP 3-way partition, NoREC optimized-vs-forced-scan; PQS OSDI ’20 + TLP OOPSLA ’20 paired; Jepsen redis-raft/Dgraph findings + elle cycle inference; Z3 — newly cloned — TACAS ’08 + tactic/solver/smt_context anchors + Cosette symbolic-row rewrite verification), experiments crate compiles: sim_fs (buffered/synced/torn-tail file) + kv (WAL KV with 4 injectable bugs: LostDelete/NoSyncOnCommit/TornWriteAccepted/StaleRead) PROVIDED, dst harness + ddmin shrinker + TLP Kleene-eval checker are todo!() stubs with 12 contract tests (all bugs caught ≤200 seeds, zero false positives over 500, deterministic replay, 1-minimal repro, null-blind engine exposed), crash_matrix PROVIDED and run: 5000 seeds/0.02 s per bug — 0.0% false positives, bugs caught at 48.8–99.6% per-seed rates, first failing seed ≤ 3; the matrix caught a real bug in this crate’s own recovery (missing WAL tail truncation made torn leftovers join the next batch — 72.7% divergence until fixed), the topic’s thesis self-demonstrated.
2026-07-10 — topic 15 scaffolded: study guide (topology menu as WHO-can-ack axis, Raft state-machine mermaid + election/log-matching/§5.4.2 three-way split, write-path comparison valkey/WAIT/raft, consistency ladder + ReadIndex, hash slots vs ranges), 6 reading guides (Raft ATC ’14 with Fig 8 worked by hand; valkey replication.c shared repl buffer + PSYNC replid/offset + REPL_STATE_ handshake + WAIT + FAILOVER with line anchors; tikv raft-rs — newly cloned — RawNode/Ready contract + step_* dispatch + Progress tracking + maybe_commit-is-§5.4.2; qdrant consensus.rs raft-for-metadata-only split with the data path outside raft; VSR Revisited round-robin views + no-disk durability + TigerBeetle disk-can-lie; DDIA ch. 5/8/9 anomaly catalog + fencing tokens + linearizability), experiments crate compiles: sim.rs deterministic lockstep network PROVIDED (seeded delivery, partition/heal — topic 16 DST preview), raft.rs todo!() stub with 5 safety-pinning tests (one leader, one-per-term across 10 seeds, replicate-to-all, minority-commit-freeze, stale-leader truncation), partition_test timeline binary, repl_lag PROVIDED and run: follower fsync policy AS ack latency — every-1 = 339 entries/s at 2973 µs p50 (F_FULLFSYNC) vs never = 18568/s at 6 µs, the topic 5 ladder measured as replication lag.
2026-07-10 — topic 14 scaffolded: study guide (recall-vs-QPS curve framing, HNSW-as-skip-list ASCII, quantization ladder u8/PQ/binary with oversample+rescore, IVF + DiskANN families, filtered-search menu with percolation), 6 reading guides (qdrant GraphLayers builder/serve split + visited pool + the per-query algorithm choice HNSW/ACORN/plain via estimate_cardinality + measured percolation at build; qdrant quantization crate u8 affine dot-expansion / PQ ADC LUTs / binary xor_popcnt + get_oversampled_top; usearch — newly cloned — node-tape layout + paper-default constants + striped locks (helix-db dropped: public repo no longer ships engine source); HNSW paper with skip-list lens; Jégou PQ with SDC/ADC + IVFADC residuals-as-FOR; DiskANN Vamana robust-prune α-slack + PQ-steers/f32-ranks SSD layout), experiments crate compiles: brute-force oracle PROVIDED and run (185 QPS at recall 1.0 over 100K×128-d — the floor), hnsw (Alg 1/2/4, level draw, ef knob) and quant (affine u8 + symmetric distance + rescore pipeline) are todo!() stubs with 10 contract tests (self-query top-1, recall@10 ≥ 0.9, sorted results, log level distribution, α/2 error bound, rescored recall ≥ 0.95), ann_bench sweeps ef 16..256 + oversampling 1/2/4.
2026-07-10 — topic 13 scaffolded: study guide (adjacency representation menu with CSR ASCII, four-architecture table neo4j/memgraph/kuzu/FalkorDB across store/Expand/pattern-match/MVCC/updates, delta-overlay-as-LSM observation, pointer-chasing cost analysis, WCOJ/AGM section, LDBC referee), 6 reading guides (GraphBLAS 4 sparsity formats + dot-vs-saxpy mxm + masks-as-pushdown + FalkorDB Delta_Matrix M/DP/DM state machine — neo4j/kuzu/GraphBLAS newly cloned; neo4j 15 B node / 34 B rel fixed records + doubly-linked rel chains = one miss per edge; memgraph skip-list vertex + small_vector edges + PointerPack’d delta MVCC; kuzu columnar CSR node groups persistent+transient + Intersect WCOJ + factorization; AGM bound / Generic Join / EmptyHeaded with the C<A>=A² equivalence; LDBC SNB correlated-power-law datagen + updates-during-reads), experiments crate compiles: adj_list oracle PROVIDED and run (1M-node/16M-edge preferential-attachment: 3.5 µs/query random vs 295 µs supernodes — the 85× graph-shaped tail, max degree 6565), csr (counting-sort build + slice two_hop) and matrix (masked-SpMV two_hop) are todo!() stubs with oracle-agreement + exact-layout + cycle-self-exclusion tests, hop_bench cross-checks via checksums.
2026-07-10 — topic 11 scaffolded: study guide (Volcano→X100→HyPer mermaid, selection vectors + vector-type flags, morsel-driven parallelism diagram, vectorized hash join/agg internals), 6 reading guides (DuckDB DataChunk/2048 + pipeline executor push-pull hybrid + join-HT salt-in-pointer probe; postgres ExecProcNode self-replacing dispatch + execExprInterp computed-goto; polars-stream Morsel/MorselSeq/SourceToken + float_sum masked-SIMD multi-accumulator + DataFusion ExecutionPlan streams and intern-then-flat-arrays GroupedHashAggregateStream; X100 CIDR’05 U-curve; VLDB’18 compiled-vs-vectorized scorecard — memory-bound probes favor vectorized, the M11 architecture argument; SIGMOD’14 morsels), experiments crate compiles: one query three engines — Volcano PROVIDED and run (180.7 M rows/s; found LLVM DEVIRTUALIZING the statically-known Box<dyn> chain, 202→180 after black_box — a compiler will silently turn your Volcano into a compiled engine), vectorized (batches + selection vectors + flat group array) and fused branchless kernel are todo!() stubs with oracle-agreement tests incl. partial-final-batch and mask-sign-extension traps, exec_bench sweeps selectivity 5/50/95.
2026-07-10 — topic 10 scaffolded: study guide (parse→bind→logical→rewrite→join-order→physical pipeline mermaid, rewrite-rule menu, Selinger DP vs DuckDB DPccp+greedy-fallback, cardinality three-lies table, Selinger-vs-Cascades memo ASCII), 5 reading guides (DuckDB optimizer.cpp 25-pass pipeline + plan_enumerator DPccp with greedy escape hatch :234 + cost=output-cardinality-only; postgres allpaths.c standard_join_search + geqo threshold 12 + DEFAULT_EQ_SEL 0.005; sqlparser-rs Pratt parse_subexpr + DataFusion fixpoint-of-rules vs DuckDB ordered passes — sqlparser/datafusion/polars newly cloned; Selinger ’79 vs Cascades with M10 architecture-choice question; Leis VLDB’15 JOB — cardinality error 10²–10⁴ dwarfs cost model 2× and search 1.2×, graph-JOB design exercise), experiments crate compiles: toy cost-based planner todo!() stubs (parse_and_plan naive left-deep → push_down → greedy reorder_joins → estimate with 1/NDV + independence + containment) with contract tests incl. join_order_flips_with_stats, explain binary PROVIDED for side-by-side DuckDB EXPLAIN comparison.
2026-07-10 — topic 9 scaffolded: study guide (latch vs lock table, memory-ordering cheat sheet + publication idiom, latch-coupling→OLC→lock-free ladder, epoch reclamation diagram, Bw-tree cautionary arc, false sharing), 4 reading guides (postgres lwlock.c packed u32 + recheck-after-enqueue lost-wakeup dance; crossbeam-epoch pin/defer/try_advance — newly cloned; RocksDB InlineSkipList CAS+splices vs memgraph lazy-locking skiplist with accessor-id GC — memgraph newly cloned; Bw-tree ICDE’13 + SIGMOD’18 reality check + Leis OLC), experiments crate compiles: lock-free ConcurrentSet todo!() stub over crossbeam-epoch with 5 contract tests (same-key/remove races exactly-one-winner, reader-survives-removal-churn UAF canary), scaling shootout PROVIDED (global mutex / 16-shard / crossbeam SkipSet / yours, 1→16 threads), false_sharing PROVIDED and run — packed 63 M inc/s vs pad128 3707 M (59×), and pad64 still 2.2× slower than pad128: Apple M-series coherence granularity is 128 B, x86-style 64 B padding only half-fixes it.
2026-07-10 — topic 8 scaffolded: study guide (anomaly-per-isolation-level table, doctors write-skew walkthrough, 2PL/OCC/MVCC comparison, postgres tuple-header + visibility flowchart, HOT chain, Hekaton contrast), 6 reading guides (postgres heapam.c/heapam_visibility.c HeapTupleSatisfiesMVCC + HOT + prune/vacuum with line anchors; RocksDB optimistic vs pessimistic txns over one base class — memtable-only OCC validation, point lock manager; surrealdb kvs layer — newly cloned — versioned reads + putc as portable OCC; Berenson ’95 history notation + SI dethroned; SSI VLDB’12 dangerous structure + the single-writer M8 shortcut question; Hekaton + Wu/Pavlo 5-axis menu), experiments crate compiles: Mvcc todo!() stub with 8 contract tests including write_skew_HAPPENS_under_SI (test passes when the anomaly occurs) and Serializable-mode prevention via read-set validation, txn_bench PROVIDED (global Mutex baseline vs MVCC, 3 mixes incl. 64-key hot set, abort counts).
2026-07-10 — topic 7 scaffolded: study guide (RESP wire anatomy, event-loop mermaid beforeSleep→poll→read→execute→buffer, three threading models table, backpressure: querybuf/output-buffer kills vs pgwire portals), 4 reading guides (redis ae.c + networking.c parse/reply path with line anchors; valkey 8 io_threads.c SPSC inboxes + tagged job pointers + memory_prefetch.c batch-MLP; pgwire Parse/Bind/Execute/Sync portals + qdrant dual tonic servers — both newly cloned; C10K → thread-per-core arc with the shared↔sharded plane exercise), experiments crate compiles: RESP2 parse/encode todo!() stub with 8 format-fixing tests (incomplete-input-keeps-bytes, binary-safe bulks, pipelining), tokio server PROVIDED (16-shard store, parse-all-then-flush-once pending-writes trick) — benches vs real redis via redis-benchmark -P 1/-P 64 + flamegraph once resp.rs is implemented.
2026-07-10 — topic 6 scaffolded: study guide (translation-cost table hash/swizzle/MMU, miss-path mermaid, three shapes of approximate-LRU, swip state diagram, mmap CIDR-’22 checklist), 6 reading guides (postgres bufmgr.c packed-atomic state + CLOCK + buffer rings; DuckDB eviction queue with dead nodes + 4096-insert purge — newly cloned; LeanStore swips/cooling/hybrid latches — newly cloned; redis zmalloc per-thread padded counters + turso CLOCK page cache bonus; mmap paper with LMDB rebuttal; LeanStore+vmcache paper arc), experiments crate compiles: CLOCK BufferPool todo!() stub with contract tests (pinned-never-evicted, dirty-writeback, scan-pressure survival), pool_vs_mmap binary (1GiB file, 4× memory budget, Zipf, tail-latency focus), eviction bench PROVIDED and run — CLOCK 67.0% vs strict-LRU 66.3% hit rate at 20× less time per access (32ms vs 678ms per 1M trace): the “nobody ships strict LRU” lesson, measured.
2026-07-10 — topic 5 scaffolded: study guide (WAL rule, four-designs axis LMDB→turso→postgres→redis-AOF, fsync ladder table, group-commit mermaid), 5 reading guides (postgres xlog.c — newly cloned — reserve-then-copy/XLogFlush-recheck/FPI with line anchors; turso WAL checksum chain + salts; redis aof.c/rdb.c with the AOF-as-LSM mapping + FalkorDB angle; ARIES three passes/CLRs; Aether four-bottleneck taxonomy), experiments crate compiles: fsync_ladder PROVIDED and run (this Mac: fsync 21µs vs F_FULLFSYNC 3.0ms — 140×, the macOS weak-fsync gap is real), Wal todo!() stub with format-fixing tests (torn tail, uncommitted-txn invisibility, commit_many = 1 fsync), crash_test kill-9 harness (100 rounds, acked-key + atomicity checks), commit_throughput bench (per-commit vs group 8/64/512).
2026-07-10 — topic 4 scaffolded: study guide (memtable→SST lifecycle mermaid, SST block anatomy, leveled/tiered/lazy RUM table, stall triggers, Monkey intuition), 6 reading guides (lsm-tree crate — newly cloned, fjall delegates to it — + RocksDB compaction/table with line anchors; Monkey, Dostoevsky, RocksDB TODS ’21, compaction design-space VLDB ’21), experiments crate compiles: mini-LSM with provided Bloom (tests pass) + Memtable, SST writer/reader + Lsm engine todo!() stubs with correctness tests (tombstone-across-compaction, WA>1 check), write_amp binary measuring the full RUM position of leveled vs tiered.
2026-07-10 — topic 3 scaffolded: study guide (slotted page anatomy, 3-sibling balance mermaid, LMDB double-meta COW commit diagram), 5 reading guides (turso btree deep + SQLite btree.c + LMDB mdb.c with line anchors from fresh clones; Graefe survey selective-read map, SQLite file-format hex-dump exercise), experiments crate compiles: slotted Page + DiskBTree todo!() stubs with format-fixing tests, bench vs redb (point/scan) + prefix-truncation stress case (32B keys, 24B shared prefix).
2026-07-10 — topic 2 scaffolded: study guide (chaining vs open addressing cache stories, incremental-rehash mermaid, skiplist/rax ASCII, dense-filter/fat-payload pattern table), 7 reading guides (redis dict/zset/rax, hashbrown SwissTable, RocksDB InlineSkipList — line numbers from local clones; ART paper, CppCon SwissTable talk), experiments crate compiles: skiplist + incremental_map todo!() stubs with tests (the build work is the learning work), benches vs hashbrown/BTreeMap/crossbeam-skiplist, rehash_spike binary (HdrHistogram per-insert max/p99.9).
2026-07-10 — topic 1 started: study guide (two-family write/read paths, amplification vocabulary, RUM triangle), 8 reading guides (fjall/turso/tidesdb/rocksdb code + O’Neil/Comer/RUM/Hellerstein papers, line numbers from fresh shallow clones), engine_shootout scaffold (fjall vs redb behind a common trait, db_bench workload names, durability parity) compiles + smoke-tested (space-amp binary at 20K keys shows fixed-overhead floor, not amplification — re-run at 1M+). Topic 0 plan audit: fixed phantom CMU-lecture reference in PLAN.md, added missing roofline-thinking section to topic 0 README §4.
2026-07-10 — topic 0 finished: cache_ladder (after fixing a self-caching bug: restarting the pointer chase at 0 measured an 8MB hot path — fixed by carrying the walker across iterations; true ladder 1.0 ns L1 / 5–9 ns L2 / ~110 ns DRAM+TLB), lookup_shootout (HashMap flat at ~7–9 ns thanks to MLP; binary search wins ≤1e4; linear scan never beats hashing at n≥100 — folklore busted), flamegraph captured (21% SipHash in HashMap lookups), reference baselines recorded in capstone/BASELINES.md. Topic 0 + M0 done.
2026-07-10 — topic 0 started: study guide + 3 experiment benches (cache_ladder, lookup_shootout, branch_misprediction); capstone workspace scaffolded with workload crate (seeded Zipfian generator, ~11M ops/s). First measured result: branchy filter 8.1x slower on shuffled vs sorted data; branchless flat at 15 Gelem/s. Repo published to github.com/AviAvni/database-learning-path.