The ORDER BY Algorithm Is Harder Than You Think

In this video I describe in detail how my implementation of the K-Way External Merge Sort algorithm works. K-Way External Merge Sort is an algorithm used to sort large datasets that don't fit in main memory (usually RAM). Therefore, this algorithm is used by databases like Postgres to process ORDER BY queries when tables don't fit in memory. The algorithm consists of a series of "passes" through one or multiple files and a number of in-memory buffers used to load and process different chunks of a file in each pass. The end result is a file that contains all the requested rows sorted by the keys given in the ORDER BY clause.

🌐 LINKS

Algorithm Implementation:

https://github.com/antoniosarosi/mkdb/blob/bf1341bc4da70971fc6c340f3a5e9c6bbc55da37/src/vm/plan.rs#L2164

✉️ CONTACT INFO

Business Email: [email protected]

Contact Email: [email protected]

Twitter: https://twitter.com/antoniosarosi

Instagram: https://www.instagram.com/antoniosarosi/

LinkedIn: https://www.linkedin.com/in/antoniosarosi/

🎵 MUSIC

https://www.youtube.com/watch?v=n9dvYxNlGJI

https://www.youtube.com/watch?v=2P9lhkAWrIw

https://www.youtube.com/watch?v=tZYdY_rSHv0

https://www.youtube.com/watch?v=bFtNgW1Evr4

📖 CHAPTERS

00:00 Introduction

00:22 The Memory Problem

01:32 Database Tables & Sorting

03:18 K-Way Data Structures

04:38 Algorithm Execution (Pass 0)

06:17 Pass 1

09:22 Pass 2

11:07 I/O Complexity

11:58 Variable Length Data

13:16 Final Thoughts

🏷️ HASHTAGS

#programming

#computerscience

#algorithm