Notes
Requirements
The requirements. Create a table from a schema: typed columns, INT or TEXT, and one primary key column. Insert checks every type and rejects a duplicate key. Select, update and delete take a where clause of conditions joined by AND, with equals, not equals and the four comparisons. Indexes can be added to any column, and explain shows which plan a query will use. Transactions come as an extension once the core works.
Agree the scope, because this question can grow forever. No SQL text parser at first; a small Java API is enough, and parsing is a follow-up. No OR, joins or grouping. Updating the primary key is rejected; do a delete and an insert. Nulls are not allowed, which keeps comparisons simple. Many clients read at once, and nothing is persisted to disk. Saying these out loud shows you can cut a big problem to a buildable one.
- createTable(name, schema)
- columns typed INT or TEXT
- one primary key column
- insert(row): types checked,
- duplicate key rejected
- select / update / delete
- WHERE a = 1 AND b < 5
- createIndex(table, column)
- explain(): which plan is used
- transactions as an extension
- parse SQL text?
- no: a fluent Java API first
- OR, joins, GROUP BY?
- out of scope, follow-ups
- update the primary key?
- rejected: delete + insert
- nulls?
- not allowed, keeps compare easy
- concurrent clients?
- yes: many readers at once
- persistence? no, memory only
Entities
The entities. The database holds tables by name. Each table owns a schema, the rows keyed by primary key, and zero or more secondary indexes. A planner decides how to find the rows a query needs. And a transaction groups several changes so they all apply or none do. The key layering decision: only the table changes rows and indexes, through exactly two methods, so they can never drift apart.
Class diagram
The types. Column and schema are records, and the schema's constructor rejects a primary key that is not a column. The schema also owns coerce, which type-checks a value and turns every integer into a long, so later comparisons only ever see longs or strings. A row is an immutable map. An update builds a new row instead of changing the old one, so a reader can never see a half-updated row, and the undo log can simply keep the old one.
enum Type { INT, TEXT }
record Column(String name, Type type)
record Schema(List<Column> columns,
String primaryKey) {
Object coerce(String col, Object v)
} // INT -> Long, wrong type: throws
record Row(Map<String, Object> values)
// unmodifiable copy: updates build
// a new Row, never mutate one WHERE conditions
A where clause is a list of conditions, all joined by AND. Each condition is plain data: a column, an operator and a value, with a matches method. One comparator orders longs against longs and strings against strings, and the operator turns its result into true or false. Keeping conditions as data rather than lambdas is what lets the planner look inside them and decide whether an index can help.
enum Op { EQ, NE, LT, LE, GT, GE;
boolean test(Object l, Object r) {
int c = VALUES.compare(l, r);
return switch (this) {
case EQ -> c == 0; ...
};
}
}
record Condition(String column, Op op,
Object value)
where = List<Condition>, all AND-ed Primary key
Rows are stored in a sorted map from primary key to row, like a clustered index in a real database. A lookup by key is logarithmic, a full scan walks rows in key order, and a duplicate key check is one contains-key call. A hash map would make key lookups constant time, and that is a fine answer too; the sorted map also gives key ranges and stable output, which makes tests predictable.
TreeMap<Object, Row> rows
= new TreeMap<>(VALUES)
PK equality: rows.get(4), O(log n)
full scan: rows.values(), in PK order
duplicate: rows.containsKey(pk)
a HashMap gives O(1) lookups, but
a TreeMap also gives PK ranges
and stable output order Secondary index
A secondary index maps each column value to the set of primary keys that have it. It is a sorted map too, so equality is one lookup and a range like salary at least a hundred is a tail map. Creating an index backfills it from the existing rows. An index cannot usefully serve not-equals, which matches most of the table anyway. The cost is that every write must now update every index, which is why the table funnels all writes through two methods.
TreeMap<Object, Set<Object>> entries
dept: data -> {3}
design -> {2}
eng -> {1, 4, 5}
salary >= 100:
tailMap(100, true) -> {1, 4}
createIndex: backfill from rows
cannot serve != (most of the table) Strategy: query plan
The planner is a Strategy chooser. Each access path is a small class with two methods: find candidate rows, and explain itself. The rules, in order: an equality on the primary key wins, then an equality on an indexed column, then a range on an indexed column, and otherwise a full scan. Whatever path is chosen, the executor then checks every condition on each candidate. That residual filter keeps the paths simple and the results always correct.
interface AccessPath {
Collection<Row> candidates(Table t);
String explain();
}
1. PK = v -> PkLookup
2. indexed col = v -> IndexScan
3. indexed col < v -> IndexScan
4. otherwise -> FullScan
then: residual filter, ALL conditions Flow: select
Follow a select. Take the read lock and normalise the condition values to the column types, so the number one hundred compares as a long. The query is salary under a hundred and department equals engineering. The planner prefers the equality, so the department index returns three keys. The residual filter checks both conditions on those three rows and keeps one, the tester. Explain shows exactly that plan, which is how you would prove an index is used.
read lock
where = normalise types
path = plan(where)
for (Row r : path.candidates(this))
if (all conditions match r) keep r
unlock
[salary < 100, dept = eng]
-> index lookup dept = eng
-> [Tester] Flow: update
Updates. First type-check every value being set, before touching any row, so a bad value cannot leave a statement half applied. Then select the matching rows with the same planner, build a new row for each, and call put. Put is one of only two write methods: it swaps the row and moves its key from the old value's index entry to the new one. Moving the tester to platform takes it out of the engineering entry and into platform, and the demo checks both.
void put(Row r) {
old = rows.put(pk, r)
for (Index ix : indexes.values()) {
if (old != null) ix.remove(old, pk)
ix.add(r, pk)
}
}
void drop(Object pk) // mirror image
update: coerce SET values first,
so no row changes if one is bad Transactions
Transactions use an undo log, the Command pattern in reverse. Every change records its inverse: an insert records drop this key, and an update or a delete records put the old row back, which is trivial because rows are immutable. Rollback runs the log newest first; commit just clears it. Single statements run as tiny transactions too, so each one is atomic. In the demo, a transaction deletes two rows, inserts one and rewrites every salary, then rolls back to exactly where it started.
insert row -> undo: drop(pk) update row -> undo: put(oldRow) delete row -> undo: put(oldRow) rollback(): run undo newest first commit(): clear the log single statements: autoCommit, so each one is atomic too begin() holds the write lock
Concurrency
Concurrency. Unlike a cache, where every get reorders entries, a select here really is read-only, so a read-write lock pays off: many selects run together. A write, or a whole transaction, holds the write lock from begin to commit, so readers never see uncommitted rows. That is serializable isolation in the simplest possible form. The demo proves it: a writer commits five hundred transactions of two rows each, and four readers never once count an odd number.
- select: read lock, many at once
- write or transaction: write lock
- held from begin() to commit()
- readers never see uncommitted
- rows: serializable, simply
- cost: one writer at a time
- demo: 500 transactions insert
- pairs; 4 readers never see an
- odd count
Extensibility
Extensions plug into one layer each. SQL text becomes a tokenizer and parser that produce the same condition objects, the Interpreter pattern. OR and NOT turn the condition list into a tree, the Composite pattern. A cost-based planner keeps counts per index value and picks the most selective one. Joins start as nested loops, then hash joins. Multi-version rows let readers skip the lock entirely, and a write-ahead log makes it durable.
- SQL text: tokenizer + parser
- to the same Condition objects
- (Interpreter pattern)
- OR and NOT: a condition tree
- (Composite pattern)
- cost-based planner: index stats
- joins: nested loop, then hash
- MVCC: versioned rows, readers
- never block writers
- durability: write-ahead log
Testing
The full code is below the player. The demo creates an employees table with roles, departments and salaries, indexes department and salary, and runs five queries, printing each plan and result: a key lookup, an index lookup, an index range, a full scan, and an index lookup with a residual filter. It rejects a duplicate key and a wrong type, rolls back a messy transaction, and runs the concurrent isolation test. Test the plan as well as the answer.
[id = 4] -> PK lookup -> [Manager] [dept = eng] -> index lookup -> [Engineer, Manager, Tester] [salary >= 100] -> index range [role = Analyst] -> full scan Rejected: duplicate primary key 1 Rejected: salary must be INT After rollback: 5 rows, salary 150 Concurrent: 500 transactions, 1000 bulk rows, torn reads: 0
Follow-ups
Expect follow-ups. Two indexes match: which wins? The most selective, which needs statistics. An index on a column with three distinct values is often slower than a scan. A composite index on department then salary uses a list of values as its sorted key, and serves queries on its leading column. On disk the sorted map becomes a B-plus tree of pages. And to stop readers and writers blocking each other, keep row versions and give readers snapshots.
- two indexes match: which one?
- the most selective (stats)
- index on a low-cardinality col?
- often worse than a scan
- composite index (dept, salary)?
- key = list of values, sorted
- big tables: B+ tree pages
- readers block the writer?
- MVCC snapshots
- unique index: reject on add
Say it like this
The short version. Rows are immutable and live in a sorted map by primary key. Secondary indexes map a value to its set of keys, sorted so ranges work. Every write goes through two methods that keep all indexes in step. A rule-based planner picks a key lookup, an index or a scan, and a residual filter guarantees correctness. Transactions keep an undo log, and a read-write lock lets selects run together.
- "Rows are immutable, in a sorted
- map by key. Indexes map value to
- key sets, sorted for ranges. All
- writes go through put and drop,
- which update every index. A rule
- planner picks key, index or scan,
- then filters. Undo log for
- transactions, RW lock for reads."