The gentle Art of referring to Columns

Why we abandoned column names in Hyrise. Or did we really?

Published in

Hyrise

10 min readSep 3, 2017

What has happened so far?

This post is part of a blog series about the progress of writing a query optimizer for Hyrise, a main-memory column-oriented research database.
So far, we have written about:

Introduction

We, as humans, like to put labels on everything and use them to refer to one thing or another as we talk about them. In databases, this means that we give names like income or birthday to columns and persons to a table when we’re communicating with a database via SQL. To the core of the database, the part that actually executes our queries and is therefore often referred to as the “execution engine”, these names mean little —it just holds a list of tables and for each table a list of columns. At the bottom of it, this article is about the best way of achieving a mapping between the name that the user likes to work with and the index in a list, which is really the way of the database to access a column.

But before we dive deeper, let’s have a quick look at why the way we can name things in SQL is not as simple to process for a database as it might seem at first glance. The short answer is: prefixing and aliases. The long answer is best given by a big wall of text, or by some examples. Let us go for the latter, shall we?

First, assume we have the following tables loaded into our database:

Now, the first query we will consider is a relatively straight forward case:

Can you hear the ambiguity bell ringing? The column a is contained in both T1 and T2 — we would have to either refer to T1.a or T2.a to remove the ambiguity, while for column c the T2. prefix would be optional. Okay, let us fix the query and extend it a bit:

Looks correct to you? Well, it is not, because the column names of InnerResult are still a and c, the first column is not named T1.a, despite us using that name to refer to it.

For the last mind challenge, imagine yourself in the shoes of a query optimizer (Remember? We’re writing Hyrise’s query optimizer!) that takes this particular query above and realises…

Wait, no need to do a full PRODUCT of T1 and T2 in the inner query, I can push down the WHERE statement from the outer query and use a JOIN instead!

…and then you go ahead and form the following query:

…and of course you would have stepped right into another trap SQL has laid out for you, because now InnerResult is not a known prefix anymore. And then it dawns on you that even removing the InnerResult prefix is not enough for the push down to work, but adding the T1 prefix again would be necessary and cold sweat starts running down your back and you scream “I’m just a query optimizer I don’t want to deal with this!!” and the execution engine agrees with you and starts wailing as well — and you know what? We think you are right — SQL’s naming complexity is not something the inner workings of Hyrise should have to worry about. To guard you from it, we will build a nice layer of defense around it, one that translates these names into nice, unambiguous column indices that are, as we will lay out further down, much easier to work with.

Resolving Names to Numbers

There is strength in numbers, but organizing those numbers is one of the great challenges.
John C. Mather

Parse, Optimize, Execute — The Three Stages of Query Processing

We can divide the processing of an SQL query into three parts. The first part takes the SQL statement as a string and parses it into C++ objects that form a syntax tree. Hyrise uses an existing open-source parser library for this stage. The output of the parser would usually not describe an ideal execution path for the query, as the parser does not know anything about selectivity or other metrics used to optimize the query plan. The second part, the optimizer, however, is responsible to do just that: based on statistics, it should find a good query plan. This stage often requires to modify the parse tree. However, the parse tree structure is not the best data structure to work with for re-organizing the tree. In Hyrise, we therefore have a second data structure that is built with these kind of operations in mind. We translate the parse tree into that data structure in the SQLToASTTranslator component and optimize the query plan by manipulating this structure. (“AST” abbreviates “Abstract Syntax Tree”, by the way.) After the optimizer has finished its optimizations, the third component, the ASTToOperatorTranslator, is responsible for compiling the query by translating the intermediate structure into operators, which can then be scheduled and executed.

Getting rid of Column Names as early as possible

In the process outlined above the question is where to translate column names to column indices. In Hyrise, we decided to introduce the indices as early in the process as possible, because we think that the unambiguity of those indices helps us in all the following stages, namely optimization and execution.
The parser is not able to translate the column names to indices because it has no knowledge of the tables and columns that are used in the statement — it operates completely independent of the storage layer. Consequently, the SQLToASTTranslator would be the next possible component. Introducing indices here has the advantage that virtually the whole code base outside of that translator does not have to resolve column names. That includes the statistics component, the ASTToOperatorTranslator, as well as all operators and optimization rules. We found that to be a major advantage regarding the complexity of the code and therefore decided to follow that approach.

Looking Up Column IDs

The SQLToASTTranslator creates the AST nodes, which have to keep a mapping from column names to indices. This mapping is required for the process of translating the parse tree to the intermediate structure.
We can divide Hyrise’s operators, and therefore the AST nodes as well, into two groups: those which (re-)define the column layout (e.g. StoredTableNode and Projection), and those which don’t (e.g. TableScan and Sort).
Whenever we translate an object in the parse tree, e.g. the WHERE clause of a SELECT statement, we need to look up the column index for the column name used in that part of the statement. The first step to being able to do that is that the AST node representing a table stored in the database (the StoredTableNode) provides a list of column names for the columns in its result. If the query contains a TableScan on a column called “item_id”, we will ask the AST node that is preceding the TableScan for the column index of that column name. If the input node is a StoredTableNode, it will search in its list of column names and return the index of that name.

