Building SaarDB, Part 5: SQL Parsing

In Parts 1-4, we built a transactional key-value store. It has WAL for durability, memtables and SSTables for storage, compaction to control file growth, and transactions for atomic multi-key writes.

Now we move to the query layer where users can actually fire SQL queries like:

CREATE TABLE payments (amount INT, id STRING, status STRING, captured BOOL, PRIMARY KEY (id))
INSERT INTO payments VALUES (500, payment_1, pending, 1)
SELECT * FROM payments WHERE id = payment_1

In this blog and the next one we answer:

How do we translate SQL strings into operations our key-value store already understands?

This post focuses on the first half of that bridge, which is parsing SQL into structured commands. In the next post, we will take those commands and turn CREATE TABLE and INSERT into bytes on disk.

The Core Idea: SQL Becomes Structured Data

The storage engine does not understand SQL. It understands keys, values, WAL entries, memtables, SSTables, and transactions.

So the SQL layer has two jobs:

1. Parse a human-readable SQL string into a structured object.
2. Translate that structured object into key-value operations.

For example:

CREATE TABLE payments (...)
    -> CreateTable{TableName: "payments", ColumnDetails: ...}

INSERT INTO payments VALUES (...)
    -> InsertIntoTable{TableName: "payments", ColumnValues: ...}

SELECT * FROM payments WHERE id = payment_1
    -> SelectFromTable{TableName: "payments", QueryConditions: ...}

Once we have these structs, the rest of the database can stop dealing with raw strings.

Why Not Parse SQL Directly in the DB Layer?

Imagine if db.CreateTable() directly walked through the SQL string and also updated storage. That would mix two very different responsibilities:

• parsing grammar,
• executing database operations.

Keeping them separate makes the system easier to reason about. The parser validates syntax and builds an AST. The DB layer receives that AST and decides what to store.

An AST, or Abstract Syntax Tree, is just a structured representation of the command.

This is how the AST struct for the 3 common use cases, CREATE, INSERT, SELECT would look like:

type CreateTable struct {
    TableName                string
    ColumnDetails            []Column
    PrimaryKeyColumnPosition int
    SecondaryIndexes         []SecondaryIndex
}

type InsertIntoTable struct {
    TableName    string
    ColumnValues []string
}

type SelectFromTable struct {
    TableName       string
    ColumnsRequired []string
    QueryConditions []QueryCondition
}

Notice that InsertIntoTable.ColumnValues is still []string. The parser does not convert 500 into an integer yet. That conversion can happen while storing in the database. The parser only understands syntax.

Parsing SQL Queries

Let's take an example for parsing one of the SQL queries.

For CREATE TABLE, the expected shape is:

CREATE TABLE <table_name> (
    <column_name> <data_type>,
    ...
    PRIMARY KEY (<column_name>)
);

We need to extract all of the useful properties out of the string into our AST CreateTable struct. One way could be to go through each of the words and keep on extracting character by character and word by word.

So, in case of CREATE TABLE queries, the parser should do something like:

1. Expect keyword CREATE.
2. Expect keyword TABLE.
3. Expect the table name. Store those in the AST struct.
4. Expect (.
5. Read column definitions until ). While reading column definitions, extract the column name and the data type. Store those in the AST struct.
6. If it sees PRIMARY KEY (...), store the primary-key column.
7. Return a CreateTable struct.

The SQL query could also contain whitespaces (spaces, tabs '\t' and new lines '\n'). The SQL query should also end with a ;.

Notice that the CREATE TABLE query parsing requires identifying a lot of details which are specific to this query like table name, column names and data type and the primary key column name, along with the necessary validations.

Apart from these distinct requirements for the specific query, there is a lot of common logic that needs to be handled for each SQL query. This includes:

1. Each query includes keywords like CREATE, TABLE, INSERT, INTO, SELECT, FROM, WHERE and AND.
2. Each query includes one or more of expressions like (, ), ,, ;, and *.
3. Each query can contain unique identifiers based on the use case. In case of CREATE TABLE queries, this could be table name, column name, data type or primary key column name. Similarly in case of SELECT query, it could be a column name or its query condition.

Tokeniser: Breaking SQL Into Small Pieces

