쭌스🎄

I earned my BS degree in Computer Science and Data Science at the University of Wisconsin-Madison. I am currently pursuing my MS degree in AI at KAIST AI.

I am broadly interested in Computer Vision, Machine Learning, Open Vocabulary, and Object Detection/Segmentation. The main objective of my study is to build a reliable, efficient, and expansive AI/ML system for sustainable development.

8 분 소요

INTRO 🙌

저번 시간에는 Relational Algebra 에 대하여 알아보았다.

이번 시간에는 Sorting & Relational Operations에 대해 알아보자.

정렬이란? 📂

  • CS 고전적인 문제
  • 정렬 데이터 필요 多
  • bulk loading B+ tree index에서 정렬은 가장 첫 과제!
  • 정렬은 record에 존재하는 duplicate copies 제거에 효과적이다
  • Sort-merge join 알고리즘은 정렬을 수반한다

하지만, 만약 1Gb 크기의 데이터를 1Mb 사양의 RAM으로 정렬을 수행할 수 없다.

잠정적 해결책 = 가상 메모리(virtual memory)

2-Way Sort: Requires 3 Buffers

image

첫 번째 단계:

  • Read a page, sort it, write it.
  • buffer page 1개; 그림에서 각각 INPUT 1 and 2

두 번째 단계:

  • Pass 2, 3, …, etc.:
  • buffer page 3개; 그림에서 INPUT 1, 2, and OUPUT

Two-Way External Merge Sort

image

  • 각 pass마다, 각 페이지 r/w 수행
  • 여전히 buffer page 3개
  • 파일 페이지 개수(N)라면,
    • \(the\ number\ of\ passes = \lceil log_{2}N\rceil+1\).
    • \(total\ cost = 2N(\lceil log_{2}N\rceil+1)\).
  • Idea: Divide and conquer: sort subfiles and merge

상기 예문은 8개의 pages가 존재하기 때문에, total cost는 8, pass 개수는 4개인 모습이다.

General External Merge Sort

image

Buffer page 개수가 3개 보다 많이 필요한 경우 사용할 수 있는 방법이다.

N개의 페이지를 가진 파일을 B개의 buffer pages 단위로 잘라서 정렬:

  • Pass 0: B buffer pages: 정렬조각개수=\(\lceil N/B\rceil\) .
  • Pass 2, …, etc.: merge \((B-1)\) runs.

첫 번째 단계에서는 N크기의 한 파일을 B 단위로 잘라서 정렬 조각을 형성한다.

이후, 초기 \((B-1)\)개 정렬 조각을 buffer pages에 할당하고, 결과를 나머지 1개의 페이지에 담는다.

이런 방식으로, \((B-1)\)개의 buffer pages 단위로 정렬을 반복하며 N과 동일한 크기의 하나의 정렬 조각을 형성한다.

Cost of External Merge Sort

