LOW LEVEL DESIGN · MACHINE CODING · HARD · 18 OF 42

Design an In-Memory Database with Indexes and a Query Planner in Java

A tiny SQL-like database designed and coded: typed schemas with a primary key, immutable rows, insert, select, update and delete with AND-ed WHERE conditions, rows ordered by key, sorted secondary indexes for equality and ranges, a rule-based planner with explain(), residual filters, transactions with an undo log, a read-write lock for isolation and the follow-ups, with full Java 17 code.

Patterns usedCompositeInterpreterStrategyCommand

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
  42. 42
1 / 18

Press play to hear the narration, or step through at your own pace. The full Java code is below.

Full Java solution

One file, Java 17, 490 lines, with a small main() demo. Save it as InMemoryDatabase.java, then run javac InMemoryDatabase.java && java InMemoryDatabase.

import java.util.ArrayList;
import java.util.Collection;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.NavigableMap;
import java.util.Set;
import java.util.TreeMap;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.locks.ReentrantReadWriteLock;

/**
 * A tiny in-memory SQL-like database: typed tables with a primary key, secondary indexes, insert, select,
 * update and delete with simple AND-ed WHERE conditions, a rule-based query planner with explain(),
 * and transactions that roll back through an undo log.
 */
public final class InMemoryDatabase {

    // ---------- schema ----------
    enum Type { INT, TEXT }

    record Column(String name, Type type) {}

    record Schema(List<Column> columns, String primaryKey) {
        Schema {
            columns = List.copyOf(columns);
            if (columns.stream().noneMatch(c -> c.name().equals(primaryKey)))
                throw new IllegalArgumentException("primary key " + primaryKey + " is not a column");
        }

        Column column(String name) {
            for (Column c : columns) if (c.name().equals(name)) return c;
            throw new IllegalArgumentException("no column " + name);
        }

        /** Type-checks one value and normalises ints to Long so comparisons are uniform. */
        Object coerce(String name, Object v) {
            Column c = column(name);
            if (v == null) throw new IllegalArgumentException(name + " cannot be null");
            return switch (c.type()) {
                case INT -> {
                    if (v instanceof Integer i) yield (long) i;
                    if (v instanceof Long l) yield l;
                    throw new IllegalArgumentException(name + " must be INT, got " + v);
                }
                case TEXT -> {
                    if (v instanceof String s) yield s;
                    throw new IllegalArgumentException(name + " must be TEXT, got " + v);
                }
            };
        }
    }

    /** Values are Long or String; one comparator orders both (only like with like is ever compared). */
    static final Comparator<Object> VALUES = (a, b) -> {
        if (a instanceof Long x && b instanceof Long y) return Long.compare(x, y);
        if (a instanceof String x && b instanceof String y) return x.compareTo(y);
        throw new IllegalArgumentException("cannot compare " + a + " with " + b);
    };

    /** An immutable row. Updates build a new Row, so readers never see a half-changed one. */
    record Row(Map<String, Object> values) {
        Row {
            values = java.util.Collections.unmodifiableMap(new LinkedHashMap<>(values));
        }

        Object get(String column) { return values.get(column); }

        @Override
        public String toString() { return values.toString(); }
    }

    // ---------- WHERE ----------
    enum Op {
        EQ("="), NE("!="), LT("<"), LE("<="), GT(">"), GE(">=");

        final String symbol;

        Op(String symbol) { this.symbol = symbol; }

        boolean test(Object left, Object right) {
            int c = VALUES.compare(left, right);
            return switch (this) {
                case EQ -> c == 0;
                case NE -> c != 0;
                case LT -> c < 0;
                case LE -> c <= 0;
                case GT -> c > 0;
                case GE -> c >= 0;
            };
        }
    }

    record Condition(String column, Op op, Object value) {
        boolean matches(Row r) { return op.test(r.get(column), value); }

        @Override
        public String toString() { return column + " " + op.symbol + " " + value; }
    }

    static Condition where(String column, Op op, Object value) { return new Condition(column, op, value); }

