Efficient Processing of Star Schema Benchmark

**Motivation.** Relational query processing is an integral part of integrated data analysis pipelines. For instance, the data to be processed by machine learning techniques is often stored in a database and needs to be retrieved by relational queries. Besides that, the output of complex simulations is often analyzed by relational queries. However, at the moment the support for efficient relational processing of SQL queries in DAPHNE is still limited.

**Task.** This project is about improving DAPHNE’s query processing capabilities. As a concrete guiding example, we use the well-known Star Schema Benchmark (SSB), which consists of 13 analytical SQL queries. The goal is to ensure that these queries (or a reasonable subset of them) can be run in DAPHNE, whereby the runtime performance should come close to existing systems and libraries for relational processing.

To this end, multiple parts of the system need to be improved, such that students get a good understanding of the overall relational query processing in DAPHNE and in general. Besides some small extensions to DAPHNE’s SQL parser, impactful additions to choose from include, but are not limited to:
- relational algebra rewrites such as selection push-down, projection push-down, and join ordering
- physical operator selection (e.g., join variants)
- operator pipeline fusion.
- efficient implementations of physical operators (kernels) for relational operations (e.g., hash join)
- support for relational operators in DAPHNE’s vectorized execution engine for parallel and cache efficient processing

Implementation in C++.

**Hints on approaching this task.**
- Get familiar with the Star Schema Benchmark. There is a [paper](https://www.cs.umb.edu/~poneil/StarSchemaB.pdf) describing it and multiple GitHub repositories, such as [this one](https://github.com/lemire/StarSchemaBenchmark), which provide the data generator.
- Use the DAPHNE documentation and external resources to get familiar with (1) SQL support in DaphneDSL scripts, (2) DAPHNE’s SQL parser (`src/parser/sql/`), (3) the DAPHNE compiler (`src/compiler/`), (4) how to implement rewrites in [MLIR](https://mlir.llvm.org/docs/) (the domain-specific compiler framework which DAPHNE’s optimizer/compiler is based on), (4) physical operator (kernel) implementation in DAPHNE (`src/runtime/local/kernels/`), and (5) DAPHNE’s vectorized engine (`src/compiler/lowering/VectorizationPass.cpp`, `src/runtime/local/vectorized/`).
- Tackle the Star Schema Benchmark step by step. Begin with query 1.1 (the simplest one), and try to make that work first. Don’t forget to (automatically) compare the query results to those obtained with an existing DBMS (e.g., DuckDB) to ensure correctness. Once one or more queries are running, think about which of the optimizer and runtime components mentioned above can be helpful to improve the overall query performance.
- The query processing in DAPHNE may start with loading CSV files containing the data.
- Since string processing support is still limited in DAPHNE (see #629), you can replace all string columns in the SSB’s schema by integers columns by applying an order-preserving dictionary encoding to the values, i.e., by mapping each distinct string value to a unique integer code. This step can be done offline.
- Implement your design, including tests and documentation.
- Think of meaningful experiments to highlight the strengths and weaknesses of your implementation of the relational query processing in DAPHNE in terms of query runtime and memory footprint. The experiments should focus on the Star Schema Benchmark and compare DAPHNE to alternative systems/libraries such as DuckDB and pandas.

**Scaling with the team size.** This project could best be done by a team of 2-3 students, but individual students are also possible. The task size can be scaled up or down with the number of team members, e.g., by focusing on more or less aspects of the problem.

Start with SSB query 1.1 and read SQL support in DaphneDSL, src/parser/sql/, src/compiler/, and the relevant runtime kernels. Compare results with DuckDB, then investigate one or more listed optimizer, physical-operator, or vectorization areas. Done means a defined SSB query subset runs correctly with tests, documentation, and runtime and memory comparisons.

Written by the indexing model from the issue text.