query-plan-estimator

A SQL query plan cost estimator written in C++20 — the optimizer half of a database engine, without the storage engine underneath it.

Feed it a SELECT statement and a JSON catalogue describing the physical layout of a database (row counts, block counts, indexes, buffer size) and it will:

Tokenize and parse the query into an AST,
Bind every identifier against the schema and type-check the WHERE clause,
Enumerate every physically meaningful execution plan via dynamic programming over subsets of the FROM tables,
Cost each plan in block transfers,
Print the cheapest plan as an ASCII tree, followed by the ranked alternatives.

No data is ever read or joined — only estimated. The cost unit throughout is one disk block transfer.

sql> SELECT ime FROM student, ispit WHERE indeks = studentindeks AND ocena > 8;

chosen plan (cost=2740):
                 Projection
                (Student.ime)
             rows=4000 cost=2740
                      |
                  HashJoin
   (Student.indeks = Ispit.studentindeks)
             rows=4000 cost=2740
                     / \
                    /   \
                   /     \
                  /       \
                 /         \
                /           \
               /             \
              /               \
             /                 \
            /                   \
           |                     \
    SeqScan Student    Materialize blocks=400
  rows=1000 cost=100     rows=4000 cost=1200
                                  |
                          Filter (sel=0.5)
                         rows=4000 cost=800
                                  |
                            SeqScan Ispit
                         rows=8000 cost=800

other candidates considered:
  cost=3300  (Student ⋈ MJ Ispit)
  cost=6500  (Student ⋈ BNLJ Ispit)
  cost=6600  (Ispit ⋈ BNLJ Student)
  cost=11100  (Student ⋈ INLJ Ispit)
  cost=14000  (Ispit ⋈ INLJ Student)
  cost=401300  (Student ⋈ NLJ Ispit)
  cost=401600  (Ispit ⋈ NLJ Student)

Quick start

cmake -S . -B build
cmake --build build
./build/query-plan-estimator        # run from the project root

Then in the menu: 1 → students → type a query ending with ;.

SELECT ime FROM student, ispit WHERE indeks = studentindeks AND ocena > 8;

Run from the project root. Schemas are located via the relative path schemas/. If the schema list comes back empty, the working directory is wrong. See RUN.md for IDE-specific setup (CLion, Visual Studio).

Architecture

Every stage is a class with a single public entry point. QueryCompiler owns one instance of each and drives them in sequence; Session owns a QueryCompiler plus the loaded Schema and runs the read–compile–display loop.

flowchart TD
    subgraph app["Application layer (query-plan-estimator)"]
        main["main.cpp<br/>console setup"]
        Menu["Menu<br/>schema discovery + selection"]
        Session["Session<br/>REPL loop"]
        IOHandler["IOHandler<br/>stdin / stdout"]
    end

    subgraph core["Core library (qpe_core)"]
        QueryCompiler["QueryCompiler<br/>orchestrator"]
        Lexer["Lexer"]
        Parser["Parser"]
        Binder["Binder"]
        Estimator["Estimator"]
        PlanPrinter["PlanPrinter"]
    end

    subgraph data["Data model"]
        Schema["Schema<br/>Table / Column / Index"]
        AST["ASTNode hierarchy"]
        PlanNode["PlanNode hierarchy"]
    end

    main --> Menu
    Menu --> Session
    Menu --> IOHandler
    Session --> IOHandler
    Session --> QueryCompiler
    Session --> Schema

    QueryCompiler --> Lexer
    QueryCompiler --> Parser
    QueryCompiler --> Binder
    QueryCompiler --> Estimator

    Parser --> AST
    Binder --> AST
    Binder --> Schema
    Estimator --> AST
    Estimator --> Schema
    Estimator --> PlanNode
    IOHandler --> PlanPrinter
    PlanPrinter --> PlanNode

The split matters for testing: qpe_core is a static library with no I/O and no main, so tests/tests.cpp links it directly and compiles queries in-process.

The compilation pipeline