Tokenisation is a common operation applicable across all SQL queries. We break the input string into small meaningful pieces called tokens.

For this query:

CREATE TABLE payments (amount INT, id STRING);

The tokens are:

CREATE     keyword
TABLE      keyword
payments   identifier
(          symbol
amount     identifier
INT        identifier
,          symbol
id         identifier
STRING     identifier
)          symbol
;          symbol

Tokenisation is the first step performed to avoid directly parsing the string. We will soon see how this step drastically simplifies things because of us working with tokens and not raw characters.

We will build a function whose job is to find the next token from the input string. It tracks the index position in the input string in a private variable pos which indicates the index till which we have already tokenised.

The tokeniser walks through the input character by character:

1. Skip whitespace.
2. Return symbols like (, ), ,, ;, and *.
3. Return conditional operators like =, <, <=, >, and >=.
4. Read alphanumeric words and decide whether they are keywords or identifiers.

This is how the NextToken function looks like:

func (t *Tokeniser) NextToken() Token {
    t.skipWhiteSpace()
    // the entire input string is read
    if t.pos >= len(t.input) {
        return Token{Type: EOF}
    }

    ch := t.input[t.pos]
    // SYMBOL token
    if ch == '(' || ch == ')' || ch == ',' || ch == ';' || ch == '*' {
        t.pos++
        return Token{Type: SYMBOL, Value: string(ch)}
    }

    // CONDITIONAL_OPERATOR token 
    if strings.ContainsRune(conditionalOperators, t.input[t.pos]) {
        start := t.pos
        for t.pos < len(t.input) && strings.ContainsRune(conditionalOperators, t.input[t.pos]) {
            t.pos++
        }
        return Token{Type: CONDITIONAL_OPERATOR, Value: string(t.input[start:t.pos])}
    }

    start := t.pos
    for t.pos < len(t.input) && isAlphanumeric(t.input[t.pos]) {
        t.pos++
    }

    // KEYWORD or IDENTIFIER token
    word := t.input[start:t.pos]
    if _, ok := keywordsMap[strings.ToUpper(word)]; ok {
        return Token{Type: KEYWORD, Value: strings.ToUpper(word)}
    }
    return Token{Type: IDENTIFIER, Value: word}
}

keywordsMap would contain the list of all supported SQL keywords like CREATE, INSERT, SELECT, etc.

Note that the only job of NextToken is to find the next upcoming token and classify it as a KEYWORD, IDENTIFIER, SYMBOL or CONDITIONAL_OPERATOR.

This is a common step required for parsing each SQL query.

Consuming Tokens

Once we know the NextToken, consuming, validating the token and converting into AST struct becomes much simpler.

We also have a common consume function which is used by each of the parser implementation functions (ParseCreateTable, ParseInsertInto, ParseSelect).

