OLAP – Phase 8 SQL Parser

The execution engine from Phases 5-7 works, but it requires manually constructing operator trees and expression objects in Go code. A real database accepts SQL text from users. This phase builds a SQL parser that converts a SQL string into an Abstract Syntax Tree (AST) — a structured representation that the planner (Phase 9) can transform into a physical execution plan.

The parser has two stages: a lexer that splits the SQL string into tokens, and a recursive descent parser that builds the AST from the token stream.

In DuckDB, the parser is based on PostgreSQL’s parser (src/parser/), which uses a grammar file and bison-generated parser. Our implementation uses hand-written recursive descent, which is simpler and easier to extend.

Here is the roadmap for the phases to come:

• Phase 8: SQL parser
• Phase 9: Query planner and optimizer
• Phase 10: Sorting, parallel execution, REPL, and server

Full Source Code

The code referenced in this post can be found in https://gitlab.com/kimserey.lam/olap-learn.

Tokens

The lexer produces a stream of tokens — the smallest meaningful units of SQL:

type TokenType uint8

const (
    TokenEOF TokenType = iota
    TokenIdent
    TokenInt
    TokenFloat
    TokenString
    TokenStar
    TokenComma
    TokenDot
    TokenSemicolon
    TokenLParen
    TokenRParen
    TokenEquals
    TokenNotEquals
    TokenLessThan
    TokenLessThanOrEqual
    TokenGreaterThan
    TokenGreaterThanOrEqual
    TokenPlus
    TokenMinus
    TokenSlash
    // keywords
    TokenSelect
    TokenFrom
    TokenWhere
    TokenAnd
    TokenOr
    TokenNot
    TokenJoin
    TokenInner
    TokenLeft
    TokenRight
    TokenOn
    TokenGroup
    TokenBy
    TokenHaving
    TokenOrder
    TokenAsc
    TokenDesc
    TokenLimit
    TokenOffset
    TokenInsert
    TokenInto
    TokenValues
    TokenCreate
    TokenTable
    TokenCopy
    TokenDistinct
    TokenAs
    TokenNull
    TokenNulls
    TokenFirst
    TokenLast
    TokenTrue
    TokenFalse
    // type keywords
    TokenInt32Type
    TokenInt64Type
    TokenFloat64Type
    TokenVarcharType
    TokenBooleanType
)

Each token carries its type, literal value, and source position.

---

Lexer

The lexer scans the SQL string character by character, producing tokens:

type Lexer struct {
    input string
    pos   int
}

func (l *Lexer) NextToken() Token {
    l.skipWhitespace()
    if l.pos >= len(l.input) {
        return Token{Type: TokenEOF}
    }

    ch := l.input[l.pos]
    switch {
    case ch == '*':
        l.pos++
        return Token{Type: TokenStar}
    case ch == '\'':
        return l.readString()
    case isDigit(ch):
        return l.readNumber()
    case isLetter(ch) || ch == '_':
        return l.readIdentOrKeyword()
    // ... operators, punctuation
    }
}

Keywords are recognized by checking the identifier against a lookup map — "SELECT" → TokenSelect, "FROM" → TokenFrom, etc. Identifiers that aren’t keywords remain as TokenIdent.

---

AST Nodes

The AST is a tree of nodes representing the structure of the SQL statement:

Statements

type SelectStmt struct {
    Distinct   bool
    SelectList []SelectItem
    From       *TableRef
    Joins      []JoinClause
    Where      Expr
    GroupBy    []Expr
    Having     Expr
    OrderBy    []OrderByItem
    Limit      Expr
    Offset     Expr
}

type CreateTableStmt struct {
    Name    string
    Columns []ColumnDef
}

type InsertStmt struct {
    Table  string
    Values [][]Expr
}

type CopyStmt struct {
    Table    string
    FilePath string
}

Expressions

type ColumnRef struct {
    Table string   // optional qualifier: "o" in "o.region"
    Name  string   // "region"
}

type BinaryExpr struct {
    Left  Expr
    Op    string   // "+", "-", "=", ">", "AND", etc.
    Right Expr
}

