{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T23:42:25Z","timestamp":1780357345070,"version":"3.54.1"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,3,13]],"date-time":"2023-03-13T00:00:00Z","timestamp":1678665600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2023,3,31]]},"abstract":"<jats:p>Sorting and searching are large parts of database query processing, e.g., in the forms of index creation, index maintenance, and index lookup, and comparing pairs of keys is a substantial part of the effort in sorting and searching. We have worked on simple, efficient implementations of decades-old, neglected, effective techniques for fast comparisons and fast sorting, in particular offset-value coding. In the process, we happened upon its mutually beneficial relationship with prefix truncation in run files as well as the duality of compression techniques in row- and column-format storage structures, namely prefix truncation and run-length encoding of leading key columns. We also found a beneficial relationship with consumers of sorted streams, e.g., merging parallel streams, in-stream aggregation, and merge join. We report on our implementation in the context of Google\u2019s Napa and F1\u00a0Query systems as well as an experimental evaluation of performance and scalability.<\/jats:p>","DOI":"10.1145\/3570956","type":"journal-article","created":{"date-parts":[[2022,11,11]],"date-time":"2022-11-11T10:58:09Z","timestamp":1668164289000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Robust and Efficient Sorting with Offset-value Coding"],"prefix":"10.1145","volume":"48","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9893-5725","authenticated-orcid":false,"given":"Thanh","family":"Do","sequence":"first","affiliation":[{"name":"Celonis Inc., New York, NY"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0194-6466","authenticated-orcid":false,"given":"Goetz","family":"Graefe","sequence":"additional","affiliation":[{"name":"Google Inc., Madison, WI, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,3,13]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.14778\/3476311.3476377"},{"key":"e_1_3_1_3_2","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1145\/1734663.1734671","volume-title":"Proceedings of the 1970 ACM SIGFIDET (Now SIGMOD) Workshop on Data Description, Access and Control (SIGFIDET\u201970)","author":"Bayer R.","year":"1970","unstructured":"R. Bayer and E. McCreight. 1970. Organization and maintenance of large ordered indices. In Proceedings of the 1970 ACM SIGFIDET (Now SIGMOD) Workshop on Data Description, Access and Control (SIGFIDET\u201970). ACM, New York, NY, 107\u2013141. 10.1145\/1734663.1734671"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/320521.320530"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/319983.319987"},{"key":"e_1_3_1_6_2","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1145\/1806596.1806638","volume-title":"Proceedings of the 31st ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI\u201910)","author":"Chambers Craig","year":"2010","unstructured":"Craig Chambers, Ashish Raniwala, Frances Perry, Stephen Adams, Robert R. Henry, Robert Bradshaw, and Nathan Weizenbaum. 2010. FlumeJava: Easy, efficient data-parallel pipelines. In Proceedings of the 31st ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI\u201910). ACM, New York, NY, 363\u2013375. 10.1145\/1806596.1806638"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/1365815.1365816"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/356770.356776"},{"key":"e_1_3_1_9_2","volume-title":"IBM Technical Disclosure Bulletin","author":"Conner W. M.","year":"1977","unstructured":"W. M. Conner. 1977. Offset-value coding. In IBM Technical Disclosure Bulletin."},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/2491245"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_3_1_12_2","unstructured":"Thanh Do Goetz Graefe and Jeffrey Naughton. 2022. Efficient sorting duplicate removal grouping and aggregation. ACM Trans. Database Syst . (2022). 10.1145\/3568027"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/85.988579"},{"key":"e_1_3_1_14_2","unstructured":"Google. 2022. A microbenchmark support library. https:\/\/github.com\/google\/benchmark."},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/152610.152611"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/1132960.1132964"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1561\/1900000028"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/5.1.10"},{"key":"e_1_3_1_19_2","volume-title":"Enterprise System Architecture\/370, Principles of Operation","year":"1988","unstructured":"IBM. 1988. Enterprise System Architecture\/370, Principles of Operation. IBM publication SA22-7200-0."},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/320831.320834"},{"key":"e_1_3_1_21_2","volume-title":"International Conference on Management of Data (COMAD\u201905)","author":"Iyer Bala R.","year":"2005","unstructured":"Bala R. Iyer. 2005. Hardware assisted sorting in IBM\u2019s DB2 DBMS. In International Conference on Management of Data (COMAD\u201905)."},{"key":"e_1_3_1_22_2","first-page":"16","volume-title":"Proceedings of the 23rd International Conference on Very Large Data Bases (VLDB\u201997)","author":"Jagadish H. V.","year":"1997","unstructured":"H. V. Jagadish, P. P. S. Narayan, S. Seshadri, S. Sudarshan, and Rama Kanneganti. 1997. Incremental organization for data recording and warehousing. In Proceedings of the 23rd International Conference on Very Large Data Bases (VLDB\u201997). Morgan Kaufmann Publishers Inc., San Francisco, CA, 16\u201325. http:\/\/dl.acm.org\/citation.cfm?id=645923.671013."},{"key":"e_1_3_1_23_2","volume-title":"The Art of Computer Programming, Volume 3: Sorting and Searching","author":"Knuth Donald E.","year":"1998","unstructured":"Donald E. Knuth. 1998. The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed.). Addison Wesley Longman Publishing Co., Inc., Redwood City, CA."},{"key":"e_1_3_1_24_2","volume-title":"The Optimization of Queries in Relational Databases","author":"Kooi Robert Philip","year":"1980","unstructured":"Robert Philip Kooi. 1980. The Optimization of Queries in Relational Databases. Ph.D. Dissertation. Cleveland, OH. AAI8109596."},{"key":"e_1_3_1_25_2","doi-asserted-by":"crossref","first-page":"472","DOI":"10.1145\/276304.276346","volume-title":"Proceedings of the 1998 ACM SIGMOD International Conference on Management of Data (SIGMOD\u201998)","author":"Larson Per-\u00c5ke","year":"1998","unstructured":"Per-\u00c5ke Larson and Goetz Graefe. 1998. Memory management during run generation in external sorting. In Proceedings of the 1998 ACM SIGMOD International Conference on Management of Data (SIGMOD\u201998). ACM, New York, NY, 472\u2013483. 10.1145\/276304.276346"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.2200\/S00394ED1V01Y201111DTM021"},{"issue":"4","key":"e_1_3_1_27_2","doi-asserted-by":"crossref","first-page":"603","DOI":"10.1007\/BF01354877","article-title":"AlphaSort: A cache-sensitive parallel external sort","volume":"4","author":"Nyberg Chris","year":"1995","unstructured":"Chris Nyberg, Tom Barclay, Zarka Cvetanovic, Jim Gray, and Dave Lomet. 1995. AlphaSort: A cache-sensitive parallel external sort. VLDB Journal 4, 4 (Oct.1995), 603\u2013628. http:\/\/dl.acm.org\/citation.cfm?id=615232.615237.","journal-title":"VLDB Journal"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050048"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3229871"},{"key":"e_1_3_1_30_2","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1145\/582095.582099","volume-title":"Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data (SIGMOD\u201979)","author":"Selinger P. Griffiths","year":"1979","unstructured":"P. Griffiths Selinger, M. M. Astrahan, D. D. Chamberlin, R. A. Lorie, and T. G. Price. 1979. Access path selection in a relational database management system. In Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data (SIGMOD\u201979). ACM, New York, NY, 23\u201334. 10.1145\/582095.582099"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.14778\/2536222.2536232"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3570956","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3570956","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:37:53Z","timestamp":1750178273000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3570956"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,13]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,3,31]]}},"alternative-id":["10.1145\/3570956"],"URL":"https:\/\/doi.org\/10.1145\/3570956","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,3,13]]},"assertion":[{"value":"2022-02-11","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-11-02","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-03-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}