While parsing the input query, we always know what is the expected token type (KEYWORD or SYMBOL or IDENTIFIER). In case of token type as KEYWORD or SYMBOL, we also know what is the expected value. For example: In case of CREATE TABLE, the first two expected keywords are CREATE and TABLE. After that we expect the table name and just after that we expect the symbol (.

This is how the consume function looks like.

type TokenType string

// Supported Token Types
const (
    IDENTIFIER           TokenType = "IDENTIFIER"
    KEYWORD              TokenType = "KEYWORD"
    SYMBOL               TokenType = "SYMBOL"
    CONDITIONAL_OPERATOR TokenType = "CONDITIONAL_OPERATOR"
    EOF                  TokenType = "EOF"
)

func (p *Parser) consume(tt TokenType, expectedVal string) error {
    if p.currentToken.Type != tt || (expectedVal != "" && p.currentToken.Value != expectedVal) {
        return fmt.Errorf("syntax error: expected %s %q, got %s %q",
            tt, expectedVal, p.currentToken.Type, p.currentToken.Value)
    }
    p.currentToken = p.tokeniser.NextToken()
    return nil
}

Notice that in case of identifier, we would not be having any expected value (expectedVal = "") as identifiers are used to fill in the AST structure. While in case of keyword or symbol, we know the expected value (expectedVal != "").

Parsing CREATE TABLE

Let's take CREATE TABLE as an example to solidify our understanding. Rest of the queries would have similar logic for parsing queries. We can utilise the consume function for parsing any SQL query.

CREATE TABLE payments (amount INT, id STRING, status STRING, captured BOOL, PRIMARY KEY (id))

The algorithm would look something like:

1. Consume CREATE as a KEYWORD.
2. Consume TABLE as a KEYWORD.
3. Consume IDENTIFIER for table name and set that within the AST struct of CreateTable.
4. Consume ( as a SYMBOL.
5. Run a for loop till we encounter ) SYMBOL as the current token.
   • Consume identifier for column name and data type and set that within the AST struct of CreateTable
   • The next token could be the keyword PRIMARY. If yes,
     • Consume keywords PRIMARY and KEY
     • Consume identifier for primary key column and set that within the AST struct of CreateTable.
   • Consume symbol ,

What we wrote can be modeled into code as:

    func (p *Parser) ParseCreateTable() (*CreateTable, error) {
        if err := p.consume(KEYWORD, KeywordCreate); err != nil {
            return nil, err
        }
        if err := p.consume(KEYWORD, KeywordTable); err != nil {
            return nil, err
        }
        tableName := p.currentToken.Value
        if err := p.consume(IDENTIFIER, ""); err != nil {
            return nil, err
        }

        if err := p.consume(SYMBOL, SymbolOpenRoundBracket); err != nil {
            return nil, err
        }

        columnDetails := []Column{}
        pkColumn := ""
        for p.currentToken.Value != SymbolClosedRoundBracket {
            if p.currentToken.Value == "," {
                p.consume(SYMBOL, ",")
            }
            if p.currentToken.Value == KeywordPrimary {
                var err error
                pkColumn, err = p.parsePrimaryKeyColumn()
                if err != nil {
                    return nil, err
                }
                continue
            }

            columnName := p.currentToken.Value
            if err := p.consume(IDENTIFIER, ""); err != nil {
                return nil, err
            }
            columnType := p.currentToken.Value
            if err := p.consume(IDENTIFIER, ""); err != nil {
                return nil, err
            }
            dataType, err := getDataTypeFromString(columnType)
            if err != nil {
                return nil, err
            }
            columnDetails = append(columnDetails, Column{
                ColumnName: columnName,
                DataType:   dataType,
            })
        }

        if len(columnDetails) == 0 {
            return nil, fmt.Errorf("expected atleast one column detail, found none")
        }

        // current simplification that if PRIMARY KEY is not provided, consider first column as primary key
        pkColumnPosition := 0
        if pkColumn != "" {
            pkColumnPosition = -1
            for i, col := range columnDetails {
                if col.ColumnName == pkColumn {
                    pkColumnPosition = i
                }
            }
            if pkColumnPosition == -1 {
                return nil, fmt.Errorf("primary key column '%s' not found", pkColumn)
            }
        }

        if err := p.consume(SYMBOL, SymbolClosedRoundBracket); err != nil {
            return nil, err
        }

        return &CreateTable{
            TableName:                tableName,
            ColumnDetails:            columnDetails,
            PrimaryKeyColumnPosition: pkColumnPosition,
        }, nil
    }

The parser returns:

CreateTable{
    TableName: "payments",
    ColumnDetails: []Column{
        {ColumnName: "amount", DataType: Int},
        {ColumnName: "id", DataType: String},
        {ColumnName: "status", DataType: String},
        {ColumnName: "captured", DataType: Bool},
    },
    PrimaryKeyColumnPosition: 1,    // 1 is the index of "id" in the ColumnDetails array, which is the primary key
}

This is already much easier for the DB layer to use than a raw SQL string.

Current Parser Limitations

This parser is intentionally small. A few examples:

• String literals are not quoted yet, so examples use pending, not 'pending'.
• INSERT requires values for all columns in schema order.
• SELECT supports simple WHERE conditions and AND, not joins, grouping, or expressions.
• CREATE supports limited set of datatypes.

These limitations are acceptable for now because the goal is to build intuition one layer at a time.

What's Next

Parsing turns SQL strings into structs. But a struct is still not durable data.

Now we need to answer the deeper question in the next post:

Once we have CreateTable and InsertIntoTable AST structs, how do we store them inside a key-value engine?

The code for SaarDB is available here:
GitHub: https://github.com/gagandeepahuja09/saardb