image

  • pass 개수: \(1+\lceil log_{B-1}(N/B)\rceil\).
  • 총 cost: \(2N*(\#\ of\ passes)\).
    • 곱하기 2하는 이유: 각 pass마다 r/w 적용
    • 곱하기 N하는 이유: 각 pass마다 모든 페이지 탐색
  • \(B(B-1)^k=N\).

예제

5 buffer pages를 가지고 108개의 페이지 파일을 정렬해보자.

  • Pass 0: 각각 5페이지 크기의 22개의 정렬조각 형성; \(\lceil 108/ 5 \rceil = 22\) (마지막 3페이지 크기)
  • Pass 1: 각각 20페이지 크기의 6개의 정렬조각 형성; \(\lceil 22 / 4 \rceil = 6\) (마지막 8페이지 크기)
  • Pass 2: 80페이지 크기 1개와 나머지 28페이지 1개, 총 2개 정렬 조각; \(\lceil 6 / 4 \rceil = 2\).
  • Pass 3: 최종 108 페이지 크기 정렬 조각

공식을 적용해보아도 동일하게, Pass 개수는 4, 총 비용은 2x108x4이다.

일반화

만약 파일 페이지 개수가 \(M\)이고, \(M <= B^2\) 라면, 총 정렬 비용은 \(4M\) 이다.

  • Pass 0: B 페이지 크기 정렬 조각 형성 (Cost of Pass 0: 2M)
  • Pass 1: B(B-1) 페이지 크기 정렬 조각 형성 (Cost of Pass 1: 2M)
    • 만약 \(M <= B^2\) 라면, 이 단계에서 종료; \(M = B(B-1) <= B^2\).

따라서, 해당 경우 총 비용이 4M이 된다.

Double Buffering

  • Reduce the response time for a given sorting query
  • No significant impact on throughput
    • CPU can be kept busy by working on other queries while waiting for one query’s I/O operation to complete.

External Sorting 문제점:

  • 입력 블록의 모든 튜플 소비 \(\rightarrow\) 튜플의 다음 블록 I/O 요청 \(\rightarrow\) I/O가 실행될 때까지 실행 일시 중단 (CPU = idle)

Double Buffering

  • I/O 요청이 수행되는 동안 CPU를 사용 중인 상태로 유지
    • CPU & I/O 처리 중첩
      • 각 입력 버퍼에 추가 페이지 할당

가령, 블록 크기 b = 32에 대해, 모든 입력(및 출력) 버퍼에 추가 32페이지 블록을 할당한다. 32페이지 블록의 모든 튜플이 소비되면, CPU는 이 실행에 대해 두 번째 ‘double’ 블록으로 전환하여 실행의 다음 32페이지를 처리할 수 있다. 동시에, 빈 블록을 채우기 위해 I/O 요청이 발행된다. 따라서, 블록을 소비하는 시간(기존 블록 튜플 소비)이 블록을 읽는 시간(빈 블록 채우기)보다 크다고 가정하면 CPU는 절대 유휴 상태가 아니게 된다.

실습

image

Relational Operations 💗

  • Selection ( \(\sigma\) ) Selects a subset of rows from relation.
  • Projection ( \(\pi\) ) Deletes unwanted columns from relation.
  • Join ( \(\infty\) ) Allows us to combine two relations.
  • Set-difference ( \(-\) ) Tuples in reln. 1, but not in reln. 2.
  • Union ( \(\cup\) ) Tuples in reln. 1 and in reln. 2.
  • Aggregation (SUM, MIN, etc.) and GROUP BY

Schema for Examples

    Sailors (sid: integer, sname: string, rating: integer, age: real)
    Reserves (sid: integer, bid: integer, day: dates, rname: string)
  • Reserves: Each tuple is 40 bytes long, 100 tuples per page, 1000 pages.
  • Sailors: Each tuple is 50 bytes long, 80 tuples per page, 500 pages.

Equality Joins With One Join Column

    SELECT  *
    FROM     Reserves R1, Sailors S1
    WHERE  R1.sid=S1.sid

\(R\infty S\): 대수학에서 종종 사용되지만, 최적화에 주의해야 한다.

  • \(R X S\)은 크기가 매우 크기 때문에, 이후에 Selection 사용하는 것은 지양해야 한다.

이제부터 살펴볼 예문들에서 다음 조건들을 충족한다고 가정해보자.

  • M pages for R, \(p_{R}\) tuples per page
  • N pages for S, \(p_{S}\) tuples per page
  • R = Reserves S = Sailors.
  • Cost metric: \(\#\ of\ I/Os\) .
    • output costs는 무시한다

Join Algorithms to Consider

  • Nested loop join
  • Sort-merge join
  • Hash join
  • Index nested loop join

상기 JOIN 각각 모두 이해 ★★★★★★

cost 구하는 문제 출제 ★★★★★★

비교

image

image

1) Nested loop join

Simple Nested Loops Join

    foreach tuple r in R do
        foreach tuple s in S do
            if ri == sj  then add <r, s> to result

image

Tuple-oriented NLJ

  • outer relation R에 존재하는 각 tuple에 대하여, inner relation S를 스캔한다.
  • \(Cost\ =\ M+p_{R}*M*N = 1000 + 100*1000*500\) I/Os

Page-oriented NLJ

  • R의 각 페이지에 대하여, S의 각 페이지를 가져와 \(<r,s>\) 작성.
  • \(Cost\ =\ M + M*N = 1000 + 1000*500\).

# output pages to disk를 Cost 계산에서 제외하는 이유?

원래 \(Cost\ =\ M + M*N + (output\ pages)\). 여기서, Cost는 서로 다른 implementations에 대한 JOIN 성능 비교를 위해 계산하는데, “# output pages”는 R, S에 대하여 고정값이기 때문에 Cost 비교에 영향을 끼치지 않아서 과감히 무시한다.

Block Nested Loops Join (Best)

\(M+N*\lceil (M/(B-2)) \rceil\)

image

  • 1) add \(<r, s>\) to result
  • 2) read next R-block, scan S, etc.

