[CMPT 454] Week 4_3 - External Sorting

June·2021년 2월 11일

CMPT 454

목록 보기

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

0개의 댓글