# SAHA: A String Adaptive Hash Table for Analytical Databases
## 3 Constructs
Otherwise, we have to always compare two long strings to check if they are equal, even when their hash values are different. Hash Table L also contains a memory pool called String Arena to keep the strings inserted. It is necessary to have complete ownership of the inserted data inside the hash table, because when processing each row in group or join workloads, the current record will be destroyed after insertion. The string key dispatcher accepts a string key and dispatches it to the corresponding hash table's routine. Because it sits in the critical part of code, the dispatcher needs careful implementation and optimization to avoid introducing performance regressions. In order to dispatch short strings, it requires loading the string data from the given pointer into current stack, and converting it into a number array. To achieve efficient memory copying, a constant number of bytes should be used instead of doing memcpy(dst, src, len) directly. We use eight bytes as a minimal memory copy unit to read one integer at a time from the string data into the array. If the string length is not divisible by eight, we load the last bytes starting from the end position minus eight. Thus, we still copy eight bytes, but shifting out the H part, as shown in Figure 6. However, if the string is shorter than eight bytes, copying eight bytes might lead to segmentation fault, which is demonstrated as underflow and overflow in Figure 6. (A segmentation fault is raised by hardware with memory protection, notifying an operating system the software has attempted to access a restricted area of memory.) To resolve this issue, we do a memory address check for the string pointer when dispatching to Hash Table S1. Since memory page size is of 4096 bytes, if pointer & 2048 = 0, it means the string data is at the top half of a memory page and it can only be underflow. We can then safely copy eight bytes from 0 and get rid of the T part. Otherwise, it can only be overflow and our previous algorithm will work correctly. Listing 1 shows the implementation of the string key dispatcher in pseudo C++. It accepts a string key with pointer and size, and dispatches the key to sub hash tables. Different hash tables require different key types but the same string data; as a result, a union structure is used. The length of the T part in each string key can be calculated using (-key.size & 7) * 8 and is used for fast memory loading. There are two main routines for a hash table when used for group and join workloads: emplace and find. The emplace routine is for inserting data into the hash table if the given key is not yet found inside, or else returning the data in the hash table with the key equal to the one being inserted. The find routine is slightly different from emplace in that it does not insert data when the given key is missing in the hash table, but returns a key-not-found indicator to the routine's caller. Here we demonstrate dispatching over emplace, and other routines are dispatched similarly. The implementation needs to make sure that all the method bodies of the sub hash tables get inlined into the dispatching code. Otherwise the dispatching process would impact the performance due to introducing additional function calls. In order to achieve this effect, the actual implementation requires careful tuning. One possible implementation can be referred to in [28]. In addition to these constructs, SAHA also provides the following optimizations to further reduce the runtime:  
* **Slot empty check for Hash Table Sn. ** As the string length is not stored in Hash Table Sn, one way to check if a given slot is empty is to verify that all the integers in the slot's key array are  
Figure 6: Three different cases of the memory layout of a string key with length shorter than eight bytes. equal to zero. However, since the zero byte in UTF8 is code point 0, NULL character. There is no other Unicode code point that will be encoded in UTF8 with a zero byte anywhere within it.