Common prefix skipping, adaptive sort

# Common prefix skipping, adaptive sort Source: [http://smalldatum.blogspot.com/2026/01/common-prefix-skipping-adaptive-sort.html](http://smalldatum.blogspot.com/2026/01/common-prefix-skipping-adaptive-sort.html) The patent expired for[US7680791B2](https://patents.google.com/patent/US7680791B2)\. I invented this while at Oracle and it[landed in 10gR2](https://www.oracle.com/technetwork/database/performance/twp-general-sort-performance-10gr2--130000.pdf)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\. The patent is for a new in\-memory sort algorithm that needs a name\. Features include: - common prefix skipping - adaptive - key substring caching - produces results before sort is done **Update**: - the sort algorithm needs a name and*common prefix skipping adaptive quicksort*is much too long\. So I suggest Orasort\. **How it came to be** From 2000 to 2005 I worked on query processing for Oracle\. I am not sure why I started on this effort and it wasn't suggested by my bosses or peers\. But the[Sort Benchmark](https://sortbenchmark.org/)contest was active and I had more time to read technical papers\. Perhaps I was inspired by the[Alphasort](https://www.cs.cmu.edu/~natassa/courses/15-721/papers/P233.PDF)paper\. While the Sort Benchmark advanced the state of the art in sort algorithms, it also encouraged algorithms that were great for benchmarks \(focus on short keys with uniform distribution\)\. But keys sorted by a DBMS are often much larger than 8 bytes and adjacent rows often have long common prefixes in their keys\. So I thought about this while falling to sleep and after many nights realized that with a divide and conquer sort, as the algorithm descends into subpartitions of the data, that the common prefixes of the keys in each subpartition were likely to grow: - were the algorithm able to remember the length of the common prefix as it descends then it can skip the common prefix during comparisons to save on CPU overhead - were the algorithm able to learn when the length of the common prefix grows then it can switch from quicksort to most\-significant digit \(MSD\) radix sort using the next byte beyond the common prefix and then switch back to quicksort after doing that - the algorithm can cache bytes from the key in an array, like Alphasort\. But unlike Alphasort as it descends it can cache the next few bytes it will need to compare rather than only caching the first few bytes of the key\. This provides much better memory system behavior \(fewer cache misses\)\. **Early implementation** This might have been in 2003 before we were able to access work computers from home\. I needed to get results that would convince management this was worth doing\. I started my proof\-of\-concept on an old[PowerPC based Mac](https://en.wikipedia.org/wiki/Power_Macintosh)I had at home that found a second life after I installed[Yellow Dog Linux](https://en.wikipedia.org/wiki/Yellow_Dog_Linux)on it\. After some iteration I had good results on the PowerPC\. So I brought my source code into work and repeated the test on other CPUs that I could find\. On my desk I had a Sun workstation and a Windows PC with a 6 year old Pentium 3 CPU \(600MHz, 128kb L2 cache\)\. Elsewhere I had access to a new Sun server with a 900MHz[UltraSPARC IV](https://en.wikipedia.org/wiki/UltraSPARC_IV)\(or IV\+\) CPU and an HP server with a PA RISC CPU\. I also implemented other state of the art algorithms including Alphasort along with the old sort algorithm used by Oracle\. From testing I learned: 1. my new sort was much faster than other algorithms when keys were larger than 8 bytes 2. my new sort was faster on my old Pentium 3 CPU than on the Sun UltraSPARC IV The first was great news for me, the second was less than great news for Sun shareholders\. I never learned why that UltraSPARC IV performance was lousy\. It might have been latency to the caches\. Once I had great results, it was time for the functional and design specification reviews\. I remember two issues: - the old sort was stable, the new sort was not - the new sort has a bad, but unlikely, worst\-case And once I had this implemented within the Oracle DBMS I was able to compare it with the old sort\. The new sort was often about 5 times faster than the old sort\. I then compared it with SyncSort\. I don't remember whether they had a DeWitt Clause so I won't share the results but I will say that the new sort in Oracle looked great in comparison\. **The End** The new sorted[landed in 10gR2](https://www.oracle.com/technetwork/database/performance/twp-general-sort-performance-10gr2--130000.pdf)and was featured in a white\-paper\. I also got a short email from Larry Ellison thanking me for the work\. A promotion or bonus would have to wait as you had to play the long\-game in your career at Oracle\. And that was all the motivation I needed to leave Oracle \-\- first for a startup, and then to Google and Facebook\. After leaving Oracle, much of my time was spent on making MySQL better\. Great open\-source DBMS, like MySQL and PostgreSQL, were not good for Oracle's new license revenue\. Oracle is a better DBMS, but not everyone needs it or can afford it\.