복합 인덱스의 검색 범위: 사전식 정렬과 Start·Stop Key

핵심 요약

Oracle B-tree Index Range Scan은 정렬된 Key 공간에서 조건을 만족할 가능성이 있는 첫 Leaf Entry를 찾은 뒤, 연결된 Leaf Block을 앞이나 뒤 방향으로 읽다가 조건 범위를 벗어나는 지점에서 멈춥니다.

Root·Branch 탐색
  → Start Key를 포함할 첫 Leaf Entry 탐색

Leaf 수평 Scan
  → 조건 범위의 Entry·ROWID 반환

Stop 경계 도달
  → 더 이상 정답이 나올 수 없으면 종료

복합 인덱스는 왼쪽 Column부터 비교하는 사전식(Lexicographic) 순서로 정렬됩니다.

Index (C1, C2)

(A,1) (A,2) (A,5)
(B,1) (B,3) (B,7)
(C,2) (C,3) (C,9)

따라서 조건의 효과는 다음 순서로 판단합니다.

선행 Equality
  → 하나의 Prefix Group 고정

첫 Range Predicate
  → 연속 Leaf Scan의 주요 Start·Stop 범위 결정

첫 Range 뒤 후행 Predicate
  → Entry·ROWID를 추가 Filter할 수 있음
  → 중간 Prefix Group의 넓은 Leaf Scan은 남을 수 있음

Start·Stop Key는 “다음 정수” 같은 물리값으로 외우지 않습니다.

Start Key
  → 조건을 만족할 수 있는 첫 논리적 Key 경계

Stop Key
  → 조건 범위를 벗어나는 첫 논리적 Key 경계

실제 Oracle 내부 Key Encoding과 경계 표현은 Data Type·Sort Direction·NULL·ROWID·Collation 등에 따라 달라질 수 있습니다. 학습에서는 포함·제외 경계와 Leaf Scan 종료 조건으로 이해합니다.

이 이론의 범위

이 이론은 SQLP의 SQL 고급활용 및 튜닝 → 인덱스 튜닝 → 인덱스 기본 원리 범위에서 복합 인덱스의 Start·Stop Key와 검색 범위를 다룹니다. Access·Filter Predicate의 비용과 Index Column 설계는 이전·후속 이론과 연결합니다.

학습 목표

이 이론을 학습한 뒤에는 다음 내용을 설명할 수 있어야 합니다.

• 복합 인덱스의 사전식 정렬을 설명한다.
• Start Key와 Stop Key를 논리적 포함·제외 경계로 설명한다.
• Equality·>·>=·<·<=·BETWEEN별 범위를 구분한다.
• 중복 Key가 있을 때 Stop 경계와 ROWID Entry의 관계를 설명한다.
• 선행 Equality Prefix가 후행 Range를 좁히는 원리를 설명한다.
• 선두·중간 Column이 Range일 때 후행 조건의 효과가 제한되는 이유를 설명한다.
• ACCESS_PREDICATES와 FILTER_PREDICATES를 실제 Leaf Scan과 연결한다.
• IN-List가 여러 불연속 Range와 반복 Starts를 만들 수 있음을 설명한다.
• 선두 Column이 없을 때 Skip Scan·Full Scan 대안을 구분한다.
• NULL Entry 규칙이 IS NULL 검색 범위에 미치는 영향을 설명한다.
• Ascending·Descending Scan과 혼합 정렬 Index를 설명한다.
• Starts·A-Rows·Buffers·Reads로 Start·Stop 효율을 검증한다.

1. 사전식 정렬

복합 인덱스 (A,B,C)는 사전에서 단어를 비교하는 방식과 비슷하게 정렬됩니다.

1. A 비교
2. A가 같으면 B 비교
3. A·B가 같으면 C 비교
4. Nonunique Index에서는 동일 Key 안에서 ROWID 순서로 구분

예시입니다.

(A=1, B=1, C=1)
(A=1, B=1, C=3)
(A=1, B=2, C=1)
(A=1, B=2, C=9)
(A=2, B=1, C=1)

다음 조건은 하나의 좁은 Prefix를 고정합니다.

WHERE A = :a
AND   B = :b
AND   C >= :c

(A=:a, B=:b) Prefix 고정
  → 해당 Group 안에서 C>=:c인 첫 Entry 탐색
  → 같은 A·B Group이 끝날 때 종료

2. Start·Stop Key를 논리적 경계로 이해한다

2.1 Equality

Index (C1,C2)에서 다음 조건을 봅니다.

WHERE C1 = 'B'
AND   C2 = 3

개념적 범위입니다.

