Conscious Incompetence

Code generation in Vitess

2021-03-23T00:00:00+00:00

Code generation in Vitess

Golang is a wonderful language. It’s simple, and most of the time not confusing or surprising. This makes it easy to jump into library code and start reading and quickly understand what’s going on. On the other hand, coming from other languages, there are a few features that would make our lives easier.

We are building Vitess using mostly golang, and most of us are happy with this choice. However, because of missing features in the language, we’ve had to build some tooling manually.

Here follows a list of how we are using meta programming in Vitess.

GRPC messages and endpoints

Everyone uses code generation for protobuf, so that’s very interesting to write about. Moving on.

SQL Parser

We use goyacc to build our parser. Goyacc reads input in the form of a sql.y file, and it outputs the sql.go parser we use. Writing this manually would not really have been an option. The code would probably become slow and very difficult to maintain. To speed up the parser to ludicrous speed, we forked the goyacc code and adapted it to our needs. You can read more about this work here.

Memory usage for plans

Query planning is a resource intensive task, and to make sure we don’t have to do that more than necessary, we cache plans. Whenever you are caching, you need to be concerned about the size of your caches - you don’t want the cache to eat too much memory. To do that, you need information about how much memory plan tree consume. And this is one of the shortcoming of golang - it’s very difficult to do this. So, again, meta generation came to the rescue.

Go comes with excellent parser and tokeniser tools to allow you to read Go code as a stream of AST objects. Unfortunately, we need more than syntax when looking at our plans to make sense of them - we also need dependencies and type information. To get this, we use golang.org/x/tools/go/packages.

What we do is to first find the plan struct, and from that, we find all types that are used by the fields of the plan.

type Plan struct {
    Type         sqlparser.StatementType 
    Original     string
    Instructions Primitive
    BindVarNeeds *sqlparser.BindVarNeeds
    Warnings     []*querypb.QueryWarning
}

For every type that we encounter, we create a CachedSize method that can calculate the memory size of an instance. If the type happens to be an interface, we instead find all implementations and do the same exercise again. This is done until we have a method for all types that might show up in a plan-tree. You can look at what the these functions look like here.

AST tooling

After parsing, the tree structure that contains the original query has been turned into an abstract syntax tree, or an AST. It contains the information we need from the query, with the uninteresting bits such as whitespaces removed. It’s a type safe version of the query the user sent us.

Our AST is pretty large, and many developers work on it, adding new types and fields all the time.

In order to plan queries, we needed a couple of utilities for our AST that Go does not provide for us.

First of, we needed to be able to traverse the AST - a plain old visitor that could traverse the whole tree quickly. Check out the code
We also need the ability to replace parts of the node. This is much like the visitor, but with a way to replace the node that is currently being visited. Check out the code
We need a way of doing equality comparisons without using reflect.DeepEqual. Struct comparisons in Go work as expected, until you have references in your structs. Then all bets are off. DeepEqual does what we need, but it does so slowly. Comparing our generated equality methods vs reflect.DeepEqual gives:

name       old time/op  new time/op  delta
Equals-16   813µs ± 0%    11µs ± 1%  -98.64%  (p=0.000 n=9+9)

The reflect.DeepEqual is >72 times slower than our generated comparator. Check out the code

We also need to be able to do a deep-clone of the AST. While exploring different alternative plans, we clone parts of the AST, so we can change it without changing the original. Check out the code
Finally, our AST knows how to print itself. This is a little trickier than you might think, because we do precedence calculations for expressions to figure out where we need parenthesis. To make this easy to write, we use something that looks a lot like printf - this allows us developers to write nicely readable code. Unfortunately, this is not very fast, since it basically means that we have to parse strings to be able to produce strings. Again, using the go/packages library, we can read the astPrintf lines, and then output a faster form of the same. The method that a developer would write would look something like:

func (node *ComparisonExpr) Format(buf *TrackedBuffer) {
	buf.astPrintf(node, "%l %s %r", node.Left, node.Operator.ToString(), node.Right)
	if node.Escape != nil {
		buf.astPrintf(node, " escape %v", node.Escape)
	}
}

