Query Processing

같은 SQL도 테이블 전체를 읽거나 인덱스로 필요한 레코드를 찾아 실행할 수 있습니다. DBMS는 SQL을 내부 표현으로 변환하고, 후보 실행 계획의 비용을 추정해 사용할 접근 경로와 알고리즘을 선택합니다.

쿼리 처리의 기본 단계

SQL은 원하는 결과를 기술하는 선언적 언어입니다. 관계대수는 선택·투영·조인 같은 연산을 조합해 그 결과를 표현합니다. 관계대수(relational algebra)와 선형대수(linear algebra)는 다른 개념입니다.

파싱 단계에서는 문법과 참조한 테이블·열을 검사합니다. 변환한 관계대수 표현식에 어떤 인덱스와 알고리즘을 사용할지 붙이면 구체적인 평가 계획, 즉 실행 계획이 됩니다.

SELECT salary
FROM instructor
WHERE salary < 75000;

위 질의에서는 전체 릴레이션을 스캔하며 조건을 검사하거나, salary 인덱스로 조건에 맞는 레코드를 찾을 수 있습니다. 선택 연산은 조건에 맞는 행을 고르고, 투영 연산은 필요한 열을 남깁니다. SQL의 SELECT 구문과 관계대수의 선택 연산을 혼동하지 않아야 합니다.

옵티마이저는 카탈로그의 레코드 수, 크기, 값 분포와 인덱스 정보를 사용해 비용을 추정합니다. 추정값이 가장 낮은 후보를 선택해도 실제 실행 시간이 항상 가장 짧다고 보장할 수는 없습니다. 통계의 정확성과 탐색한 계획의 범위가 판단에 영향을 줍니다.

쿼리 비용을 계산하는 기준

비용 = 블록 전송 횟수 × tT + 탐색 횟수 × tS

tT는 블록 하나를 전송하는 시간이고 tS는 한 번 탐색하는 시간입니다. 원문은 CPU와 네트워크 비용을 제외하고 디스크 접근에 집중합니다. 결과를 최종 저장소에 쓰는 비용도 별도로 세지 않습니다. 읽기와 쓰기의 블록 전송 비용을 같은 값으로 취급하는 모델입니다.

원문에 인용한 4 KB 블록 예시에서 자기 디스크는 tS = 4 ms, tT = 0.1 ms입니다. 이 가정에서는 한 번 탐색하는 비용이 한 블록을 전송하는 비용의 40배입니다. SSD 예시값은 각각 20–90 μs, 2–10 μs이며, SSD에는 자기 디스크의 기계적 헤드 이동이 없습니다. 이 수치를 현재 장비의 성능값으로 사용해서는 안 됩니다.

이미 버퍼에 있는 블록은 디스크에서 다시 읽을 필요가 없습니다. 아래 식은 대체로 캐시 적중이 없고 버퍼가 제한된 경우를 가정합니다. 여유 메모리가 늘면 같은 알고리즘에서도 I/O 횟수가 줄어듭니다.

선택 연산 — 파일 스캔과 인덱스

A1: 선형 탐색

전체 스캔: b_r × tT + tS
키 동등성 검색의 평균: (b_r / 2) × tT + tS

선형 탐색은 파일의 블록을 읽으며 각 레코드가 조건을 만족하는지 검사합니다. 키 동등성 검색에서는 일치 레코드를 발견하면 멈출 수 있으므로, 레코드가 존재하고 위치가 균등하다고 가정하면 평균적으로 절반을 읽습니다. 없는 키를 찾을 때는 끝까지 읽어야 합니다.

b_r / 2는 이진 탐색을 뜻하지 않습니다. 파일을 임의로 건너뛰는 탐색은 추가적인 랜덤 접근을 요구하며, 파일 배치와 탐색용 구조가 그 방식을 지원하는지도 확인해야 합니다.

A2·A3: 데이터 배치와 일치하는 인덱스

원문의 primary index라는 표현은 아래에서 clustering index로 구분합니다. 비용식의 조건은 검색 키 순서와 데이터의 물리적 배치가 일치한다는 것입니다. SQL의 PRIMARY KEY 선언과 모든 DBMS에서 같은 의미를 갖지는 않습니다.

A2에서는 인덱스의 루트부터 리프까지 h_i개 페이지를 읽고 데이터 블록을 한 번 더 읽습니다. 리프가 레코드 주소를 가리키는 모델이므로 +1이 붙습니다. 데이터 자체를 리프에 저장하거나 인덱스만으로 질의에 답할 수 있는 경우에는 이 가정을 그대로 적용하지 않습니다.