If a second scan follows the first one, the process is a bit different. The second scan has as its input the first scan, and therefore asks that node to resolve the column name. That node does not change the table structure and therefore simply redirects the task to its input, which would in this case be the StoredTableNode. The advantage is that we only have to define the lookup functionality for nodes whose input and output structures are different. In Hyrise, we currently have four nodes that can change the table layout: StoredTableNode, ProjectionNode, JoinNode, and AggregateNode.
ProjectionNode and AggregateNode are different from the other two in that they have the power to create new columns that do not stem from its input. In the case of the AggregateNode that would be aggregate functions, and for the Projection that would be arithmetic expressions. The respective nodes have to consider that when resolving column names.
This is important since all nodes provide a mapping from a node’s output column indices to its input column indices. For output columns that are created by this node, a special token is used.

Treating Table Name

As mentioned in the beginning of this post, SQL provides a way to specify which table a column is being accessed from. This is required if a column otherwise cannot be resolved unambiguously, and optional otherwise. To support that, nodes can be asked whether they manage a respective table qualifier, and will only be taken under consideration if they do. Currently, StoredTableNodes store the table name and can thereby take responsibility for that respective table qualifier. Other nodes simply ask their input nodes whether they manage that table.
The one interesting special case is the JoinNode, which handles two tables. It knows how many columns each of the two inputs specifies, and can therefore limit the search to the columns of the responsible table.
In the future, this concept needs to be extended to support aliases for subqueries as well — and we have plans prepared for that.

Optimizing the Query Plan With Column IDs

The main objective of the optimizer is to generate a query plan as close to optimal as possible within a reasonable time frame. Often times that means changing the order in which operators are being executed. By relying on column indices instead of names, changing the tree might involve the need to change column indices as well. Imagine a simple example, in which we first do an INNER JOIN of two tables and subsequently scan the join result on a column of the right table of the join. The optimizer might decide that it is cheaper to first scan the right table and then join the left table with the result of the scan.
However, the AST node representing the TableScan uses as a column index the column index that is correct for the table resulting from the INNER JOIN, which first contains all columns of the left input and then all columns of the right input. This column index is different if the scan is to be executed before the join, because then the input table for the scan only has the columns of the right table.

That means there are three cases to consider in the rules:

If a rule moves a node that does not change the table structure past nodes that do not change the structure either, the column indices do not have to be updated anywhere. An example of such a rule is a simple predicate ordering for multiple predicates of a WHERE clause.
If a rule moves a node that does not change the table structure past nodes that do change the structure, the column indices of the node that is moved have to be updated. Other nodes, however, remain untouched. This is the case for the predicate push-down example given above.
In the third case, the rule moves a node that re-defines the table structure. In that case, the changes of column indices have to be propagated up the tree, up to the next node re-defining the table structure. A rule that fits this case is join-enumeration.

To ease the implementation of rules in Hyrise, we plan to provide helper functions in the future that handle these updates of column indices automatically.

Column Indices in the execution engine

Up until quite recently, Hyrise did not have an SQL interface — if you wanted to perform operations on it, you would have to create the individual operators of a query yourself and chain them up appropriately. Since it was the most intuitive way, you would pass column and table names to the operators and each individual operator itself would do the work of translating a column name into a column index. This led to both boilerplate code, since every operator would have one or more input_table->column_id_by_name(…) calls, and redundant column index resolutions, e.g. when chaining two TableScans of the same column.
With the new column index system in place this work is taken out of the execution engine and each operator will simply receive the indices of the columns of its input table it should work on. The transition to this approach was thankfully as straight forward as simply removing the column_id_by_name(…) calls and replacing std::string _column_name members of the operators with ColumnID _column_id members.

While this makes the implementation of the operators somewhat cleaner, less redundant and even a slight bit faster, this approach has some downsides too, that we have to be open about:

It is more complicated, e.g. in tests, to create queries from operators manually, because you will have to hardcode column indices yourself. This is less readable, because now your tests refer to, e.g., columns ColumnID{2} and ColumnID{4} instead of c and e. Also, if someone, unlikely, but let’s consider it, decides to mess with the order of the columns in the test table files, all tests referring to that table will have to be adjusted as well. We haven’t found a good solution to this problem yet, mostly since the order of columns that go into an operator is per Hyrise’s architecture only determined once the operators predecessor is executed, but the column indices have to be specified when the operators are created. This problem is definitely a nuisance, but even if we can’t come up with a solution it is limited to the low level tests of the operators. (Here is hope, that most of Hyrise’s testing will at some point be done via tests that take SQL queries and compare their results with those of an established database.)
When debugging the execution of an SQL query and stepping through the operators you will have to deal with the debugger only telling you about column indices, not names, which is less intuitive as well.

Despite these problems we still decided to make the shift, since we think that the reduced complexity in the optimizer makes up for it.

From here on

Integrating column indices deep into Hyrise’s architecture at this point was a lot of work. But this work makes the life of the optimizer and execution engine coders so much more joyful — and that makes it worth it.
Dear reader, thank you for following us until here, but our journey is almost over. In fact this was the last content-heavy blog post of this semester’s master project at HPI’s EPIC chair. But don’t leave us just yet, because there is a nice wrap-up article for our whole project coming your way soon — see you then!