After code generation, the output becomes:

func (node *ComparisonExpr) formatFast(buf *TrackedBuffer) {
	buf.printExpr(node, node.Left, true)
	buf.WriteByte(' ')
	buf.WriteString(node.Operator.ToString())
	buf.WriteByte(' ')
	buf.printExpr(node, node.Right, false)
	if node.Escape != nil {
		buf.WriteString(" escape ")
		buf.printExpr(node, node.Escape, true)
	}
}

How to make it work

One learning we have had, is that it’s a good idea to hide the generated code behind an easy-to-use API. That is the method that the rest of the code base will interact with, not directly with the generated code. This gives us the chance to drastically change what the generated code looks like, but not have to change anything else in the code base. We use this pattern for the parser, for the rewriter, and for the visitor.

Summary

We use code generation for two main reasons. We are easily bored people, so writing lots of repetitive code would be no fun. This code would be difficult to write correctly, and annoying to review. Using meta programming, we can avoid the repetitive code that is hard to get right and easy to mess up.

The second reason is that it’s just easier to write fast code this way. We benchmark and profile the generated code pretty hard, and make sure to squeeze as much juice as possible. Then we change the generator, and wham! 642 rewriter methods have been updated. This would not really have been possible if we had to change those methods manually.

Honorable mention: Most of this code is either written by, or heavily influenced by the latest developer luminary to join the PlanetScale and Vitess ranks - @vmg

Life of a Vitess Query - Query Graph

2021-02-08T00:00:00+00:00

Life of a Vitess Query - Query Graph

(This is a post in a series. You should start here: Parsing and Rewriting)

The process of plan building is all about evaluating in which order to execute joins find the cheapest join combination we can use.

So, we need a better data structure than a tree to represent this, and the title of this post has probably spoiled which one that is.

A graph is perfect for this problem.
Tables are the nodes, and the join predicates are the relationships between them.

As a struct, what I ended up using looks something like this:

type queryGraph struct {
  tables     []*queryTable
  predicates map[semantics.TableSet][]sqlparser.Expr
}

// queryTable is a single FROM table, including all predicates particular to this table
type queryTable struct {
  tableID    semantics.TableSet
  alias      *sqlparser.AliasedTableExpr
  table      sqlparser.TableName
  predicates []sqlparser.Expr
}

Sub queries complicate things, but I’m keeping it simple in these posts and not handling them.

I think of the query graph as the FROM and the WHERE of the query. When doing join ordering, this is actually the only information we need - we don’t need anything else from the AST

Let’s look at those structs a little more. A queryTable struct contains information about a table, and all predicates that only depend on this particular single table.

To find join predicates between two tables, we just do a bit OR between the two TableSet, and use that as the key to search for join predicates between the two tables.

The common solution would probably have been an adjacency matrix, but using a map[semantics.TableSet][]sqlparser.Expr makes it possible to deal with N-way joins, something that would mean extra logic using a matrix.

Just to recap - we start with a query as a string, which is parsed into an AST, that is distilled into a query graph.

This is what we need to do join ordering.

Life of a Vitess Query - Semantic Analysis

2021-02-04T00:00:00+00:00

Life of a Vitess Query - Semantic Analysis

(This is a post in a series. You should start here: Parsing and Rewriting)

By now we have a well formed tree structure representing the query the user sent. Next step is called semantic analysis.

I’ll use the following query to illustrate how it’s done.

SELECT
    tbl.col,
    ( SELECT count(tbl.col)
      FROM otherTable as tbl)
FROM
    tbl

As a tree:

   SELECT (S1)
    ├── Exprs
    │   ├── tbl.col
    │   └── SELECT (S2)
    │       ├── Exprs
    │       │   └── COUNT
    │       │       └── tbl.col
    │       └── FROM
    │           └── otherTable as tbl
    └── FROM
        └── tbl

The main problem we are trying to solve - make it easy for the planner to know which table is meant when it encounters tbl.col.

