I hated writing documentation before working on features. But after a while I realized I couldn't communicate well enough, even with folks I had a good connection with. It took me a number of mistaken deliveries to get the message.
Designers solve this by producing low-fidelity sketches early on in the process, iterating on feedback to produce a high-fidelity mockup. I solve this by producing short RFC (request for comment) documents. This isn't an original idea, but I see it so rarely I wanted to share.
Now as soon as I begin thinking about a technical or organizational change, I write an RFC. My RFCs are typically a page or two long and typically take me 30-60 minutes for a good first draft. I make clear in the title that it is a proposal or draft. This allows me to make crazy suggestions without upsetting folks; a draft can be easily thrown away.
My RFCs include three key sections:
After I write the first draft I circulate it among a small group of peers I respect, my boss, etc. I request feedback at leisure and I check in every few days with a reminder. If no one responds after a while and there is little concern, I typically move forward with the proposed solution.
In addition to clarifying intent up front, this removes the need to schedule a meeting to discuss a problem. Discussion and decisions can be held asynchronously. I only schedule a meeting if there is disagreement that is unable to be resolved in writing.
After incorporating feedback, I either throw away the RFC and move on or feel reasonably confident about the proposal. I send it out to a wider group of relevant participants. Final meetings are held as needed.
In contrast, synchronous-first and undocumented proposals make some sense when you've got a small team in the same timezone with a similar schedule. Otherwise, you repeatedly reschedule meetings to accommodate everyone. You spend your first few meetings simply coming to understand and agree on the problem.
Spending 30-60 minutes to draft a proposal is almost always easier. It makes the decision-making process faster and produces more accurate results.
Spending 30-60 minutes to draft a technical (or organizational) proposal is almost always easier for discussion and action than just scheduling a meeting. Or "my asynchronous-first manifesto"https://t.co/gm4SUzBD2W
— Phil Eaton (@phil_eaton) May 16, 2020
Previously in database basics:
<! forgive me, for I have sinned >
1. SELECT, INSERT, CREATE and a REPL
2. binary expressions and WHERE filters
3. indexes
In this post, we'll extend gosql
to implement the database/sql driver interface. This will
allow us to interact with gosql the same way we would interact with
any other database.
Here is an example familiar program (stored in
cmd/sqlexample/main.go) we'll be able to run:
package main
import (
"database/sql"
"fmt"
_ "github.com/eatonphil/gosql"
)
func main() {
db, err := sql.Open("postgres", "")
if err != nil {
panic(err)
}
defer db.Close()
_, err = db.Query("CREATE TABLE users (name TEXT, age INT);")
if err != nil {
panic(err)
}
_, err = db.Query("INSERT INTO users VALUES ('Terry', 45);")
if err != nil {
panic(err)
}
_, err = db.Query("INSERT INTO users VALUES ('Anette', 57);")
if err != nil {
panic(err)
}
rows, err := db.Query("SELECT name, age FROM users;")
if err != nil {
panic(err)
}
var name string
var age uint64
defer rows.Close()
for rows.Next() {
err := rows.Scan(&name, &age)
if err != nil {
panic(err)
}
fmt.Printf("Name: %s, Age: %d\n", name, age)
}
if err = rows.Err(); err != nil {
panic(err)
}
}
Our gosql driver will use a single instance of the
Backend for all connections.
Aside from that, it is a simple matter of wrapping our existing APIs
in structs that implement the database/sql/driver.Driver
interface.
This post is largely a discussion of this commit.
A driver is registered by calling sql.Register with a
driver instance.
We'll add the registration code to an init function in a
new file, driver.go:
struct Driver {
bkd Backend
}
func init() {
sql.Register("postgres", &Driver{NewMemoryBackend()})
}
According to the Driver
interface, we
need only implement Open to return an connection instance
that implements the database/sql/driver.Conn interface.
type Driver struct {
bkd Backend
}
func (d *Driver) Open(name string) (driver.Conn, error) {
return &Conn{d.bkd}, nil
}
func init() {
sql.Register("postgres", &Driver{NewMemoryBackend()})
}
According to the Conn interface, we must implement:
Prepare(query string) (driver.Stmt, error) to handle prepared statementsClose to handle cleanupBegin to start a transactionThe connection can also optionally implement Query and
Exec.
To simplify things we'll panic on Prepare and on
Begin (we don't have transactions yet). There's no
cleanup required so we'll do nothing in Close.
type Conn struct {
bkd Backend
}
func (dc *Conn) Prepare(query string) (driver.Stmt, error) {
panic("Prepare not implemented")
}
func (dc *Conn) Begin() (driver.Tx, error) {
panic("Begin not implemented")
}
func (dc *Conn) Close() error {
return nil
}
The only method we actually need, Query, is not required
by the interface. It takes a query string and array of query
parameters, returning an instance implementing
the database/sql/driver.Rows interface.
To implement Query, we basically copy the logic we had in
the cmd/main.go REPL. The only change is that when we
return results when handling SELECT, we'll return a
struct that implements the database/sql/driver.Rows
interface.
database/sql/driver.Rows is not the same type as
database/sql.Rows, which may sound more
familiar. database/sql/driver.Rows is a simpler,
lower-level interface.
If we receive parameterized query arguments, we'll ignore them for now. And if the query involves multiple statements, we'll process only the first statement.
func (dc *Conn) Query(query string, args []driver.Value) (driver.Rows, error) {
if len(args) > 0 {
// TODO: support parameterization
panic("Parameterization not supported")
}
parser := Parser{}
ast, err := parser.Parse(query)
if err != nil {
return nil, fmt.Errorf("Error while parsing: %s", err)
}
// NOTE: ignorning all but the first statement
stmt := ast.Statements[0]
switch stmt.Kind {
case CreateIndexKind:
err = dc.bkd.CreateIndex(stmt.CreateIndexStatement)
if err != nil {
return nil, fmt.Errorf("Error adding index on table: %s", err)
}
case CreateTableKind:
err = dc.bkd.CreateTable(stmt.CreateTableStatement)
if err != nil {
return nil, fmt.Errorf("Error creating table: %s", err)
}
case DropTableKind:
err = dc.bkd.DropTable(stmt.DropTableStatement)
if err != nil {
return nil, fmt.Errorf("Error dropping table: %s", err)
}
case InsertKind:
err = dc.bkd.Insert(stmt.InsertStatement)
if err != nil {
return nil, fmt.Errorf("Error inserting values: %s", err)
}
case SelectKind:
results, err := dc.bkd.Select(stmt.SelectStatement)
if err != nil {
return nil, err
}
return &Rows{
rows: results.Rows,
columns: results.Columns,
index: 0,
}, nil
}
return nil, nil
}
According to the Rows interface we must implement:
Columns() []string to return an array of columns namesNext(dest []Value) error to populate an row array with the next row's worth of cellsClose() errorOur Rows struct will contain the rows and colums as
returned from Backend, and will also contain an
index field we can use in Next to populate
the next row of cells.
type Rows struct {
columns []ResultColumn
index uint64
rows [][]Cell
}
func (r *Rows) Columns() []string {}
func (r *Rows) Close() error {}
func (r *Rows) Next(dest []driver.Value) error {}
For Columns we simply need to extract and
return the column names from ResultColumn.
func (r *Rows) Columns() []string {
columns := []string{}
for _, c := range r.columns {
columns = append(columns, c.Name)
}
return columns
}
For Next we need to iterate over each cell in the current
row and retrieve its Go value, storing it in dest. The
dest argument is simply a fixed-length array of
interface{}, so we'll need no manual conversion.
Once we've reached the last row, the Next contract is to
return an io.EOF.
func (r *Rows) Next(dest []driver.Value) error {
if r.index >= uint64(len(r.rows)) {
return io.EOF
}
row := r.rows[r.index]
for idx, cell := range row {
typ := r.columns[idx].Type
switch typ {
case IntType:
i := cell.AsInt()
if i == nil {
dest[idx] = i
} else {
dest[idx] = *i
}
case TextType:
s := cell.AsText()
if s == nil {
dest[idx] = s
} else {
dest[idx] = *s
}
case BoolType:
b := cell.AsBool()
if b == nil {
dest[idx] = b
} else {
dest[idx] = b
}
}
}
r.index++
return nil
}
Finally in Close we'll set index higher than
the number of rows to force Next to only ever
return io.EOF.
func (r *Rows) Close() error {
r.index = uint64(len(r.rows))
return nil
}
And that's all the changes needed to implement a
database/sql driver! See
here
for driver.go in full.
With the driver in place we can try out the example:
$ go build ./cmd/sqlexample/main.go
$ ./main
Name: Terry, Age: 45
Name: Anette, Age: 57
Next post in the database basics series, implementing a database/sql driver for more seamless interactions in Go.https://t.co/AUZfUByNGE
— Phil Eaton (@phil_eaton) May 10, 2020
Previously in database basics:
<! forgive me, for I have sinned >
1. SELECT, INSERT, CREATE and a REPL
2. binary expressions and WHERE filters
Next in database basics:
4. a database/sql driver
In this post, we extend gosql
to support indexes. We focus on the addition of PRIMARY
KEY constraints on table creation and some easy optimizations
during SELECT statements.
$ go run cmd/main.go
Welcome to gosql.
# CREATE TABLE users (id INT PRIMARY KEY, name TEXT, age INT);
ok
# \d users
Table "users"
Column | Type | Nullable
---------+---------+-----------
id | integer | not null
name | text |
age | integer |
Indexes:
"users_pkey" PRIMARY KEY, rbtree ("id")
This post will broadly be a discussion of this commit.
An index is a mapping of a value to a row in a table. The value is
often a column, but it can be many kinds of expressions. Databases
typically store indexes in tree structures that provide O(log(n))
lookup time. When SELECTing and filtering on a column
that is indexed, a database can greatly improve lookup time by
filtering first on this index. Without an index, a database must do a
linear scan for matching rows. Though sometimes if a condition is
broad enough, even with an index, a database may still end up doing a
linear scan.
While it may make sense initially to map a value to a row using a hash
table for constant lookup times, hash tables don't provide
ordering. So this would prevent an index from being applicable on
anything but equality checks. For example, SELECT x FROM y WHERE
x > 2 couldn't use a hash index on x.
Indexes in many SQL databases default to a B-Tree, which offers efficient ordering of elements. These indexes are thus not constant-time lookups even if filtering on a unique column for a single item. Some databases, like PostgreSQL, allow you to use a hash-based index instead of a tree. Here the previously listed restrictions apply (i.e. only equality checks will use the index).
We proceed as follows:
INSERTs to let any indexes on the table process the new rowSELECTs to make use of any indexes, if possibleTo allow the specification of a single column as the primary key when creating a table, we have to first modify the lexer and parser.
Since we've covered this process a few times already suffice it so say we make the following key additions:
PRIMARY KEY as a new keyword token to the lexerNext we move on to handling a primary key during table creation.
Since there are many existing papers and blogs on implementing tree data structures, we will import an open-source implementation. And while most databases use a B-Tree, the most important properties of the tree for our purposes are 1) efficient ordering and 2) optionally duplicate keys. We go with a Red-Black Tree, GoLLRB.
The full definition of an index now includes:
rbtree for now)type index struct {
name string
exp expression
unique bool
primaryKey bool
tree *llrb.LLRB
typ string
}
When we create a table, we add an index if one of the columns is a
primary key. We call out to a new public
method, CreateIndex, that will handle actually setting
things up.
func (mb *MemoryBackend) CreateTable(crt *CreateTableStatement) error {
if _, ok := mb.tables[crt.name.value]; ok {
return ErrTableAlreadyExists
}
t := createTable()
t.name = crt.name.value
mb.tables[t.name] = t
if crt.cols == nil {
return nil
}
var primaryKey *expression = nil
for _, col := range *crt.cols {
t.columns = append(t.columns, col.name.value)
var dt ColumnType
switch col.datatype.value {
case "int":
dt = IntType
case "text":
dt = TextType
case "boolean":
dt = BoolType
default:
delete(mb.tables, t.name)
return ErrInvalidDatatype
}
if col.primaryKey {
if primaryKey != nil {
delete(mb.tables, t.name)
return ErrPrimaryKeyAlreadyExists
}
primaryKey = &expression{
literal: &col.name,
kind: literalKind,
}
}
t.columnTypes = append(t.columnTypes, dt)
}
if primaryKey != nil {
err := mb.CreateIndex(&CreateIndexStatement{
table: crt.name,
name: token{value: t.name + "_pkey"},
unique: true,
primaryKey: true,
exp: *primaryKey,
})
if err != nil {
delete(mb.tables, t.name)
return err
}
}
return nil
}
Implementing CreateIndex is just a matter of adding a new
index to the table.
func (mb *MemoryBackend) CreateIndex(ci *CreateIndexStatement) error {
table, ok := mb.tables[ci.table.value]
if !ok {
return ErrTableDoesNotExist
}
for _, index := range table.indexes {
if index.name == ci.name.value {
return ErrIndexAlreadyExists
}
}
index := &index{
exp: ci.exp,
unique: ci.unique,
primaryKey: ci.primaryKey,
name: ci.name.value,
tree: llrb.New(),
typ: "rbtree",
}
table.indexes = append(table.indexes, index)
return nil
}
And that's it for creation of tables and indexes! Table creation is also the last time we need to make changes to the gosql frontend. The rest of the changes simply wrap existing insertion and selection.
When a row is inserted into a table, each index on that table needs to process the row so it can add value-to-row mappings to the index.
In the project code, you'll notice logic in CreateIndex
to also go back over all existing rows to add them to the new index.
This post omits further discussing the case where an index is
created after a table is created. After reading this post, that case
should be easy to follow.
Adding a row to an index is a matter of evaluting the index expression against that row and storing the resulting value in the tree. Along with the value, we store the integer index of the row in the table.
If the index is required to be unique, we first check that the value does not yet exist.
func (i *index) addRow(t *table, rowIndex uint) error {
indexValue, _, _, err := t.evaluateCell(rowIndex, i.exp)
if err != nil {
return err
}
if indexValue == nil {
return ErrViolatesNotNullConstraint
}
if i.unique && i.tree.Has(treeItem{value: indexValue}) {
return ErrViolatesUniqueConstraint
}
i.tree.InsertNoReplace(treeItem{
value: indexValue,
index: rowIndex,
})
return nil
}
And that's it for insertion!
Until now, the logic for selecting rows from a table is to pick the
table and iterate over all rows. If the row does not match
the WHERE filter, we pass the row.
If the table has an index and we are using the index in a recognized
pattern in the WHERE AST (more on that later), we can
pre-filter the table based on the index before iterating over each
row. We can do this for each index and for each time a recognized
pattern shows up.
This process is called query planning. We build a simplified
version of what you may see in SQL databases, specifically focusing
on index usage since we don't yet support JOINs. For
further reading, SQLite has
an excellent
document on their query planner for index usage.
func (mb *MemoryBackend) Select(slct *SelectStatement) (*Results, error) {
t := createTable()
if slct.from != nil {
var ok bool
t, ok = mb.tables[slct.from.value]
if !ok {
return nil, ErrTableDoesNotExist
}
}
if slct.item == nil || len(*slct.item) == 0 {
return &Results{}, nil
}
results := [][]Cell{}
columns := []ResultColumn{}
if slct.from == nil {
t = createTable()
t.rows = [][]memoryCell{{}}
}
for _, iAndE := range t.getApplicableIndexes(slct.where) {
index := iAndE.i
exp := iAndE.e
t = index.newTableFromSubset(t, exp)
}
for i := range t.rows {
result := []Cell{}
isFirstRow := len(results) == 0
if slct.where != nil {
val, _, _, err := t.evaluateCell(uint(i), *slct.where)
if err != nil {
return nil, err
}
if !*val.AsBool() {
continue
}
}
for _, col := range finalItems {
value, columnName, columnType, err := t.evaluateCell(uint(i), *col.exp)
if err != nil {
return nil, err
}
if isFirstRow {
columns = append(columns, ResultColumn{
Type: columnType,
Name: columnName,
})
}
result = append(result, value)
}
results = append(results, result)
}
return &Results{
Columns: columns,
Rows: results,
}, nil
}
It's very simple and easy to miss, here is the change called out:
for _, iAndE := range t.getApplicableIndexes(slct.where) {
index := iAndE.i
exp := iAndE.e
t = index.newTableFromSubset(t, exp)
}
There are probably a few very simple patterns we could look for, but
for now we look for boolean expressions joined by AND
that contain an index expression.
func (t *table) getApplicableIndexes(where *expression) []indexAndExpression {
var linearizeExpressions func(where *expression, exps []expression) []expression
linearizeExpressions = func(where *expression, exps []expression) []expression {
if where == nil || where.kind != binaryKind {
return exps
}
if where.binary.op.value == string(orKeyword) {
return exps
}
if where.binary.op.value == string(andKeyword) {
exps := linearizeExpressions(&where.binary.a, exps)
return linearizeExpressions(&where.binary.b, exps)
}
return append(exps, *where)
}
exps := linearizeExpressions(where, []expression{})
iAndE := []indexAndExpression{}
for _, exp := range exps {
for _, index := range t.indexes {
if index.applicableValue(exp) != nil {
iAndE = append(iAndE, indexAndExpression{
i: index,
e: exp,
})
}
}
}
return iAndE
}
More specifically though, within binary operations we only support matching on an index if the following three conditions are met:
=,
>, <, >=, or
<=exp valueThis is a simpler, stricter matching of an index than PostgreSQL where you can index expressions more generally, not just identifer literals.
func (i *index) applicableValue(exp expression) *expression {
if exp.kind != binaryKind {
return nil
}
be := exp.binary
// Find the column and the value in the boolean expression
columnExp := be.a
valueExp := be.b
if columnExp.generateCode() != i.exp.generateCode() {
columnExp = be.b
valueExp = be.a
}
// Neither side is applicable, return nil
if columnExp.generateCode() != i.exp.generateCode() {
return nil
}
supportedChecks := []symbol{eqSymbol, neqSymbol, gtSymbol, gteSymbol, ltSymbol, lteSymbol}
supported := false
for _, sym := range supportedChecks {
if string(sym) == be.op.value {
supported = true
break
}
}
if !supported {
return nil
}
if valueExp.kind != literalKind {
fmt.Println("Only index checks on literals supported")
return nil
}
return &valueExp
}
And that's it for finding applicable indexes.
The last remaining piece is to go from a boolean expression in
a WHERE clause (where an index is applicable) to a subset
of rows in a table.
Since we are only working with patterns of the type
indexed-column OP literal-value, we grab the literal
using the previous applicableValue helper. Then we
look up that literal value in the index and return a new table with
every row in the index that meets the condition of the operator for the
literal value.
func (i *index) newTableFromSubset(t *table, exp expression) *table {
valueExp := i.applicableValue(exp)
if valueExp == nil {
return t
}
value, _, _, err := createTable().evaluateCell(0, *valueExp)
if err != nil {
fmt.Println(err)
return t
}
tiValue := treeItem{value: value}
indexes := []uint{}
switch symbol(exp.binary.op.value) {
case eqSymbol:
i.tree.AscendGreaterOrEqual(tiValue, func(i llrb.Item) bool {
ti := i.(treeItem)
if !bytes.Equal(ti.value, value) {
return false
}
indexes = append(indexes, ti.index)
return true
})
case neqSymbol:
i.tree.AscendGreaterOrEqual(llrb.Inf(-1), func(i llrb.Item) bool {
ti := i.(treeItem)
if bytes.Equal(ti.value, value) {
indexes = append(indexes, ti.index)
}
return true
})
case ltSymbol:
i.tree.DescendLessOrEqual(tiValue, func(i llrb.Item) bool {
ti := i.(treeItem)
if bytes.Compare(ti.value, value) < 0 {
indexes = append(indexes, ti.index)
}
return true
})
case lteSymbol:
i.tree.DescendLessOrEqual(tiValue, func(i llrb.Item) bool {
ti := i.(treeItem)
if bytes.Compare(ti.value, value) <= 0 {
indexes = append(indexes, ti.index)
}
return true
})
case gtSymbol:
i.tree.AscendGreaterOrEqual(tiValue, func(i llrb.Item) bool {
ti := i.(treeItem)
if bytes.Compare(ti.value, value) > 0 {
indexes = append(indexes, ti.index)
}
return true
})
case gteSymbol:
i.tree.AscendGreaterOrEqual(tiValue, func(i llrb.Item) bool {
ti := i.(treeItem)
if bytes.Compare(ti.value, value) >= 0 {
indexes = append(indexes, ti.index)
}
return true
})
}
newT := createTable()
newT.columns = t.columns
newT.columnTypes = t.columnTypes
newT.indexes = t.indexes
newT.rows = [][]memoryCell{}
for _, index := range indexes {
newT.rows = append(newT.rows, t.rows[index])
}
return newT
}
As you can see, an index may not necessarily improve on a linear
search in some conditions. Imagine a table of 1 million rows indexed
on an autoincrementing column. Imagine filtering on col >
10. The index may be able to eliminate 10 items but still
return a pre-filtered table of around 1 million rows that must
be passed through the WHERE filter.
Additionally since we process each boolean expression one at a time,
we can't take advantage of knowledge that might seem obvious to a
human for two boolean expressions that together bound a range. For
example in x > 10 AND x < 20 we can see that only
integers from 11 to 19 are applicable. But the current logic would go
through each expression separately and find all rows that match either
before the final linear search through all pre-filtered rows would
eliminate the bulk.
Thankfully real databases have decades of optimizations. But even
then it can be difficult to know what index usages are being
optimized without reading documentation, benchmarking, using
EXPLAIN ANALYSE, or reading the source.
But that's it for changes needed to support basic indexes end-to-end!
Since the addition of indexes is so seamless, it is difficult to tell without trial that the index is effective. So we write a simple program that inserts N rows with and without an index. Finally it will query for the first and last items inserted. We show time and memory used during both insertion and selection.
package main
import (
"fmt"
"os"
"runtime"
"strconv"
"time"
"github.com/eatonphil/gosql"
)
var inserts = 0
var lastId = 0
var firstId = 0
func doInsert(mb gosql.Backend) {
parser := gosql.Parser{}
for i := 0; i < inserts; i++ {
lastId = i
if i == 0 {
firstId = lastId
}
ast, err := parser.Parse(fmt.Sprintf("INSERT INTO users VALUES (%d)", lastId))
if err != nil {
panic(err)
}
err = mb.Insert(ast.Statements[0].InsertStatement)
if err != nil {
panic(err)
}
}
}
func doSelect(mb gosql.Backend) {
parser := gosql.Parser{}
ast, err := parser.Parse(fmt.Sprintf("SELECT id FROM users WHERE id = %d", lastId))
if err != nil {
panic(err)
}
r, err := mb.Select(ast.Statements[0].SelectStatement)
if err != nil {
panic(err)
}
if len(r.Rows) != 1 {
panic("Expected 1 row")
}
if int(*r.Rows[0][1].AsInt()) != inserts-1 {
panic(fmt.Sprintf("Bad row, got: %d", r.Rows[0][1].AsInt()))
}
ast, err = parser.Parse(fmt.Sprintf("SELECT id FROM users WHERE id = %d", firstId))
if err != nil {
panic(err)
}
r, err = mb.Select(ast.Statements[0].SelectStatement)
if err != nil {
panic(err)
}
if len(r.Rows) != 1 {
panic("Expected 1 row")
}
if int(*r.Rows[0][1].AsInt()) != 0 {
panic(fmt.Sprintf("Bad row, got: %d", r.Rows[0][1].AsInt()))
}
}
func perf(name string, b gosql.Backend, cb func(b gosql.Backend)) {
start := time.Now()
fmt.Println("Starting", name)
cb(b)
fmt.Printf("Finished %s: %f seconds\n", name, time.Since(start).Seconds())
var m runtime.MemStats
runtime.ReadMemStats(&m)
fmt.Printf("Alloc = %d MiB\n\n", m.Alloc/1024/1024)
}
func main() {
mb := gosql.NewMemoryBackend()
index := false
for i, arg := range os.Args {
if arg == "--with-index" {
index = true
}
if arg == "--inserts" {
inserts, _ = strconv.Atoi(os.Args[i+1])
}
}
primaryKey := ""
if index {
primaryKey = " PRIMARY KEY"
}
parser := gosql.Parser{}
ast, err ... (truncated)