A3에서는 같은 검색 키에 여러 레코드가 일치합니다. 아래 그림처럼 일치 레코드가 연속된 b개 블록을 차지하면, 첫 블록 탐색 뒤에는 레코드마다 별도 탐색 없이 b × tT의 전송 비용만 추가합니다.

A4: 보조 인덱스와 흩어진 레코드

후보키 동등성 검색이면 한 레코드만 가져오므로 A2와 같은 식이 나옵니다. 비키 검색에서는 일치하는 레코드가 서로 다른 블록에 있을 수 있습니다.

두 트리 그림은 같은 노드와 탐색 경로를 사용하고 블록 배치만 달리합니다. A4에서는 인덱스의 정렬 순서가 데이터 블록의 물리 순서를 보장하지 않으므로, 최악에는 인덱스에서 찾은 일치 레코드 수 n만큼 서로 다른 블록에 랜덤 접근합니다. 결과가 많으면 랜덤 I/O가 늘어 전체 스캔보다 비싸질 수 있습니다.

A5·A6: 범위 비교

A5, A >= V:
h_i × (tT + tS) + tS + b × tT

데이터가 A 순서로 배치되어 있으면 인덱스로 첫 일치 레코드를 찾고 이후 블록을 순차적으로 읽을 수 있습니다. A3와 같은 비용 구조입니다.

A <= V라면 파일의 처음부터 읽다가 V를 넘는 첫 레코드에서 멈추는 방법이 있습니다. 경계값을 알 수 없어서 인덱스를 못 쓰는 것은 아닙니다. 이 모델에서는 파일 시작부터 필요한 구간을 읽을 수 있어 별도의 시작점 탐색을 생략합니다.

A6는 보조 인덱스의 리프를 범위 순서로 읽고, 각 항목이 가리키는 레코드를 가져옵니다. 인덱스 내부의 순차 탐색과 데이터 블록의 랜덤 접근을 나눠 봐야 합니다. 원문의 (h_i + n) × (tT + tS)는 일치 레코드마다 접근이 필요한 경우의 단순화이며, 긴 범위를 읽는 실제 비용에는 추가 리프 페이지를 읽는 비용도 포함됩니다.

A7–A10: AND·OR 조건

salary = 40000 AND dept_name = 'comp_sci'처럼 여러 조건이 붙으면 인덱스 하나로 후보를 줄이거나 여러 인덱스의 레코드 식별자를 결합할 수 있습니다.

A9는 같은 릴레이션에 있는 여러 인덱스를 사용합니다. 각 조건이 서로 다른 테이블의 인덱스를 뜻하는 것은 아닙니다. 일부 조건에 인덱스가 없으면 가져온 레코드에서 추가로 검사할 수 있습니다.

A10 방식으로 OR의 모든 후보를 인덱스에서 찾으려면 각 조건을 지원하는 인덱스가 필요합니다. 한 조건을 인덱스로 처리하지 못하면 그 조건에만 맞는 레코드도 찾아야 하므로 선형 스캔을 고려합니다.

복합 인덱스가 있다고 항상 가장 낮은 비용이 되는 것은 아닙니다. 열 순서, 조건의 형태, 선택도와 데이터 접근 비용이 판단 기준입니다. NOT 조건도 선형 탐색을 사용할 수 있지만, 일치하는 결과가 적고 인덱스를 적용할 수 있다면 인덱스 접근이 후보가 됩니다.

정렬 — 메모리에 들어가는가

릴레이션이 메모리에 들어가면 내부 정렬 알고리즘으로 처리할 수 있습니다. 전체를 올릴 수 없다면 일부를 읽어 정렬한 뒤 저장하고, 정렬된 조각을 병합해야 합니다. 이 조각을 run이라고 부릅니다.

External sort-merge

메모리가 M개 블록을 담을 수 있다고 가정합니다. 입력에서 최대 M개 블록을 읽어 정렬하고 디스크에 run으로 씁니다. 입력을 모두 처리할 때까지 반복하면 초기 run 수는 ceil(b_r / M)입니다.