    // ---------- secondary index: value -> primary keys, sorted so ranges work ----------
    static final class Index {
        final String column;
        private final TreeMap<Object, Set<Object>> entries = new TreeMap<>(VALUES);

        Index(String column) { this.column = column; }

        void add(Row r, Object pk) {
            entries.computeIfAbsent(r.get(column), v -> new LinkedHashSet<>()).add(pk);
        }

        void remove(Row r, Object pk) {
            Set<Object> pks = entries.get(r.get(column));
            if (pks == null) return;
            pks.remove(pk);
            if (pks.isEmpty()) entries.remove(r.get(column));
        }

        boolean supports(Op op) { return op != Op.NE; }

        Collection<Object> lookup(Op op, Object v) {
            NavigableMap<Object, Set<Object>> range = switch (op) {
                case EQ -> entries.subMap(v, true, v, true);
                case LT -> entries.headMap(v, false);
                case LE -> entries.headMap(v, true);
                case GT -> entries.tailMap(v, false);
                case GE -> entries.tailMap(v, true);
                case NE -> throw new IllegalArgumentException("an index cannot serve !=");
            };
            List<Object> out = new ArrayList<>();
            range.values().forEach(out::addAll);
            return out;
        }
    }

    // ---------- query plans: how to find candidate rows ----------
    /** Strategy: each access path finds candidates; the executor re-checks every condition on them. */
    interface AccessPath {
        Collection<Row> candidates(Table t);

        String explain();
    }

    record PkLookup(Condition c) implements AccessPath {
        public Collection<Row> candidates(Table t) {
            Row r = t.rows.get(c.value());
            return r == null ? List.of() : List.of(r);
        }

        public String explain() { return "PK lookup " + c; }
    }

    record IndexScan(Condition c) implements AccessPath {
        public Collection<Row> candidates(Table t) {
            List<Row> out = new ArrayList<>();
            for (Object pk : t.indexes.get(c.column()).lookup(c.op(), c.value())) out.add(t.rows.get(pk));
            return out;
        }

        public String explain() { return (c.op() == Op.EQ ? "index lookup " : "index range ") + c; }
    }

    record FullScan(String table) implements AccessPath {
        public Collection<Row> candidates(Table t) { return t.rows.values(); }

        public String explain() { return "full scan of " + table; }
    }

    // ---------- a table: rows by primary key plus its indexes ----------
    static final class Table {
        final String name;
        final Schema schema;
        final TreeMap<Object, Row> rows = new TreeMap<>(VALUES); // ordered by PK, like a clustered index
        final Map<String, Index> indexes = new HashMap<>();

        Table(String name, Schema schema) {
            this.name = name;
            this.schema = schema;
        }

        /** Rule-based planner: PK equality, then an indexed equality, then an indexed range, else scan. */
        AccessPath plan(List<Condition> where) {
            for (Condition c : where)
                if (c.column().equals(schema.primaryKey()) && c.op() == Op.EQ) return new PkLookup(c);
            for (Condition c : where)
                if (c.op() == Op.EQ && indexes.containsKey(c.column())) return new IndexScan(c);
            for (Condition c : where) {
                Index ix = indexes.get(c.column());
                if (ix != null && ix.supports(c.op())) return new IndexScan(c);
            }
            return new FullScan(name);
        }

        List<Row> select(List<Condition> where) {
            List<Row> out = new ArrayList<>();
            for (Row r : plan(where).candidates(this))
                if (where.stream().allMatch(c -> c.matches(r))) out.add(r); // residual filter
            return out;
        }

        // The only two mutations; both keep every index in step with the rows.
        void put(Row r) {
            Object pk = r.get(schema.primaryKey());
            Row 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) {
            Row old = rows.remove(pk);
            if (old != null) for (Index ix : indexes.values()) ix.remove(old, pk);
        }
    }

    // ---------- the database ----------
    private final Map<String, Table> tables = new HashMap<>();
    // Reads really are read-only here, so a read-write lock lets many selects run together.
    private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();

