Patent for Oracle’s Sorting Algorithm Expired; Now Available in the Public Domain.

Oracle is one of the most popular database products in the world.

Highly complex applications rely on Oracle for their critical data and transactions.

Oracle has had to invent many optimisation techniques so that its database becomes faster and more reliable.

One of those inventions is a sorting technique for database tables.

Oracle invented an algorithm named Orasort, which made sorting 5x faster. The Oracle team not only implemented it intelligently but also optimised it at the CPU level.

This article will explain the Orasort algorithm in simple language that even a programmer with no experience can understand.

A patent for this algorithm was registered for Mark Callaghan.

After reaching its 20-year term in 2024, the patent for Orasort automatically expired and entered the public domain.

We will see how this algorithm works, what benefits cloud companies like AWS and open-source communities are getting from it, and other important things.

Before we begin to understand how Orasort works, we need to understand how traditional sorting works and how it affected Oracle’s performance.

How Traditional Sorting Worked in a DBMS

Character-wise Sorting

In a traditional sorting algorithm, each character in one string is compared with the corresponding character in another string.

Sorting is performed character by character between two strings.

It does not sort only by the first character, such as values starting with ‘A’; the database also needs to sort values that start with ‘A’.

Consider the following example.

There are two values that start with ‘A’:

Apple

Amazon

Now, sorting between these two words starts.

‘A’ is the same in both words.

Now, the second character needs to be checked. ‘P’ is compared with ‘M’, and since M < P, the decision is made based on the second character.

Now, the ascending order is:

Apple

Amazon

The above comparison was simple; the DBMS had to compare only two characters.

Now consider the second example.

Applet

Apples

Here, the comparison will continue until the last character, and the ascending order will be:

Apples

Applet

Now consider the following example.

Apple is good

Apple is bad

Here, the comparison will take more CPU cycles.

The ascending order will be:

Apple is bad

Apple is good

So, this is the way traditional sorting works.

We can imagine how time-consuming it is.

Orasort Comes as a Saviour

The traditional sorting method used character-wise comparison, or in short, 1-byte comparison.

Orasort came up with a very smart idea in which the Oracle team utilised CPU registers.

A CPU register is naturally 8 bytes in size, and if Oracle extracts 8 bytes from two strings for comparison, then the comparison requires fewer registers and fewer CPU cycles.

Oracle extracts the first 8 bytes from both values and converts those bytes into a 64-bit integer.

Then, each value becomes a single 64-bit integer, and the same process happens with the other value being compared.

If a decision is made, the comparison stops. Otherwise, it takes the next 8 bytes, and the comparison continues.

 

Subscribe to us for lifetime free content.

Benefits Provided by Orasort

 

Open Source Databases

Since becoming public, Orasort has provided massive benefits to open-source communities.

Open-source databases, including MySQL and PostgreSQL, have integrated Orasort and are experimenting with it.

Cost-cutting in Cloud Computing

Companies use cloud services for their businesses. Orasort lowers operational costs due to fewer CPU cycles.

High-level Process of Orasort

 

Key Extraction and Normalization

Suppose a table has 10 thousand records, and the column named ’email’ has been selected for sorting.

Then, 10 thousand records will be loaded into RAM in a buffer.

However, these records are not fetched with all their values; only keys and IDs are generated for each record.

These records are loaded into the sorted area, where sorting takes place.

Now, the Orasort process that we discussed earlier takes place in this sorted area, which is a part of RAM.

But what if the records are in the millions? Oracle cannot load all record pointers into the buffer.

In this case, Oracle creates multiple parts of the data and keeps them on disk for future use. It then brings those parts into RAM one by one.

Writing Sorted Data Back to Disk

Writing is an asynchronous task, and Oracle does not take the approach of writing all sorted data at once.

It uses an intermediate writing approach, where it keeps writing while Orasort is still running. When the writing is complete, the final merge happens on the disk.

 

DSS is not a normal tech blog; we study Open Source projects, act as a tech journalist, and present you deep technical information on almost any technical platform. Consider subscribing to us. We are building community where you will get free life time access of such articles.