We start by figuring out which scopes exist, and which tables exist in each scope.

Given this information, we can look at column expressions and resolve which tables are being referenced.

Let’s go over what this would look like for this query.

We start traversing the tree at the root, S1. Since this is a SELECT struct, we push a new scope on to the scope stack, and visit the FROM clause next.

The scope stack, after visiting S1 and its FROM:

(tbl)

Next we visit the SELECT expressions of S1. When we visit the first expression, we take note of the current scope, and move on. Now we know which scope this expression lives in and what tables are available to it.

Next, we’ll visit the subquery that contains S2. When encountering S2, we push another scope on the stack and add the tables S2 to this new scope.

The scope stack, after visiting S2 and its FROM:

(otherTable as tbl)
(tbl)

When visiting the expressions of S2, we note the current scope for the expressions.

There is nothing left of S2 to visit, so we exit the sub query. When coming back up from S2, we pop the top-most scope, and we are ready to do the binding process.

Binding is visiting all the column expressions, and figuring out, given the scoping information, which table the column belongs to. If the user has not provided a qualifier, we need to look up column information for all available tables and check if we can uniquely identify which one the user means. This binding information is stored the semantic table - the output of this process.

To do this as fast as possible, we do this in a single tree traversal, not in to separate steps. This way, we don’t have to remember scope information per expression - we just use the current scope stack, looking down the stack until we find the table.

Also, instead of using strings to reference the dependencies, we use bitmasks, where each table is a bit in an uint64 value. At the end of the semantic processing, we have the dependency information we need in for all expressions in the query.

The devil is in the details, so let me spell it out:

  type TableSet uint64

  type table struct {
    tableName, alias string
  }

  type SemTable struct {
    Tables           []table
    exprDependencies map[sqlparser.Expr]TableSet
  }

The way to get the TableSet for a table is to find the offset in the Tables for the table we are looking for, and then left shift 1 that many steps.

func (st *SemTable) TableSetFor(t table) TableSet {
  for idx, t2 := range st.Tables {
    if t == t2 {
      return 1 << idx
    }
  }
  return 0
}

This information is used to create the query graph, the next stop in the journey to a Vitess execution plan.

Life of a Vitess Query - Parsing and rewriting

2021-02-03T00:00:00+00:00

Life of a Vitess Query - Parsing and rewriting

SQL is a declarative language, which means you tell it what you want done, and the database engine figures out how to do it for you. When I started with databases, this seemed an almost magical process to me, and I have been fascinated by it for decades now.

As my 20% project, I have been working on a new query planner for Vitess, and I wanted to share what the design looks like and what the important characters in this story are. The project is being tracked here.

Before I write more about the details, let me tell you about one driving force behind the design. During plan building, the process of creating and evaluating differ access patterns is the most costly. This is just because of the search space that has to be explored - the number of possible plans grows exponentially with the number of tables involved in the query. So a lot of the steps and complications that come before are done so that this expensive evaluation can be done as efficiently as possible.

Now to the first step during query execution

Step 1 - Parsing

When a query comes to the vtgate executor, it will first parse the query. The input is your query string, and the output is a struct called the AST - abstract syntax tree. Like the name implies, this is a tree shaped struct that represents the interesting parts of query.

Example query:

SELECT t.col + s.col
FROM t 
  JOIN s ON t.id = s.t_id
WHERE (t.foo = 42) 
  AND (s.bar = 'dud')

This query becomes a tree that, simplified, looks something like this:

  SELECT
    ├── Exprs
    │   └── +
    │       ├── t.col
    │       └── s.col
    ├── FROM
    │   └── JOIN
    │       ├── t
    │       ├── s
    │       └── ON
    │           └── =
    │               ├── t.id
    │               └── s.t_id
    └── WHERE
        └── AND
            ├── =
            │   ├── t.foo
            │   └── 42
            └── =
                ├── s.bar
                └── "dud"