flowchart LR
    A["raw SQL<br/>std::string"] --> B["Lexer"]
    B --> C["vector&lt;Token&gt;"]
    C --> D["Parser"]
    D --> E["SelectStmtAST"]
    E --> F["Binder"]
    F --> G["bound AST<br/>SELECT * expanded<br/>types checked"]
    G --> H["Estimator"]
    H --> I["vector&lt;PlanNode&gt;<br/>all candidates"]
    I --> J["QueryCompiler<br/>pick argmin cost"]
    J --> K["CompileResult<br/>plans + best index"]
    K --> L["IOHandler + PlanPrinter<br/>ASCII tree"]

A whole query run, end to end:

sequenceDiagram
    participant U as User
    participant M as Menu
    participant S as Session
    participant QC as QueryCompiler
    participant L as Lexer
    participant P as Parser
    participant B as Binder
    participant E as Estimator
    participant IO as IOHandler

    U->>M: "1" then schema name
    M->>M: resolveSchema(name)
    M->>S: Session(path)
    S->>S: Schema loads JSON catalogue
    loop until "exit"
        U->>IO: SQL text, terminated by a semicolon
        IO->>S: query string
        S->>QC: compile(query, schema)
        QC->>L: tokenize(query)
        L-->>QC: tokens
        QC->>P: parse(tokens)
        P-->>QC: SelectStmtAST
        QC->>B: bind(stmt, schema)
        B-->>QC: bound AST
        QC->>E: makePlans(stmt, schema)
        E-->>QC: candidate plans
        QC-->>S: CompileResult{plans, best}
        S->>IO: printPlans(result)
        IO-->>U: ASCII plan tree + ranked alternatives
    end

1 — Lexer

include/Lexer.hpp · src/lexer.cpp

A single left-to-right scan producing a flat std::vector<Token> terminated by END.

Token	Produced from
`KW_SELECT` `KW_FROM` `KW_WHERE` `KW_ORDER` `KW_BY` `KW_AND`	keywords, case-insensitive
`IDENTIFIER`	`[A-Za-z_][A-Za-z0-9_]`, lowercased*
`NUMBER`	digits with at most one interior `.`
`STRING`	`'…'`, single-quoted
`COMPARATOR`	`=` `<` `>` `<=` `>=` `<>`
`DOT` `COMMA` `STAR`	`.` `,` `*`
`END`	end of input

Every token carries its byte offset, so errors point at a position. Identifiers are lowercased here and schema names are lowercased at load time, which is what makes Student, student and STUDENT interchangeable.

An unterminated string or an unexpected character raises LexicalError.

2 — Parser

include/Parser.hpp · src/parser.cpp

A recursive-descent parser over the token vector, with one-token lookahead (peek), optional consumption (match) and mandatory consumption (expect). The grammar it accepts:

select      ::= "SELECT" ( "*" | column_list )
                "FROM" table_list
                [ "WHERE" condition { "AND" condition } ]
                [ "ORDER" "BY" column_ref ]
                END

column_list ::= column_ref { "," column_ref }
table_list  ::= identifier { "," identifier }          (* at most 4 *)
condition   ::= column_ref comparator value            (* at most 6 *)
value       ::= number | string | column_ref
column_ref  ::= identifier [ "." identifier ]
comparator  ::= "=" | "<" | ">" | "<=" | ">=" | "<>"

Project-imposed limits are enforced right here and surface as ParseError: ≤ 4 tables, ≤ 6 conjuncts in WHERE, ≤ 1 attribute in ORDER BY. WHERE is left-associative, so a AND b AND c becomes AND(AND(a, b), c).

The AST it produces:

classDiagram
    class ASTNode {
        <<abstract>>
        +print(out, indent)*
    }
    class ExprAST {
        <<abstract>>
    }
    class SelectStmtAST {
        -columns : vector~ColumnExprAST~
        -tables : vector~string~
        -where : ExprAST
        -orderBy : vector~ColumnExprAST~
        -selectAll : bool
        +setColumns()
    }
    class ColumnExprAST {
        -table : string
        -column : string
        +boundTable : Table*
        +boundColumn : Column*
    }
    class NumberExprAST {
        -value : double
    }
    class StringExprAST {
        -value : string
    }
    class BinaryExprAST {
        -op : string
        -lhs : ExprAST
        -rhs : ExprAST
    }

    ASTNode <|-- ExprAST
    ASTNode <|-- SelectStmtAST
    ExprAST <|-- ColumnExprAST
    ExprAST <|-- NumberExprAST
    ExprAST <|-- StringExprAST
    ExprAST <|-- BinaryExprAST
    SelectStmtAST *-- ColumnExprAST
    SelectStmtAST *-- ExprAST
    BinaryExprAST *-- ExprAST

Ownership is unique_ptr throughout — the AST is a tree, never shared.

3 — Binder

include/Binder.hpp · src/binder.cpp

The semantic pass. It mutates the AST in place rather than producing a new one: each ColumnExprAST gets its boundTable and boundColumn pointers filled in, and everything downstream dereferences those instead of re-resolving names.

flowchart TD
    A["bind(stmt, schema)"] --> B["resolve every FROM table"]
    B --> C{"duplicate table?"}
    C -->|yes| ERR1["SemanticError<br/>duplicate table in FROM"]
    C -->|no| D{"SELECT * ?"}
    D -->|yes| E["expand to every column<br/>of every FROM table"]
    D -->|no| F["keep listed columns"]
    E --> G["bind each SELECT column"]
    F --> G
    G --> H["bind WHERE expression tree"]
    H --> I["bind ORDER BY column"]

    G -.-> R["bindColumn"]
    H -.-> R
    I -.-> R

    R --> S{"qualified<br/>t.c ?"}
    S -->|yes| T["table must be in FROM<br/>column must exist in it"]
    S -->|no| U["search all FROM tables"]
    U --> V{"matches found"}
    V -->|0| ERR2["SemanticError<br/>unknown column"]
    V -->|2+| ERR3["SemanticError<br/>ambiguous column"]
    V -->|1| W["bind it"]

    H --> X["checkComparable<br/>on each non-AND node"]
    X --> Y{"numeric vs text<br/>family match?"}
    Y -->|no| ERR4["SemanticError<br/>type mismatch"]
    Y -->|yes| Z["ok"]

Type checking collapses the four column types into two families — INT/DOUBLE are numeric, STRING/DATE are text — and rejects any comparison across families. SELECT * is expanded here, not in the parser, because expansion needs the schema.

4 — Estimator

include/Estimator.hpp · src/estimator.cpp

The heart of the project. Given a bound AST it returns every candidate plan for the query, each carrying its own cost and outRows. See the cost model and join order search below.

Before any plan is built, the WHERE tree is flattened into a list of conjuncts and each conjunct is classified:

flowchart LR
    W["WHERE tree"] --> F["collectConjuncts<br/>flatten the AND spine"]
    F --> C{"both sides are columns<br/>from different tables?"}
    C -->|yes| J["cross predicate<br/>-> a join condition"]
    C -->|no| L["local predicate<br/>-> filter / index lookup<br/>on one table"]

5 — Plan printer

include/PlanPrinter.hpp · src/planPrinter.cpp

A small recursive layout engine that renders a plan as an ASCII tree. Each node becomes a Block — a list of text lines plus an anchor column where its parent's connector attaches. Leaves anchor at their own centre; a unary parent keeps its child's anchor and drops a |; a binary parent places the right subtree past the left one, anchors itself at the midpoint and draws / and \ diagonals out to each child's anchor, padding with | when one side is closer than the other. Trailing spaces are trimmed on output.

The cost model

Every cost is a count of block transfers. The buffer size M (in blocks) comes from the schema file; a floor of max(3, M) is applied where an algorithm structurally needs at least three frames.

