⚠

The web version only has simple instructions since chapter 04, while the full book has detailed explanations and background info.

0501: Infix Expressions

Represent Expressions as Trees

To add range query to SQL, we need to parse more complex syntax. Earlier, we could only parse this fixed form of WHERE:

select a, b from t where a = 123 and b = 456;

Now we need to support these forms:

select a, b from t where a > 123;
select a, b from t where (a, b) > (123, 0);

We need a data structure to represent the expressions in WHERE:

type ExprBinOp struct {
    op    ExprOp
    left  interface{}
    right interface{}
}

For example:

// a = 123 and b = 456
ExprBinOp{op: OP_AND,
    left:  &ExprBinOp{op: OP_EQ,
        left: "a",
        right: &Cell{Type: TypeI64, I64: 123}},
    right: &ExprBinOp{op: OP_EQ,
        left: "b",
        right: &Cell{Type: TypeI64, I64: 456}}}
// a > 123
ExprBinOp{op: OP_GT,
    left:  "a",
    right: &Cell{Type: TypeI64, I64: 123}}

Using interface{} can refer to any data type. It is similar to void * in C/C++, but it keeps type info, so it can be checked and cast back. Here we use 3 kinds of types:

Parse Infix Expressions

In this step, we ignore operator priority and only parse expressions with +-:

// a
"a"
// a + b
&ExprBinOp{op: OP_ADD, left: "a", right: "b"}
// a + b - 3
&ExprBinOp{op: OP_SUB,
    left:  &ExprBinOp{op: OP_ADD, left: "a", right: "b"},
    right: &Cell{Type: TypeI64, I64: 123}}

The operands include column names and constants, and return interface{}:

func (p *Parser) parseAtom() (interface{}, error) {
    if name, ok := p.tryName(); ok {
        return name, nil
    }
    cell := &Cell{}
    if err := p.parseValue(cell); err != nil {
        return nil, err
    }
    return cell, nil
}

Implement the parseAdd() function. It loops and calls parseAtom() and tryPunctuation():

func (p *Parser) parseAdd() (interface{}, error)

ⓘ

CodeCrafters.io has similar courses in many programming languages, including build your own Redis, SQLite, Docker, etc. It’s worth checking out.