    void createTable(String name, Schema schema) {
        lock.writeLock().lock();
        try {
            if (tables.putIfAbsent(name, new Table(name, schema)) != null)
                throw new IllegalArgumentException("table " + name + " exists");
        } finally {
            lock.writeLock().unlock();
        }
    }

    void createIndex(String table, String column) {
        lock.writeLock().lock();
        try {
            Table t = table(table);
            t.schema.column(column);
            Index ix = new Index(column);
            t.rows.forEach((pk, r) -> ix.add(r, pk)); // backfill existing rows
            t.indexes.put(column, ix);
        } finally {
            lock.writeLock().unlock();
        }
    }

    List<Row> select(String table, Condition... where) {
        lock.readLock().lock();
        try {
            return table(table).select(normalise(table(table), List.of(where)));
        } finally {
            lock.readLock().unlock();
        }
    }

    String explain(String table, Condition... where) {
        lock.readLock().lock();
        try {
            return table(table).plan(normalise(table(table), List.of(where))).explain();
        } finally {
            lock.readLock().unlock();
        }
    }

    void insert(String table, Map<String, Object> values) { autoCommit(tx -> tx.insert(table, values)); }

    int update(String table, Map<String, Object> set, Condition... where) {
        int[] n = new int[1];
        autoCommit(tx -> n[0] = tx.update(table, set, where));
        return n[0];
    }

    int delete(String table, Condition... where) {
        int[] n = new int[1];
        autoCommit(tx -> n[0] = tx.delete(table, where));
        return n[0];
    }

    /** One statement outside a transaction is its own transaction: all of it applies, or none. */
    private void autoCommit(java.util.function.Consumer<Transaction> work) {
        Transaction tx = begin();
        try {
            work.accept(tx);
            tx.commit();
        } catch (RuntimeException e) {
            tx.rollback();
            throw e;
        }
    }

    /** Starts a transaction on this thread. It holds the write lock until commit or rollback. */
    Transaction begin() {
        lock.writeLock().lock();
        return new Transaction();
    }

    /** Command + undo log: every change records its inverse; rollback replays them newest first. */
    final class Transaction {
        private final List<Runnable> undo = new ArrayList<>();
        private boolean done;

        void insert(String table, Map<String, Object> values) {
            Table t = open(table);
            Map<String, Object> clean = new LinkedHashMap<>();
            for (Column c : t.schema.columns())
                clean.put(c.name(), t.schema.coerce(c.name(), values.get(c.name())));
            Row r = new Row(clean);
            Object pk = r.get(t.schema.primaryKey());
            if (t.rows.containsKey(pk)) throw new IllegalArgumentException("duplicate primary key " + pk);
            t.put(r);
            undo.add(() -> t.drop(pk));
        }

        int update(String table, Map<String, Object> set, Condition... where) {
            Table t = open(table);
            if (set.containsKey(t.schema.primaryKey()))
                throw new IllegalArgumentException("cannot update the PK");
            Map<String, Object> clean = new LinkedHashMap<>();
            set.forEach((k, v) -> clean.put(k, t.schema.coerce(k, v))); // validate before touching any row
            List<Row> hits = t.select(normalise(t, List.of(where)));
            for (Row old : hits) {
                Map<String, Object> next = new LinkedHashMap<>(old.values());
                next.putAll(clean);
                t.put(new Row(next));
                undo.add(() -> t.put(old));
            }
            return hits.size();
        }

        int delete(String table, Condition... where) {
            Table t = open(table);
            List<Row> hits = t.select(normalise(t, List.of(where)));
            for (Row old : hits) {
                t.drop(old.get(t.schema.primaryKey()));
                undo.add(() -> t.put(old));
            }
            return hits.size();
        }

        void commit() {
            finish();
            undo.clear();
        }

        void rollback() {
            if (done) return;
            for (int i = undo.size() - 1; i >= 0; i--) undo.get(i).run();
            finish();
        }

        private Table open(String table) {
            if (done) throw new IllegalStateException("transaction finished");
            return table(table);
        }

        private void finish() {
            if (done) throw new IllegalStateException("transaction finished");
            done = true;
            lock.writeLock().unlock();
        }
    }

