Exercises

Each lesson's key functions with the bodies removed and the tests left in. Read the post, then make the tests pass.

The exercise copies live in clojure/ex/exercises/lessonNN and go/exercises/lessonNN; each blank is a TODO that throws, with a hint above it. At a REPL: clj -A:ex, then (require 'exercises.lessonNN.ns-test :reload) and (clojure.test/run-tests 'exercises.lessonNN.ns-test). The reference lessons are the answer key.

Part 1 · Expressions

cd clojure && clojure -M:ex -d ex -n exercises.lesson01.<ns>-test
cd go && go test ./exercises/lesson01/

• eval-binary Go go/exercises/lesson01/expressions.go
  Evaluate the left side with Eval. For AND/OR, stop if it already decides the answer (FALSE AND …, TRUE OR …); otherwise evaluate the right side and combine: AND/OR with three-valued logic (Logic3), every other operator through ApplyBinary.
• compile-closures Go go/exercises/lesson01/expressions.go
  Walk the tree once and return a closure per node. Resolve column names to positions now, so the returned function only indexes into the row.
• and-or-3vl Go go/exercises/lesson01/expressions.go
  Return the deciding value if either side has it (false for AND, true for OR); otherwise NULL if either side is NULL; otherwise the ordinary boolean answer.
• eval-binary Clojure clojure/ex/exercises/lesson01/expressions.clj
  Apply + - * / to two values with SQL rules: NULL in → NULL out, int∘int stays an int, anything with a float is a float, / always returns a float, x/0 → NULL.
• and-or-3vl Clojure clojure/ex/exercises/lesson01/expressions.clj
  AND: false wins, then NULL, then true. OR: true wins, then NULL, then false.
• eval-tree Clojure clojure/ex/exercises/lesson01/expressions.clj
  Look at the node's tag, evaluate its children recursively against `row`, and combine them (columns, literals, arithmetic, comparisons, AND/OR/NOT, IS NULL, functions).
• compile-closures Clojure clojure/ex/exercises/lesson01/expressions.clj
  Walk the tree once, now, and return (fn [row] ...). Resolve column names to indexes here, so the returned closures only index into the row and combine results.

Part 2 · Iterators

cd clojure && clojure -M:ex -d ex -n exercises.lesson02.<ns>-test
cd go && go test ./exercises/lesson02/

• filter-next Go go/exercises/lesson02/iterators.go
  Pull rows from the child until one passes the predicate; report exhaustion when the child runs out.
• limit-next Go go/exercises/lesson02/iterators.go
  Pass rows through until N have been returned, then stop — without asking the child for another row.
• filter-next Clojure clojure/ex/exercises/lesson02/iterators.clj
  Pull rows from the child until one makes the predicate exactly true and return it; return nil when the child runs out.
• limit-next Clojure clojure/ex/exercises/lesson02/iterators.clj
  Pass child rows through until n have been returned; after that, return nil WITHOUT asking the child for another row.

Part 3 · Joins

cd clojure && clojure -M:ex -d ex -n exercises.lesson03.<ns>-test
cd go && go test ./exercises/lesson03/

• nl-join-next Go go/exercises/lesson03/joins.go
  For each outer row, rewind and walk the whole inner side, emitting concatenated rows that pass Pred; for LEFT OUTER, emit the outer row padded with NULLs if nothing matched.
• hash-join-build Go go/exercises/lesson03/joins.go
  Read the entire right side into a hash table keyed on RightKey (skipping NULL keys), counting BuildRows; then open the left side for probing. Build phase: a pipeline breaker. Nothing comes out until the right side is fully read.
• hash-join-probe Go go/exercises/lesson03/joins.go
  For the current probe row, look its key up in the table built in Open and emit one joined row per match; pad with NULLs for left outer when nothing matched.
• merge-join-next Go go/exercises/lesson03/joins.go
  Both inputs are sorted on the key. Advance whichever side is behind; when keys are equal, buffer the right side's group of equal keys and pair it with every left row carrying that key.