Start
  → (B,3)의 첫 Entry

Stop
  → (B,3)의 모든 중복 Entry와 ROWID가 끝난 뒤
     다음 Key Group으로 넘어가는 경계

Stop을 (B,4)로 외우면 부정확합니다.

• NUMBER에는 3.1·3.5가 존재할 수 있습니다.
• 문자에는 단순한 “다음 문자열”이 없습니다.
• DATE·TIMESTAMP는 정밀도가 다릅니다.
• Nonunique Index에는 같은 Key의 여러 ROWID Entry가 존재합니다.

2.2 중복 Key와 ROWID

Nonunique Index Leaf는 (Key, ROWID) 순서로 정렬됩니다.

(B,3,ROWID-1)
(B,3,ROWID-2)
(B,3,ROWID-3)

Equality Range는 같은 Key의 모든 ROWID Entry를 포함해야 합니다.

Start
  → 첫 (B,3,최소 ROWID 경계)

Stop
  → 마지막 (B,3,최대 ROWID 경계)을 지난 지점

이는 논리적 설명이며 실제 내부 Sentinel이나 Encoded Key를 직접 가정하지 않습니다.

3. 단일 Prefix Group 안의 하한·상한

Index (C1,C2)를 사용합니다.

3.1 C1='B'

Start
  → B Group의 첫 Entry

Stop
  → C1>'B'인 첫 Entry

3.2 C1='B' AND C2>=3

Start
  → (B,3) 이상 첫 Entry

Stop
  → B Group이 끝나는 경계

3.3 C1='B' AND C2>3

Start
  → C2=3의 모든 중복 Entry가 끝난 뒤 첫 Entry

Stop
  → B Group 끝

3.4 C1='B' AND C2<=3

Start
  → B Group의 첫 Entry

Stop
  → (B,3)의 모든 중복 Entry를 포함한 뒤 범위를 벗어나는 경계

3.5 C1='B' AND C2<3

Start
  → B Group의 첫 Entry

Stop
  → C2=3인 첫 Entry 직전의 논리적 경계

3.6 C1='B' AND C2 BETWEEN 2 AND 3

BETWEEN은 양쪽 포함입니다.

Start
  → (B,2) 이상 첫 Entry

Stop
  → (B,3)의 모든 중복 Entry를 포함한 뒤 경계

선행 C1이 Equality로 고정됐으므로 C2의 하한과 상한을 하나의 연속 범위에 정확하게 적용하기 쉽습니다.

4. 세 Column 이상에서의 Prefix와 첫 Range

Index (A,B,C,D)를 가정합니다.

WHERE A = :a
AND   B = :b
AND   C BETWEEN :c1 AND :c2
AND   D = :d

일반적인 물리 효과입니다.

D가 Index에 있으면 Table에 전달할 ROWID를 줄일 수 있습니다. 그러나 C Range 안의 Leaf Block과 D가 다른 Entry까지 읽는 비용은 남을 수 있습니다.

후보 Index (A,B,D,C)에서는 D가 Equality로 항상 제공될 때 다음처럼 더 좁은 Prefix가 만들어질 수 있습니다.

(A=:a, B=:b, D=:d) 고정
  → C Range

다만 D가 없는 다른 SQL의 공용성, 정렬, DML 비용을 함께 평가합니다.

5. 선두·중간 Column이 Range일 때

Index (C1,C2)에서 다음 조건을 봅니다.

WHERE C1 BETWEEN 'A' AND 'C'
AND   C2 BETWEEN 2 AND 3

전체 사전식 경계는 개념적으로 다음과 같습니다.

Start
  → ('A',2) 이상 첫 Entry

Stop
  → ('C',3)을 포함한 뒤 경계

하지만 중간 C1 Prefix에서는 C2 전체가 이 사전식 범위 안에 들어올 수 있습니다.

('A',2)   통과
('A',5)   C2 Filter에서 탈락 가능

('B',1)   전체 사전식 범위 안, 탈락 가능
('B',2)   통과
('B',3)   통과
('B',9)   전체 사전식 범위 안, 탈락 가능

('C',1)   탈락 가능
('C',3)   통과

핵심입니다.

C2가 ACCESS_PREDICATES에 표시됨
  ≠ 모든 C1 Prefix에서 C2=2~3만 물리적으로 읽음

Oracle은 전체 Key 경계를 이용하고, 범위 안에서 추가 조건을 평가할 수 있습니다. 실제 Scan량은 Buffers·Reads로 확인합니다.

6. ACCESS_PREDICATES와 FILTER_PREDICATES

Oracle 공식 Plan Column은 다음과 같습니다.

