Chapter 12: Overview of query evaluation (self-reading: 12.1 - 12.3)

Chapter 13: External sorting

External Sorting

• The Problem: sort 100Gb of data with 100Mb of RAM
• The file is stored on disk and too large for any in-memory sorting methods.
• Cost model: I/O pages.

Why External Sort?

• A classic problem in computer science!
• Data requested in sorted order
  • e.g., find students in increasing gpa order
• First step in bulk loading B+ tree index (i.e., sort data entries and records)
• Useful for eliminating duplicate copies in a collection of records (Why?)
• Sort-merge join algorithm involves sorting.

Merge Sort

• Idea: Divide and conquer: sort subfiles (Pass 0) and merge them in multiple passes (Pass 1, 2, 3, ...).

2-Way Sort: Requires 3 Buffer pages

• Pass 0: Read a page, sort it, write it to disk

  Read하고 Write에 1 I/O가 드나, sort에는 들지 않는다.

• Pass 1,2,3,...,: Two-way merge using three buffer pages.

• Input/output buffers: memory space for holding pages read/written to disk.

Pass 0: Read a page, sort it, write it

Pass 1, 2, ...

• Each pass merges two runs at a time and writes the merged run to disk
• Next pass is needed if there are more than 1 run

위의 (1,3,7) 그리고 (1,2,4)를 기준으로 설명하면 7과 4를 비교해서 7이 크니 ouput buffer에 7을 담는다. 그리고 4와 3을 비교해서 3을.. 그렇게 (3,4,7)이 만들어지면 디스크에 write하고 나머지를 비교한다. 3 buffer pages이니 이렇게 해야한다.

I/O 계산하는 법: 모든 page가 들어오고 나가야한다. 각 Pass마다 각 페이지가 들어가고 나가야한다. 여기에는 4개의 페이지가 한 Pass가 들어오고 나가니 8 I/O이다. Pass가 2개이니 16이다.

2 - Way External Merge Sort

General External Merge Sort

Pass 0

Pass 1, 2, ...

• Merge B-1 runs at a time
  

General External Merge Sort