# SAHA: A String Adaptive Hash Table for Analytical Databases
## 4 Pre-Hashing and Vectorized Programming Interface  
SAHA is designed for analytical databases, and the vectorized processing query pipeline gives a unique opportunity for optimizations. One of the main optimizations is pre-hashing. When doing element insertion or lookup in hash tables, a required step is to compute the element's hash value. This requires examining the entire content of the element, which means the CPU cache will be populated with this element. When the string is long, it can take up a lot of space in the cache and potentially evict the ones used for hash table slots, leading to cache contention. In order to better utilize CPU cache when probing, we need to avoid reading the string content. This is possible for inserting new long strings or finding non-existing long strings with precomputed hashes. For instance, when a fresh long string is inserted into SAHA, it gets dispatched to Hash Table L. Then we directly use the precomputed hash for probing. Since the Hash Table L also stores saved hashes in slots, it is likely for a fresh string to find an empty slot without any string comparison involved. Even if two different long  
\begin{table}
\begin{tabular}{c c c c} \hline \hline
**Parameter** & **Baseline** & **SAHA** & **Optimizations** \\ \hline \(H\) & 33 & 22 & Memory loading optimization \\ \(P_{L}+P_{C}\) & 56 & 37 & String inlining and slot empty check optimization \\ \(S_{P}\) & 34 & 6 & String dispatching and automatic ownership handling \\ \(S_{W}\) & 16 & 14 & Selective hash saving \\ \hline
**Unit** & Cycles per key & Cycles per key \\ \hline \hline \end{tabular}
\end{table}
Table 2: Comparison of the complexities of cost model parameters with and without optimization.  
strings have the same hash value, comparing these two strings will likely finish early unless these two strings share a long prefix. For long strings, the dataset is usually of high cardinality, and processing fresh keys is the majority case for the hash table. As a result, there is a high chance we can get rid of reading the string content with precomputed hash values.  
We can calculate the hash values after receiving a batch of records but before processing them in the hash table. Figure 7 illustrates the comparison with and without pre-hashing. It is trivial to implement pre-hashing outside the hash table. However, this is a bad design for analytical databases, since it also aggregates integer keys and compound keys where pre-hashing does not make sense. Thus, the optimization should be transparent to the aggregator and live inside the hash table. In order to achieve pre-hashing, the hash table should receive a batch of records instead of one row per time. Therefore, we proposed a vectorized programming interface for SAHA. It can also be applied to other hash tables.  
Figure 8 shows a diagram of a hash table which accepts a batch of records. It precomputes the hash values before doing other operations. After processing each record, the registered callback is invoked to finish the operation. In the aggregator example, the callback is an aggregate function applied to the record. Listing 2 shows the comparison of the emplace routine with and without vectorization. With the help of the vectorized programming interface, we can achieve other optimizations such as reordering the batch of records to break data dependency.  
Figure 8: Aggregator using a hash table with vectorized programming interface and pre-hashing.  
Figure 7: Comparison of vectorized aggregation implementations with and without pre-hashing.