병합 단계에서는 각 run의 입력 버퍼와 출력 버퍼가 필요합니다. 따라서 단순한 구성에서 동시에 병합할 run 수는 최대 M−1개입니다. run이 더 많으면 여러 번에 나누어 병합합니다. 원문의 “요소 세 개” 예시는 원리를 보여주기 위한 축약이며 실제 메모리 예산은 블록과 버퍼 단위로 셉니다.

각 입력 버퍼의 맨 앞 레코드 중 작은 값을 출력 버퍼에 추가합니다. 입력 버퍼를 소진하면 해당 run의 다음 블록을 읽고, 출력 버퍼가 차면 디스크에 씁니다. 그림은 정렬된 두 run을 병합하는 부분만 보여주며, 아래 출력 행은 누적 결과를 표시합니다.

정렬된 보조 인덱스 순서로 레코드를 가져오는 방법도 있습니다. 다만 레코드마다 다른 데이터 블록을 읽어야 한다면 비용이 커질 수 있습니다. 인덱스 순서대로 읽는 비용과 외부 정렬 비용을 비교해야 합니다.

조인 알고리즘

원문은 student 5,000개 레코드·100개 블록, takes 10,000개 레코드·400개 블록을 예시로 사용합니다. 아래에서는 바깥쪽 릴레이션을 r, 안쪽을 s로 표기합니다.

Nested loop join

for each tuple outer in r:
    for each tuple inner in s:
        if join_condition(outer, inner):
            emit(outer, inner)

r의 레코드 하나마다 s를 스캔합니다. 두 입력에서 블록 하나씩만 유지하는 제한된 버퍼 모델에서는 다음 비용을 사용합니다.

블록 전송: n_r × b_s + b_r
탐색: n_r + b_r

안쪽 입력의 전체 블록을 바깥쪽 레코드마다 다시 읽으므로 n_r × b_s가 붙습니다. 바깥쪽 입력 자체를 읽는 비용이 b_r입니다. 탐색 횟수에는 반복되는 안쪽 스캔의 시작과 바깥쪽 블록 접근을 반영합니다.

student가 바깥쪽:
5,000 × 400 + 100 = 2,000,100 transfers
5,000 + 100 = 5,100 seeks

takes가 바깥쪽:
10,000 × 100 + 400 = 1,000,400 transfers
10,000 + 400 = 10,400 seeks

takes를 바깥쪽에 두면 전송 횟수는 줄고 탐색 횟수는 늘어납니다. 앞의 자기 디스크 예시값을 적용하면 각각 약 220.41초와 141.64초입니다. 이 모델에서는 takes를 바깥쪽에 두는 편이 낮은 비용입니다. 실제 실행 시간은 캐시와 저장 장치에 따라 달라지며, 위 숫자는 계산 결과입니다.

안쪽 릴레이션 전체와 필요한 입출력 버퍼가 메모리에 들어가면 반복해서 디스크를 읽을 필요가 없습니다. 이때 입력을 읽는 비용은 b_r + b_s transfers와 2 seeks까지 줄어들 수 있습니다.

Block nested loop join

for each block outer_block in r:
    for each block inner_block in s:
        for each tuple outer in outer_block:
            for each tuple inner in inner_block:
                if join_condition(outer, inner):
                    emit(outer, inner)

바깥쪽의 반복 단위를 레코드에서 블록으로 바꿉니다. 한 번 읽은 안쪽 블록을 바깥쪽 블록의 모든 레코드와 비교하므로 디스크 재접근 횟수가 줄어듭니다.

블록 전송: b_r × b_s + b_r
탐색: 2 × b_r

student가 바깥쪽:
100 × 400 + 100 = 40,100 transfers
2 × 100 = 200 seeks

메모리 여유가 있으면 바깥쪽 블록을 여러 개 묶어 안쪽 스캔 한 번에 처리할 수 있습니다. 안쪽 조인 키가 유일한 동등 조인에서는 일치 레코드를 찾은 뒤 해당 바깥쪽 레코드의 탐색을 끝낼 수도 있습니다. 안쪽 스캔 방향을 번갈아 바꾸어 직전에 읽은 블록을 재사용하는 방법도 있습니다.

Indexed nested loop join

동등 조인이나 자연 조인에서 안쪽 조인 키에 인덱스가 있으면, s 전체를 매번 읽는 대신 인덱스로 일치 레코드를 찾을 수 있습니다.

비용 = b_r × (tT + tS) + n_r × c

c는 바깥쪽 레코드 하나와 조인할 안쪽 레코드들을 찾는 비용입니다. 인덱스 탐색뿐 아니라 일치 레코드를 가져오는 비용도 포함합니다. 바깥쪽 레코드 수가 적으면 인덱스 탐색 반복 횟수를 줄일 수 있습니다.

