DB에서 사용하는 정렬 알고리즘

DB에서 사용하는 정렬 알고리즘

 

데이터베이스 시스템은 일반적인 프로그래밍 언어에서 사용하는 정렬 알고리즘 외에도, 대규모 데이터셋과 디스크 I/O를 고려한 최적화된 정렬 방식을 사용합니다.

 

알고리즘/기법 설명 사용 시점

퀵 정렬 (Quick Sort)	메모리 내에서 빠른 정렬을 위해 사용하는 알고리즘. 평균적으로 빠르지만 최악의 경우 O(n²) 발생 가능.	소규모 데이터셋 또는 메모리에 적재 가능한 경우.
병합 정렬 (Merge Sort)	데이터를 나누어 정렬한 후 병합하는 방식. 대규모 데이터셋이나 외부 정렬(디스크 기반)에 적합.	대용량 데이터셋, 메모리 초과 시 디스크 기반 정렬 (External Sort).
힙 정렬 (Heap Sort)	우선순위 큐(힙)을 사용해 특정 조건(TOP-N 쿼리 등)을 빠르게 정렬.	LIMIT이 포함된 쿼리, TOP-N 결과 추출 시.
External Merge Sort	데이터가 메모리 크기를 초과하는 경우, 디스크를 활용하여 블록 단위로 데이터를 정렬한 후 병합.	메모리보다 큰 데이터셋 정렬 시, 디스크 기반 정렬 수행.
B-Tree 인덱스 기반 정렬	인덱스가 존재하는 경우, 인덱스를 활용해 추가 정렬 없이 빠르게 정렬된 결과 반환.	ORDER BY에 인덱스 컬럼 사용 시.
Loose Index Scan	인덱스를 느슨하게 스캔하여 원하는 값만 추출하는 방식. 불필요한 정렬을 피하고 효율적인 결과를 제공.	DISTINCT, GROUP BY, ORDER BY 최적화 시 사용.
Filesort (파일 정렬)	인덱스가 없는 경우, 데이터를 임시 파일로 내보내 정렬 후 다시 불러오는 방식. 메모리 기반과 디스크 기반으로 나뉨.	인덱스 없는 ORDER BY 시, 쿼리 실행 계획에 Using filesort 표시.
Sort-Merge Join 정렬	조인(Join) 수행 시 두 테이블을 각각 정렬한 후 병합하여 결과를 반환하는 방식.	대규모 테이블 간 조인 시, 인덱스가 없을 때 사용.
Hash 정렬	해시 테이블을 사용해 그룹화 및 정렬을 수행. 주로 GROUP BY나 DISTINCT 최적화에 활용.	GROUP BY 또는 DISTINCT 시, Using temporary로 표시 가능.