inner 관계 S를 스캔하기 위해, 한 페이지를 input buffer, 다른 한 페이지를 output buffer, 나머지 페이지들을 outer R의 “block” 저장소로 사용한다.

  • R이 한 번 스캔될 때, \(cost = M\) pages
  • 각 block 사이즈 = \((B-2)\) (\(B\) = # of buffer pages)
    • S 읽는 횟수 = \(\lceil (M/(B-2)) \rceil\).
  • 총 비용: \(M+N*\lceil (M/(B-2)) \rceil\).
Examples of Block Nested Loops

비용: Scan of outer + #outer blocks * scan of inner

  • \(\#\ outer\ blocks = \lceil (\#\ of\ pages\ of\ outer\ /\ blocksize) \rceil\).

Reserves (R) = outer | 한 번에 100 pages of R 조회 가능:

  • R 스캔 비용 = 1000 I/Os; a total of 10 blocks (1000 / 100).
  • Per block of R, S 스캔 횟수 = 10*500 I/Os.

만약 한 번에 R 스캔 90 pages 가능 \(\rightarrow\) S 스캔 횟수 = 12.

90 * 12 = 1080; R 페이지 개수 = 1000개

S = outer with 100-page block:

  • S 스캔 비용 = 500 I/Os; a total of 5 blocks.
  • Per block of S, R 스캔 횟수 = 5*1000 I/Os.

최적화 (Minimization)★★★

  • 1) 크기가 작은 relation, S를 outer로 지정하면 비용이 감소; \(Cost\ =\ 500 + 500*1000\)
  • 2) tuple 대신 block 단위(= page 단위)로 JOIN 구현해야 비용이 감소
  • 3) buffer를 최대 활용한다; 빈공간 없도록!
    • outer pages로 메모리 빈공간 채움 \(\rightarrow\) Cost 감소!!

2) Sort-merge join \(R \infty S\).

\(Cost: 5(M+N) = 4(M+N)+(M+N)\)

image

R, S에 대하여 JOIN 이후, join col 기준으로 merge 수행

image

  • 1) R 스캔 until R-tuple \(>=\) 현재 S-tuple
  • 2) S 스캔 until S-tuple \(>=\) 현재 R-tuple
  • 3) 종료 until 현재 R-tuple \(=\) 현재 S-tuple
    • 이 시점에서, Ri-tuple = Sj-tuple (매칭)
  • 4) output \(<r,s>\).
  • 5) R, S 스캔 재개

R 스캔 한 번 = 각 S group 스캔 한 번 (per matching R tuple)

  • 여러 번의 S group 스캔 \(\rightarrow\) buffer에서 대상 페이지 탐색 가능성 ↑

image

상기 테이블은 크기가 더 큰 테이블이 outer이므로, cost가 비효율적이니, 순서를 바꾸자.

image

\[Cost: 5(M+N) = 4(M+N)+(M+N)\]

상기 공식은 항상 옳지 않다. 왜냐하면, 스캔 비용(\(M+N\))은 드물게 \(M*N(worse\ case)\)이 될 수 있기 때문이다.

Worst-case: 상기 사진 아래 부분, 모든 tuple들이 identical 한 경우

