4장. 누가 고를 것인가 — System R과 비용 기반 옵티마이저

{/* 삽화 자리 — 갈림길 앞에서 두 경로의 값을 저울에 달아보는 사람 */}

200만 행 테이블에서 13.2%까지는 인덱스를 타고, 13.7%에서는 풀스캔으로 넘어갑니다. 그런데 인덱스만 읽으면 되는 조회는 81%에서도 인덱스를 씁니다. 이 판단을 내리는 건 사람이 아닙니다.

면접 실전 질문: ① 인덱스를 걸었는데 왜 안 탈까요? ② 옵티마이저는 무엇을 근거로 실행계획을 고르나요? ③ 통계가 낡으면 무슨 일이 생기나요?

배경 — 3장이 남긴 질문

3장의 표를 다시 봅시다. 같은 인덱스로 같은 테이블을 읽는데, 구간이 1건이면 이득이 1.8배뿐이고 1만 건이면 2,175배였습니다. 같은 인덱스인데 구간 크기에 따라 값이 세 자릿수로 갈립니다.

그러면 이 쿼리가 어느 쪽인지는 누가 판단할까요. 그리고 언제 판단할까요.

관계형 데이터베이스 이전에는 답이 간단했습니다. 프로그래머가 직접 썼거든요.

📄 문서 기반 (미검증) — CODASYL 계열의 네트워크 모델 DB와 IBM IMS의 DL/I가 그 방식이었습니다. 프로그램이 레코드를 하나씩 짚어가며 “이 집합에서 다음 것” 식으로 경로를 직접 지시했어요. 경로를 사람이 정했으니 누가 고를지 고민할 일도 없었죠.

대신 대가가 있었습니다. 데이터가 바뀌거나 인덱스가 하나 추가되면 경로를 지정한 코드를 전부 다시 써야 했습니다.

SQL은 여기서 약속을 하나 합니다. 무엇을 원하는지만 쓰세요. 어떻게 가져올지는 우리가 정합니다.

-- 어디로 어떻게 가라는 말이 한 마디도 없다
SELECT * FROM scan_demo WHERE transaction_no BETWEEN ? AND ?;

좋은 약속인데, 이걸 하는 순간 누군가는 반드시 골라야 합니다. 사람이 안 고르기로 했으니까요.

스토리 — 1979년, 고르는 방법을 정하다

IBM 산호세 연구소의 System R 팀이 그 방법을 내놨습니다. 1979년 SIGMOD에 실린 「Access Path Selection in a Relational Database Management System」이고, 저자는 퍼트리샤 셀린저와 애스트러핸·체임벌린·로리·프라이스입니다(23–34쪽).

제안은 세 걸음으로 요약됩니다.

1. 후보를 나열한다. 이 쿼리를 처리할 수 있는 경로를 전부 늘어놓습니다 — 풀스캔, 이 인덱스, 저 인덱스, 조인이라면 어느 쪽을 먼저 읽을지까지.
2. 각 후보의 비용을 계산한다. 실행하지 않고, 숫자로 견줍니다.
3. 제일 싼 걸 고른다.

당연해 보이지만, 이게 당연해지려면 앞의 두 걸음에 답이 있어야 합니다.

비용을 무엇으로 셀 것인가

1장에서 우리가 한 고민을 이들도 했습니다. 무엇을 세야 하는가.

📄 문서 기반 (미검증) — System R의 비용식은 페이지 읽기 횟수 + W × RSI 호출 횟수였습니다. 뒤쪽 항이 실제 CPU 시간이 아니라 꺼낸 튜플 수라는 게 핵심이에요. 디스크 왕복과 행 처리를 따로 세고 가중치 W로 합친 겁니다.

1장에서 우리가 잰 게 정확히 이 두 항이었습니다. 메모리에 다 올라와 있을 때 스캔 시간을 끌고 간 건 페이지가 아니라 행 처리 비용이었죠. 1979년에 이미 둘을 나눠 놓은 이유를 47년 뒤 노트북에서 다시 본 셈입니다.

