DB - Query Processing (2)

jaewonnow_·2025년 10월 17일

Database

데이터베이스

목록 보기

4/11

4. Comparison

정의

$\mathbf{>}$ (크다), $\mathbf{\ge}$ (크거나 같다), $\mathbf{<}$ (작다), $\mathbf{\le}$ (작거나 같다) 등의 비교 연산자를 사용하여 데이터를 검색하는 쿼리.

동등 검색 (Equality): WHERE A = 10 $\to$ 결과 값은 특정 값(10)과 일치하는 레코드들이다 (한개일수도 여러개일수도. 어차피 찾는 비용은 같다).

비교 검색 (Comparison): WHERE A >= 10 $\to$ 결과 값은 10보다 크거나 같은 모든 레코드들입니다.따라서 Comparison은 특정 시작점(여기서는 10)부터 데이터가 끝나는 지점까지의 범위를 찾습니다.

그러나 범위를 찾으려면 다 찾아야 하니까 Linear 랑 비슷하겠다 생각하겠지만 아니다.

Comparison vs Linear

이 둘의 비용을 가르는 핵심은 "어디서 스캔을 시작하는가"이다.

Linear Search : 디스크에 저장된 테이블의 첫 블록부터 끝 블록까지 무조건 순차적으로 모두 읽음.

Comparison : B $^+$ -tree 인덱스로 시작점( $v$ )을 찾은 후, 조건에 맞는 $\mathbf{b}$ 개의 블록만 순차적으로 읽음.

4-1. Primary B+-Tree Index (정렬 O , 비교)

여기서 h 만큼 I/O cost 하고, 거기서 실제 레코드를 찾고(Primary) 그 레코드를 읽고 그뒤로 블록개수 b만큼(블록은 해당 조건에 대해 정렬) I/O Cost 발생
업로드중..

4-2. Secondary B+-tree Index (정렬 X ,비교)

여기서 h 만큼 I/O cost 하고, 거기서 레코드를 포인터를 찾고(Secondary) 그 레코드부터 찾아가 읽어들임 , 그뒤로 찾을때까지 (블록은 해당 조건에 대해 정렬 X) N회 I/O Cost 발생

Cost ≈ Cost=(h + n) × (tT + tS)

인덱스 탐색 (h):  트리의 높이 h 
조건을 만족하는 n개의 레코드

5. Conjunction (논리곱 AND)

데이터베이스 쿼리에서 여러 개의 조건이 모두 참일 때 레코드를 선택하는 방법( $\sigma_{\theta_1 \wedge \theta_2 \wedge \dots \wedge \theta_n}(r)$ )을 최적화하는 전략

SQL의 $\mathbf{AND}$ 연산으로 연결된 여러 개의 WHERE 절 조건을 처리하는 방법

5-1. 하나의 인덱스만 사용 (Using One Index)

이 전략은 여러 조건 중 가장 선택도가 좋은(가장 적은 결과를 반환할 것으로 예상되는) 하나의 조건( $\theta_i$ )에 해당하는 인덱스만 사용.

작동 방식

