Common prefix skipping, adaptive sort

20 days ago

Patent US7680791B2 expired for an in-memory sort algorithm invented at Oracle, featured in 10gR2 with ~5X performance improvement over the previous sort.
Algorithm features include common prefix skipping, adaptive switching between quicksort and MSD radix sort, key substring caching to reduce CPU cache misses, and producing results before completion.
Proposed name 'Orasort' as a shorter alternative to 'common prefix skipping adaptive quicksort'.
Development was inspired by the Sort Benchmark contest and Alphasort paper, focusing on large keys with common prefixes in DBMS contexts.
Algorithm optimizations include remembering common prefix lengths for comparison skipping and caching next key bytes for better memory behavior.
Implementation challenges included making the new sort stable (addressed but not detailed) and managing worst-case quicksort pivot risks via statistical analysis using Scheme.
Post-Oracle work involved improving MySQL and recent developments in RonDB for parallel sorted index scans and merge sort optimizations.
Discussions on career progression at Oracle noted delayed rewards compared to peers at other companies.
References provided for parallel merge sort optimizations, including RocksDB's N-way heap and Goetz Graefe's work on offset-value coding.

Hasty Briefsbeta