Writing a Cypher query parser and planner in C++

Intro

0:00 Hello and welcome back to episode seven, where we're going to teach smollerGraph a small subset of Cypher, the query language we used with Neo4j and Kùzu in episode one. Let's begin with a quick look at where we're going to be by the end of the episode.

0:15 By the end, the page is going to send a Cypher query to smollerGraph, the food chain question from episode one: what's two hops of EATS from the red fox. SmollerGraph parses it, plans it and runs it, and the answers come back as rows, the clover and the wheat, filled in on the graph.

0:34 On the website of the series, you can find more information about the project. The code is open source on GitHub, tagged at each step of each episode, so that you can follow along, and each episode has a page here, with its chapters and its code.

Last time

0:49 Now, before we get to today's work, let's quickly go over what we did last time. We built an index on names, a B+ tree, which started as a page of names in order. Pages split as they filled, which grew it into a tree, a level at a time. The graph finds its nodes through it, so opening a graph reads nothing, and its leaves let the UI suggest names as they're typed. But to ask smollerGraph anything, we still call a function, Walk, with a start, a type and a number of hops. Today, we ask it in Cypher, as we asked Neo4j.

Today

1:23 Today, a query goes from text to answers in four stages, which is how most databases do it. A lexer splits the text into tokens, words, strings, numbers and punctuation. A parser reads the tokens into a query, a structure that says what the pattern is and what to return. A planner turns that into steps, which say where to start and how to go on from there. And an executor runs the steps, which turn into rows of answers. Then sg query prints them, and the UI gets a query box. All right, let's get started with what our subset of Cypher is going to be.

Our subset

1:57 Neo4j turns each query into a plan made of operators, and its manual lists them, a long page of them. One finds the start of a pattern through an index, Node Index Seek, and another reads each node, All Nodes Scan, when there's no index to use. Expand follows relationships from the nodes it's given to the next ones, and Filter keeps the rows that match. Our plans are going to take their steps' names from these, so that EXPLAIN in smollerGraph reads a bit like Neo4j's.

2:26 Our subset is going to be small, so that it fits in an episode, but it answers real questions. A query starts with MATCH, and a node in brackets, with a variable, and an optional name in braces. Relationships go right, with their type after a colon, and a star and a number for several hops in a row. Each one leads to another node, and RETURN lists the variables whose names come back, with DISTINCT to drop the repeats. And EXPLAIN in front shows the plan, without running it. No WHERE, no properties other than the name, and no arrows to the left, for now.

Tokens

3:03 The lexer goes in a header of its own, lexer dot h. It includes cstddef, string, string view and vector, and Abseil's status or. Token kind is an enum class of the kinds of token in our subset, as its comment says. A word is a keyword or a name, such as MATCH, a, name or EATS, and the parser tells them apart later. A string is a name in quotes, without its quotes, a number is a whole number, and a symbol is one character of punctuation, such as a bracket or an arrowhead. End comes after the last token, so the parser always has a token to look at. A token is a struct with its kind, its text, and where it starts in the query, which the comment says is for errors. Lex takes the query, and returns its tokens in an absl Status Or. Its comment says it splits a query into tokens, ending with an end token. It also says when it returns an error instead: at a character it doesn't know, or at a string with no closing quote, with what's wrong and where in the error. In lexer dot c c, we include cctype, for telling letters from digits, and Abseil's status and str cat, for errors. In an unnamed namespace, three small functions say what a character can be: a word starts with a letter or an underscore, and goes on with those or digits, and is digit picks out a digit. Each of them casts the char to unsigned char first, as the functions in cctype take a character's code that isn't negative. Lex starts with an empty list of tokens, and walks through the query with an index, i, remembering where each token starts. Whitespace is skipped, as all it does is separate tokens. A word runs while the characters are part of a word, and becomes a word token, with its text and its start. A number runs for as long as there are digits, and becomes a number token, with its text and its start, like a word does. A string starts with either kind of quote, and find looks for the next quote like it, after the first. The comment says where the string ends: at the next quote like the one it started with. When there's no closing quote, it returns an invalid argument error that says so, with where the string started, put together with str cat. The token is the text between the quotes. Any of the characters in that string of punctuation is a symbol token, on its own: brackets, braces, a colon, a comma, a dot, a minus, arrows and a star. Anything else is unexpected, and the error says which character, and where. At the end comes the end token, at the end of the query, and Lex returns the tokens, which the status or holds. In CMake, lexer dot c c joins the library, and its test joins the tests. Lexer test dot c c has a helper, Describe, whose comment says what it's for: it writes the tokens' kinds and texts as one string, so a test can check them at a glance. Words, strings and numbers get their kind in front of their text, and symbols are written as they are. Splits a query into tokens lexes the two-hop query, and checks its tokens, from MATCH to the end. The arrow comes out as a minus and a greater than, and the parser is going to put them back together. Says what it cannot read checks a string with no closing quote, which starts at sixteen, and a semicolon, at eighteen, which isn't in our subset.