    private Table table(String name) {
        Table t = tables.get(name);
        if (t == null) throw new IllegalArgumentException("no table " + name);
        return t;
    }

    private static List<Condition> normalise(Table t, List<Condition> where) {
        List<Condition> out = new ArrayList<>();
        for (Condition c : where)
            out.add(new Condition(c.column(), c.op(), t.schema.coerce(c.column(), c.value())));
        return out;
    }

    // ---------- demo ----------
    static Map<String, Object> row(Object... kv) {
        Map<String, Object> m = new LinkedHashMap<>();
        for (int i = 0; i < kv.length; i += 2) m.put((String) kv[i], kv[i + 1]);
        return m;
    }

    static void check(boolean ok, String what) { if (!ok) throw new AssertionError(what); }

    static String roles(List<Row> rows) {
        return rows.stream().map(r -> (String) r.get("role")).toList().toString();
    }

    public static void main(String[] args) throws InterruptedException {
        InMemoryDatabase db = new InMemoryDatabase();
        List<Column> cols = List.of(new Column("id", Type.INT), new Column("role", Type.TEXT),
                new Column("dept", Type.TEXT), new Column("salary", Type.INT));
        db.createTable("employees", new Schema(cols, "id"));
        db.insert("employees", row("id", 1, "role", "Engineer", "dept", "eng", "salary", 120));
        db.insert("employees", row("id", 2, "role", "Designer", "dept", "design", "salary", 95));
        db.insert("employees", row("id", 3, "role", "Analyst", "dept", "data", "salary", 90));
        db.insert("employees", row("id", 4, "role", "Manager", "dept", "eng", "salary", 150));
        db.insert("employees", row("id", 5, "role", "Tester", "dept", "eng", "salary", 80));
        db.createIndex("employees", "dept");
        db.createIndex("employees", "salary");

        Condition[][] queries = {
            {where("id", Op.EQ, 4)},
            {where("dept", Op.EQ, "eng")},
            {where("salary", Op.GE, 100)},
            {where("role", Op.EQ, "Analyst")},
            {where("salary", Op.LT, 100), where("dept", Op.EQ, "eng")},
        };
        for (Condition[] q : queries)
            System.out.println(List.of(q) + " -> " + db.explain("employees", q) + " -> "
                    + roles(db.select("employees", q)));
        check(roles(db.select("employees", where("salary", Op.LT, 100), where("dept", Op.EQ, "eng")))
                .equals("[Tester]"), "residual filter");

        int moved = db.update("employees", row("dept", "platform"), where("id", Op.EQ, 5));
        System.out.println("Moved " + moved + " to platform; eng now " + roles(db.select("employees",
                where("dept", Op.EQ, "eng"))) + ", platform " + roles(db.select("employees",
                where("dept", Op.EQ, "platform"))));
        check(db.select("employees", where("dept", Op.EQ, "eng")).size() == 2, "index follows the update");

        for (Map<String, Object> bad : List.of(row("id", 1, "role", "Intern", "dept", "eng", "salary", 50),
                row("id", 9, "role", "Intern", "dept", "eng", "salary", "fifty"))) {
            try {
                db.insert("employees", bad);
                throw new AssertionError("should reject " + bad);
            } catch (IllegalArgumentException e) {
                System.out.println("Rejected: " + e.getMessage());
            }
        }

        Transaction tx = db.begin();
        tx.delete("employees", where("dept", Op.EQ, "eng"));
        tx.insert("employees", row("id", 6, "role", "Intern", "dept", "eng", "salary", 40));
        tx.update("employees", row("salary", 1), where("salary", Op.GT, 0));
        tx.rollback();
        List<Row> all = db.select("employees");
        System.out.println("After rollback: " + all.size() + " rows, eng " + roles(db.select("employees",
                where("dept", Op.EQ, "eng"))) + ", salary of 4 = " + db.select("employees",
                where("id", Op.EQ, 4)).get(0).get("salary"));
        check(all.size() == 5 && db.select("employees", where("salary", Op.EQ, 1)).isEmpty(), "rollback");

        tx = db.begin();
        tx.insert("employees", row("id", 6, "role", "Intern", "dept", "eng", "salary", 40));
        tx.commit();
        System.out.println("After commit: " + db.select("employees").size() + " rows");

        // Readers never see half a transaction: each writer transaction inserts two "bulk" rows at once.
        AtomicBoolean writing = new AtomicBoolean(true);
        AtomicInteger reads = new AtomicInteger(), torn = new AtomicInteger();
        ExecutorService pool = Executors.newFixedThreadPool(5);
        CountDownLatch done = new CountDownLatch(5);
        pool.submit(() -> {
            try {
                for (int i = 0; i < 500; i++) {
                    Transaction w = db.begin();
                    w.insert("employees", row("id", 1000 + 2 * i, "role", "Contractor", "dept", "bulk",
                            "salary", i));
                    w.insert("employees", row("id", 1001 + 2 * i, "role", "Contractor", "dept", "bulk",
                            "salary", i));
                    w.commit();
                }
            } finally {
                writing.set(false);
                done.countDown();
            }
        });
        for (int r = 0; r < 4; r++) {
            pool.submit(() -> {
                while (writing.get()) {
                    int n = db.select("employees", where("dept", Op.EQ, "bulk")).size();
                    if (n % 2 != 0) torn.incrementAndGet(); // saw one row of a pair: isolation broken
                    reads.incrementAndGet();
                }
                done.countDown();
            });
        }
        done.await();
        pool.shutdown();
        int bulk = db.select("employees", where("dept", Op.EQ, "bulk")).size();
        System.out.println("Concurrent: 500 transactions, " + bulk + " bulk rows, torn reads: " + torn.get());
        check(bulk == 1000 && torn.get() == 0, "isolation");
    }
}

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.

