ECE356 Lecture Notes - Lecture 17: External Sorting, Socalled, Pseudocode

• School: University of Waterloo
• Department: Electrical and Computer Engineering
• Course: ECE356
• Professor: Zarnett

Document Summary

Having examined in some detail the idea of di erent strategies for carrying out a select operation. The next thing we would like to do is expand to more advanced queries, speci cally, join queries. Join queries will be cripplingly ine cient if they operate on unsorted data. Remember that in a join, we need to match a tuple of the left hand relation with a tuple of the right hand relation. If for every tuple we had to linearly search the right hand relation, that would be painful. One way or another, we probably have to sort one of the relations to make this work. So let us take a few minutes to talk about sorting. Wait, i hear you say, you already know all about sorting, insertion sort and selection sort and bogo sort and radix sort. When you learn about sorting in a data structures and algorithms context, you are sorting a manageable amount of data.