Skip to content

014-simple-query-planner.md

Latest commit

聽

History

History
49 lines (29 loc) 路 3.49 KB

014-simple-query-planner.md

File metadata and controls

49 lines (29 loc) 路 3.49 KB
Raw

Entry 14: The Simple Query Planner and Phase 3 Complete

Objective

To implement the final component of the core query processing engine: a Planner. This class bridges the gap between the parser and the execution engine, translating the Abstract Syntax Tree (AST) from ANTLR into a runnable tree of executor objects. This commit marks the completion of the Phase 3 roadmap.

Key Concepts & Design Decisions

The Role of the Planner

The Planner is the brain of the query processing system. While a production planner is incredibly complex (handling optimization, cost models, and statistics), our simple planner has one clear responsibility: translation. It takes a SQL string as input and produces a ready-to-execute Executor tree as output.

The createPlan method is the entry point. It orchestrates the entire translation pipeline.

The ANTLR Translation Pipeline

The planner first uses the ANTLR-generated classes to transform a raw SQL string into a structured object. This process involves several key components from the ANTLR runtime:

  • SimpleSQLLexer: The Lexer (or "tokenizer") is the first stage. It consumes the character stream and groups the characters into meaningful tokens (e.g., SELECT, *, users).
  • CommonTokenStream: The parser needs to be able to look ahead. The CommonTokenStream acts as a buffer, pulling all tokens from the lexer and storing them in a list to provide that lookahead capability.
  • SimpleSQLParser: The Parser is the main brain. It consumes the stream of tokens and tries to match them against the structural rules in our grammar, building a tree-like "Context" object (the AST) in memory.

From AST to Executor Tree

Once the planner has the ANTLR Context Tree, it inspects it to determine the type of statement (SELECT, INSERT, etc.) and delegates to a specific build method (e.g., buildSelectPlan).

The buildSelectPlan method demonstrates the core logic of the planner. It builds the executor tree from the bottom up:

  1. It always starts with a SeqScanExecutor as the base of the plan.
  2. It then checks the AST for a WHERE clause. If one exists, it recursively builds our own Expression tree from the AST and wraps the SeqScanExecutor in a FilterExecutor.
  3. Finally, it checks for a specific column list (a projection). If found, it creates an output Schema and wraps the current plan in a ProjectionExecutor.

This bottom-up construction results in a final, runnable plan like Projection -> Filter -> SeqScan, which can be returned to the client.

Phase 3 Complete

With the Planner in place, our database can now accept SQL strings for a variety of single-table queries and execute them correctly. The core query processing engine is complete. We have successfully built:

  • An expanded SQL parser.
  • Executors for SELECT (with projection and filtering), INSERT, and DELETE.
  • A planner to automatically assemble these executors into a query plan.

Next Steps

The database is now functional but not yet performant for large tables. All queries that require finding specific rows must perform a full table scan. Phase 4 will address this by implementing Indexing for Performance. This will involve:

  1. Implementing a B+-Tree data structure from scratch.
  2. Building an IndexScanExecutor that can use the B+-Tree to find specific tuples without scanning the entire table.
  3. Enhancing the Planner to be able to choose between a SeqScan and an IndexScan based on the query.