Offset-Value Coding in Database Query Execution

Offset-value codes are surrogate keys and thus akin to hash values. For decades, offset-value codes have sped up internal and external merge sort; recent work has introduced them into database query execution. This paper reports on their performance effects in individual query execution algorithms and in entire query plans, showing their substantial performance benefits over traditional sort-based query execution. Beyond speeding up comparisons in sort-based query algorithms such as merge join and in-stream duplicate removal, offset-value codes can be shared in pipelines of operators in exactly the same places where query optimization can exploit interesting orderings. This includes not only scans of ordered storage structures such as b-trees but also reassembly of complex application objects from database relations in normal forms. New experiments show the value of combining the proven performance benefits of interesting orderings and those of surrogate keys such as hash values and, now, offset-value codes.