Notation: b_r = blocks of the left/outer input, b_s = blocks of the right/inner input, n_r = rows of the outer input, V(A, r) = distinct values of attribute A in r.

Two helpers shape all the formulas:

readBlocks() — how many blocks it costs to re-scan an input. For a SeqScan this is the table's block count; for everything else it's the node's own output size.
inputCost() — a join adds its children's costs, except for a SeqScan child, whose block reads are already counted inside the join's own b_r/b_s terms. This is what stops base-table scans from being double-charged.

Selectivity

For a local predicate column ⊗ literal:

Predicate	Selectivity
`A = v`, `A` unique	`1 / n`
`A = v`, otherwise	`1 / V(A, r)`
`A <> v`	`1 − sel(A = v)`
`A < v`, `>`, `<=`, `>=`	`0.5` (flat fallback — no histograms)

Access paths

flowchart TD
    T["table in FROM"] --> S["SeqScan<br/>always available"]
    S --> SF["+ FilterNode for every<br/>unserved local conjunct"]

    T --> I{"for each index<br/>on the table"}
    I --> H{"HASH index?"}
    H -->|yes| HE{"equality conjunct<br/>on EVERY indexed attribute?"}
    HE -->|no| SKIP["index unusable — skip"]
    HE -->|yes| IS["IndexScan<br/>sel = product of served selectivities"]
    H -->|no, B+ tree| BE{"any conjunct except &lt;&gt;<br/>on the FIRST attribute?"}
    BE -->|no| SKIP
    BE -->|yes| IS
    IS --> IF["+ FilterNode for the<br/>conjuncts the index did NOT serve"]

Node	Rows out	Cost
`SeqScan`	`n`	`blockCount`
`IndexScan`, clustered	`n · sel`	`lookup + sel · blockCount`
`IndexScan`, unclustered	`n · sel`	`lookup + sel · n`

where lookup = 1 for a hash index and treeHeight for a B+-tree. Unclustered scans pay one block per matching row, which is exactly why a wide predicate is usually better served by a sequential scan.

A SeqScan or IndexScan over a clustered B+-tree records that its output is sorted on the index's leading attribute. That flag lets a downstream ORDER BY or merge join skip a sort entirely.

Join algorithms

classDiagram
    class PlanNode {
        <<abstract>>
        +outRows : double
        +cost : double
        +outRowsPerBlock : double
        +sortedOn : vector~string~
        +outBlocks() double
        +readBlocks() double
        +isSortedOn(key) bool
        +describe()* string
        +labelLines()* vector~string~
        +children() vector~PlanNode~
    }
    class SeqScanNode
    class IndexScanNode
    class FilterNode
    class ProjectionNode
    class SortNode
    class MaterializeNode
    class JoinNode {
        <<abstract>>
        #left : PlanNode
        #right : PlanNode
        #condition : string
    }
    class NestedLoopJoinNode
    class BlockNestedLoopJoinNode
    class IndexNestedLoopJoinNode
    class MergeJoinNode
    class HashJoinNode

    PlanNode <|-- SeqScanNode
    PlanNode <|-- IndexScanNode
    PlanNode <|-- FilterNode
    PlanNode <|-- ProjectionNode
    PlanNode <|-- SortNode
    PlanNode <|-- MaterializeNode
    PlanNode <|-- JoinNode
    JoinNode <|-- NestedLoopJoinNode
    JoinNode <|-- BlockNestedLoopJoinNode
    JoinNode <|-- IndexNestedLoopJoinNode
    JoinNode <|-- MergeJoinNode
    JoinNode <|-- HashJoinNode

Algorithm	I/O cost	Notes
Nested loop (`NLJ`)	`b_s ≤ M−2` → `b_r + b_s` otherwise `n_r · b_s + b_r`	one inner pass per outer row
Block nested loop (`BNLJ`)	`b_s ≤ M−2` → `b_r + b_s` otherwise `⌈b_r / (M−2)⌉ · b_s + b_r`	one inner pass per outer chunk
Index nested loop (`INLJ`)	`b_r + n_r · cost(IndexScan)`	requires a usable index on the inner join column; inner is always a single base table
Merge join (`MJ`)	`b_r + b_s`	each side is wrapped in a `SortNode` first unless already sorted on its key
Hash join (`HJ`)	see below	equijoin only