6:18 Let's build it, and run just the lexer's two tests, the ones whose names start with lexer. Both of them pass, so the tokens are ready for a parser.

A parser

6:29 The parser goes in parser dot h, which includes optional, string, string view and vector, and Abseil's status or. Node pattern is a node in a pattern, such as a with the name red fox. Its comment says that its variable and its name are both optional, and that empty brackets match any node, and give it no variable. So the variable is a string, left empty when there isn't one, and the name is an optional string. Relationship pattern is a relationship from a node to the next one, with its type, and its hops, one unless it says more, as the comment explains with EATS star two. Query is what the parser reads a query into, and the comment shows one. Explain says whether it started with EXPLAIN, and then come the nodes and the relationships, where relationship i goes from node i to node i plus one. Distinct says whether to drop repeated rows, and returns lists the variables whose names are returned, in order. Parse reads a query, and returns it, or an error that says what's wrong and where, when it isn't one our subset has. In parser dot c c, we include cctype, charconv, cstddef and utility from the standard library, then Abseil's status, status or and str cat, and our lexer. K max hops is ten, the most hops one relationship in a pattern can stand for. Equals ignoring case compares two words a character at a time, in upper case, as Cypher's keywords can be written in any case. Then comes the parser, a class of its own. Its comment says what kind it is: a recursive descent parser, a function for each part of the query, which reads that part's tokens and calls the functions for the parts inside it. Each one returns false, with the parser's status filled in, when the tokens don't fit. The constructor keeps the tokens, and status returns what's wrong with the query, once a part has failed, as its comment says. Parse query reads the whole query, and the comment over it is its grammar, in a notation where square brackets are optional and a star repeats. EXPLAIN in front is optional, so Keyword reads it if it's there. MATCH has to be there, and then a node. While the next token is a minus, there's a relationship, and a node after it. Each node and each relationship goes on the query's lists as it's read, the relationship first, and then the node it leads to. Then RETURN has to come next, DISTINCT is optional, and the returned items follow, separated by commas, which is what the do while loop reads: each item's variable goes on the list of returns. Anything left over is an error, as the query has to end there, and when nothing is, Parse query returns true. Parse node has its own line of grammar over it. It starts from an empty node, and reads an opening bracket. A word after it is the variable, which is optional. Then, in braces, comes the name, which is optional too: the word name, a colon, and a string, or it fails, saying it expected a name in quotes. After the name comes its closing brace, and last the closing bracket, which ends the node. Parse relationship, which reads the arrow between two nodes, has its grammar over it too. It reads a minus, a square bracket and a colon, each through Expect symbol, which we'll come to, and returns false as soon as one is missing. Then comes the type, which has to be a word, or it fails, saying it expected a relationship type. When a star comes next, the number of hops follows it. From chars reads the number's text into hops, and the number has to be a number token, read without an error, from one to ten. Anything else is an error that says what a number of hops is, and once it's been checked, we take the number's token, with Next. Then the closing square bracket, a minus and a greater than, the arrowhead, each of which has to be there, in that order. Expect symbol reads each one in turn, and the first that's missing fails the whole relationship. A relationship pointing left would start with a less than, which isn't a minus, so it fails right at the start. Those lines are the arrow, minus the left-pointing kind, which our subset leaves out. Parse item reads a variable, which has to be a word, or it fails, saying it expected a variable to return. Then come a dot and the word name, as names are what our nodes have. Then come the helpers that the parts share, which keep each part of the grammar to a few lines. Peek looks at the next token, without taking it, and Next takes it, moving on to the one after. The end token at the back of the list means Peek always has something to return, so none of the parts has to check for running off the end. Is symbol says whether the next token is a given symbol, and Symbol reads a symbol, if it's the next token, as its comment says, moving on past it. Keyword reads a keyword, if it's the next token, and its comment adds that Cypher's keywords can be written in any case, so match is MATCH. So the next token has to be a word that equals the keyword when the case is ignored. Expect symbol and Expect keyword fail when what they expect isn't there, with what they expected in the error, so each of them is a single line: read it, or fail. Expect word compares a property's name case and all, which its comment says is what Cypher does, and fails with the word it wanted when it isn't there. Fail's comment says what it does: it says what was expected, where, and what was there. It looks at the next token, and fills in the status, an invalid argument error that str cat puts together: what was expected, where, and the token's text, or the end, when the query has run out. It returns false, so a part can fail and return in a single line, which is why the parts read like the grammar does. The parser keeps the tokens, the position of the next one, and the error it fills in. Last comes Parse, outside the class, in the smollerGraph namespace. Parse lexes the text, and returns the lexer's error if there is one. Then a parser reads the tokens into a fresh query, with the tokens moved into it instead of copied. Parse returns the query, or the parser's status when a part failed. In CMake, parser dot c c and its test join the build. Parser test dot c c has three tests. Reads a pattern parses a three-node pattern with DISTINCT and two returned names, and checks each part: the red fox's name, the missing name on c, EATS, the two hops and the returned variables. Reads keywords in any case parses a query in lower case, with empty brackets for a node, which has no variable. Says what it expected checks three errors: a missing bracket, an arrow without its head, and twenty hops, which is over the limit.

