Build a highly scalable cost optimisation service
NashTech helped SQream build a highly secured, performant, extensible compiler frontend service that successfully optimised all queries, reducing
SQream provides an analytics platform that minimises Total Time to Insight (TTTI) for time-sensitive data, on-prem and on-the-cloud. Designed for tera-to-petascale data, the GPU-powered platform enables enterprises to rapidly ingest and analyse their growing data – providing full-picture visibility for improved customer experience, operational efficiency, and previously unobtainable business insights.
SQream DB has a Rule-based query optimiser, but it is impossible to correctly optimise the query without considering the data, data skewness, workloads, and the variety of data. The rule-based optimiser applies different rules to optimise the query, so to cover all the plans, more rules are needed, which results in many complex rules as well as we have to add hints to make those rules work. Still, the required query efficiency can not be achieved for complex queries. Hence, the idea of Cost-Based Optimisation looks lucrative, but it is a hard problem to solve in distributed databases. Since the need was urgent, we narrowed it down to Calcite which has a lot of inbuilt rules, as well as a cost-based planner known as Volcano. We wanted to leverage as much functionality from Volcano to enable us to build a Cost-Based Optimiser for SQream DB. Calcite offers you a framework to build your own rules as well the framework is highly customisable to support all the needs that we have.
The primary goals for us were to:
To achieve these goals the following High-Level Architecture was proposed to build a highly scalable cost optimisation service as described in the diagram below. To achieve these goals the following High-Level Architecture was proposed to build a highly scalable cost optimisation service as described in the diagram below.
The whole process starts with parsing. A query, to be understood by the database engine, must first be parsed using an SQL parser, which takes a string of characters and tries to deduce its syntactic structure in the form of a parse tree. It uses a set of syntax rules called language grammar, which defines how an SQL query must look to be considered valid and acceptable to the query engine.
For instance, a rule for parsing SQL SELECT statements might look like this:
[<GROUP> <BY> groupingList]
It declares that a SELECT statement must start with the keyword SELECT, followed by a list of fields and/or expressions to select (could be only one), and optionally any, or all, of the following: a FROM clause specifying the source of data from which to do a select (i.e. a table or a subquery); a WHERE clause filtering selected rows based on a Boolean condition; a GROUP BY clause aggregating rows together based on some keys; and a HAVING clause filtering out some groups if a condition isn’t satisfied.
Another important purpose of validation is to correctly identify to which exact object (field, table, function) any identifier named in the query really refers and also to assign correct data types to every field, row, or expression that therein occurs.
So how we do the validations:
03 Regional algebra
Relational algebra deals with abstract transformations over sets of data, such as.
Conversion to a Relational Tree:
AST(abstract syntax tree) is not convenient for query optimisation because the semantics of its nodes are too complicated. It is much more convenient to perform query optimisation on a tree of relational operators, defined by the RelNode subclasses, such as Scan, Project, Filter, Join, etc. We use SqlToRelConverter, another monstrous class of Apache Calcite, to convert the original AST into a relational tree.
04 Query optimisation
Optimisation is a process of conversion of a relation tree to another relational tree. You may do rule-based optimisation with heuristic or cost-based planners, HepPlanner and VolcanoPlanner respectively. You may also do any manual rewrite of the tree without a rule. Apache Calcite comes with several powerful rewriting tools, such as RelDecorrelator and RelFieldTrimme.
The result was a highly secured, performant, extensible compiler frontend service that successfully optimised all the queries and generate the corresponding physical tree.
“I want to thank NashTech for their great contribution in building the CBO for SQream enabling us to successfully integrate calcite into our system.”
Gill Cohen – SQream Project Manager