여기서 중요한 건 공식이 아니라 태도입니다. 비용이 하나의 숫자가 되어야 후보끼리 비교할 수 있습니다. “인덱스가 빠르다”가 아니라 “이 인덱스는 71,747이고 풀스캔은 199,736이다”여야 고를 수 있어요.

이 숫자에 단위는 없습니다. 초도 아니고 바이트도 아니에요. 오직 후보끼리 견주기 위한 값입니다.

그런데 실행하기 전에 어떻게 비용을 아나

이게 진짜 어려운 부분입니다. 비용을 계산하려면 결과가 몇 건인지 알아야 하는데, 그건 실행해봐야 압니다.

System R의 답은 추정이었습니다. 조건마다 “이 조건을 통과하는 비율”을 계산하고, 그걸 전체 행 수에 곱합니다. 이 비율을 선택도(selectivity) 라고 부릅니다.

숫자로 보면 헷갈릴 일이 없습니다. 우리 테이블에서 transaction_no = '...'는 값이 전부 달라 200만 분의 1이고, status = 'DONE'처럼 값이 몇 종류뿐인 조건은 3분의 1쯤이에요. 앞은 인덱스가 크게 이기고, 뒤는 인덱스를 타봐야 테이블의 3분의 1을 읽습니다.

선택도를 계산하려면 데이터의 분포를 알아야 하고, 그래서 통계가 필요합니다. 이 테이블에 행이 몇 개인지, 이 컬럼에 서로 다른 값이 몇 개인지.

정리하면 이런 사슬입니다.

통계  →  선택도 추정  →  결과 건수 추정  →  비용 계산  →  경로 선택

사슬의 맨 앞이 틀리면 맨 뒤도 틀립니다. 이 문장이 3부 전체의 주제고, 특히 10장은 통계가 아예 없을 때 무슨 일이 생기는지만 다룹니다.

이 설계가 47년째 살아남았습니다. 오늘의 MySQL·PostgreSQL·Oracle이 전부 이 세 걸음을 밟습니다. 그러니 직접 열어보면 됩니다.

핵심 — 옵티마이저의 계산을 꺼내봤습니다

MySQL은 자기가 견준 비용을 보여줍니다.

SET optimizer_trace = 'enabled=on';
SELECT * FROM scan_demo
 WHERE transaction_no BETWEEN LPAD(500000,20,'0') AND LPAD(699999,20,'0');
SELECT TRACE FROM information_schema.OPTIMIZER_TRACE;

트레이스는 세션 단위고 기본으로 마지막 문장 하나만 남습니다. 그리고 optimizer_trace_max_mem_size(기본 1MB)를 넘으면 잘리니, 잘렸는지는 같은 테이블의 MISSING_BYTES_BEYOND_MAX_MEM_SIZE로 확인하세요.

트레이스 안에 이런 게 들어 있습니다. 두 군데에서 발췌한 것입니다 — rows_estimation의 table_scan과 그 아래 range_analysis.range_scan_alternatives요.

"table_scan": { "rows": 1917639, "cost": 199736 },
"range_scan_alternatives": [
  { "index": "idx_txno", "rows": 423422, "cost": 148218, "chosen": true }
]

후보 둘과 각각의 값입니다. 셀린저의 세 걸음이 그대로 보입니다.

range_scan_alternatives의 chosen은 range 후보들 중 1등이라는 뜻이고, 풀스캔과의 최종 대결은 best_access_path에서 벌어집니다. 거기 적힌 비용에는 행 평가 비용이 더 붙어 있어 숫자가 다르니, 위 두 값을 견주세요.

인덱스를 버리는 지점

200만 행 테이블에서 구간을 넓혀가며 옵티마이저가 무엇을 고르는지 봤습니다.

✅ 실측 (MySQL 8.0.46 / Docker / Apple M1 / macOS, 2026-08. 200만 행, SELECT *. 비용은 정수로 반올림했습니다. 측정 전 SET GLOBAL innodb_stats_auto_recalc=OFF; ANALYZE TABLE scan_demo;로 통계를 잠갔습니다 — compose 기본값은 ON이라 이 두 줄을 먼저 쳐야 합니다. 재현: WIDTHS="10000 100000 200000 300000 330000 340000 400000" ./ch04/tippingpoint.sh. 전체 소스: docs/book/code/db-index/ch04/tippingpoint.sh)