Hash join, with build = min(b_r, b_s) and M = max(3, bufferBlocks):

Case	Cost
`build ≤ M` — build side fits in memory	`b_r + b_s`
`⌈build / M⌉ ≤ M` — one partitioning pass	`3(b_r + b_s) + 4⌈build / M⌉`
otherwise — recursive partitioning	`2(b_r + b_s)·p + b_r + b_s`, `p = ⌈log_(M−1)(build / M)⌉`

All five join costs additionally include inputCost(left) + inputCost(right).

Output density is combined harmonically — 1/rowsPerBlock_out = 1/rowsPerBlock_left + 1/rowsPerBlock_right — modelling a joined row as the concatenation of one row from each side.

Sort, materialize, projection

Node	Cost	Notes
`Filter`	`cost(child)`	pipelined — no extra I/O, only `outRows` shrinks
`Projection`	`cost(child)`	pipelined; inherits sortedness
`Sort`	`cost(child) + 2 · p · B`	external merge sort, `B = outBlocks(child)`, `runs = ⌈B / M⌉`, `p = runs > 1 ? ⌈log_(M−1)(runs)⌉ : 0`
`Materialize`	`cost(child) + outBlocks()`	writing an intermediate result to disk

MaterializeNode is inserted automatically around any join input that is not a bare SeqScan — an intermediate result has to be written out before it can be re-read by the join. That write cost is exactly the missing term in the naïve "just add the children up" model, and it is why the printed trees show Materialize blocks=N above sub-joins.

Join cardinality

For a join with predicate set P, starting from |R| · |S|:

Predicate	Multiplier
`R.A = S.B`	`1 / max(V(A, R), V(B, S))`
`R.A <> S.B`	`1 − 1 / max(V(A, R), V(B, S))`
any other comparison	`0.5`

V comes from the catalogue (rowCount for a unique column, distinctValues otherwise), clamped to the number of rows actually flowing into that side of the join — a distinct count can never exceed the cardinality of the input that carries it.

Join order search

For n tables the estimator runs bottom-up dynamic programming over subsets, the System R / Selinger scheme. best[mask] holds the cheapest plan for the set of tables in mask; subsets are processed in increasing numeric order, which guarantees every proper subset of a mask is already solved when that mask is reached.

flowchart TD
    A["n tables in FROM"] --> B["singletons:<br/>best[1&lt;&lt;i] = cheapest access path for table i"]
    B --> C["for mask = 3 .. 2^n − 1<br/>with popcount(mask) ≥ 2"]
    C --> D["for every split mask = s1 | s2"]
    D --> E["preds = cross predicates<br/>spanning s1 and s2"]
    E --> F["rows = joinRows(best[s1], best[s2], preds)"]
    F --> G["emit candidates"]
    G --> H["best[mask] = argmin cost over all candidates"]
    H --> C
    H --> I{"mask == full set?"}
    I -->|yes| J["keep ALL candidates, not just the best"]
    J --> K["each one gets Sort (if ORDER BY needs it)<br/>then Projection"]
    K --> L["QueryCompiler picks argmin"]

Which candidates each split emits:

flowchart TD
    S["split (s1, s2)"] --> NLJ["NestedLoopJoin"]
    S --> BNLJ["BlockNestedLoopJoin"]
    S --> EQ{"any equijoin<br/>predicate?"}
    EQ -->|no| END["done — cross product"]
    EQ -->|yes| SYM{"s1 &lt; s2 ?"}
    SYM -->|yes| HJ["HashJoin"]
    SYM -->|yes| MJ["MergeJoin<br/>(sort each side unless already sorted)"]
    SYM -->|no| SKIP["skip — symmetric, already emitted"]
    EQ -->|yes| ONE{"s2 is a single table<br/>with a usable index<br/>on its join column?"}
    ONE -->|yes| INLJ["IndexNestedLoopJoin"]

