INTRO TO DATABASE SYSTEMS (CMU 15-445) · PART 11
#11 - Sorting & Aggregation Algorithms
DATABASESCMU 15-445
Assumption:
These lectures and the following sorting & aggregation algorithms will optimize for sequential IO rather than O(n) notation. Why? Because we work under the assumption that entire working set (eg. all of DB data), and further more even intermediate data won't fit in all of memory, and we'll need to perform a lot of I/O.
Sorting
We cover sorting first, because other than naive "ORDER BY" SQL, it also makes other operations such as "GROUP BY" or "DISTINCT" trivial once data has been sorted (quick reminder: We keep data sorted by indices, but we might want to sort by a different field for which we don't have a primary or secondary index).