표에 “구간 폭”과 “실제 행 수”를 따로 실은 이유가 있습니다. 처음엔 폭을 그대로 행 수로 적었다가 틀렸어요. 시드가 INSERT ... SELECT로 데이터를 불리면서 auto_increment에 구멍을 냈고(MAX(id)가 260만인데 COUNT(*)는 200만입니다), 그래서 폭 34만이 실제로는 27만 4천 행입니다.

폭으로 셌더니 실제와 달랐다 — 이 장이 다루는 이야기가 정확히 그겁니다. 옵티마이저도 같은 일을 겪습니다.

풀스캔 비용은 199,736에서 꼼짝하지 않습니다. 구간이 얼마든 테이블 전체를 읽는 값은 같으니까요. 움직이는 건 인덱스 쪽뿐이고, 그 값이 199,736을 넘는 순간 갈아탑니다.

13.2%에서 193,949, 13.7%에서 205,655. 경계가 그 사이에 있습니다.

흔히 “테이블의 20~30%를 넘으면 인덱스를 안 탄다”는 경험칙이 돌아다니는데, 이 실험에서는 13.7%였습니다. 경험칙의 하한인 20%에도 못 미쳤습니다. 그리고 이 숫자는 테이블마다 달라요 — 행이 얼마나 넓은지, 인덱스가 얼마나 큰지, 버퍼풀에 얼마나 올라와 있는지가 전부 저 비용에 들어가니까요. 외울 숫자가 아니라 꺼내볼 숫자입니다.

같은 인덱스인데 81%까지 쓰는 경우

같은 실험을 SELECT COUNT(*)로 바꿔 돌렸습니다. 인덱스 안의 값만 있으면 되는 조회죠.

✅ 실측 (같은 환경·같은 테이블·같은 인덱스. 쿼리만 SELECT COUNT(*). 재현: QUERY="SELECT COUNT(*) FROM scan_demo" WIDTHS="200000 400000 800000 1600000 2000000" ./ch04/tippingpoint.sh)

81%를 읽는데도 인덱스가 쌉니다. 앞 표에서는 13.7%에서 버렸는데요.

여기서 이런 의심이 들 수 있습니다. 추정이 절반에서 멈췄다면(바로 다음 절), 81%라는 건 옵티마이저가 몰라서 고른 것 아닌가? 아닙니다. 실제 162만 행으로 계산해도 행 평가 비용만 16만 남짓이라 커버링 쪽이 여전히 쌉니다. 천장이 없었어도 답은 같았어요.

차이는 하나입니다. SELECT *는 인덱스에서 찾은 뒤 실제 행을 가지러 클러스터드 인덱스로 다시 내려가야 합니다. COUNT(*)는 그럴 필요가 없고요. 같은 구간에서 견줘보면 이렇습니다.

폭 400,000의 인덱스 비용 236,668은 옵티마이저가 버린 range 후보의 값입니다(추정 676,102). 표1의 추정 행 수 열은 고른 경로 기준이라 그 줄에는 풀스캔 값이 찍혀 있어요.

두 지점에서 정확히 같은 배수가 나옵니다. 왕복 비용이 구간 크기에 비례한다는 뜻이에요 — 행 하나마다 한 번씩 내려가야 하니까요. 실제로 붙은 값은 폭 200,000에서 104,748, 폭 400,000에서 167,257로 같이 커집니다.

그러니까 “이 쿼리가 인덱스를 타느냐”는 인덱스만 보고 답할 수 없습니다. 무엇을 select 하느냐가 같이 정합니다. 그 왕복이 정확히 무엇인지는 7장에서 재고, 아예 없애는 방법은 16장입니다.

추정이 멈추는 자리

커버링 표에서 눈에 걸리는 게 있습니다. 36.7%·65.7%·81.0% 세 줄의 추정 행 수가 958,819로 똑같습니다. 비용도 98,436으로 같고요.

