hard Algorithms & Recursion

Mini SQL Engine

The Brief

A consultancy has been handed a stack of CSV files from a legacy system and asked to deliver "a query layer". They cannot stand up a database server, they cannot install third-party packages — air-gapped client environment. The only tool available is Python.

Build a working SQL engine in pure standard library. Tokenize the input, parse it into an AST, then execute it against in-memory tables loaded from CSV.

Must support: SELECT col, col, * FROM table; WHERE col OP value with =, !=, <, >, <=, >= and AND/OR; INNER JOIN table ON col = col; ORDER BY col [ASC|DESC]; LIMIT n. Values may be strings (single-quoted), integers, or floats. Identifiers are case-sensitive; SQL keywords are case-insensitive. This is the legendary tier — build the lot.

Acceptance Criteria

Tap a criterion to mark it off as you work. Tap a category header to expand or collapse.

1 Array

2 Array

3 Array

4 Array

💡 Hints 0 / 7

Guest Mode Attempt this challenge freely, or log in to earn EXP & CodeCoins.

solution.py

Python 3

import re
import csv


KEYWORDS = {"SELECT","FROM","WHERE","AND","OR","ORDER","BY","ASC","DESC","LIMIT","INNER","JOIN","ON","AS"}


def tokenize(sql):
    """Return list of (kind, value) tuples."""
    # TODO
    pass


class Parser:
    def __init__(self, tokens):
        self.tokens = tokens
        self.pos = 0

    def parse(self):
        """Return dict AST: columns, table, join, where, order_by, limit."""
        # TODO
        pass


def try_cast(v):
    """Cast string CSV value to int/float/string."""
    pass


def load_csv(path):
    """Return list of dict rows with cast values."""
    pass


def eval_condition(cond, row):
    """Evaluate a WHERE AST node against a row."""
    pass


class MiniDB:
    def __init__(self):
        self.tables = {}

    def register(self, name, rows):
        self.tables[name] = rows

    def execute(self, sql):
        """Tokenize, parse, execute. Return list of result rows."""
        # TODO
        pass

Console