Introduction

As digital industrialization and industrial digitization become important drivers of economic growth, enterprise Data analytics scenarios are becoming increasingly diverse, and the requirements for Data analytics architecture are also rising. New Data analytics scenarios are creating new requirements, mainly in three areas:

  • Users want to load and store any amount of relational data, such as operational databases and data from line-of-business applications, and non-relational data, such as operational databases and data from mobile applications, IoT devices, and social media, at a lower cost and in a more real-time manner.
  • Users want their Data assets to be tightly protected.
  • Users want Data analytics to become faster, more flexible, and more real time.

The emergence of the Data lake has effectively met the first two requirements. It allows users to load any amount of real-time data as it becomes available. Users can collect data from multiple sources and store it in its Raw data form in the Data lake. A Data lake offers extremely strong horizontal scalability, enabling users to store data at any scale. At the same time, its underlying layer usually uses low-cost storage solutions, significantly reducing the cost of storing data.

Through measures such as sensitive data identification, classification, privacy protection, resource permission control, encrypted data transmission, encrypted storage, data risk identification, and compliance audits, a Data lake helps users establish security early-warning mechanisms, enhance overall security protection, and ensure that data can be used without being exposed, while remaining secure and compliant.

To further meet users’ requirements for Data lake analytics, we need an analytics engine built for the Data lake. It should enable users to use more data from more sources in less time, process and analyze data collaboratively in different ways, and make better and faster decisions. This article explains the key technologies behind such a Data lake analytics engine in detail. It also uses a system architecture example to help readers better understand how the engine works.

We will later publish two follow-up articles to introduce the kernel and use cases of a high-speed Data lake analytics engine in more detail:

  • Code walkthrough: This article will walk through the key data structures and algorithms of an open-source analytical database kernel to help readers further understand the principles and implementation details of a high-speed Data lake analytics engine.
  • Case Study: This article will explain how large enterprises use a high-speed analytics engine to gain real-time and flexible insights from data in a Data lake, make better business decisions, and understand how the theory is applied in real-world scenarios.

What Is a Data Lake?

According to Wikipedia, “A data lake is a system or repository of data stored in its natural/raw format, usually object blobs or files.” In plain terms, a Data lake can be understood as a layer built on top of low-cost Object storage or a Distributed file system. This layer brings together discrete objects or files in these storage systems and exposes them externally through unified semantics, such as the “table” semantics commonly seen in a Relational database.

After understanding the definition of a Data lake, the next natural question is: what unique capabilities does a Data lake provide, and why should we use it?

Before the concept of the Data lake emerged, many enterprises and organizations already used the Hadoop Distributed File System (HDFS) or Amazon S3 at large scale to store various types of data generated in day-to-day business operations. For example, a company building an app might want to record every click event generated by its users in detail.

Because the value of this data may not be discovered in the short term, enterprises often choose a low-cost storage system to temporarily store it, expecting to extract valuable information from it when it becomes useful in the future. However, Hadoop Distributed File System (HDFS) and Amazon S3 expose relatively simple semantics: Hadoop Distributed File System (HDFS) exposes file semantics, while Amazon S3 exposes object semantics. Over time, engineers may no longer be able to answer exactly what data has been stored there.

To avoid having to parse every piece of data one by one before understanding its meaning in future use, engineers came up with a better approach: organize data with consistent definitions together, and then use additional data to describe it. This additional data is called metadata, because it is data that describes data. Later, by parsing the metadata, users can understand what the data actually means. This was the original role of the Data lake.

As users’ requirements for Data quality continue to rise, the Data lake has started to add more capabilities. For example, it can provide database-like ACID properties to help users obtain a point-in-time view during continuous data writes, preventing various errors during data reads. It can also provide higher-performance Data loading capabilities. Today, the Data lake has evolved from simple metadata management into a system with richer, more database-like semantics.

In a not entirely precise but intuitive description, a Data lake is like a lower-cost “AP database.” However, a Data lake only provides data storage and organization capabilities. A complete database needs not only data storage, but also Data analytics capabilities. Therefore, how to build an efficient analytics engine for the Data lake and provide users with the ability to gain insights from data is the core focus of this article.

The following sections break down the internal structure and implementation of a modern OLAP analytics engine step by step:

  • How to perform high-speed analytics on a Data lake
  • The architecture of a modern Data lake analytics engine

How to Perform High-Speed Analytics on a Data Lake

From this section onward, let us return to database fundamentals. Architecturally, an analytics engine for a Data lake and an analytics engine for a database are essentially the same. We usually consider them to include the following parts:

  • Parser: Parses the query entered by the user into an Abstract syntax tree (AST).
  • Analyzer: Analyzes whether the syntax and semantics of the query are correct and comply with definitions.
  • Optimizer: Generates a physical query plan with higher performance and lower cost for the query.
  • Execution Engine: Executes the physical query plan, collects the query results, and returns them.