이 숫자의 정체는 이렇습니다.

958,819  =  1,917,639 ÷ 2

1,917,639는 통계가 본 이 테이블의 전체 행 수입니다(실제 200만과 왜 다른지는 바로 다음 절에서 봅니다). 추정이 전체의 정확히 절반에서 멈춥니다. 그 위로는 구간을 아무리 넓혀도 추정이 안 올라가고, 비용이 추정에 정비례하니(958,819÷676,102 = 1.418, 98,436÷69,411 = 1.418) 비용도 같이 멈춥니다.

원인은 확인하지 못했습니다. 관측된 사실은 “절반에서 포화한다”까지예요. 더 파보려면 InnoDB의 btr_estimate_n_rows_in_range()와 ha_innobase::records_in_range()가 출발점입니다. 다만 결과는 분명해요 — 추정치가 전체의 절반에 닿는 순간 옵티마이저는 그 위를 구별하지 못합니다. 이 표에서는 실제 36.7% 줄에서 이미 멈췄어요. 추정이 실제의 두 배쯤이니 실제로는 24% 근처부터 눈이 감기는 셈입니다.

추정은 실제의 두 배였습니다

표를 다시 보면 불편한 열이 하나 있습니다. 추정 행 수 열입니다.

✅ 실측 (같은 환경. 실제 행 수는 같은 조건으로 COUNT(*)를 돌려 확인)

다섯 지점 전부 두 배 근처입니다. 그리고 이 테이블은 추정이 가장 쉬운 조건이에요 — transaction_no가 200만 행에 전부 다른 값이거든요.

그런데 통계는 그것조차 정확히 모릅니다.

✅ 실측 (서로 다른 값은 mysql.innodb_index_stats의 n_diff_pfx01, 전체 행 수는 mysql.innodb_table_stats의 n_rows. 통계는 전수 조사가 아니라 페이지 샘플링이라 이렇게 어긋납니다)

아래쪽 1,917,639를 어디서 봤는지 기억나시나요. 앞 표의 풀스캔 추정 행 수가 바로 그 숫자입니다. 사슬의 맨 앞이 이미 4% 틀린 채로 계산이 시작되고 있었던 거예요.

방향은 분명합니다 — 옵티마이저는 실행 전에 답을 모릅니다. 통계에서 추정할 뿐이고, 추정은 틀립니다. 여기서는 두 배로 틀렸는데도 결론은 안 바뀌었어요. 두 후보의 값 차이가 그보다 컸으니까요.

그 차이가 크지 않을 때, 혹은 통계가 아예 없을 때 무슨 일이 생기는지는 10장입니다. 미리 말하면 이렇습니다 — 운영에서 잰 어떤 쿼리는 추정이 실제와 37만 배 어긋났습니다(✅ 운영 실측 인용 — 조건을 안 걸면 빠릅니다).

통계가 바뀌면 판단도 바뀝니다

이 실험을 처음 돌렸을 때 결과가 이상했습니다. 6%에서 풀스캔을 고르더니 7%에서 다시 인덱스로 돌아갔거든요. 구간을 넓혔는데 인덱스로 돌아가는 건 말이 안 됩니다.

범인은 통계 갱신이었습니다. 측정하는 동안 InnoDB가 통계를 다시 계산하면서 두 후보의 값이 같이 흔들렸습니다 — 풀스캔만 해도 221,284에서 199,736으로 움직였어요(같은 환경, 같은 테이블입니다). 어느 쪽이 얼마나 흔들려 순서를 뒤집었는지는 그 회차 로그를 안 남겨 못 가릅니다.

ANALYZE TABLE로 한 번 고정하고 innodb_stats_auto_recalc=OFF로 잠근 뒤에야 표가 단조로워졌습니다.

이건 실험의 사고였지만 동시에 이 장의 결론이기도 합니다. 같은 쿼리, 같은 데이터, 같은 인덱스인데 통계가 갱신됐다는 이유만으로 실행계획이 바뀝니다. 어제 잘 돌던 쿼리가 오늘 느려지는 이야기의 상당수가 여기서 시작됩니다.

