Oracleの特許が失効：ソートを5倍高速化した「Orasort」アルゴリズムの全貌

Common prefix skipping, adaptive sort

Oracle 10gR2で採用され、従来比約5倍の性能向上を実現したインメモリソートアルゴリズムの特許が失効しました。著者（発明者）がその設計思想と実装の裏話を公開します。共通プレフィックスのスキップ、クイックソートとMSD基数ソートの適応的切り替え、キー部分文字列のキャッシュにより、DBMSのソート性能を劇的に改善しました。開発の動機からOracle退社に至るまでの経緯も綴られています。