3 months 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.