• nl-join-next Clojure clojure/ex/exercises/lesson03/joins.clj
  For the current outer (left) row, scan the inner (right) side from the top and return each combined row where the predicate is true; then advance the outer row. For :left, emit the outer row padded with NULLs if nothing matched. Count each test in :comparisons.
• hash-join-build Clojure clojure/ex/exercises/lesson03/joins.clj
  Drain the right child into @table: a map from (hash-key key) to the vector of right rows with that key, in arrival order. Skip NULL keys; count :build-rows.
• hash-join-probe Clojure clojure/ex/exercises/lesson03/joins.clj
  For each left row, look its key up in @table and emit one joined row per match (buffer them in `pending`); pad with NULLs for :left when nothing matched. NULL keys never match. Count :probes and :comparisons (bucket size).
• merge-join-next Clojure clojure/ex/exercises/lesson03/joins.clj
  Both inputs are sorted. For each left key, skip right rows with smaller keys, gather the group of right rows with an equal key (reuse it if the next left row has the same key), and emit the left row joined with each. Compare keys with `cmp`.

Part 4 · Aggregation & sorting

cd clojure && clojure -M:ex -d ex -n exercises.lesson04.<ns>-test
cd go && go test ./exercises/lesson04/

• hash-aggregate Go go/exercises/lesson04/aggregation.go
  Read the whole child. Find or create each row's group in a hash table (remembering first-seen order) and step its accumulators; then emit one row per group. No GROUP BY over empty input still yields one row.
• external-sort-merge Go go/exercises/lesson04/aggregation.go
  The heap holds the smallest unread row of every run. Pop the smallest, refill the heap from the run it came from, and return it.
• top-n Go go/exercises/lesson04/aggregation.go
  Keep only the best N rows seen so far in a heap with the worst on top; a better row replaces the top (count Evictions). At the end, sort what's left for output.
• hash-aggregate Clojure clojure/ex/exercises/lesson04/aggregation.clj
  Drain the child. For each row compute its group key, find (or create) that group's accumulators, and step each one with its aggregate's input value. Then close the child and put the finished rows (key ++ finalized aggregates) in @result, in first-seen order. No GROUP BY and no input still yields one row.
• external-sort-merge Clojure clojure/ex/exercises/lesson04/aggregation.clj
  The heap holds [row run-index position] for the head of each run. Take the smallest, push the next row from the same run (if any), and return the row taken. Count :heap-pops in `stats`.
• top-n Clojure clojure/ex/exercises/lesson04/aggregation.clj
  Read every child row as [row seq-no]. Keep at most n entries in `pq`, whose head is the worst kept: fill it up, then replace the head only when a new row is strictly better.

Part 5 · Indexes

cd clojure && clojure -M:ex -d ex -n exercises.lesson05.<ns>-test
cd go && go test ./exercises/lesson05/

• btree-split Go go/exercises/lesson05/btree.go
  Insert into the right leaf (extending the posting list if the key exists). When a node overflows, split it in half and return the separator and new right sibling to the parent: leaves copy their first right key up, internal nodes move the middle key up.
• btree-search Go go/exercises/lesson05/btree.go
  Descend from the root to the leaf that could hold key, choosing a child at each internal node; count every node visited.
• btree-range Go go/exercises/lesson05/btree.go
  Find the starting leaf (or the leftmost one), then walk the leaf chain collecting row ids for keys inside the bounds, stopping at the first key past hi. Count node visits.
• btree-split Clojure clojure/ex/exercises/lesson05/btree.clj
  Move the upper half of the leaf's keys/vals to a new page (alloc), keep the lower half in page `id`, and fix the :next links so the leaf chain stays in order. Return [tree {:key first-key-of-right-half :right new-page-id}] for the parent.
• btree-search Clojure clojure/ex/exercises/lesson05/btree.clj
  Start at the root page. At an internal page, follow the child whose key range holds k (keys equal to a separator go right: upper-bound); nil k means leftmost. Stop at a leaf. Count every page you read.
• btree-range Clojure clojure/ex/exercises/lesson05/btree.clj
  Descend once to the leaf where lo would be, then walk forward collecting [key row-ids] until a key passes hi, following :next to the following leaf page when one runs out.

Part 6 · Statistics & planning