NLJ and BNLJ are emitted for both orientations, because the loop visits every split (s1, s2) and its mirror (s2, s1). HJ and MJ are symmetric in cost here, so they are emitted only once per unordered split (s1 < s2). INLJ requires the inner side to be a single base table, so it is only considered when popcount(s2) == 1.

The subset lattice for a three-table query — every edge is a split the search evaluates:

flowchart BT
    A["{Student}"] --> AB["{Student, Ispit}"]
    B["{Ispit}"] --> AB
    B --> BC["{Ispit, Predmet}"]
    C["{Predmet}"] --> BC
    A --> AC["{Student, Predmet}"]
    C --> AC
    AB --> ABC["{Student, Ispit, Predmet}"]
    BC --> ABC
    AC --> ABC

At the root the estimator deliberately keeps all candidates rather than only the cheapest, so the UI can show the ranked alternatives. Only there is Sort (when ORDER BY is not already satisfied by a clustered index or a merge join's output order) and the final Projection applied.

Complexity is O(3^n) splits, trivially bounded because the project caps n at 4.

Schema format

The catalogue is plain JSON. bufferBlocks is the size of the buffer pool, in blocks.

{
  "bufferBlocks": 10,
  "schema": {
    "tables": [
      {
        "name": "Student",
        "rowCount": 1000,
        "blockCount": 100,
        "rowsPerBlock": 10,
        "attributes": [
          { "name": "indeks", "type": "STRING", "unique": true,  "distinctValues": 1000 },
          { "name": "smer",   "type": "STRING", "unique": false, "distinctValues": 5 }
        ],
        "indexes": [
          {
            "name": "idx_student_indeks_clustered",
            "attributes": ["indeks"],
            "type": "B_PLUS_TREE",
            "clustered": true,
            "treeHeight": 3
          },
          {
            "name": "idx_student_ime_hash",
            "attributes": ["ime"],
            "type": "HASH",
            "clustered": false
          }
        ]
      }
    ]
  }
}

Field	Meaning
`bufferBlocks`	buffer pool size `M`, in blocks
`rowCount` / `blockCount` / `rowsPerBlock`	physical size of the table
`type` (attribute)	`STRING` · `DOUBLE` · `INT` · `DATE`
`unique`	drives equality selectivity `1/n`
`distinctValues`	`V(A, r)`, drives everything else
`type` (index)	`B_PLUS_TREE` · `HASH`
`clustered`	clustered/sorting index — also makes its leading attribute a sort order
`treeHeight`	B+-tree height; the per-lookup traversal cost. Ignored for hash indexes
`attributes`	indexed attributes, in order — order matters for B+-trees

Table and column names are lowercased on load, so queries are case-insensitive. Drop any .json file into schemas/ and it shows up in the menu.

schemas/students.json ships as a worked example: a four-table university database (Student, Ispit, Predmet, Stipendija) with clustered and unclustered B+-trees, single- and multi-attribute hash indexes, and a 10-block buffer.

Supported SQL

SELECT  <columns> | *
FROM    t1 [, t2 [, t3 [, t4]]]
[WHERE  cond [AND cond]*]              -- up to 6 conjuncts
[ORDER BY col]                          -- exactly one attribute
;

Supported

Projection, including SELECT * (expanded to every column of every FROM table)
Selection: equality, comparison (< > <= >= <>), conjunctions
Column references qualified (ispit.predmetid) or bare (ocena)
Numeric and single-quoted string literals
Comma-separated joins with predicates in WHERE
B+-tree and hash indexes, clustered and unclustered, single- and multi-attribute
External merge sort for ORDER BY
All five join algorithms; materialization of intermediate results

Not supported (out of scope for the assignment)

Subqueries, JOIN syntax, OR, GROUP BY, aggregates, set operations
Expressions in the SELECT list
More than 4 tables, more than 6 WHERE conjuncts, more than 1 ORDER BY attribute

Runtime UI

menu:
  1) load schema
  2) list schemas
  3) exit