쿼리 옵티마이저가 비용이 가장 적게 드는 하나의 조건( $\theta_i$ )을 선택하고, 해당 인덱스를 사용하여 레코드를 디스크에서 메모리로 가져옵니다. (이때 Selection Algorithm 중 적절한 알고리즘을 사용.

메모리로 가져온 레코드에 대해 나머지 모든 조건( $\theta_1, \dots, \theta_{i-1}, \theta_{i+1}, \dots$ )을 CPU와 메모리 버퍼 상에서 테스트하여 최종 결과를 필터링합니다.

장점: 하나의 인덱스만 사용하므로 디스크 I/O가 비교적 단순하다.

5-2. 복합 인덱스 사용 (Using Composite Index)

이 전략은 여러 개의 조건이 포함된 인덱스( $\theta_1$ 와 $\theta_2$ 가 모두 키로 포함된 인덱스)가 있을 때 사용.

작동 방식:

쿼리 옵티마이저는 사용 가능한 복합 인덱스 중 쿼리 조건과 가장 잘 일치하는 인덱스를 선택합니다.복합 인덱스의 정렬 구조를 활용하여 여러 조건( $\theta_1 \wedge \theta_2$ )을 동시에 만족하는 레코드를 단 한 번의 인덱스 스캔으로 효율적으로 찾아냅니다.

장점: 디스크 접근 횟수를 획기적으로 줄여 가장 높은 성능을 제공할 수 있습니다.

5-3. 식별자 교차 (Intersection of Identifiers)

이 전략은 여러 조건( $\theta_i$ )에 각각 개별적인 인덱스가 있을 때 사용.

작동 방식:

각 조건( $\theta_1, \theta_2, \dots$ )에 해당하는 인덱스를 각각 스캔하여, 해당 조건을 만족하는 레코드 주소(Pointer 또는 Primary Key 값)들의 집합을 얻습니다.
얻어진 모든 주소 집합의 교차점(Intersection)을 계산합니다. 이 교집합은 모든 조건을 동시에 만족하는 레코드들의 주소 목록이 됩니다.
이 교집합 목록을 사용하여 실제 데이터 파일로 접근하여 레코드를 가져옵니다. (랜덤 I/O가 발생할 수 있습니다.)
인덱스가 없는 조건 처리: 만약 일부 조건에 적절한 인덱스가 없다면, 교차점 계산 후 메모리로 가져온 레코드에 대해 메모리 내에서 나머지 조건 테스트를 적용합니다.

장점: 여러 인덱스를 동시에 활용할 수 있어, 각 인덱스의 선택도가 낮더라도 결합하면 매우 효과적일 수 있다.

6. Disjunction (논리합 OR)

SQL의 OR 연산으로 연결된 여러 조건(σθ1∨θ2∨⋯∨θn(r))을 처리하는 최적화 전략.

논리합 검색의 주된 전략은 식별자 합집합을 통한 선택(Disjunctive Selection by Union of Identifiers).

6-1. 식별자 합집합을 통한 선택

이 전략은 OR 조건을 만족하는 모든 레코드를 찾기 위해 개별 인덱스를 활용한 후, 그 결과들을 합치는 방식입니다.

적용 조건: 이 전략은 모든 개별 조건(θ1,θ2,…)에 사용 가능한 인덱스가 있을 때만 효율적. 만약 일부 조건에 인덱스가 없다면, 인덱스를 사용하는 것보다 Full Table Scan (선형 스캔)이 더 빠를 수 있습니다.

작동 방식:

개별 인덱스 스캔: 각 조건(θi)에 해당하는 인덱스를 각각 스캔하여, 해당 조건을 만족하는 레코드들의 주소(Pointer 또는 Primary Key 값) 집합을 얻습니다.
합집합 계산 (Union): 얻어진 모든 주소 집합의 합집합(Union)을 계산합니다. 이 합집합은 하나 이상의 조건을 만족하는 모든 레코드들의 주소 목록이 됩니다.
데이터 인출 (Fetch): 이 합집합 목록에 있는 주소를 사용하여 실제 데이터 파일로 접근하여 레코드를 가져옵니다.
비용 고려: 합집합을 통해 주소 목록을 얻은 후 데이터를 가져오는 과정은 랜덤 I/O를 유발한다. 하지만, 각 조건에 맞는 레코드만 효율적으로 찾기 때문에, Full Table Scan보다 빠를 가능성이 훨씬 높다.

6-2. Negation (부정) 검색 전략 - σ¬θ(r)

WHERE NOT condition 은 인덱스 사용이 어려운 대표적인 경우다.

기본 전략 - 선형 스캔 (Linear Scan on File)

B+-tree와 같은 인덱스는 특정 값이나 범위의 시작점을 빠르게 찾는 데 최적화되어 있다. 전체 데이터의 대부분을 제외하는 ¬θ와 같은 부정 조건은 인덱스를 사용하기 어려운 상태이므로 보통 Full Table Scan (선형 스캔)을 기본 전략으로 선택한다.

예외 - 인덱스 역활용

NOT condition을 만족하는 레코드가 매우 적고, condition 자체에는 인덱스를 적용할 수 있는 경우에 한해 다음 방법을 사용할 수 있습니다.
θ를 만족하는 레코드를 인덱스로 찾습니다.
전체 레코드에서 이 결과를 제외하는 방식으로 부정 조건을 만족하는 레코드를 간접적으로 찾을 수 있습니다.

여기까지가 Selection Operation 관계 대수 6가지 특징이다.

특징을 요약하자면