Optimizing External Merge Sort for Projection with Duplicate Elimination

1. Analyzing the I/O Cost of External Merge Sort

The performance of any external memory algorithm is dominated by the amount of data it reads from and writes to disk. In external merge sort, we make multiple passes over the data. In each full pass, we read every page of the file and write every page back out to a new file.

Therefore, the total I/O cost can be expressed as:

where N is the number of pages in the file. Our main goal in optimizing external sort is to minimize the number of passes.

Let's assume we have B pages available in our buffer pool. How can we use them to reduce the number of passes? The strategy involves two key ideas:

1. Make initial runs as long as possible: In Pass 0, we can read B pages into memory at once, sort them, and write out a single sorted run of size B. This "chops" the base of the conceptual merge tree, creating fewer, longer initial runs.
2. Merge as many runs as possible at once: In subsequent merge passes, we need one buffer page for the output. This leaves B-1 pages to be used as input buffers. Therefore, we can perform a (B-1)-way merge, which "widens" the merge tree.

This short video explains these two optimizations visually and intuitively.

The General Cost Formula

As the video explained, these optimizations lead us to a general formula for the number of passes and the total I/O cost.

Let's summarize the key formulas from the slides:

• Pass 0: We use all B buffer pages to create initial sorted runs of size B.
  • Number of initial runs = $\lceil N/B\rceil$
• Merge Passes (1, 2, ...): We perform a (B-1)-way merge in each subsequent pass.
  • Number of merge passes = \lceil \log_{B-1} (\text{# of initial runs}) \rceil
• Total Passes: \text{# of passes} = 1 + \lceil \log_{B-1} \lceil N/B \rceil \rceil
• Total I/O Cost: $$\text{Total I/O Cost}=2N\times \left(1+\lceil {\log }_{B-1}\lceil N/B\rceil \rceil \right)$$

Let's re-examine the example from the slides to solidify this:

• N = 108 pages
• B = 5 buffer pages

1. Pass 0: Create $\lceil 108/5\rceil =22$ runs, each 5 pages long (except the last).
2. Pass 1 (Merge): We do a (5-1) = 4-way merge. We merge the 22 runs, producing $\lceil 22/4\rceil =6$ longer runs.
3. Pass 2 (Merge): We merge the 6 runs, producing $\lceil 6/4\rceil =2$ even longer runs.
4. Pass 3 (Merge): We merge the final 2 runs, producing $\lceil 2/4\rceil =1$ sorted file.

Total passes = 1 (for run creation) + 3 (for merging) = 4 passes.
Total I/O Cost = $2\times 108\times 4=864$ I/Os.

2. Application: Projection with Duplicate Elimination

Sorting is not just for ORDER BY. It's a general-purpose tool that can be used to implement other relational operators. A classic example is projection with duplicate elimination, which is what the database does for a SELECT DISTINCT query.

The basic idea is simple: if you sort a list of values, all the duplicates will end up next to each other. Then, a single scan through the sorted list is enough to identify and discard them.

How can we implement this efficiently for a large table?

1. Scan and Project: In Pass 0 of the external sort, instead of just sorting, we first read the pages of the original table, extract only the columns needed for the DISTINCT clause, and then sort these projected tuples to create the initial runs. This is a crucial first step, as the projected data is often much smaller than the original tuples, reducing the amount of data we have to sort and write to disk.

2. Merge and Eliminate: In the subsequent merge passes, we can modify the merge logic. As we're picking the next smallest element to write to the output, we compare it to the very last element we wrote. If it's a duplicate, we simply discard it and move on. This "fuses" the duplicate elimination step directly into the merge logic.

This technique can significantly reduce I/O. By eliminating duplicates early, the intermediate runs written to disk in each merge pass become smaller and smaller, saving write and subsequent read costs.

To see this idea of fusing operations into the merge process in action, the following video provides an excellent and detailed visualization. It discusses it in the context of GROUP BY and aggregation, but duplicate elimination is just a special case of this (grouping by all projected columns and picking one from each group).

Conclusion

In this lesson, we moved from implementing external merge sort to analyzing its performance and extending its use. This shift from "how it works" to "how much it costs" is central to database systems engineering.

Key Takeaways:

• The I/O cost of external merge sort is driven by the number of passes.
• We can minimize passes by using available memory (B) to create long initial runs (size B) and perform wide merges (fan-in of B-1). In many practical scenarios, this results in a simple two-pass sort.
• The total I/O cost is approximately $2N\times (\text{passes})$.
• External merge sort is a powerful primitive for more than just ordering. By sorting data, we can efficiently implement SELECT DISTINCT because duplicates become adjacent.
• A key optimization is to fuse the duplicate elimination logic directly into the merge passes, which reduces the size of intermediate data and saves I/O.

Preview of the Next Lesson

We've now covered scanning, filtering, and sorting—all operations on single tables. Next, we'll tackle one of the most important and complex operations in a relational database: the join. We will start by implementing and analyzing the cost of the simplest join algorithm: the block nested loop join.