>

1 / load — prompts for a schema name. The name resolves in order against <name>, schemas/<name>, schemas/<name>.json, so students is enough.
2 / list — lists every .json file in schemas/.
3 / exit — quit.

Inside a session the prompt is sql>. Queries may span multiple lines — continuation lines are prompted with -> and the statement ends at ;. exit or quit returns to the menu. The screen is cleared between queries when stdout is a TTY.

Worked examples

All against schemas/students.json (bufferBlocks = 10).

Index beats scan

SELECT ime FROM student WHERE indeks = '123';

indeks is unique with a clustered B+-tree of height 3, so sel = 1/1000 and cost = 3 + (1/1000)·100 = 3.1 against the sequential scan's 100.

Scan beats index

SELECT ime FROM student WHERE prosek > 8;

A range predicate falls back to sel = 0.5, and there is no index on prosek — so it's a full scan plus a pipelined filter: cost = 100, rows = 500.

Filters stack, sort comes free

SELECT ime, prosek FROM student WHERE smer = 'RI' AND prosek > 8 ORDER BY prosek;

chosen plan (cost=100):
           Projection
  (Student.ime, Student.prosek)
        rows=100 cost=100
                |
      Sort (Student.prosek)
        rows=100 cost=100
                |
        Filter (sel=0.5)
        rows=100 cost=100
                |
        Filter (sel=0.2)
        rows=200 cost=100
                |
         SeqScan Student
       rows=1000 cost=100

smer has 5 distinct values → sel = 0.2 → 200 rows, then prosek > 8 halves it to 100. Those 100 rows fit in 10 blocks ≤ M, so the external sort needs zero merge passes and adds nothing to the cost.

Multi-attribute hash index

SELECT ocena FROM ispit WHERE predmetid = 5;              -- index unusable
SELECT ocena FROM ispit WHERE predmetid = 5 AND ocena = 10;  -- index used

A hash index can only be probed with a full equality cover of all its attributes. idx_ispit_predmet_ocena_hash therefore sits idle for the first query and is chosen for the second.

Three-way join

SELECT ime FROM student, ispit, predmet
WHERE indeks = studentindeks AND ispit.predmetid = predmet.predmetid AND espb = 6;

The DP search filters Predmet down to 16 rows first, block-nested-loop-joins it with Ispit, materializes the 1600-row result, and hash-joins that against Student — cost = 2432. Adding ORDER BY ime puts an external sort on top and pushes it to 4352.

Project layout

include/            public headers (one per component)
  ASTNode.hpp         AST class hierarchy
  Binder.hpp          name resolution + type checking
  CompileResult.hpp   { plans, best }
  Errors.hpp          CompileError / Lexical / Parse / Semantic
  Estimator.hpp       plan enumeration + costing
  IOHandler.hpp       console I/O
  JoinNode.hpp        the five join plan nodes + Materialize
  Lexer.hpp           tokens + tokenizer
  Menu.hpp            schema discovery loop
  Parser.hpp          recursive-descent parser
  PlanNode.hpp        plan node base + scan/filter/project/sort
  PlanPrinter.hpp     ASCII tree renderer
  QueryCompiler.hpp   pipeline orchestrator
  Schema.hpp          catalogue: Table / Column / Index
  Session.hpp         per-schema REPL
src/                implementations (+ main.cpp)
tests/              framework-free test binary
schemas/            JSON catalogues, discovered at runtime
third_party/        vendored nlohmann/json v3.11.3 (single header)
docs/               assignment text (EN/SR) + full technical walkthrough

Two CMake targets:

Target	Contents
`qpe_core`	static lib: lexer, parser, binder, estimator, plan printer, schema
`query-plan-estimator`	executable: `main`, `Menu`, `Session`, `IOHandler` + `qpe_core`

