⚠

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

0404: Row Iterator

Iterator Interface

Now that sort order is right, we can build range queries on top of KV.Seek():

// Return the first position >= primary key
func (db *DB) Seek(schema *Schema, row Row) (*RowIterator, error)

// Is iteration finished?
func (iter *RowIterator) Valid() bool
// Current row
func (iter *RowIterator) Row() Row
// Move forward
func (iter *RowIterator) Next() error

This converts KV pairs from KVIterator into rows. There is one issue: keys of different tables are split by prefixes, so during scan we must check whether a key belongs to a table. Update Row.DecodeKey() so that when a key does not belong to the table, it returns ErrOutOfRange:

var ErrOutOfRange = errors.New("out of range")

func (row Row) DecodeKey(schema *Schema, key []byte) (err error) {
    if len(key) < len(schema.Table)+1 {
        return ErrOutOfRange
    }
    if string(key[:len(schema.Table)+1]) != schema.Table+"\x00" {
        return ErrOutOfRange
    }
    // ...
}

Iterator Implementation

RowIterator is a wrapper around KVIterator. After moving KVIterator, we must decode KV and check ErrOutOfRange, so the decoded row needs to be stored somewhere.

type RowIterator struct {
    schema *Schema
    iter   *KVIterator
    valid  bool // decode result (err != ErrOutOfRange)
    row    Row  // decode result
}

Valid() and Row() just return stored results:

func (iter *RowIterator) Valid() bool { return iter.valid }
func (iter *RowIterator) Row() Row    { return iter.row }

Decode the result after the iterator is moved or created:

func (iter *RowIterator) Next() (err error) {
    if err = iter.iter.Next(); err != nil {
        return err
    }
    iter.valid, err = decodeKVIter(iter.schema, iter.iter, iter.row)
    return err
}

The remaining functions are left to the reader:

func decodeKVIter(schema *Schema, iter *KVIterator, row Row) (bool, error)
func (db *DB) Seek(schema *Schema, row Row) (*RowIterator, error)

Summary

Another core database feature is done: range query. Next steps:

ⓘ

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