13:12 Let's build it, and run just the parser's three tests, the ones whose names start with parser. All three pass, errors and all, with the error messages we expected.

A plan

13:24 Here's the plan our planner is going to make for the food chain query. It works on rows, with a slot for each node of the pattern. The red fox has a name, so the plan starts by finding it in the index we built last time, which gives one row, with the fox in slot a. Two hops of EATS are two expands, one after the other. The first gives a row for each node the fox eats, in a slot of its own with no variable, underscore one, and the second goes from there to c. And last, the plan returns the name in c, for each row.

13:58 The planner goes in plan dot h, which includes string and vector, Abseil's status or, and the parser. A step is one step of a plan. The comment says how a plan works: on rows, with a slot for each node of the pattern, and each step turns the rows it's given into the rows for the next step. The steps take their names from Neo4j's plans. Its kind is one of four, each with a comment. Node index seek gives a row for the node named text, in slot to, found in the index. All nodes scan gives a row for each node in the graph. Expand gives, for each row, a row for each node a relationship of type text goes to from the node in slot from. Filter keeps the rows whose node in slot from is named text. The step's other fields are those two slots and the text. A plan is how to answer a query, as its comment says: where to start, and where to go from there. It has its steps, its slots, each with the pattern's variable or nothing, as the comment says, and the slots whose names are returned, with their columns' headings. Distinct comes over from the query, as it is. Plan query plans a query, and returns the plan, or an error when the query returns a variable its pattern doesn't have, or gives two nodes one variable. Explain writes the plan's steps, a line each, in the order they run, as EXPLAIN shows them. In plan dot c c, we include algorithm and cstddef, and Abseil's status, status or, str cat and str join, and two helpers go in an unnamed namespace first. Slot name gives a slot's name for the plan's text, and its comment says what that is: the slot's variable, or an underscore and its number, for a node the pattern didn't name. It looks the variable up, and when it's empty, str cat puts the underscore and the number together. Add filter takes a node of the pattern, and the slot it's in. Its comment says what it's for: a name on a node after the start keeps the rows that reach a node with that name, with a filter on the node's slot. So when the node has a name, it adds a filter step, with the name as its text. It has a function of its own so that clang-tidy can see that the name is there before it's read, which it couldn't, in the middle of the loops below. Plan query starts with a fresh plan, as Parse starts a fresh query. Then two loops, one inside the other, compare each node's variable with the variables of the nodes before it, and check that no variable is on two nodes. A pattern like that would need the two to be one node, which our plans can't check yet. Then comes the start, and the comment says how the planner picks: a start with a name is found in the index, and without one, each node in the graph is a start. That's a real planner's choice, if a small one: an index seek reads a few pages, and a scan reads them all. Then, for each relationship, and the node it leads to, the comment explains the expands: each hop is an expand into a slot of its own, and the last hop's slot is the pattern's next node. A loop goes over the hops: from is the slot before, last says whether this is the last hop, and the new slot gets the node's variable on the last hop, and nothing before it. The expand goes from that slot to the new one, along the relationship's type. Then Add filter keeps the rows that reach a node with the next node's name, if it has one, with a filter on the slot just filled. Last, the returned variables: each is looked up among the slots, and one that isn't there is an error, which says there's no variable called that. Its slot is returned, and its column is called the variable dot name. Explain writes a line for each step, with a case for each kind. Node index seek and filter show the slot and the name in braces, all nodes scan shows the slot, and expand shows the relationship between its two slots, the way a pattern would. Each line goes on the end of the text with str append. The last line says what's returned, with DISTINCT when it's there, and the columns, which str join puts commas between. In CMake, plan dot c c and its test join the build. Plan test dot c c has a helper, Explained, which parses and plans a query and returns its plan as EXPLAIN shows it, or the error. Starts from the index when the start has a name checks the food chain's plan, the one we just drew. Scans when the start has no name checks a query for what lives in the meadow: an all nodes scan, an expand, and a filter on the meadow's name. And refuses variables it cannot plan checks the two errors.