ACCESS_PREDICATES
  → Access Structure에서 Row·Entry를 찾는 데 사용
  → Range Scan의 Start·Stop Predicate가 대표적

FILTER_PREDICATES
  → Operation이 읽은 Row·Entry를 상위에 반환하기 전에 평가

다음 Plan을 가정합니다.

INDEX RANGE SCAN T_X1
  access("C1">=:B1 AND "C1"<=:B2
     AND "C2">=:B3 AND "C2"<=:B4)
  filter("C2">=:B3 AND "C2"<=:B4)

같은 조건이 Access와 Filter 양쪽에 보일 수도 있습니다.

• 양쪽 끝 Key 경계 결정에 사용
• 중간 Prefix Group에서 조건을 다시 평가

따라서 Predicate Text만으로 물리적 Entry 검사량을 확정하지 않습니다.

7. IN-List는 여러 불연속 Range다

Index (status,order_date)를 가정합니다.

WHERE status IN ('PAID','READY')
AND   order_date >= DATE '2026-07-01'

논리적 Range는 두 개입니다.

Range 1
  ('PAID', 2026-07-01) ~ PAID Group 끝

Range 2
  ('READY', 2026-07-01) ~ READY Group 끝

실행계획에는 다음이 나타날 수 있습니다.

INLIST ITERATOR
  TABLE ACCESS BY INDEX ROWID
    INDEX RANGE SCAN

각 IN 값에 대해 하위 Index Operation이 반복되므로 Starts를 확인합니다.

IN 값 20개
Index Starts 20
1회 Buffers 8
→ 총 Index Buffers 약 160

각 Range 내부 정렬은 유지될 수 있지만 여러 Range를 결합한 전체 결과가 ORDER BY를 자동 만족한다고 가정하지 않습니다.

8. 선두 Column이 없을 때: Skip Scan

Index (gender,email)에 다음 조건만 있습니다.

WHERE email = :email

선두 gender가 없으므로 일반적인 하나의 Prefix Range를 바로 정하기 어렵습니다.

Optimizer는 다음을 고려할 수 있습니다.

• Table Full Scan
• Index Full Scan
• Index Fast Full Scan
• Index Skip Scan

Skip Scan은 선두 Column의 NDV가 작을 때 Logical Subindex를 반복 탐색합니다.

gender='F' Group의 email Range
gender='M' Group의 email Range
...

다음 조건에서 상대적으로 유리할 수 있습니다.

• 선두 Column NDV가 작음
• 비선두 Predicate가 선택적임
• Table·Index 전체 Scan보다 반복 Probe 비용이 작음

Skip Scan은 선두 Equality를 가진 일반 Range Scan과 같지 않습니다. Starts·Buffers·Reads를 확인합니다.

9. NULL과 검색 범위

일반 B-tree는 모든 Index Key Column이 NULL인 Row를 저장하지 않습니다.

9.1 단일 Column

CREATE INDEX t_c1_ix ON t(c1);

c1 IS NULL Row는 Entry가 없으므로 이 Index만으로 모든 NULL Row를 찾을 수 없습니다.

9.2 복합 Index

CREATE INDEX t_c1_id_ix ON t(c1,id);

id가 NOT NULL이면 다음 Key는 저장됩니다.

(NULL,1001)
(NULL,1002)

전체 Key가 NULL이 아니기 때문입니다. Optimizer가 이 Index를 c1 IS NULL 검색에 사용할지는 통계·비용·Column 순서와 실제 Plan으로 확인합니다.

10. 날짜·Timestamp Range

하루 범위는 반개구간으로 작성합니다.

WHERE order_ts >= :day_start
AND   order_ts <  :next_day_start

개념적 경계입니다.

Start
  → day_start 이상 첫 Key

Stop
  → next_day_start 이상 첫 Key에 도달하기 전 종료

반개구간은 DATE와 Fractional Second를 가진 TIMESTAMP 모두에서 안전합니다.

다음 조건은 일반 원본 Index의 Start·Stop Key를 만들기 어렵게 할 수 있습니다.

WHERE TRUNC(order_ts) = :day_start

대안입니다.

• 원본 Column의 반개구간
• 동일 표현식 Function-Based Index
• Virtual Column + Index

11. Ascending·Descending Scan과 혼합 정렬

Oracle B-tree Leaf는 연결돼 있어 앞이나 뒤 방향으로 Range Scan할 수 있습니다.

INDEX RANGE SCAN
  → 기본 Key 방향

INDEX RANGE SCAN DESCENDING
  → 반대 방향

Index (customer_id ASC, order_date ASC)는 다음 정렬을 지원할 수 있습니다.

