BlazeDB

Table of Contents

1. About The Project
2. Join
   • Join Graph
   • Edge Resolution
   • Modified BFS
3. Duplicate Elimination and Aggregation
4. Optimisation
   • Joins
   • Sort
   • Duplicate Elimination
   • Tuple Metadata
5. Query Planner

About The Project

Implementation of a lightweight database supporting core SQL operators using iterator model.

Join

Join Graph

We can represent all conditions and joins using a graph. The edges correspond to the join predicates and nodes are the tables.

For a query

select *
from R,
     S,
     T
where R.a = S.a
  and R.b = S.b
  and S.b = T.b
  and R.c = T.c
  and R.a < 10
  and 1 = 1

We can construct a graph as such

This graph is constructed by the JoinGraph class. The predicates are grouped by the set of tables it references, and then they are converted to a conjunction of predicates in an Expression. E.g. predicates $R_a=S_a$ and $R_b=S_b$ both reference the tables $R$ and $S$. They are grouped together, and their conjunction taken. The expression $\sigma_{R_a=S_a\wedge R_b=S_b}$ is set as the undirected edge between $R$ and $S$.

For predicates with a single column reference, we can treat is as a self-edge on a node. For literals such as $1=1$, we can set it as a self-edge on the root node so that it is evaluated as early as possible.

This graph sufficiently represents the entire join structure and selection structure of our query. Then constructing our join tree and applying selections can be done by resolving edges in this graph. We have to be careful in the order in which the edges are processed.

Edge Resolution

The first optimisation step is resolving all self-edges, also known as predicate pushdown. We further optimise to set self-edges of the literal predicates to the root node. If it is false, the left-deep leaf node on our join tree will be empty which reduces computation.

We then do our joins which uses a modified Breadth First Search (BFS). We start with our root node $R$ which is decided by the order of joins in the FROM clause. We explore the neighbours of $R$ which finds that $S$ is reachable. We join $$C_0 = R$$ $$C_1 = C_0\bowtie_{R_a=S_a\wedge R_b=S_b}S$$ to form cluster $C_0$.

Next we explore the next neighbour of $R$, which is $T$. We cannot simply join $C_1\bowtie T$ on the edge $\sigma_{R_c=T_c}$ as we are missing the edge between $T$ and $S$. BFS only considers the edge from the currently explored node $R$ to the neighbour $T$. If we resolve edge-by-edge in BFS, we will end up joining $T$ twice. As such the BFS needs to be slightly modified.

Modified BFS

As we explore each neighbour, find all edges that connects neighbour $V$ to cluster $C_t$ where $t$ is the number of tables. The cluster $C$ can be defined as the current set of tables already joined. Thus in the example of exploring $T$ as a neighbour of $R$, we can find all edges connecting neighbour node $T$ to the current cluster $C_1$. We create a conjunction of all connecting edges from $T$ to $C_1$, $$ C_2 = C_1\bowtie_{R_c=T_c\wedge S_b=T_b} T $$ and join the cluster to $T$ based on that conjunction to form new cluster $C_2$.

This is akin to a growing cluster algorithm, where we explore the next node to add to the cluster using BFS. BFS allows us to find the set of nodes connected to the current cluster.

We run this algorithm for all nodes that are not visited, as we can have multiple disjoint clusters. Each disjoint cluster is then cross product to obtain the final cluster of all tables.

Ordering of tuples is not maintained in this join operation due to the order in which edges are resolved. Projection is called at the end of the operation on the final cluster to maintain column ordering specified in FROM.

Duplicate Elimination and Aggregation

We need to handle group by, sum, and distinct and different combination of these which can be complicated. It is best broken down into the different cases, then handled independently. Let's explore these cases.

• group by & sum
  Create a key based on group by columns. Within each group, sum based on equation. Return tuples for each group in the order they were created.
• group by only
  Remove all duplicates based on the group by columns.
• sum only
  Sum based on equation for entire relation
• distinct
  Distinct operates independently above group by and sum. It has the same effect as group by only and it simply removes duplicates based on the columns in the select items instead of the group by items.

Optimisation

Joins

We have some opportunities for optimisation here by sorting the nodes based on table size so that the smallest table is always the outer relation in the join. But with selection, we also need to consider selectivity of predicates for truly optimal joins. All of which I did not implement.

Sort

Sorting stores a List of sorted tuples. We remove each element when the next tuple is requested instead of incrementing a pointer and dereferencing the element. Removing an element when requested reduces the memory required to store the entire list.

Duplicate Elimination

We make this operator non-blocking when it is called without aggregations. We can store a set of unique tuples. We only return the next tuple if it does not exist in the set. Then we add the tuple to the set. We also implicitly project the tuple to the key columns while doing duplicate elimination. E.g. select distinct a, b from Student, then we have the key columns a and b which we can also project to in the same operator. The same can be done for group by.

Tuple Metadata

Metadata for each tuple is required to specify the columns and table that the tuple data correspond to. This metadata is stored as an instance variable within each operator to reduce memory consumption. We do not want to create a new metadata object for every tuple. This also allows us to determine the output shape of the tuple before calling getNextTuple.

Query Planner

The planner is important for composing the operators in the correct order for correctness and optimal performance. The general ordering is as such

1. Scan base table
   Base table as the left-most leaf relation in our operator tree. We will build the entire tree off this leaf.
2. Join & Selection
   Apply selection and joins on all the tables as explained here. Predicate pushdown and join order ensure optimality.
3. Duplicate elimination with Aggregate
   We process the group by statement and sum, which also does implicit projection
4. Duplicate elimination
   For distinct which is independent of group by and sum.
5. Projection
   Remove unwanted columns
6. Sort
   Done last as this always blocking and expensive

We do duplicate elimination again for distinct because we can have

select distinct SUM(Student.A), Student.B
from Student
group by Student.A, Student.B

which means that we group by and sum first, which already does duplicate elimination for the key columns Student.A and Student.B and aggregate the sum. But distinct does duplicate elimination again on the aggregate.

(back to top)