정리

• SQL이 “무엇을 원하는지만 쓰라”고 약속한 순간, 어떻게 가져올지를 고르는 일이 시스템 몫이 됐습니다.
• 1979년 System R 팀이 방법을 정했습니다. 후보를 나열하고, 각각의 비용을 숫자로 계산하고, 제일 싼 걸 고른다. 47년이 지나도 이 세 걸음은 그대로입니다.
• 비용을 계산하려면 결과 건수를 알아야 하는데 실행 전에는 모릅니다. 그래서 통계 → 선택도 → 건수 추정 → 비용이라는 사슬이 생겼고, 맨 앞이 틀리면 맨 뒤도 틀립니다.
• 실측: 풀스캔 비용은 199,736으로 고정이고 인덱스 비용만 구간을 따라 오릅니다. 교차점은 13.2%와 13.7% 사이였습니다. 흔한 경험칙(20~30%)의 하한에도 못 미칩니다.
• 같은 테이블·같은 인덱스인데 커버링 조회는 81%에서도 인덱스를 씁니다. 무엇을 select 하느냐가 판단을 바꿉니다.
• 추정은 실제의 약 두 배였습니다. 그래도 결론은 안 바뀌었어요 — 두 후보의 값 차이가 충분히 컸으니까요.
• 추정에는 천장이 있었습니다. 통계 행 수의 절반(958,819)에서 멈춰, 그 위로는 구간을 넓혀도 옵티마이저가 구별하지 못했습니다.
• 통계가 갱신되자 같은 쿼리의 계획이 뒤집혔습니다. 실행계획은 데이터만의 함수가 아닙니다.

생각해볼 질문

1. 풀스캔 비용이 199,736으로 고정이었던 건 테이블 크기가 안 변했기 때문입니다. 그렇다면 테이블에 행이 계속 쌓이면 이 경계는 어느 쪽으로 움직일까요?
2. 커버링 조회가 81%에서도 인덱스를 쓴 이유는 왕복이 없기 때문이었습니다. 그 왕복은 정확히 몇 번의 페이지 접근일까요? (7장)
3. 추정이 두 배 틀려도 결론이 안 바뀌었습니다. 그럼 추정이 몇 배 틀려야 옵티마이저가 잘못된 경로를 고를까요? 그리고 그때 우리는 그걸 어떻게 알아챌까요? (10장)

여기까지가 제1부입니다. 인덱스가 왜 이 모양으로 태어났고(1·2장), 왜 리프가 이어져 있고(3장), 누가 그걸 쓸지 고르는지(4장)를 봤습니다.

그런데 지금까지 계속 쓰면서도 제대로 뜯어보지 않은 단어가 하나 있습니다. 페이지. 1장에서 이 책의 단위로 정했고, 2장에서 팬아웃을 정했고, 방금 옵티마이저의 비용 계산에도 들어갔죠.

커버링 표에서 옵티마이저가 견준 풀스캔 비용 199,736을 뜯어보면 이렇습니다.

행 평가:  0.1 × 1,917,639 = 191,764   (96%)
페이지:   199,736 − 191,764 = 7,972   (4%)
          7,972 ÷ 0.25 = 31,888 페이지

✅ 실측 (mysql.server_cost의 row_evaluate_cost 0.1, mysql.engine_cost의 memory_block_read_cost 0.25. 환산된 31,888은 mysql.innodb_table_stats가 보고한 클러스터드 31,872페이지와 16페이지 차입니다)

비용의 96%가 행을 훑는 값이고 페이지 값은 4%뿐입니다. 버퍼풀에 다 올라와 있으니까요 — 1장에서 본 그대로입니다.

그럼 페이지가 진짜로 청구되는 건 언제일까요. 디스크에서 가져와야 할 때고, 그 값이 얼마인지 알려면 페이지가 무엇인지부터 알아야 합니다.

그게 정확히 무엇인지, 안에 무엇이 어떻게 들어 있는지가 제2부입니다.

▶ 5장. 모든 것은 16KB다 — 페이지·행·오버플로