ORDER BY customer_id ASC, order_date ASC

전체 방향을 뒤집은 정렬도 역방향 Scan으로 가능할 수 있습니다.

ORDER BY customer_id DESC, order_date DESC

혼합 방향은 별도 Index가 필요할 수 있습니다.

CREATE INDEX orders_mix_ix
ON orders(customer_id ASC, order_date DESC);

ORDER BY customer_id ASC, order_date DESC

다만 ORDER BY를 생략하고 Index 순서에 의존하지 않습니다. Optimizer가 다른 Access Path를 선택할 수 있으므로 결과 순서가 필요하면 반드시 ORDER BY를 사용합니다.

12. 실제 Leaf 작업량 검증

SELECT /*+ GATHER_PLAN_STATISTICS */
       *
FROM   t
WHERE  c1 BETWEEN :c1_low AND :c1_high
AND    c2 BETWEEN :c2_low AND :c2_high;

SELECT *
FROM TABLE(
  DBMS_XPLAN.DISPLAY_CURSOR(
    :sql_id,
    :child_no,
    'ALLSTATS LAST +PREDICATE +ALIAS +NOTE'
  )
);

확인 순서입니다.

1. Index Column 순서를 기록합니다.
2. 선행 Equality Prefix를 표시합니다.
3. 첫 Range 조건을 찾습니다.
4. 논리적 Start·Stop 경계를 그립니다.
5. 중간 Prefix에서 후행 조건이 Filter될 수 있는지 판단합니다.
6. ACCESS_PREDICATES·FILTER_PREDICATES를 확인합니다.
7. Starts·E-Rows·A-Rows·Buffers·Reads를 확인합니다.
8. Index 후보 ROWID와 Table Access·최종 Row를 비교합니다.

12.1 A-Rows 주의

Index Operation의 A-Rows는 상위 Operation으로 반환한 Row 수입니다.

Leaf Entry 검사 100,000
Index Filter 통과 1,000
Index A-Rows 1,000
Index Buffers 5,000

A-Rows만 보면 1,000개만 읽은 것처럼 오해할 수 있습니다. Buffers·Reads, SQL Trace의 cr·pr·rows, 다른 Index 후보와의 전후 비교를 함께 사용합니다.

12.2 Starts 주의

INLIST ITERATOR나 Nested Loops에서 Index Operation이 반복될 수 있습니다.

Starts 10,000
A-Rows 20,000
Buffers 80,000

Row / Start
  = 2

Buffers / Start
  = 8

1회 비용이 작아도 Starts가 크면 총비용은 큽니다.

13. 컬럼 순서 비교

주요 SQL입니다.

WHERE customer_id = :customer_id
AND   order_date >= :from_date
AND   order_date <  :to_date
AND   status = :status

후보 A: (customer_id, order_date, status)

customer_id Equality
→ order_date Range
→ status 후행 Filter 가능

• 상태 없는 고객 날짜 조회에 공용성이 높습니다.
• 날짜 범위가 넓으면 Leaf Scan이 클 수 있습니다.

후보 B: (customer_id, status, order_date)

customer_id·status Equality
→ order_date Range

• 상태 조건이 항상 있으면 Leaf Range를 더 좁힐 수 있습니다.
• 상태 조건이 빠지는 SQL의 공용성이 낮아질 수 있습니다.

후보 C: Full·Partition Scan

결과 비율이 크거나 많은 Table Block을 방문한다면 Index가 항상 유리한 것은 아닙니다.

비교 지표입니다.

• Index·Table Buffers
• Physical Reads
• Elapsed·CPU
• Sort·TEMP
• 대표 Bind·Fetch
• DML CPU·Redo·Undo
• 다른 SQL Regression

14. 진단 절차

1. Index Column 순서를 왼쪽부터 기록한다.
2. Predicate를 각 Column에 대응한다.
3. 선행 Equality가 어디까지 이어지는지 표시한다.
4. 첫 Range와 논리적 Start·Stop 경계를 그린다.
5. 후행 조건의 중간 Prefix Filter 가능성을 표시한다.
6. IN-List면 불연속 Range 수와 Starts를 계산한다.
7. 선두 조건이 없으면 Skip Scan·Full Scan 대안을 확인한다.
8. NULL·Sort Direction·Fetch 범위를 확인한다.
9. 실제 access·filter와 Starts·A-Rows·Buffers·Reads를 수집한다.
10. 동일 Bind·Fetch에서 Index 후보와 Full Scan을 반복 비교한다.
11. DML·공간·다른 SQL Regression을 확인한다.

15. 자주 혼동하는 판단