원문처럼 c를 5 transfers와 5 seeks로 두면, student를 바깥쪽으로 사용했을 때 각각 100 + 5,000 × 5 = 25,100회입니다. 원문의 100 × 5000 × 5는 곱셈 오기이므로 덧셈으로 수정했습니다. 이 가정에서 block nested loop join보다 전송 횟수는 적지만 탐색 횟수는 많습니다. 인덱스를 사용했다는 이유만으로 비용이 낮아지는 것은 아닙니다.

Merge join

양쪽 입력이 조인 키 순서로 정렬되어 있다면 작은 쪽의 키를 앞으로 이동시키며 같은 키를 찾을 수 있습니다. 여기서는 동등 조인과 자연 조인을 다룹니다. 같은 키가 여러 번 나타나면 양쪽의 같은 키 그룹에서 필요한 모든 튜플 쌍을 출력해야 합니다.

블록 전송: b_r + b_s
탐색: ceil(b_r / b_b) + ceil(b_s / b_b)
정렬되지 않은 입력: 정렬 비용 추가

b_b는 입력을 한 번에 읽는 버퍼의 블록 수입니다. 위 식은 각 입력 블록을 한 번씩 읽을 수 있는 경우를 가정합니다. 중복 키 그룹이 커서 재읽기가 필요하면 추가 비용을 고려해야 합니다. 원문의 식에는 블록 묶음 수를 세는 올림을 명시했습니다.

Hash join

해시 조인은 동등한 키가 같은 해시값을 가진다는 성질을 사용합니다. 두 입력을 같은 해시 함수로 파티셔닝하고, 대응하는 파티션끼리 조인합니다. 각 파티션 쌍에서는 한쪽으로 메모리 해시 테이블을 만들고 다른 쪽을 조회합니다.

해시값이 같다고 키가 같은 것은 아닙니다. 6 % 3과 9 % 3은 모두 0이지만 6과 9는 서로 다릅니다. 후보를 찾은 뒤 실제 키 비교가 필요합니다. 원문은 파티션을 나누는 함수와 메모리 해시 테이블의 함수를 구분합니다. 한 파티션의 build 입력이 메모리에 들어간다는 가정도 필요합니다.

복합 조인 조건

AND 조건에서는 먼저 적용할 수 있는 조인 조건으로 후보 쌍을 구하고, 나머지 조건을 검사할 수 있습니다. 예를 들어 S.id = T.id AND S.dept_name = T.dept_name이면 id가 일치하는 쌍에 부서 조건을 적용합니다. 일반적인 조건은 block nested loop join으로도 평가할 수 있습니다.

OR 조건은 각 조건으로 구한 튜플 쌍의 합집합을 사용할 수 있습니다. 다만 같은 쌍이 두 조건에 모두 맞으면 중복으로 출력하지 않도록 처리해야 합니다. SQL의 중복 의미를 유지하려면 값이 같은 서로 다른 입력 튜플과 동일한 튜플 쌍을 구분해야 합니다. 조건을 그대로 검사하는 block nested loop join도 후보입니다.

기타 연산

중복 제거는 정렬로 같은 값을 인접하게 만들거나 해시로 묶어 처리할 수 있습니다. SQL에서는 DISTINCT로 중복 제거를 요구합니다. 필요한 열을 남기는 SQL 투영만으로는 중복 행을 자동으로 제거하지 않습니다.

집계는 같은 그룹의 레코드를 모아 부분 집계값을 갱신합니다. 정렬과 해시 모두 그룹을 구성하는 데 사용할 수 있습니다. 합집합·교집합·차집합도 정렬 후 병합하거나 해시로 대응 항목을 찾는 방식으로 구현합니다.

외부 조인은 매칭 여부를 기록하고, 보존해야 할 입력 중 끝까지 짝을 찾지 못한 레코드에 NULL을 채워 출력하도록 조인 알고리즘을 확장합니다.

용어와 비용식은 Database System Concepts 7판, 15장 Query Processing 강의 자료의 선택·정렬·조인 절을 대조했습니다. 식을 실제 실행 계획에 적용할 때는 버퍼 적중, 데이터 배치, 중복 키 수와 결과 쓰기 비용처럼 이 모델에서 생략한 조건을 추가로 확인해야 합니다.