cd clojure && clojure -M:ex -d ex -n exercises.lesson06.<ns>-test
cd go && go test ./exercises/lesson06/

• join-order-dp Go go/exercises/lesson06/planner.go
  For subset sizes 2..n, for each subset S and each table t in it, extend Best[S−{t}] by joining t (joinPreds, orient, joinCandidates) and keep the cheapest candidate in Best[S]. Skip cross products when another order could use a join predicate.
• eq-selectivity Go go/exercises/lesson06/stats.go
  Assume uniformity: every distinct value is equally common, and NULLs never match. Use Rows, Nulls and NDV; guard against an empty or all-NULL column.
• join-cardinality Go go/exercises/lesson06/stats.go
  Every value on the side with fewer distinct values finds a partner on the other side (containment), so each row matches 1/max(ndv(a), ndv(b)) of the other side's rows.
• range-selectivity Go go/exercises/lesson06/stats.go
  Walk the equi-depth histogram: buckets entirely below v count fully; the bucket that contains v counts in proportion to where v falls inside it. Return a fraction of all rows.
• range-selectivity Clojure clojure/ex/exercises/lesson06/planner.clj
  Sum the histogram: buckets entirely below v count fully, buckets at or above v count nothing, and the bucket straddling v counts the fraction of its [lo, hi] span below v.
• eq-selectivity Clojure clojure/ex/exercises/lesson06/planner.clj
  Assume every distinct non-NULL value is equally common: non-NULL rows spread evenly over ndv values (0.0 when there are no distinct values).
• join-cardinality Clojure clojure/ex/exercises/lesson06/planner.clj
  Each value on the side with fewer distinct values finds its partners on the other side: 1 / max(ndv(l), ndv(r)) (guard against 0).
• join-order-dp Clojure clojure/ex/exercises/lesson06/planner.clj
  Starting from best1 (one relation each), for k = 2..n and every k-subset s, try adding each r in s to the best plan for (s − r) via join-candidates; prefer candidates with a join edge; keep the cheapest per s. Count candidates in `considered`.

Part 7 · Bytecode

cd clojure && clojure -M:ex -d ex -n exercises.lesson07.<ns>-test
cd go && go test ./exercises/lesson07/

• compile-filter Go go/exercises/lesson07/compiler.go
  Produce the child. In its consume callback, compile the predicate into a register, emit an IfNot that jumps past this row's code, call consume, and then patch the jump's target to the address after it.
• compile-nl-join Go go/exercises/lesson07/compiler.go
  Produce the left child; inside its consume, produce the right child, so its loop nests inside. With both rows in registers, test the ON predicate (if any) like a filter and consume the concatenated registers.
• vm-step-loop Go go/exercises/lesson07/vm.go
  Fetch–execute until fuel runs out: advance PC before executing (jumps overwrite it). Halt ends the program; ResultRow returns a copy of its registers as a row (PC already points past it, so the next Step resumes there); everything else goes to exec.
• vm-cursor-ops Go go/exercises/lesson07/vm.go
  OpenScan points a cursor at a table; Rewind moves it to row 0 (or jumps to P2 if the table is empty); Column copies column P2 of the current row into register P3; Next advances and jumps back to P2 while rows remain.
• compile-filter Clojure clojure/ex/exercises/lesson07/compiler.clj
  Have the child produce rows; for each, emit code computing pred, an IfNot that skips the row, then the parent's consume. Patch the IfNot's jump target to just after it.
• compile-nl-join Clojure clojure/ex/exercises/lesson07/compiler.clj
  Emit the right side's loop INSIDE the left side's consume. In the inner consume, combine both envs (join-env), test pred like a filter, and call the parent's consume.
• vm-result-row Clojure clojure/ex/exercises/lesson07/vm.clj
  Hand a row to the caller: put the values of registers p1 .. p1+p2-1 under :out. (pc has already moved past this instruction, so resuming continues after it.)
• vm-step-loop Clojure clojure/ex/exercises/lesson07/vm.clj
  Call `step` repeatedly. Stop with :done once halted, :out-of-fuel after `fuel` instructions, or :row as soon as a step leaves a row under :out (remove it from the returned state).