일반 경우에서, 100 buffer pages를 사용하여 R, S는 2 passes 안에 정렬될 수 있다.

\(total\ join\ cost = 4(500+1000)+1000+500=7500\).

참고, \(최대 Cost\ =\ 4(M + N)\ (most\ cases);\ where\ M,\ N<=B^2\)

하지만, relations R, S가 정렬된 상태라면 해당 경우는 고려하지 않아도 무방하다.

메모리에 모두 한 번에 넣을 수 있다면 (= memory ↑, table ↓), \(Cost=M+N\).

3) Hash join

hash-join 동작원리 시각화 기말고사 출제 ★★★★★★★★★

\[Cost = 3(M+N) = 2(M+N)+(M+N)\]
  • partition: \(2(M+N)\); read+write
  • read both relations(h2 함수): \((M+N)\)

직관

image

남자 카테고리에서 먼저 성을 기준으로 JOIN하여 partition을 형성하고, 이후 partitions들을 여자 카테고리와 JOIN을 수행.

image

  • hash 함수 h를 사용하여 R, S partition 각각 형성
  • partition i의 R tuples은 오로지 S tuples in partition i과 매칭
  • hash 함수 h2를 사용하여 partition of R과 partition of S를 매칭

동작원리

image

  • 4크기의 메모리: 1개를 INPUT, 나머지 3개를 buffer pages
  • 직관 파트에서 본 남자는 R, 여자는 S과 매칭
  • 해쉬 함수 h: R, S JOIN 수행
  • 해쉬 함수 h2: R, S의 각 대응하는 partition JOIN 수행

1) R, S 해쉬 함수(h) JOIN \(\#\ partition ={M \over B-1},\ where\ -1\ for\ input\ buffer\ page\) 2) 매칭되는 partition끼리 해쉬 함수(h2) JOIN \({M \over B-1} < B-2,\ where\ -2\ for\ input/output\ buffer\ pages\) \(M<(B-1)(B-2) \approx B^2\) 3) JOIN 결과 output

4) Index Nested Loop Join

    foreach tuple r in R do
        foreach tuple s in S where ri == sj  do
            add <r, s> to result

만약 inner table에서 한 relation에서 JOIN되는 column의 index를 안다면, 해당 relation 전체 tuples 탐색이 아니라, 해당 인덱스까지만 비용 계산하면 될 것이다.

image

가령, 상기 그림에서 현재 타겟 = 20 \(\rightarrow\) inner table에서 인덱스 20만 빠르게 조회

각 R tuple에 대하여, S index 탐색 비용:

  • hash index: 1.2
  • B+ tree: [2, 4]

Index Nest Loop Join에서 Cost 계산은 기말 안 나옴!

\(Cost: M + ( (M*pR) * cost\ of\ finding\ matching\ S\ tuples)\).

Clustered index: 1 I/O (typical)

Unclustered: up to 1 I/O per matching S tuple.

Clustered vs Unclustered

image

Clustered Index

        Cluster : 군집
        Clustered : 군집화
        Clustered Index : 군집화 된 인덱스

[id = Clustered index]

image

  • 테이블 당 하나의 Clustered index
  • 검색 속도 ↑, 데이터 삽입 비용 ↑
  • 데이터 물리적 저장 순서 정의
    • 특정 컬럼을 기준 데이터 정렬

image

Unclustered Index

        NonCluster : 비 군집
        NonClustered : 비 군집화
        NonClustered Index: 군집화되어 있지 않은 인덱스

image

  • 테이블 당 여러개 unclustered index
  • Unclustered index 테이블 저장 X, 별도의 장소에 저장
  • 테이블의 물리적인 순서에 따라 데이터 정렬
    • 순서대로 정렬 X

Summary ✔

  • Join = very common, but very expensive
  • 비슷한 tuples 매칭 필요
    • sort
    • hash
    • using an index
    • just enumerate all pairs (nested loop joins)

Reference

Database Management Systems by Raghu Ramakrishnan and Johannes Gehrke

Relational Operators

댓글남기기

참고