We do this because working with strings is slow and clunky, compared to using type safe datastructures like this. Instead of string matching, we can check the fields and types in structs, in order to understand what the user is asking for. It also removes lots of unnecessary details. Parentheses, for example, are only needed because the query comes in as a one-dimensional string. In the tree, the grouping and precedence of expressions is clearly visible in the structure of the tree, and so parenthesis do not exist in the AST. When we need to turn the AST back into a string, we can figure out where we need to inject parens.

I’m not going to go into details about our parsing or AST. It’s fast, used by lots of other projects, and built using yacc.

Step 2 - AST rewriting

Before passing on the AST, we rewrite it a little. We do this for three reasons:

We want queries to share the same plan when possible, so we remove literals.

SELECT 42

is turned into

SELECT :_vtlit1

If we later encounter SELECT 5, we can use the cached plan.
To minimize the work the planner needs to do, we normalize the AST, so the planner doesn’t have to understand two equivalent ways of expressing the same thing.

An example of this is that we make sure that columns are on the left-hand side of equality comparisons.

42 = t.col

is turned into

t.col = 42
A very important part of what Vitess does is to create an illusion for the user.

It’s the illusion of a dedicated connection to a single database, when in reality, Vitess will do connection pooling for you, and spread out your query to sometimes hundreds of MySQL instances. To create the illusion, we rewrite away variables, both system variables and user defined variables, and lots of function calls. We also change queries against the information_schema to use the table and database names that are really used in MySQL.

By the end of these two steps, we are still working with the input query that the user sent, but it’s been massaged into a form that is easier for the planner to work with.

Next up is semantic analysis.

Cypher - A view from a recovering SQL DBA

2011-11-06T00:00:00+00:00

Cypher - A view from a recovering SQL DBA

An SQL query walks into a bar and sees two tables.
He walks up to them and asks ‘Can I join you?’

An SQL query walks into a NOSQL bar, and finds no tables.
So he leaves.

For many years, I worked with SQL databases. I got to know the relational model and various SQL implementations very well, but then the world changed with the advent of NOSQL, and I changed too when I became heavily involved with Neo4j.

I understand that changing from the familiar SQL to the unfamiliar NOSQL query languages is hard: no schemas, JSON all over the place, and no joins? But I’ve made it through the learning curve and so can you. This guide is all about people like us - people who understand SQL. We can use that prior knowledge to quickly get going with Cypher and start exploring Neo4j.

START

SQL starts with the result you want - we SELECT what we want and then declare how to source it. In Cypher, the START clause is quite a different concept which specifies starting points in the graph from which the query will execute.

From a SQL point of view, the identifiers in a START are like table names that point to a set of nodes or relationships. The set can be listed literally, come via parameters, or as I show in the following example, be defined by an index look-up.

So in fact rather than being SELECT-like, the START clause is somewhere between the FROM and the WHERE clause in SQL.

SQL

SELECT *
FROM  Person
WHERE firstName = "Anakin"

Cypher

START anakin=node:persons(firstName = "Anakin")
RETURN anakin

Cypher allows multiple start points. This should not be strange from a SQL perspective - every table in the FROM clause is another start point.

MATCH

Unlike SQL which operates on sets, Cypher predominantly works on subgraphs. The relational equivalent is the current set of tuples being evaluated during a SELECT query.

The shape of the subgraph is specified in the MATCH clause. The MATCH clause is analogous to the JOIN in SQL. A normal a–>b relationship is an inner join between nodes a and b - both sides have to have at least one match, or nothing is returned.

A simple example, where we find all nodes that are connected to node with id 101, through an incoming relationship.

SQL

SELECT bar.*
FROM foo 
JOIN bar ON foo.id = bar.foo_id
WHERE foo.id = 101

Cypher

START foo=node(101)
MATCH foo-->bar
RETURN bar

There is no join table here, but if one is necessary writing the pattern relationship like so: -[foo_bar]-> will introduce (the equivalent of) a join table named foo_bar. In reality this is a named relationship in Cypher, so we’re saying “join foo to bar via foo_bar.” To illustrate this, consider this image, comparing the SQL modell and Neo4j/Cypher.