Rows

18:32 Now the executor, which runs a plan on a graph. In plan dot h, we include the graph. A result is what a query returns, as its comment says: a row for each match of its pattern, with a node for each column. It has the columns, and the rows of node ids. Run runs a plan on a graph, a step at a time, each on all of the rows at once. In plan dot c c, we include optional, set and utility. Run takes the plan and the graph, and returns a result. It starts with a single row, whose slots are still to be filled in, as the comment says. Then, for each step, it makes the next rows from the rows it has. A node index seek finds the node by its name, and when the index has it, the row is copied, with the node in its slot. An all nodes scan copies the row for each node in the graph. An expand copies the row for each neighbour of the node in its from slot, along the relationship's type, with the neighbour in its to slot. And a filter keeps the rows whose node has the name. After each step, the next rows become the rows, moved instead of copied, and the next step starts from them. Those few lines are the whole executor: four kinds of step, and rows going through them. Each step builds all of its rows before the next one starts, which is simple, but holds all of them in memory. Real databases pass rows along one at a time, or in small batches, which we may do later. Then the result: for each row, the returned slots' nodes, in order, in a vector that reserves room for them first. With DISTINCT, a set remembers the rows it's seen, and the comment says what happens: DISTINCT keeps the first of the rows that return identical nodes, and drops the rest. In plan test dot c c, Answers runs a query, and writes each row's names as a string, with commas between the columns. Run test is a fixture: its set up loads a few of the animals, the food chain and the meadow, into a graph of its own, before each of its tests. Walks down the food chain asks for two hops of EATS from the red fox, and has to get the clover and the wheat, each in a row with the fox. Filters a later node by name asks what lives in the meadow, which is the rabbit and the field mouse. Returns distinct rows asks what's eaten, by anything at all. The comment says why it matters here: the fox and the owl both eat the field mouse, so it's in two rows, and DISTINCT keeps one. That's five rows without DISTINCT, and four with it. In main dot c c, we include status or, the parser and the plan, and the usage gets sg query, with a graph folder and a query. Run query takes the graph and the query's text. Its comment says what it does: it runs a query in our subset of Cypher, and prints what it returns as a table, or prints its plan, when it starts with EXPLAIN. It parses the text, and plans the query when it parsed, so the plan's status or holds the parser's error when there was one. If either one failed, it prints the status's message after sg and a colon, and returns one. With EXPLAIN, it prints the plan, and returns zero. Otherwise, it runs the plan, and prints a table. First come the columns, separated by bars: a column for each returned variable, and its heading is the variable dot name, as the plan named it. Then comes a line for each row, with the names of its nodes. Each row's names are read from the node records, through the graph, after the plan has run, so the plan works on ids alone. Last comes how many rows there were, or a single row. In main, a new flag, query, is true when the command is query, with one argument after the folder, the query, in quotes. The usage is printed when it's missing, along with the other commands. After the graph opens, the query runs, through Run query.

22:19 Let's build it, and run all of the tests. They pass, from episode one's tests on, all thirty-six of them, the lexer's and the parser's among them. Then, with the animals loaded, here's the food chain question, in Cypher, the way we asked Neo4j in episode one. Two rows come back, the clover and the wheat. With EXPLAIN in front, a query about the meadow shows its plan, which starts with an all nodes scan, as its start has no name, then expands to where each node lives, and filters for the meadow. And who eats the field mouse, in our graph? The red fox and the tawny owl, each in a row of its own, with the field mouse next to it.