Requirements
  • 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
Clarify first
  • 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.

Schema and Row
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.

Condition
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.

Storage
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.

Index on dept / salary
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.

Rule-based planner
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.

select(table, where...)
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.

One write path
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.

Undo log
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.

Isolation
  • 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.

Extension points
  • 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.

Run it
[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.

Follow-ups to expect
  • 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.

In the interview
  • "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."

Interview questions

How do you store rows and look them up by primary key?

A map from primary key to an immutable row. A HashMap gives O(1) key lookups; a TreeMap gives O(log n) plus key ranges and ordered scans, like a clustered index. Duplicate keys are rejected with a containsKey check before inserting.

How does a secondary index work?

It maps each column value to the set of primary keys holding it. Using a sorted map lets it serve equality with one lookup and ranges with headMap or tailMap. Every insert, update and delete must update every index, so all writes go through one put and one drop method.

How does your query planner choose a plan?

Rule-based: an equality on the primary key first, then an equality on an indexed column, then a range on an indexed column, otherwise a full scan. Whichever path is chosen, every condition is re-checked on the candidates, so the plan affects speed, never the answer.

When is an index worse than a full scan?

When the condition matches a large fraction of the table, such as a column with few distinct values or a not-equals condition. Following many index entries back to rows costs more than reading rows in order. A cost-based planner uses statistics to decide.

How do you implement transactions?

An undo log: each change records its inverse, drop the key for an insert, put the old row back for an update or delete. Rollback replays the log newest first; commit clears it. Immutable rows make the old version free to keep.

How do you keep readers from seeing uncommitted changes?

A read-write lock: selects share the read lock, and a transaction holds the write lock from begin to commit or rollback. It is serializable but allows only one writer; multi-version concurrency control removes the blocking by giving readers snapshots.

Why is a read-write lock useful here but not in an LRU cache?

Here a select changes nothing, so many readers can safely share the lock. In an LRU cache every get reorders entries, so reads also mutate state and need exclusive access.

How would you add SQL parsing and OR conditions?

A tokenizer and recursive-descent parser produce the same Condition objects, which is the Interpreter pattern. OR and NOT turn the flat AND list into a tree of conditions, the Composite pattern; the planner can then only use an index for branches that are AND-ed at the top.