Expired Oracle Patent Opens Fast Sorting Algorithm to Open Source Databases

"Granted in 2010 to Oracle Corporation, patent US7680791B2 covers a method for sorting data using common prefix bytes and a sort algorithm, which the inventor suggests calling "Orasort", that addresses the inefficiency caused by repeatedly comparing the same leading parts of similar keys during sorting. The algorithm combines several techniques: skipping common prefixes when comparing keys, adaptively switching between quicksort and radix sort, caching key substrings to reduce cache misses, and producing results before the sort completes."

"I invented this while at Oracle and it landed in 10gR2 with claims of ~5X better performance vs the previous sort algorithm used by Oracle. I hope for an open-source implementation one day. The patent has a good description of the algorithm, it is much easier to read than your typical patent. Thankfully the IP lawyer made good use of the functional and design docs that I wrote."

An expired Oracle patent now permits open-source databases to implement a fast sorting technique freely. Patent US7680791B2 described a sort that uses common prefix bytes and an algorithm referred to as "Orasort" to skip redundant comparisons of leading key bytes. The method combines skipping shared prefixes, adaptively switching between quicksort and radix sort, caching key substrings to cut cache misses, and producing partial results before completion. Dividing data into smaller groups increases shared prefix length, enabling remembered prefixes to be skipped and next bytes to be preloaded. Tests showed roughly 5X improvement versus the previous Oracle sort, and database projects are preparing implementations.

Read at InfoQ