For a Data lake analytics engine, the Optimizer and the Execution Engine are the two core modules that affect performance. Below, we break down the core technical principles of these two modules from three dimensions. By comparing different technical approaches, we help readers understand the full picture of a modern Data lake analytics engine.

RBO vs CBO

Fundamentally, the optimizer’s job is to generate an execution plan with the lowest, or relatively lower, query cost for a given query. Different execution plans can differ in performance by thousands or even tens of thousands of times. The more complex the query and the larger the data volume, the more important query optimization becomes.

Rule Based Optimization (RBO) is a common optimization strategy used by traditional analytics engines. At its core, RBO is based on equivalent transformations in relational algebra. It transforms queries through a predefined set of rules to obtain lower-cost execution plans. Common RBO rules include predicate pushdown, Limit pushdown, and Constant folding.

In RBO, there is a strict set of usage rules. As long as you write queries according to these rules, the generated execution plan is fixed regardless of the actual content in the data tables. However, in real business environments, data volume can have a major impact on query performance, and RBO cannot use this information to obtain a better execution plan.

To address the limitations of RBO, the Cost Based Optimization (CBO) strategy emerged. CBO estimates the cost of an execution plan by collecting statistical information about data, including dataset size, number of columns, and column cardinality.

For example, suppose we have three tables: A, B, and C. When running an A join B join C query, without the corresponding statistics, we cannot determine the cost difference between different join orders. If we collect statistics for the three tables and find that both A and B contain 1 million rows, while C contains only 10 rows, then executing B join C first can significantly reduce the amount of intermediate result data. Without statistics, this is almost impossible to determine.

As query complexity increases, the state space of execution plans becomes extremely large. Anyone who has practiced algorithm problems knows that once the state space is very large, brute-force search is not feasible. At that point, a good search algorithm becomes especially important. CBO usually uses dynamic programming to obtain the optimal solution and reduce the cost of repeatedly computing subspaces. When the state space reaches a certain scale, we can only choose greedy algorithms or other heuristic algorithms to obtain a local optimum. In essence, a search algorithm is a way to trade off search time against result quality.

Common CBO implementation architecture

Record Oriented vs Block Oriented

An execution plan can be considered an execution flow made by connecting a series of operators, or relational algebra operators, end to end. The output of the previous operator is the input of the next operator. Traditional analytics engines are Row Oriented, meaning the output and input of operators are processed row by row.

Consider a simple example with the following table and query:

sql
CREATE TABLE t (n int, m int, o int, p int);
SELECT o FROM t WHERE m < n + 1;

Example source: GitHub - jordanlewis/exectoy

When the query above is expanded into an execution plan, it is roughly as shown in the original diagram.

Execution plan for SQL query SELECT o FROM t WHERE m < n+1

Typically, in the Row Oriented model, execution of the plan can be represented by the following pseudocode:

sql
next: 
  for: 
    row = source.next() 
    if filterExpr.Eval(row): 
      // return a new row containing just column o 
      returnedRow row 
      for col in selectedCols: 
        returnedRow.append(row[col]) 
      return returnedRow

According to the evaluation in DBMSs On A Modern Processor: Where Does Time Go?, this execution method creates a large number of L2 data stalls and L1 I-cache stalls, and also suffers from low branch prediction efficiency.

With the rapid development of hardware technologies such as disks, the widespread use of compression algorithms, encoding algorithms, and storage technologies that trade CPU for I/O has made CPU performance a bottleneck for analytics engines. To solve the problems in Row Oriented execution, academia began exploring new approaches.

The paper Block oriented processing of Relational Database operations in modern Computer Architectures proposed passing data between operators by block. This approach can amortize the time spent on condition checks and branch prediction. Building on this, MonetDB/X100: Hyper-Pipelining Query Execution went a step further and proposed changing data processing from Row Oriented to Column Oriented, further improving CPU cache efficiency and making compiler optimization easier.

In the Column Oriented model, execution of the plan can be represented by the following pseudocode:

sql
// first create an n + 1 result, for all values in the n column 
projPlusIntIntConst.Next(): 
  batch = source.Next() 

  for i < batch.n: 
    outCol[i] = intCol[i] + constArg 

  return batch 

// then, compare the new column to the m column, putting the result into 
// a selection vector: a list of the selected indexes in the column batch 

selectLTIntInt.Next(): 
  batch = source.Next() 

  for i < batch.n: 
    if int1Col < int2Col: 
      selectionVector.append(i) 

  return batch with selectionVector 

// finally, we materialize the batch, returning actual rows to the user, 
// containing just the columns requested: 