Cypher in the UI

23:02 In api dot h, Query JSON parses, plans and runs a query from a request. Its comment lists what it answers with: the columns and the rows, each node with its id and name, or the plan, after EXPLAIN, or what's wrong with the query. In api dot c c, we include the parser and the plan. Query JSON parses the text, and returns the parser's error when it doesn't parse. Then it plans the query, and returns the planner's error when that fails. Both are invalid arguments, which Send turns into a four hundred. After EXPLAIN, the answer is the plan, as a JSON string. Otherwise, it runs the plan, and writes the columns as an array of strings. Then the rows, as an array of arrays: each row opens a bracket, after a comma when it isn't the first, and closes one at its end. For each node in a row, str append adds an object, with the node's id and its name, so the page can find the node in the graph. Its test, Answers with rows or a plan, asks what the red fox eats, in a graph of two nodes, and checks the JSON: one column, and one row, the rabbit. EXPLAIN answers with the plan, as a JSON string, its new lines escaped as backslash u, zero zero zero a, the way Json string writes control characters. And a broken query, with a bracket missing, has to be an invalid argument. In server dot c c, a new handler, for slash A P I slash query, reads the query from a parameter called q, which cpp-httplib decodes for us. It sends whatever Query JSON returns, rows, a plan or an error, with the status that comes with it. In index dot html, a second form in the header holds the query, in an input with spellcheck off, and the food chain query to start with, next to a button to run it. Then a section for the results, with a paragraph for an error, a pre element for a plan, and a table for the rows. The style sheet puts the query on a line of its own, as wide as the page, and the results in a panel over the bottom of the graph. It also stops the font from drawing a minus and a greater than as an arrow, as its comment says, so the query reads the way it's typed. In graph dot js, the comment says what a query does: sg serve parses, plans and runs it, its rows go in a table, and the nodes they return are filled in, in the graph. After EXPLAIN, the panel shows the plan instead. Query form is the form, and results the panel. On submit, the query goes to slash A P I slash query, in the query string, and the answer comes back as JSON. The panel opens, and shows the error and the plan, if there are any. The table is emptied, and if there are no rows, that's all. Otherwise, a heading row gets a cell for each column. Then another data join, two levels deep: a row for each of the answer's rows, and in each, a cell for each node, with its name, which d three sets as the cell's text. Then the graph: a walk that's still lighting up stops, and the comment over that says why: the query's nodes take the place of a walk's. The set of returned nodes is made from all of the rows, and those nodes are filled in, with the rest cleared. And the README says what sg query understands, and what it doesn't.

26:12 With the page at the end of this episode, running the query that's in the box asks for the food chain, and fills in the clover and the wheat. Let's ask something new, with EXPLAIN first: where does the tawny owl's prey live? The pattern starts at the owl, follows EATS to its prey, and then LIVES_IN to a place. The plan seeks the owl in the index, expands along EATS, and then along LIVES_IN. Now that pattern again, without EXPLAIN, and returning the prey's name as well as the place's name, so this time the page runs it, instead of showing its plan. And the answer is the field mouse, which lives in the meadow, both filled in on the graph.

What's missing

26:51 Our subset leaves a lot out, and some of it is worth knowing about. There's no WHERE, and no properties other than names, as our records don't have any yet. Arrows go right, as each node keeps the relationships that start at it, and to follow one to the left, we'd need each node's incoming relationships too. Cypher doesn't use a relationship twice in one path, and our expands don't check that, which matters once the graph has cycles. And each step builds all of its rows before the next one runs, which a bigger graph would run out of memory doing. Each of these is a step we can take later.

Wrap-up

27:27 So, today a query went from text to answers. A lexer split it into tokens, and a recursive descent parser read them into a query. A planner made steps named after Neo4j's, seeking the start in our index when it has a name, scanning when it doesn't, and expanding hop by hop, and EXPLAIN shows them. An executor runs the steps on rows, and sg query and the UI both speak our subset of Cypher now. Next time, we can finally make the comparison with Neo4j and Kùzu fair, asking all three databases one question in Cypher, parsing and planning included.

28:03 This is going to be an evolving project, so I'd love to hear from you. Let me know in the comments which part of Cypher you'd like smollerGraph to learn next, and if you'd like to follow along, subscribe to the channel. I hope you find this useful, and thanks for watching.