Efficient Parallel Hash-Join Operator for Speeding up the SSB

**Motivation:** The *Star Schema Benchmark (SSB)* [1] is a well-known benchmark for analytical query processing. Its schema contains a central fact table and multiple dimension tables. The 13 queries of the benchmark involve one or multiple primary-key/foreign-key (semi-)joins. In fact, these joins are the most expensive operations in the SSB queries. Hence, a highly efficient physical join operator is crucial for achieving superb performance on the SSB. Given that the join predicate is equality and the join inputs are typically not sorted, a *hash-join* is the most promising physical join operator for the SSB. A prototypical hash-join consists of two phases: In the *build phase*, one of the inputs (typically the smaller one) is scanned and its keys are inserted into a hash table along with a payload or tuple id. Then, in the *probe phase*, the other input is scanned and its keys are looked up in the hash table; in case of a match, an output tuple is generated. The efficient implementation of hash-joins has been the subject of research for many years. However, so far DAPHNE only has a naive baseline implementation of a hash-join operator.

**Task:** The goal of this project is to design and implement a highly efficient hash-join in DAPHNE by taking inspiration from existing work in this field and possibly adding a few new optimizations. In the end, a significant performance improvement on the SSB is expected (and very realistic); ideally, DAPHNE would come close to state-of-the-art database management systems. To this end, we need:

1. *An efficient hash table implementation.* Hash tables are a fundamental data structure for mapping a key to a value with constant time complexity. Essentially, a hash is calculated for a key and determines where in the hash table the value for that key could be found. Hash collisions are a special challenge and can be addressed using various hashing schemes (e.g., linear probing). Furthermore, there are numerous simple (e.g., multiply-shift) and complex (e.g., Murmur) hash functions that promise to make collisions more or less likely, given a certain load factor. A good overview of hash tables can be found in an E&A paper on this subject [2].
1. *An efficient build-operator and an efficient probe-operator* for the two phases of the hash-join. These should be implemented as separate physical operators so that they can become part of different pipelines in the query. For top efficiency, both operators should exploit parallelism offered by modern processors in terms of multi-threading (MIMD) and optionally also in terms of SIMD instructions that process multiple values at a time. Multi-threading could be handled inside the operator, but ideally it would be achieved through an integration with and extension of DAPHNE’s vectorized engine. Furthermore, well-known techniques such as bloom filters and adequate partitioning should be employed. See Matthias Boehm's ADBS lecture slides for an overview of related work on hash-joins [3]. Besides that, there is room for new ideas as well.
1. *The integration of the new data structure and operators in DaphneIR*, DAPHNE’s [MLIR](https://mlir.llvm.org/)-based intermediate representation. This step involves adding hash tables as a new data type to DaphneIR and adding new operations for the build and probe phase of a hash join. Furthermore, there should be compiler passes that rewrite a generic join operation to a build and probe operation.

Different designs of hash-joins and semi-joins can be implemented and compared to each other. The efficiency of the newly added hash-join implementation shall be evaluated using micro benchmarks on various aspects of join processing as well as end-to-end experiments using the Star Schema Benchmark. The latter has already been implemented in DAPHNE (and will be made available in time), such that the main focus will be on the impact of the new hash-join in the context of the SSB queries. The performance should also be compared to existing open-source DBMSs such as DuckDB, MonetDB, PostgreSQL, MySQL, and SQLite.

**Hints:**
- Besides the execution of a given join, *join ordering* (determining a good execution order of multiple joins in a query) is a crucial challenge in query optimization. However, for this project we will assume we know a good execution order of the joins. The focus will be on the execution itself.

-----

[1] Pat O'Neil, Betty O'Neil, Xuedong Chen: Star Schema Benchmark. Revision 3, June 5, 2009 [[pdf](https://www.cs.umb.edu/~poneil/StarSchemaB.pdf)]
[2] Stefan Richter, Victor Alvarez, Jens Dittrich: A Seven-Dimensional Analysis of Hashing Methods and its Implications on Query Processing. Proc. VLDB Endow. 9(3): 96-107 (2015) [[pdf](https://www.vldb.org/pvldb/vol9/p96-richter.pdf)]
[3] Matthias Boehm: Architecture of DB Systems (WiSe 2023/24), 06 Query Processing, slides 26ff [[pdf](https://mboehm7.github.io/teaching/ws2324_adbs/06_QueryProcessing.pdf)]