슬라이드 49 중복 제거 (Duplicate Elimination) / 추출 (Projection) 중복 제거란? 같은 데이터가 여러 번 나오는 것을 없애는 연산이다. 정렬(Sort) 방식: 정렬하면 같은 값이 나란히 붙으므로, 첫 번째 값만 남기고 나머지를 삭제한다. 최적화 (Optimization) — 어디서 중복을 제거할 수 있나? 외부 정렬(External Merge Sort)의 run 생성 단계에서 미리 제거할 수 있다. 병합(merge) 단계에서도 중간에 중복을 제거할 수 있다. 해싱(Hashing) 방식으로 중복 제거 해시 함수로 릴레이션을 여러 파티션(partition)으로 나눈다. 각 파티션에서 인메모리 해시 인덱스(in-memory hash index)를 만든다. 인덱스에 없는 튜플(tuple)은 추가하고, 이미 있는 튜플(= 중복)은 버린다. 파티션 처리가 끝나면 인덱스에 남은 튜플들이 결과다. 하지만 SQL은 중복 제거 비용이 크므로, 사용자가 DISTINCT를 명시하지 않으면 자동으로 실행하지 않는다. 추출 (Projection)이란? 원하는 속성(컬럼)만 뽑아낸 뒤, 남은 튜플 중 중복을 제거하는 연산이다. 각 튜플에 추출 연산을 수행 → 중복 레코드 제거 순으로 구현한다. 추출에 사용한 속성이 릴레이션의 키(key)를 포함하면 중복이 생길 수 없으므로, 중복 제거 단계를 건너뛸 수 있다.
Run 생성이란 무엇인가? 문제 상황 먼저 왜 "Run"이 필요한가? 데이터가 1억 개면 메모리에 한 번에 다 올릴 수 없다. 메모리는 한정되어 있기 때문이다. 📦 디스크 (Disk) 데이터가 전부 저장되어 있다. 용량은 크지만 느리다. ⚡ 메모리 (Memory) 빠르지만 작다. 데이터 일부만 올릴 수 있다. 하지만 정렬하려면 값들을 서로 비교해야 한다. 메모리에 조금씩만 올릴 수 있다면 어떻게 전체를 정렬하나? 해법: 전체를 한 번에 정렬하지 말고, 메모리에 들어갈 만큼씩 잘라서 각각 정렬한 뒤 나중에 합친다. 이 "잘라서 정렬한 조각" 하나하나를 Run이라고 부른다. 예시 구체적인 예시로 이해하기 아래 12개 점수를 정렬하려 한다. 메모리는 한 번에 4개만 올릴 수 있다고 가정하자. 전체 데이터 (디스크에 저장됨)70 30 90 50 20 80 40 60 10 50 30 70 Run 1 생성 — 첫 4개를 메모리에 올려 정렬 1 디스크에서 4개를 읽어 메모리에 올린다. ⚡ 메모리 (4개 들어옴) 70 30 90 50 2 메모리 안에서 정렬한다. ⚡ 메모리 (정렬 완료) 30 50 70 90 3 정렬된 결과를 디스크에 저장한다. 이것이 Run 1이다. 💾 디스크 — Run 1 저장 완료 Run 1: 30 → 50 → 70 → 90 Run 2 생성 — 다음 4개를 메모리에 올려 정렬 ⚡ 메모리 (다음 4개 들어옴) 20 80 40 60 ↓ 메모리 안에서 정렬 후 디스크에 저장 💾 디스크 — Run 2 저장 완료 Run 2: 20 → 40 → 60 → 80 Run 3 생성 — 나머지 4개 ⚡ 메모리 (마지막 4개) 10 50 30 70 ↓ 메모리 안에서 정렬 후 디스크에 저장 💾 디스크 — Run 3 저장 완료 Run 3: 10 → 30 → 50 → 70 Run 생성 완료 후 3개의 Run이 만들어졌다 💾 디스크에 저장된 Run들 Run 1: 30 → 50 → 70 → 90 Run 2: 20 → 40 → 60 → 80 Run 3: 10 → 30 → 50 → 70 각 Run은 내부적으로 이미 정렬되어 있다. 이제 이 Run들을 병합(Merge)하면 전체가 정렬된다. Run 생성 = "메모리에 들어갈 만큼 잘라서 정렬한 뒤 디스크에 저장하는 것"이다. 메모리가 4개짜리라도 데이터가 100만 개인 전체를 정렬할 수 있게 해주는 핵심 아이디어다. Run을 생성할 때 중복도 미리 제거하면, 이후 병합 단계의 데이터 양이 줄어들어 더 빠르게 처리할 수 있다.
중복 제거 — 예시로 완전 이해하기 상황 설정 예시 데이터 학생 성적 테이블에서 점수(score) 컬럼만 뽑는다고 가정하자. 아래처럼 중복이 많다. 전체 튜플 (총 8개) 30 70 50 70 30 90 50 70 목표: 30, 50, 70, 90 — 딱 4개의 고유한 값만 남기기 방법 1 외부 정렬(External Merge Sort)로 중복 제거 데이터가 너무 커서 메모리에 다 못 올릴 때 쓰는 정렬 방법이다. 2단계로 진행된다. 1단계 — Run 생성 (정렬된 덩어리 만들기) 메모리에 들어갈 만큼씩 데이터를 잘라서 정렬한다. 이때 바로 중복을 제거한다. Run 1 — 첫 4개 [30, 70, 50, 70] 정렬 후 중복 제거 정렬 전 30 70 50 70 ↓ 정렬 → 나란히 붙은 중복 삭제 정렬 후 (중복 제거됨) 30 50 70 70 → 저장: 30, 50, 70 Run 2 — 나머지 4개 [30, 90, 50, 70] 정렬 후 중복 제거 정렬 전 30 90 50 70 ↓ 정렬 → 중복 없음 정렬 후 30 50 70 90 → 저장: 30, 50, 70, 90 2단계 — Merge 병합 (두 Run을 합치며 중복 제거) 두 Run을 동시에 읽으면서 작은 값부터 하나씩 출력한다. 같은 값이 나오면 하나만 남긴다. Run 1 30 50 70 Run 2 30 50 70 90 ↓ 병합: 30=30이면 하나만, 50=50이면 하나만, 70=70이면 하나만 최종 결과 30 50 70 90 핵심: 정렬하면 같은 값이 무조건 붙어있으므로, 앞 값과 현재 값을 비교하는 것만으로 중복을 O(1)에 제거할 수 있다.
집합 연산 — 해싱으로 구현하기 (예시 완전 설명) 예시 데이터 설정 두 릴레이션 r과 s 동아리 가입 학생 번호가 담긴 두 테이블이 있다고 하자. 릴레이션 r (축구 동아리) 10 20 30 40 릴레이션 s (농구 동아리) 20 30 50 60 r에만 있음 (10, 40) 둘 다 있음 (20, 30) s에만 있음 (50, 60) 공통 1단계 해시 함수로 파티션 나누기 해시 함수 h(x) = x mod 3 을 r과 s 모두에 똑같이 적용한다. 같은 값은 반드시 같은 파티션에 들어간다. 그래서 파티션끼리만 비교하면 된다. r 파티션 파티션 0 30 파티션 1 10 40 파티션 2 20 s 파티션 파티션 0 30 60 파티션 1 20 50 파티션 2 없음 계산: 10 mod 3=1, 20 mod 3=2, 30 mod 3=0, 40 mod 3=1, 50 mod 3=2, 60 mod 3=0연산 1 r ∪ s — 합집합 (둘 중 하나라도 있으면 결과에 포함) 축구 또는 농구 동아리에 가입한 학생 전체를 구한다. 중복 없이. 파티션 0 처리 (r₀ = {30}, s₀ = {30, 60}) 1 r₀ = {30} 으로 인덱스 구축 → 인덱스: { 30 } 2 s₀의 30 → 인덱스에 이미 있음 → 추가 안 함. s₀의 60 → 없음 → 추가. 인덱스: { 30, 60 } 3 인덱스 전체를 결과에 추가 → 30, 60 파티션 1 처리 (r₁ = {10, 40}, s₁ = {20, 50}) 1 인덱스: { 10, 40 } 2 20 없음 → 추가, 50 없음 → 추가. 인덱스: { 10, 40, 20, 50 } 3 결과에 추가 → 10, 40, 20, 50 파티션 2 처리 (r₂ = {20}, s₂ = {}) 1 인덱스: { 20 } 2 s₂가 비어있어 추가할 것 없음. 3 결과에 추가 → 20 최종 결과 r ∪ s 10 20 30 40 50 60 r과 s의 모든 값이 중복 없이 포함됐다.연산 2 r ∩ s — 교집합 (양쪽 모두 있는 것만 결과에 포함) 축구와 농구 동아리 모두에 가입한 학생만 구한다. 파티션 0 처리 (r₀ = {30}, s₀ = {30, 60}) 1 r₀로 인덱스 구축 → 인덱스: { 30 } 2 s₀의 30 → 인덱스에 있음 → 결과에 추가 ✓ s₀의 60 → 인덱스에 없음 → 무시 파티션 0 결과 30 파티션 1 처리 (r₁ = {10, 40}, s₁ = {20, 50}) 1 인덱스: { 10, 40 } 2 s₁의 20 → 없음 → 무시. 50 → 없음 → 무시. 파티션 1 결과 없음 파티션 2 처리 (r₂ = {20}, s₂ = {}) 1 인덱스: { 20 } 2 s₂가 비어있음 → 아무것도 결과에 추가 안 됨. 최종 결과 r ∩ s 20 30 r과 s 양쪽에 모두 있는 20, 30만 결과에 포함됐다.연산 3 r − s — 차집합 (r에는 있지만 s에는 없는 것만) 축구 동아리에는 가입했지만 농구 동아리에는 없는 학생만 구한다. 파티션 0 처리 (r₀ = {30}, s₀ = {30, 60}) 1 r₀로 인덱스 구축 → 인덱스: { 30 } 2 s₀의 30 → 인덱스에 있음 → 인덱스에서 제거 ✗. 인덱스: { } s₀의 60 → 인덱스에 없음 → 무시 3 인덱스에 남은 것 없음 → 결과에 추가 없음 파티션 0 결과 없음 파티션 1 처리 (r₁ = {10, 40}, s₁ = {20, 50}) 1 인덱스: { 10, 40 } 2 s₁의 20 → 인덱스에 없음 → 무시. 50 → 없음 → 무시. 인덱스 그대로: { 10, 40 } 3 남은 것 결과에 추가 → 10, 40 파티션 1 결과 10 40 파티션 2 처리 (r₂ = {20}, s₂ = {}) 1 인덱스: { 20 } 2 s₂가 비어있어 제거할 것 없음. 인덱스: { 20 } 3 남은 것 결과에 추가 → 20 최종 결과 r − s 10 20 40 r에만 있고 s에는 없는 10, 20, 40만 결과에 포함됐다.세 연산의 핵심 차이 한눈에 보기 r ∪ s 합집합 s 값이 인덱스에 없으면 추가. 마지막에 인덱스 전체 출력. r ∩ s 교집합 s 값이 인덱스에 있으면 바로 결과에 출력. 인덱스 자체는 변경 없음. r − s 차집합 s 값이 인덱스에 있으면 제거. 마지막에 남은 것만 출력. 세 연산 모두 "r로 인덱스 구축 → s로 검사"하는 구조는 동일하다. s를 만났을 때 무엇을 하느냐만 다르다.

방법1 > 합병 조인 비참여 튜플 수식

 

 

 

바닷속벨루가
바닷속벨루가
바다처럼 넓은 컴퓨터 공부를 재밌고 이해하기 쉽게 알려드립니다. 사랑하고 좋아하는 것에는 빠질 수 밖에 없어

티스토리툴바