NashTech

Build a highly scalable cost optimisation service

Build a highly scalable cost optimisation service

Introduction

NashTech helped SQream build a highly secured, performant, extensible compiler frontend service that successfully optimised all queries, reducing the cost of running a query by 60%.

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.

Impact

  • Build a cost-based optimiser for the existing database engine and integrate it with an industry-standard SQL parser.
  • Bring down the cost of running a query by 60% by selecting the best plan based on the SQream representation of the data.

Challenges

  • SQreamDB is a distributed database and it is quite complex to model the costs of query execution.
  • Need of an industry-standard SQL parser/validator which can be enhanced to keep up the pace with the competitors.
  • The backend engine needs to execute queries efficiently on huge volumes of data.
  • A particular complex SQL can generate many query plans so the cost calcutaion of each and every query plan is expensive, hence there should be a balance between the query cost and cost of selecting the best plan.

Approach

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.

Solution

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.

sqream

01 Parsing

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:
select:

<SELECT> expressionList
[<FROM> table]
[<WHERE> condition]
[<GROUP> <BY> groupingList]
[<HAVING> condition]

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.

02 Validation

The purpose of validation is to test the semantic correctness of the query, i.e. whether a query written by a user makes sense or not. Validation ensures every object mentioned in the query exists and every operation specified can be done. If it isn’t so, the process halts with an explanatory error message.

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

Query optimisation is a process in which the original query is transformed according to a set of rules into some other, equivalent query that is faster to run and/or requires less computational resources for its execution.

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.

Results

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

Read more case studies

From rising above adversity to riding the wave of digital transformation in the education sector

Explore how NashTech help Trinity College London ride the wave of digital transformation in the education sector

Migrating and modernising the virtual learning environment to AWS for an enhanced experience

The migrated and modernised Moodle infrastructure means that The Open University can now take advantage of cloud benefits.

A glimpse into a year-long RPA journey with a leading digital advertising service

A glimpse into a year-long RPA journey with a leading digital advertising services and solutions provider and how NashTech helped them.

Our partnerships

Scroll to Top
SAMPLE TITLE
sample short
sample heading lorem isump
FREE WHITEPAPER
Unlock the power of knowledge with our new whitepaper
“Elevating User Experience for Product Owners”