In this video I describe in detail how my implementation of the KWay External Merge Sort algorithm works. KWay 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 inmemory 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...

✉ CONTACT INFO

Business Email: [email protected]
Contact Email: [email protected]
Twitter:   / antoniosarosi  
Instagram:   / antoniosarosi  
LinkedIn:   / antoniosarosi  

MUSIC

   • [Chillstep] Broken Elegance  Shelter  
   • Ptr.  Genesis  
   • Digital Road  
   • Juno  

CHAPTERS

00:00 Introduction
00:22 The Memory Problem
01:32 Database Tables & Sorting
03:18 KWay 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