materialize.Next(): 
  batch = source.Next() 

  for s < batch.n: 
    i = selectionVector[i] 
    returnedRow row 
    for col in selectedCols: 
      returnedRow.append(cols[col][i]) 
      yield returnedRow

As shown above, Column Oriented execution provides better Data locality and instruction locality, improves CPU cache hit rates, and makes it easier for the compiler to perform SIMD optimization.

Pull Based vs Push Based

In database systems, an input SQL statement is usually converted into a series of operators, and then a physical execution plan is generated for actual computation and result return. In the generated physical execution plan, operators are usually pipelined. There are two common pipeline approaches:

  • A data-driven Push Based mode, where upstream operators push data to downstream operators.
  • A demand-driven Pull Based mode, where downstream operators actively pull data from upstream operators. The classic volcano model is a Pull Based mode.

The Push Based execution mode improves cache efficiency and can better enhance Query performance.

Reference: Push vs. Pull-Based Loop Fusion in Query Engines

Architecture of a Modern Data Lake Analytics Engine

Through the previous section, readers should now have a basic understanding of the frontier theory behind Data lake analytics engines. In this section, we use a modern architecture example to further explain how a Data lake analytics engine organically combines the advanced theories above and presents them to users through an elegant system architecture.

StarRocks modern data lake analytics engine architecture diagram

As shown in the original diagram, this architecture is very concise. The core system contains only two types of processes: FE (Frontend node) and BE (Backend node). It does not depend on any external components, making it easy to deploy and maintain. The FE (Frontend node) is mainly responsible for parsing SQL queries, optimizing queries, and query scheduling. The BE (Backend node) is mainly responsible for reading data from the Data lake and completing a series of operations such as Filter and Aggregate.

Frontend

StarRocks Frontend SQL query processing flowchart

The main role of the FE (Frontend node) is to convert an SQL statement through a series of transformations and optimizations into Fragments that the BE (Backend node) can understand.

Here is an imperfect but easy-to-understand analogy: if the BE (Backend node) cluster is regarded as a distributed thread pool, then a Fragment is a Task in that thread pool.

From SQL text to Fragment, the main work of the FE (Frontend node) includes the following steps:

  • SQL Parse: Converts SQL text into an Abstract syntax tree (AST).
  • Analyze: Performs syntax and semantic analysis based on the AST.
  • Logical Plan: Converts the AST into a logical plan.
  • Optimize: Based on relational algebra, statistics, and the cost model, rewrites and transforms the logical plan, then selects the physical execution plan with the “lowest” cost.
  • Generate Fragment: Converts the physical execution plan selected by the Optimizer into a Fragment that the BE (Backend node) can execute directly.
  • Coordinate: Schedules the Fragment to suitable BE (Backend node) instances for execution.

Backend

StarRocks Backend node architecture diagram

The BE (Backend node) is responsible for receiving Fragments sent by the FE (Frontend node), executing them, and returning results to the FE (Frontend node).

All BE (Backend node) instances are fully peer-to-peer. The FE (Frontend node) assigns data to the corresponding BE (Backend node) instances according to specific strategies.

A typical Fragment workflow reads part of the files in the Data lake, calls the corresponding Reader, such as a Parquet Reader for Parquet files and an ORC Reader for ORC files, to parse the data in these files, uses a Native vectorized engine to further filter and aggregate the parsed data, and then returns the results to other BE (Backend node) instances or to the FE (Frontend node).

Conclusion

This article introduced the core technical principles of a high-speed Data lake analytics engine and compared different technical implementations from multiple dimensions. To support deeper follow-up discussions, it also introduced the system architecture design of an open-source Data lake analytics engine. We look forward to further discussion and exchange with industry peers.

Appendix

Benchmark Test

This test used the standard TPC-H 100G dataset and compared the performance differences among Native tables, Hive external tables, and Trino (PrestoSQL) on Hive.

The comparison test was conducted on a TPC-H 100G dataset with 22 queries. The results are as follows:

TPCH 100G benchmark: StarRocks VS Trino chart

The test covered two query methods: Native table queries and Hive external table queries. The Hive external table queries and Trino on Hive queried the same dataset. The data was stored in ORC format and compressed in zlib format. The test environment was built on Alibaba Cloud EMR.

In the final results, Native table queries took 21 seconds in total, Hive external table queries took 92 seconds in total, and Trino queries took 307 seconds in total. This shows that the Hive external table query mode significantly outperformed Trino in Query performance, but still had a sizable gap compared with Native table queries. The main reasons are that accessing Remote storage increases network overhead, and the latency and IOPS of Remote storage are usually not as good as Local disk. The next plan is to use mechanisms such as cache to address these issues and further narrow the gap between Native table queries and Hive external table queries.