Offset-value coding in database query processing

Recent work measures how much offset-value coding speeds up database query operations. It speeds up not only sorting but also duplicate removal, grouping (aggregation) in sorted streams, order-preserving exchange (shuffle), and merge join. It already saves thousands of CPUs in Google's Napa and F1~Query systems, e.g., in grouping algorithms and in log-structured merge-forests. In order to achieve the full benefits of interesting orderings, however, query execution algorithms must not only consume and exploit offset-value codes but also provide offset-value codes to the next operation in the pipeline. This short paper describes in detail how order-preserving algorithms (from filter to merge join and even shuffle) can compute offset-value codes for their outputs. These calculations are surprisingly simple and very efficient.