SQL

SELECT bar.*, foo_bar.*
FROM foo 
  JOIN foo_bar ON foo.id = foo_bar.foo_id 
  JOIN bar ON foo_bar.bar_id = bar.id
WHERE foo.id = 1

Cypher

START foo=node(1)
MATCH foo-[foo_bar]->bar
RETURN bar, foo_bar

An outer join is just as easy. Add a question mark -[?:KNOWS]-> and it’s an optional relationship between nodes - the outer join of Cypher.

Whether it’s a left outer join, or a right outer join is defined by which side of the pattern has a starting point. This first example is a left outer join, because the bound node is on the left side:

SQL

SELECT bar.*
FROM foo 
LEFT JOIN bar ON foo.id = bar.foo_id
WHERE foo.id = 1

Cypher

START foo=node(1)
MATCH foo-[?]->bar
RETURN bar

If the right side is has the start point, it is a right outer join. And if both sides have starting points, it’s a full outer join, like this:

SQL

SELECT bar.*
FROM foo 
  FULL OUTER JOIN bar ON foo.id = bar.foo_id
WHERE foo.id = 1 and bar.id = 2

Cypher

START foo=node(1), bar=node(2)
MATCH foo-[r?]->bar
RETURN r

Relationships in Neo4j are first class citizens - it’s like the SQL tables are pre-joined with each other. So, naturally, Cypher was designed to be able to handle highly connected data easily.

One such domain is tree structures - anyone that has tried storing tree structures in SQL knows that you have to work hard to get around the limitations of the relational model. There are even books on the subject.

To find all the groups and sub-groups that Anakin belongs to, this query is enough in Cypher:

Cypher

START user=node:person(name="Anakin")
MATCH group<-[:BELONGS_TO*]-user
RETURN group

The * after the relationship type means that there can be multiple hops across BELONGS_TO relationships between group and user. Some SQL dialects have recursive abilities, that allow the expression of queries like this, but personally I’ve always had a hard time wrapping my head around those. Expressing something like this in SQL is hugely impractical if not practically impossible.

WHERE

This is the easiest thing to understand - it’s the same animal in both languages. It filters out result sets/subgraphs. Not all predicates have a equivalent in the other language, but the concept is the same.

SQL

SELECT person.*
FROM person
WHERE person.age >35 OR person.hair = "blonde"

Cypher

START person = node:persons("name:*")
WHERE person.age >35 OR person.hair = "blonde"
RETURN person

RETURN

This is SQL’s SELECT. We just put it in the end because it felt better to have it there - you do a lot of matching and filtering, and finally, you return something.

Aggregate queries work just like they do in SQL, apart from the fact that there is no explicit GROUP BY clause. Everything in the return clause that is not an aggregate function will be used as the grouping columns.

SQL

SELECT person.name, count(*)
FROM Person
GROUP BY person.name
ORDER BY person.name

Cypher

START person=node:persons("name:*")
RETURN person.name, count(*)
ORDER BY person.name

Order by is the same in both languages - ORDER BY expression ASC/DESC. Nothing weird here.

Use the right tool

No database is the silver bullet for data persistence and querying. That is what NOSQL means to us - look at your data and what you want to do with it, and then choose the appropriate tool for the job. Neo4j and Cypher are custom built for the challenges of heavily connected data. Compare the shortest path query here (all 43 lines of it) with what it looks like in Cypher:

Cypher

START lucy=node(1000), kevin=node(759)
MATCH p = shortestPath( lucy-[*]-kevin )
RETURN p

Wrap up

The performance characteristics are radically different when you move from a relational data store to Neo4j. Things that a SQL developer might fear because the performance bug has bitten there before, might not at all be expensive in a graph database.

Relational databases have a different underlying model than graph databases, and so the query languages for them naturally have different design goals. Cypher was designed to make querying of complex, heavily interconnected data as natural as possible. It should not only make the querying possible, but we aim to have a query language that helps you think about your data query.

If you know SQL well, you will quickly be productive with Cypher.