Technical Perspective:Optimistically Compressed Hash Tables & Strings in the USSR

摘要

Hash tables are possibly the single most researched element of the database query processing layers. There are many good reasons for that. They are critical for some key operations like joins and aggregation, and as such are one of the largest contributors to the overall query performance. Their efficiency is heavily impacted by variations of workloads, hardware and implementation, leading to many research opportunities. At the same time, they are sufficiently small and local in scope, allowing a starting researcher, or even a student, to understand them and contribute novel ideas. And benchmark them... Oh, the benchmarks... :)This paper by Tim Gubner, Viktor Leis and Peter Boncz addresses less frequently researched aspects of hash tables, in particular string processing, and presents some useful real-system implementation ideas. It improves the main aspects of the (in-memory) hash table performance, CPU operations and memory accesses, with 3 techniques.