백만 행에서 왜 서너 장만 읽나
인덱스 페이지 한 장(8KiB)에는 키가 수백 개 들어갑니다. 그래서 한 층 내려갈 때마다 가지가 수백 배로 늘고, 트리의 높이는 행 수의 로그로만 자랍니다. 행이 천 배가 되어도 층은 한두 개 늘 뿐입니다. 그런데 같은 인덱스가 많은 행을 고르는 질의에서는 표 전체를 읽는 것보다 느려집니다. 두 이야기를 차례로 봅니다.
루트에서 잎까지, 그리고 힙까지
위가 루트, 아래로 갈수록 잎, 맨 아래가 표 데이터(힙)입니다 · 인덱스 페이지 · 이번에 읽는 페이지 · 찾아 내려가는 길 · 힙 페이지 · 층 전체(다 그리지 못한 페이지)
층의 넓이는 로그 눈금입니다. 실제 비율로 그리면 잎 층이 루트의 수천 배라 화면에 들어가지 않습니다. 한 층에는 페이지를 11×11 장까지만 그리고, 나머지는 옅은 바닥이 대신합니다.
행 수와 키 크기 바꿔 보기
한 줄을 찾을 때 읽는 페이지
- 팬아웃 (한 페이지에 드는 키)
- 트리 높이
- 한 줄 찾기에 읽는 페이지
- 표 데이터(힙)
| 층 | 페이지 수 | 읽는 페이지 |
|---|
| 행 수 | 트리 높이 | 한 줄 찾기에 읽는 페이지 |
|---|
실제로는 루트와 중간 층이 거의 늘 메모리(공유 버퍼)에 있어서, 디스크까지 가는 것은 잎과 힙 한두 장인 경우가 많습니다. 여기서는 그 캐시를 빼고 모두 읽는다고 셉니다. int 와 bigint 의 팬아웃이 같은 것은 실수가 아닙니다 — 항목이 8바이트 경계에 맞춰 놓이므로 둘 다 한 항목이 같은 자리를 차지합니다.
인덱스가 손해인 경우 — 많이 고르는 범위 질의
인덱스는 키 순서로 정렬되어 있지만, 그 키가 가리키는 행은 힙 곳곳에 흩어져 있습니다. 행을 하나 고를 때마다 힙을 무작위로 한 장씩 읽어야 합니다. 고르는 행이 늘어 어느 선을 넘으면, 차라리 표 전체를 처음부터 순서대로 읽는 편(전체 스캔)이 쌉니다.
인덱스로 읽을까, 전체를 읽을까
- 고르는 행
- 인덱스로 읽는 비용
- 전체 스캔 비용
- 유불리가 뒤집히는 선택도
- 판정
| 선택도 | 고르는 행 | 인덱스 비용 | 전체 스캔 비용 | 싼 쪽 |
|---|
이 비용 모델의 가정
- 페이지는 8KiB. 인덱스 페이지는 머리·꼬리 40바이트를 빼고 90% 까지 채웁니다.
- 인덱스 항목 하나 = 키 + 8바이트 머리를 8바이트 경계로 올린 것 + 줄 포인터 4바이트. 모든 층이 같은 팬아웃이라고 봅니다.
- 행 한 줄은 데이터 100바이트에 머리 24바이트. 그래서 힙 페이지 한 장에 61행이 들어갑니다.
- 캐시가 없습니다. 읽는 페이지는 전부 저장 장치에서 옵니다.
- 힙의 물리 순서와 키 순서는 관계가 없습니다(상관 0). 고른 행마다 힙을 무작위로 한 장씩 읽고, 같은 페이지를 다시 읽어도 다시 셉니다.
- 인덱스 페이지도 무작위 읽기로 셉니다. 전체 스캔은 힙을 순서대로 한 번 읽습니다. 행을 거르는 CPU 비용은 뺍니다.
뒤집히는 선택도는 표 크기와 거의 상관이 없습니다 — 한 줄에 무작위 한 장, 한 페이지에 61줄이므로 대략 1 ÷ (61 × 무작위 비용) 근처에서 갈립니다. 실제 데이터베이스는 이 사이를 메우는 길을 더 가지고 있습니다. 표가 키 순서로 저장되어 있으면(상관이 높으면) 힙도 순서대로 읽게 되어 인덱스가 훨씬 오래 유리하고, PostgreSQL 의 비트맵 힙 스캔은 고른 행의 페이지를 먼저 모아 정렬한 뒤 한 번씩만 읽습니다. 플래너가 인덱스를 두고도 전체 스캔을 고른다면 대개 이 계산 때문입니다.