Sefism is free for learners. We are here to help you grow, one step at a time.Join for free
Sefism.
Other

SQL Query Engine with a Cost-Based Optimiser for Analytics Files

A SQL query engine that runs SELECT queries over CSV and Parquet files, with a parser, logical plan, rule and cost-based optimiser, and vectorised execution for joins and aggregates. An advanced database systems final year project that shows exactly why one query plan beats another, with benchmarks on standard workloads.

Topics
Difficulty

Advanced

Needs a team, real planning, and a supervisor who knows the area.
Effort

2 semesters · 3 students

Deliverables

7 to ship

3 optional extras

Suggested stack

Rust, C++ or JavaApache Arrow columnar formatParquet readerHand-written SQL parserTPC-H style benchmark dataCriterion or JMH benchmarks
A suggestion, not a requirement. Swap anything for what you already know.

What you should ship

  • A SQL parser and binder for SELECT with WHERE, JOIN, GROUP BY, ORDER BY and LIMIT, with clear error messages that point to the column and position.
  • A logical plan and at least five rewrite rules: predicate pushdown, projection pruning, constant folding, limit pushdown and ORDER BY plus LIMIT turned into top-N.
  • Table statistics (row counts, distinct counts, min and max, simple histograms) collected from files and used to estimate cardinalities.
  • A cost-based join order search for up to six tables using dynamic programming, with EXPLAIN output that shows estimated and actual row counts.
  • A vectorised executor over columnar batches with scan, filter, projection, hash join, hash aggregate and sort operators.
  • A benchmark over a TPC-H style dataset at two scale factors, comparing naive plans, rule-optimised plans and cost-optimised plans.
  • A correctness suite that runs every query against a reference engine such as DuckDB or SQLite and compares results.

If you have time left

  • Spill-to-disk for hash joins and sorts when memory is limited.
  • Parallel execution across CPU cores with morsel-driven scheduling.
  • A cardinality estimation error report showing where your statistics mislead the optimiser.

The problem: students query databases but never see why a query is fast

Every developer writes SQL, and most have seen a query take 40 seconds that should take 40 milliseconds. Few know what the database did in between: how it parsed the text, chose a join order, estimated how many rows each step would produce, and picked hash join over nested loops. The optimiser is the most important and least understood part of a database, and it is exactly the kind of work that database and data platform teams hire for.

On the practical side, analysts increasingly query files directly (CSV exports, Parquet from a data lake) rather than loading them into a server. Embedded engines that do this well are now a core part of the data stack.

What already exists and the gap

  • DuckDB is an in-process analytical database that queries CSV and Parquet directly, with a mature optimiser and vectorised engine.
  • Apache DataFusion is an extensible query engine in Rust built on Apache Arrow, used as the base for several products.
  • CMU's BusTub is the teaching database from the 15-445 course, where students implement executors and a few optimiser rules such as turning nested loop joins into hash joins.
  • SQLite is the most deployed database in the world, row-oriented and designed for transactional workloads rather than analytics.

The gap for a final year project is not a better DuckDB. It is a small, readable engine where every optimiser decision is visible and measured, taking BusTub's teaching idea further into cost-based join ordering and statistics.

What you build

A command-line and library engine that reads files and answers SQL.

  • Front end: a hand-written recursive descent parser, a binder that resolves names and types, and precise error messages.
  • Logical plan: a tree of relational operators. Rewrite rules transform it into an equivalent, cheaper tree.
  • Statistics: gathered when a file is first registered, stored alongside it, refreshed on change.
  • Cost model: estimates rows and cost for each candidate plan; dynamic programming over join subsets picks the cheapest order.
  • Physical execution: operators process columnar batches in the Arrow format, which keeps loops tight and cache friendly.
  • EXPLAIN ANALYZE: prints the chosen plan with estimated and actual row counts per operator.

The technically interesting part

Cardinality estimation is the heart of it. The optimiser is only as good as its guesses about how many rows survive a filter or a join. With min and max values and distinct counts you can estimate simple predicates; correlated columns and skewed joins will fool you. The project becomes excellent when you show this: run a set of queries, plot estimated versus actual rows per operator, and explain the worst misses. Then show how the chosen join order changes the runtime, sometimes by orders of magnitude.

The second interesting part is the executor. Processing a batch of a few thousand values at a time instead of one row at a time is why modern analytical engines are fast. Measure the difference between a row-at-a-time version of one operator and your vectorised version.

How to evaluate it

  • Correctness: every query in your suite returns the same result as the reference engine; zero mismatches.
  • Optimiser impact: runtime of each benchmark query under no optimisation, rules only, and rules plus cost-based ordering.
  • Estimation quality: q-error (the ratio between estimated and actual rows) per operator, summarised across the workload.
  • Execution speed: rows per second for scan, filter, join and aggregate, row-at-a-time versus vectorised.
  • Honest comparison: the same workload in DuckDB, reported to show the gap and where it comes from.

Suggested plan

  1. Weeks 1 to 3: work through the CMU 15-445 query processing and optimisation lectures; choose the SQL subset.
  2. Weeks 4 to 8: parser, binder, logical plan and a naive executor that returns correct answers.
  3. Weeks 9 to 13: rewrite rules, correctness suite against the reference engine.
  4. Semester 2, weeks 1 to 5: statistics, cost model and join ordering, EXPLAIN ANALYZE.
  5. Weeks 6 to 10: vectorised operators over columnar batches, Parquet reader.
  6. Weeks 11 to 14: benchmarks, estimation error analysis and final report.

Path to a product

Realistically this is a portfolio and research piece that leads to jobs on database, data platform and analytics teams. There is still a product angle: a small embedded engine for a niche, for example querying exported accounting or point-of-sale files on a shopkeeper's laptop without a server, or a teaching tool that visualises plans for database courses, licensed to universities. Contributing a rule or an operator back to an open source engine like DataFusion is another strong outcome.

Scope warning

Do not implement INSERT, UPDATE, transactions or indexes; this is a read-only analytics engine. Do not support the full SQL standard; subqueries and window functions are stretch goals at most. Do not write your own Parquet decoder from zero; use a library and spend the time on the optimiser.

Learn what you need on Sefism

Get help with this idea

A query engine is a large build, so the real skill here is cutting SQL features without cutting the optimiser. If you want a second opinion on scope, stack or how to evaluate it before you pitch it to your supervisor, bring your draft proposal and we will pressure-test it together. You build it; the guidance is on the decisions.

New here? Create a free account first.

Ideas and guidance, not finished projects

These are project ideas and scoping guidance, published free for students to use as a starting point. I do not build, write, or sell final-year projects, and I do not complete coursework for anyone. Take an idea, make it yours, and build it.

Not sure this one fits you?

I help students pick an idea that matches their skills and their deadline, then scope it down until it is finishable. Guidance only, never done for you.

Discuss this idea
Work with me

Stuck on something specific?

Writing only gets you so far. If you want an answer to your situation rather than the general case, book a session and we will work through it together. Sessions are free for approved Sefism members, and a few slots open each week.

Book a free sessionSee all services

Follow along

New writing, resources and project ideas land here first.