# SAHA: A String Adaptive Hash Table for Analytical Databases
## 2 Related Works  
### Hash Tables  
Hash tables are a well established and extensively researched data structure that still continues to be a hot topic of research. We have briefly mentioned implementations that are well known in textbooks in Section 1. Here, we discuss three other implementations actively used in the real world: (1) the Robin-Hood table [7] is a derived linear probing hash table that constrains the length of each slot's conflicting chain by shifting the current elements out of the slot if the probing key is too far away from its slot; (2) Hopscotch [8] is similar, but instead of shifting elements out, it swaps the probing key towards its slot based on the metadata in each slot; (3) Cuckoo hash [10] uses two hash functions, providing two possible locations in the hash table for each key. As a result, it guarantees a low number of memory accesses per lookup. The conflicting chain becomes a graph-like structure with interesting mathematical characteristics, which attracts many researchers [11; 12; 13]. All these works are focused on general datasets and are orthogonal to ours. SAHA can use any of these hash tables as the backend with small adaptations.  
Some of the hash tables focus on memory saving by supporting high load factors [14; 15]. These compact hash tables use a bitmap for occupancy check and a dense array to store the elements. However, the actual amount of memory saved is insignificant when processing string data compared to string encoding techniques. With additional bitmaps to maintain, both insertion and lookup operations become slower. SAHA optimizes memory usage by inlining short strings. It achieves similar memory consumption but is more efficient than these compact hash tables.  
In industry, the state-of-the-art hash tables used widely are Google's Swiss-Table [16] and Facebook's F14 Table [17]. Both are designed for general usage and optimized for modern hardware. The technique is to group elements into small chunks and pack each chunk as a small hash table with additional metadata for probing. Each of these chunks can be operated more efficiently compared to operating over the entire hash table. The main difference between Swiss-Table and F14 Table is that in Swiss-Table, the chunk's metadata is stored separately, while in F14, the metadata and the elements of a chunk are stored together. Though they achieve good performance in common lookup and insert operations, they are slightly slower than carefully crafted linear probing hash tables, such as the one used in Click-House [3], which is the fastest aggregation implementation we can find. It uses specialized linear hash tables which are trimmed for group and join operations and has optimized implementation of rehashing. It is 20% faster than both Swiss-Table and F14 Table in group workloads. However, it is not optimized when dealing with string data. SAHA combines the string optimizations with this heavily tuned hash table, which makes it competent for analysis workloads on string datasets.  
Figure 4: A bar graph of time consumption of various hash tables to process group and join benchmarks compared to SAHA.