type FunctionCall struct {
    Name     string   // "SUM", "COUNT", etc.
    Args     []Expr
    Distinct bool     // COUNT(DISTINCT x)
    Star     bool     // COUNT(*)
}

type IntLit struct{ Value int64 }
type FloatLit struct{ Value float64 }
type StringLit struct{ Value string }
type BoolLit struct{ Value bool }
type NullLit struct{}
type StarExpr struct{}

---

Recursive Descent Parser

The parser consumes tokens and builds the AST using a top-down approach. Each grammar rule becomes a method:

Operator Precedence

The key challenge is parsing expressions with correct precedence. We handle this by nesting parse functions — each level handles operators of one precedence:

parseExpr()              → OR
  parseAndExpr()         → AND
    parseNotExpr()       → NOT
      parseCompExpr()    → =, !=, <, >, <=, >=
        parseAddExpr()   → +, -
          parseMulExpr() → *, /
            parseUnary() → unary -
              parsePrimary() → literal, column, function, (expr)

For example, a + b * c > 10 AND x = 1 parses as:

AND
├── >
│   ├── +
│   │   ├── a
│   │   └── *
│   │       ├── b
│   │       └── c
│   └── 10
└── =
    ├── x
    └── 1

Parsing SELECT

func (p *Parser) parseSelect() (*SelectStmt, error) {
    p.expect(TokenSelect)

    stmt := &SelectStmt{}

    // DISTINCT?
    if p.match(TokenDistinct) {
        stmt.Distinct = true
    }

    // select list
    stmt.SelectList = p.parseSelectList()

    // FROM
    p.expect(TokenFrom)
    stmt.From = p.parseTableRef()

    // JOINs
    for p.isJoinKeyword() {
        stmt.Joins = append(stmt.Joins, p.parseJoinClause())
    }

    // WHERE
    if p.match(TokenWhere) {
        stmt.Where = p.parseExpr()
    }

    // GROUP BY
    if p.matchSequence(TokenGroup, TokenBy) {
        stmt.GroupBy = p.parseExprList()
    }

    // HAVING
    if p.match(TokenHaving) {
        stmt.Having = p.parseExpr()
    }

    // ORDER BY
    if p.matchSequence(TokenOrder, TokenBy) {
        stmt.OrderBy = p.parseOrderByList()
    }

    // LIMIT / OFFSET
    if p.match(TokenLimit) {
        stmt.Limit = p.parseExpr()
        if p.match(TokenOffset) {
            stmt.Offset = p.parseExpr()
        }
    }

    return stmt, nil
}

Parsing Function Calls

func (p *Parser) parseFunctionCall(name string) *FunctionCall {
    p.expect(TokenLParen)
    fn := &FunctionCall{Name: name}

    if p.match(TokenStar) {
        fn.Star = true
    } else if p.match(TokenDistinct) {
        fn.Distinct = true
        fn.Args = p.parseExprList()
    } else if !p.check(TokenRParen) {
        fn.Args = p.parseExprList()
    }

    p.expect(TokenRParen)
    return fn
}

---

Example Parse

SELECT o.region, SUM(o.amount)
FROM orders o
WHERE o.year > 2023
GROUP BY o.region;

Produces:

SelectStmt {
    SelectList: [
        ColumnRef{Table: "o", Name: "region"},
        FunctionCall{Name: "SUM", Args: [ColumnRef{Table: "o", Name: "amount"}]}
    ],
    From: TableRef{Name: "orders", Alias: "o"},
    Where: BinaryExpr{
        Left:  ColumnRef{Table: "o", Name: "year"},
        Op:    ">",
        Right: IntLit{Value: 2023}
    },
    GroupBy: [ColumnRef{Table: "o", Name: "region"}]
}

This AST is pure syntax — it doesn’t know whether orders is a real table, whether region is a valid column, or what type amount is. That’s the binder’s job in Phase 9.

Summary

The parser converts SQL text into a structured AST through two stages: lexing (character stream → tokens) and recursive descent parsing (token stream → AST). Operator precedence is handled by nesting parse functions. The AST captures the full structure of SELECT, CREATE TABLE, INSERT, and COPY statements, ready for semantic analysis and planning in the next phase.