◄ prev contents next ►

⚠

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

0507: SQL Range Query

Connect to DB.Range()

We can finally add range queries to SQL:

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

That is, connect the WHERE condition to the existing DB.Range():

type RangeReq struct {
    StartCmp ExprOp // <= >= < >
    StopCmp  ExprOp
    Start    []Cell
    Stop     []Cell
}

func (db *DB) Range(schema *Schema, req *RangeReq) (*RowIterator, error)

SELECT, UPDATE, and DELETE all need changes. Add execCond() to handle WHERE:

func (db *DB) execCond(schema *Schema, cond interface{}) (*RowIterator, error) {
    req, err := makeRange(schema, cond)
    if err != nil {
        return nil, err
    }
    return db.Range(schema, req)
}

func (db *DB) execSelect(stmt *StmtSelect) (output []Row, err error) {
    // ...
    iter, err := db.execCond(&schema, stmt.cond)
    for ; err == nil && iter.Valid(); err = iter.Next() {
        // ...
    }
    // ...
}

The main work of this step is makeRange():

func makeRange(schema *Schema, cond interface{}) (*RangeReq, error)

Parse Tuples

To support syntax like (a, b) < (1, 2), add a struct and update parenthesis handling:

type ExprTuple struct {
    kids []interface{}
}

func (p *Parser) parseAtom() (expr interface{}, err error) {
    if p.tryPunctuation("(") {
        p.pos--
        return p.parseTuple()
    }
    // ...
}
func (p *Parser) parseTuple() (expr interface{}, err error)

Detect Range Queries

Querying a = 123 is the same as 123 <= a AND a <= 123, so single primary key queries can also use range queries. The old DB.Select() can use this shortcut.

func makeRange(schema *Schema, cond interface{}) (*RangeReq, error) {
    if keys, ok := matchAllEq(cond, nil); ok {
        if pkey, ok := extractPKey(schema, keys); ok {
            return &RangeReq{
                StartCmp: OP_GE,
                StopCmp:  OP_LE,
                Start:    pkey,
                Stop:     pkey,
            }, nil
        }
    }
    if req, ok := matchRange(schema, cond); ok {
        return req, nil
    }
    return nil, errors.New("unimplemented WHERE")
}

Matching expressions is just a set of if-else cases, which the reader can implement:

func matchRange(schema *Schema, cond interface{}) (*RangeReq, bool) {
    binop, ok := cond.(*ExprBinOp)
    if ok && binop.op == OP_AND {
        // a > 1 AND a < 2
    } else if ok {
        // a > 1
    }
    return nil, false
}

Only a single range is supported now. To support OR, it would map to multiple DB.Range() calls, and it is best to simplify range unions and intersections. You get the idea, but the implementation is tendious, so we stop here.

ⓘ

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

◄ prev contents next ►