TODO.md

TODOs

Roadmap - A List of Things to be Done

Lexer

• define regular expression of tokens (as part of the grammar)
• implement tokens
• implement lexical analysis and tokenization
• provide lexer tests
  • unit tests
  • integration tests

Parser

• define grammar
  • expressions
  • clauses
  • statements
    • CREATE
    • SELECT
    • INSERT
    • UPDATE
    • DELETE
• implement abstract syntax tree (AST)
• provide parser tests
  • unit tests tests
  • integration tests

Semantic Analysis

• SQL types
  • boolean type BOOL
  • character strings CHAR(N) and VARCHAR(N)
  • numeric types
    • integers INT(1) to INT(8)
    • floating point FLOAT (32 bit) and DOUBLE (64 bit)
    • DECIMAL(p, s) type with p decimal digits and a decimal dot left of the s rightmost digits
• define rules of the SQL type system
• implement SQL type system
• implement semantic analysis

Intermediate Representation

• conjunctive normal form
  • implement CNF representation and operations
  • CNF unit tests
• design IR
• implement IR
  • translate expression AST to CNF
  • test IR
• implement join graph representation
• rewrite rules on the join graph
  • push-down rules
  • de-correlation
  • unnesting

Catalog

• define internal type system
• define and implement Schema
• define core components of a catalog
  • schema
  • tables
  • index structures
  • statistics
    • workload
    • data

Store

• which kind of storage to provide
  • memory-only non-persistent storage
    • in-memory row store
    • in-memory columnar store
  • disk-based persistent storage
• which data layouts to provide
  • row-major layout
  • column-major layout
  • partition across (PAX)
• define interface for access
  • by query interpreter
  • by query compiler

Query Planner

• AI Planning
  • beam search
    • track in StateTracker whether a state made it to the beam_Q. if not, and it is part of a beam, add it to the beam_Q no matter its cost

Query Interpreter

Query Compiler

Statistics

• gather statistics to aid query planning/compilation
  • statistics about data
  • statistics about workload

Documentation

• document every class with at least 1-3 sentences
• document interface functions (most public's)
• document non-trivial functions/code

Testing

• automatically run tests locally before every push (to master) (commit?)