Plus format / format-check targets when clang-format is on PATH.

Building

Requires CMake ≥ 3.16 and a C++20 compiler (g++ 11+, clang 13+, MSVC 2019 16.10+). No network access and no package manager — the only dependency is vendored.

cmake -S . -B build
cmake --build build
./build/query-plan-estimator

Without CMake at all:

g++ -std=c++20 -Iinclude -Ithird_party src/*.cpp -o qpe && ./qpe

Warnings are on by default: -Wall -Wextra -Wpedantic -Wconversion -Wshadow (GCC/Clang) or /W4 /utf-8 (MSVC). See RUN.md for Windows, Visual Studio and CLion.

Testing

ctest --test-dir build --output-on-failure

tests/tests.cpp is a dependency-free harness (a check() function and a failure counter) that links qpe_core and compiles queries in-process. It pins the cost model down to exact numbers, so any accidental change to a formula fails loudly:

Errors — every LexicalError, ParseError and SemanticError path, including all three project limits
Single table — clustered-index equality at 3.1, range fallback at 0.5, sort-free ORDER BY on a clustered key, external sort at 100 + 2·2·100, hash-index cover rules, <> excluded from B+-tree lookups
SELECT * — expansion across one and several tables
Two-table join — exactly 8 candidates, and the precise cost of every one of them (HJ 2740, MJ 3300, BNLJ 6500/6600, INLJ 11100/14000, NLJ 401300/401600), plus the presence of Materialize and the tree's / \ | connectors
Three-table join — DP picking the filtered Predmet first (2432), and the added top-level sort (4352)

Error handling

All failures derive from CompileError, so Session catches one type and the REPL never dies on a bad query.

flowchart TD
    RE["std::runtime_error"] --> CE["CompileError"]
    CE --> LE["LexicalError<br/>+ byte position"]
    CE --> PE["ParseError<br/>+ byte position"]
    CE --> SE["SemanticError"]

sql> SELECT ime FROM student WHERE ime = 5;
semantic error: type mismatch in '=': left side is text, right side is numeric

Schema-loading failures (missing file, malformed JSON, unknown type name) throw std::runtime_error and are caught by Menu, which reports them and returns to the menu.

Name		Name	Last commit message	Last commit date
.vscode		.vscode
docs		docs
include		include
schemas		schemas
src		src
tests		tests
third_party/nlohmann		third_party/nlohmann
.clang-format		.clang-format
.gitignore		.gitignore
CMakeLists.txt		CMakeLists.txt
README.md		README.md
RUN.md		RUN.md
format.sh		format.sh

Navigation Menu

Repository navigation

About

Repository files navigation

query-plan-estimator

Table of contents

Quick start

Architecture

The compilation pipeline

1 — Lexer

2 — Parser

3 — Binder

4 — Estimator

5 — Plan printer

The cost model

Selectivity

Access paths

Join algorithms

Sort, materialize, projection

Join cardinality

Join order search

Schema format

Supported SQL

Runtime UI

Worked examples

Index beats scan

Scan beats index

Filters stack, sort comes free

Multi-attribute hash index

Three-way join

Project layout

Building

Testing

Error handling

Further reading

About

Releases

Packages

Contributors

Languages

Latest commit

History

Folders and files

Repository files navigation

query-plan-estimator

Table of contents

Quick start

Architecture

The compilation pipeline

1 — Lexer

2 — Parser

3 — Binder

4 — Estimator

5 — Plan printer

The cost model

Selectivity

Access paths

Join algorithms

Sort, materialize, projection

Join cardinality

Join order search

Schema format

Supported SQL

Runtime UI

Worked examples

Index beats scan

Scan beats index

Filters stack, sort comes free

Multi-attribute hash index

Three-way join

Project layout

Building

Testing

Error handling

Further reading

About

Resources

Stars

Watchers

Forks

Releases

Packages

Contributors

Languages