CockroachDB 2.1에 새로 도입된 비용 기반 SQL 옵티마이저가 무엇인지, 왜 필요했는지, 그리고 변환 규칙과 memo 구조를 중심으로 내부가 어떻게 동작하는지 소개합니다.
여기 Cockroach Labs에서는 성능과 확장성을 개선하는 데 지속적으로 집중해 왔습니다. 그 목표의 일환으로, 2.1 릴리스에는 완전히 새로, 처음부터 구축한 비용 기반(cost-based) SQL 옵티마이저가 포함되어 있습니다. 이 옵티마이저는 처음으로 상관 서브쿼리 같은 SQL 기능을 가능하게 해줄 뿐 아니라, 향후 릴리스에서 특히 더 복잡한 리포팅 쿼리에서 큰 성능 개선을 이끌어낼 유연한 최적화 프레임워크도 제공합니다. 더 빨라져야 한다고 생각되는 쿼리가 있다면 저희에게 보내 주세요! 옵티마이저 성능을 튜닝하고 향후 작업의 우선순위를 정하는 데 사용하는 쿼리 라이브러리를 구축하고 있습니다.
엔지니어로서 저는 새 옵티마이저가 어떻게 동작하는지의 세부로 바로 뛰어들고 싶습니다(TL;DR - 정말 멋진 내용입니다). 하지만 먼저 배경을 설정해야 합니다. 비용 기반 SQL 옵티마이저가 무엇인지 설명한 다음, 왜 우리가 그런 것이 정말, 정말 필요하다고 결정하게 되었는지의 이야기를 들려드리겠습니다. 4명의 엔지니어를 창문 없는 Slack 방에 가둬두고 CockroachDB의 주요 컴포넌트를 마음껏 다시 쓰도록 허락할 만큼 말이죠. 이야기를 마친 뒤에는 새 옵티마이저의 “내부”를 살짝 들여다보며 정말 흥미로운 내용으로 넘어가겠습니다. 다만 더 깊이 파고들려면 블로그 글 한 편으로는 감당할 수 없을 정도로 많은 설명이 필요하므로, 여기서는 살짝 맛보기만 하겠습니다. 그래도 실망하지 마세요. 앞으로의 글에서 옵티마이저 내부를 더 깊게 다룰 예정이니 계속 지켜봐 주세요.
SQL 옵티마이저는 SQL 쿼리를 분석하고 이를 실행하는 가장 효율적인 방법을 선택합니다. 가장 단순한 쿼리는 실행 방법이 하나뿐일 수도 있지만, 더 복잡한 쿼리는 수천 가지, 심지어 수백만 가지 방법이 있을 수 있습니다. 옵티마이저가 좋을수록, 쿼리를 실행하는 가장 효율적인 방법인 최적 실행 계획(optimal execution plan) 에 더 가깝게 선택하게 됩니다.
겉보기엔 deceptively simple(생각보다 단순해 보이는) 쿼리 하나를 보겠습니다:
**``` SELECT * FROM customers c, orders o WHERE c.id=o.cust_id AND c.name < ’John Doe’
이 쿼리에 대해 옵티마이저가 답해야 하는 질문의 전체 목록을 장황하게 늘어놓지는 않겠습니다(저도 여러분도 지루할 테니까요). 하지만 제 요점을 보여주기 위한 몇 가지만 꼽아보면 다음과 같습니다:
1. name 필터는 조인 전에 평가해야 할까요, 아니면 조인 후에 평가해야 할까요?
2. hash join, merge join, 아니면 인덱스를 사용하는 nested loop join(CockroachDB에서는 “lookup join”이라고 부릅니다) 중 무엇을 사용해야 할까요?
3. lookup join 또는 hash join이라면, customers를 열거한 다음 orders를 lookup해야 할까요? 아니면 orders를 열거한 다음 customers를 lookup해야 할까요?
4. “name”에 보조 인덱스(secondary index)가 있다면, 매칭되는 name을 찾는 데 그것을 써야 할까요, 아니면 매칭되는 id를 찾기 위해 기본 인덱스(primary index)를 쓰는 편이 더 나을까요?
게다가 옵티마이저가 이런 질문 각각에 대해 개별적으로 답하기만 하면 충분하지 않습니다. 최선의 계획을 찾으려면 답들의 _조합_ 을 봐야 합니다. lookup join을 선택할 때는 보조 인덱스를 쓰는 것이 최선일 수 있습니다. 하지만 merge join을 사용한다면 기본 인덱스가 더 나을 수도 있죠. 최적 실행 계획은 행(row) 수, 여러 물리 연산자(physical operator)의 상대 성능, 데이터 값의 위치와 빈도, 그리고… 그 밖의 아주 많은 요소에 달려 있습니다.
Heuristic vs. cost-based
-------------------------------------------------------------------------------------------------------
그렇다면 옵티마이저는 이렇게 많은 가능한 실행 계획 중에서 어떻게 선택할까요? 이 문제에 대해 사람들은 제가 태어나기 전부터 고민하고 글을 써 왔기 때문에, 어떤 답이든 불충분할 수밖에 없습니다. 그래도 이 문제에 대한 두 가지 흔한 접근을 논의해 보는 것은 여전히 가치가 있습니다.
첫 번째 접근은, 옵티마이저를 처음 만드는 사람이라면 누구나 취하는 방식입니다. 일반 원칙에 기반한 미리 정해진 휴리스틱 규칙(heuristic rule)을 만들어 둡니다. 예를 들어, 등가 조건(equality condition)이 존재하면 항상 nested loop join 대신 hash join을 사용하라는 휴리스틱 규칙이 있을 수 있습니다. 대부분의 상황에서 이는 더 나은 실행 계획으로 이어지므로 좋은 휴리스틱입니다. 이런 규칙에 기반한 옵티마이저를 **휴리스틱 옵티마이저(heuristic optimizer)** 라고 합니다.
하지만 정적인 휴리스틱 규칙에는 단점이 있습니다. 대부분의 경우에는 잘 동작하지만, 다른 경우에는 최선의 계획을 찾지 못할 수 있습니다. 예를 들어 lookup join은 외부(outer) 릴레이션의 행들을 반복하면서, 내부(inner) 릴레이션에 대한 인덱스를 계속 probe하여 조건에 맞는 내부 행을 찾습니다. 이는 외부 행의 수가 작을 때는 잘 동작하지만, 그 수가 늘어나면서 각 행마다 probing하는 오버헤드가 실행 시간을 지배하게 되면 성능이 급격히 나빠집니다. 어떤 교차 지점(cross-over point)을 지나면 hash join이나 merge join이 더 나았을 것입니다. 하지만 이런 미묘함을 포착하는 휴리스틱을 설계하는 것은 어렵습니다.
여기서 **비용 기반 옵티마이저(cost-based optimizer)** 가 등장합니다. 비용 기반 옵티마이저는 가능한 실행 계획을 열거하고 각 계획에 비용(cost)을 부여합니다. 이 비용은 해당 계획을 실행하는 데 필요한 시간과 자원을 추정한 값입니다. 가능한 계획들을 열거한 뒤, 옵티마이저는 가장 낮은 비용의 계획을 선택해 실행 단계로 넘깁니다. 비용 모델(cost model)은 일반적으로 처리량(throughput), 즉 초당 쿼리 수를 최대화하도록 설계되지만, 지연 시간(latency), 즉 첫 번째 행을 가져오는 시간 최소화나 메모리 사용량 최소화 같은 다른 바람직한 쿼리 동작을 선호하도록 설계할 수도 있습니다.
이 시점에서 여러분은 “그런데 그 비용 모델이 틀리면 어떡하죠?”라고 생각할 수도 있습니다. 좋은 질문입니다. 비용 기반 옵티마이저는 결국 자신이 할당하는 비용의 품질만큼만 좋다는 점은 사실입니다. 또한 비용의 정확도는 옵티마이저가 수행하는 _행 수 추정(row count estimates)_ 의 정확도에 크게 좌우된다는 사실도 밝혀져 있습니다. 이름 그대로, 옵티마이저가 쿼리 계획의 각 단계가 얼마나 많은 행을 반환할지를 추정하는 것입니다. 여기서 또 다른 수십 년 연구 주제로 이어지는데, 바로 **데이터베이스 통계(database statistics)** 입니다.
데이터베이스 통계를 수집하는 목표는 옵티마이저가 더 정확한 행 수 추정을 할 수 있도록 정보를 제공하는 것입니다. 유용한 통계로는 테이블의 행 수, 컬럼의 고유 값(distinct) 수 및 null 값 수, 그리고 값 분포를 이해하기 위한 히스토그램 등이 있습니다. 이런 정보는 비용 모델로 들어가 조인 타입, 조인 순서, 인덱스 선택 등 다양한 결정을 돕습니다.
(Re)birth of an optimizer
--------------------------------------------------------------------------------------------------------
CockroachDB는 시간이 지나며 점점 더 복잡해진(대부분의 옵티마이저가 그렇듯) 단순한 휴리스틱 옵티마이저로 시작했습니다. 2.0 릴리스 즈음에는, 휴리스틱 설계의 한계를 더 이상 쉽게 우회할 수 없게 되면서 문제에 부딪히기 시작했습니다. 정교하게 튜닝된 휴리스틱 규칙들이 서로 충돌하기 시작했지만, 그 사이에서 무엇을 선택해야 할지 결정할 명확한 방법이 없었습니다. 예를 들어 다음 같은 단순한 휴리스틱은:
> “등가 조건이 있으면 hash join을 사용한다”
이렇게 변했고:
> “등가 조건이 있으면 hash join을 사용한다. 단, 두 입력이 모두 조인 키 기준으로 정렬되어 있다면 merge join을 사용한다”
마지막에는 이런 휴리스틱까지 고려하게 됐습니다:
> “등가 조건이 있으면 hash join을 사용한다. 단, 두 입력이 모두 조인 키 기준으로 정렬되어 있다면 merge join을 사용한다. 즉, 한쪽 조인 입력의 행 수가 작고 다른 입력에 사용할 수 있는 인덱스가 있다면 lookup join을 사용한다는 예외를 둔다”
새 휴리스틱 규칙을 추가할 때마다, 기존에 이미 존재하는 모든 휴리스틱 규칙과의 관계를 점검해 서로 잘 맞물려 동작하는지 확인해야 했습니다. 비용 기반 옵티마이저조차도 때때로 아슬아슬하게 균형 잡힌 젠가(Jenga) 탑처럼 보이기도 하지만, 휴리스틱 옵티마이저는 훨씬 낮은 높이에서도 무너집니다.
2017년 하반기쯤에는 낡아 보이기 시작한 휴리스틱 옵티마이저를 교체하자는 내부 모멘텀이 Cockroach Labs에서 커지고 있었습니다. 공동 창업자 중 한 명인 Peter Mattis는 데이터베이스 옵티마이저 외부 전문가를 초빙해 몇 달짜리 부트캠프를 진행하도록 했고, 최첨단 옵티마이저가 어떻게 동작하는지 개발자들에게 가르치는 것을 목표로 삼았습니다. 여기에는 해당 분야의 고전 논문을 읽는 숙제도 포함되어 있었습니다. 논의와 모멘텀을 촉진하기 위해 Peter는 중요한 개념 몇 가지를 시연하고 이후의 프로덕션 작업에 영향을 준, “opttoy”라는 [비용 기반 옵티마이저 프로토타입](https://github.com/petermattis/opttoy)도 만들었습니다.
제가 2018년 초에 입사했을 때, 회사는 이제 다음 단계로 나아갈 때라는 공동의 결론에 도달해 있었습니다. 제 배경과 이 주제에 대한 관심을 고려해, 저는 소규모(하지만 매우 의욕적인) 팀을 이끌고 비용 기반 옵티마이저를 처음부터 구축하는 일을 맡게 되었습니다. 9개월간의 집중적인 노력 끝에, 우리 팀은 CockroachDB 2.1 릴리스의 일부로 새 옵티마이저의 첫 번째 버전을 출시하고 있습니다. 아직 우리가 할 수 있는(그리고 할) 일이 훨씬 더 많지만, 이 첫 릴리스는 중요한 전진을 의미합니다. 2.1 비용 기반 옵티마이저가 지원하는 중요한 새 기능을 몇 가지 소개하면 다음과 같습니다:
* **상관 서브쿼리(Correlated subqueries)** - 외부 쿼리의 컬럼을 참조하는 내부 서브쿼리를 포함하는 쿼리입니다. 예를 들어 다음과 같습니다:
**```
SELECT *
FROM customers c
WHERE EXISTS (
SELECT *
FROM orders o
WHERE o.cust_id = c.id
)
```**
상관 서브쿼리를 최적화하는 것은 그 자체로 또 다른 블로그 글 하나 분량이며, 앞으로 다루고자 합니다.
* **lookup join의 자동 계획 수립(Automatic planning of lookup joins)**: 조인을 실행하는 방법을 결정할 때, 옵티마이저는 이제 merge join과 hash join뿐 아니라 lookup join도 고려합니다. lookup join은 등가 조인의 빠른 실행에 중요합니다. 한 입력은 행 수가 적고, 다른 입력은 등가 조건에 대한 인덱스를 가지고 있는 경우가 대표적입니다:
SELECT COUNT(*) FROM customers c, orders o WHERE c.id=o.cust_id AND c.zip='12345' AND c.name='John Doe'
여기서 옵티마이저는 먼저 우편번호 “12345”에 살며 이름이 “John Doe”인 고객을 찾고(대개 소수의 행일 가능성이 큽니다), 그 다음 orders 테이블을 probe하여 행 수를 카운트하는 계획을 고려하게 됩니다.
Under the Hood
---------------------------------------------------------------------------------------------
약속드린 대로, 새 옵티마이저의 내부를 빠르게 살짝 보여드리겠습니다. 시작하기 전에, 쿼리 계획을 트리(tree)로 생각하면 유용합니다. 트리의 각 노드는 실행 계획의 한 단계를 나타냅니다. 실제로 [SQL EXPLAIN](https://www.cockroachlabs.com/docs/stable/explain) 문이 실행 계획을 보여주는 방식이 바로 이것입니다:
[](https://images.ctfassets.net/00voh0j35590/1MhwoJVGgzgmebiwJm9CaH/200a58600ef8759a5443dabd0a1b1dc1/unoptimized-execution-plan.jpeg)
이 출력은 _최적화되지 않은(unoptimized)_ 계획이 어떻게 실행되는지를 보여줍니다. 먼저 customers와 orders 테이블의 전체 크로스 곱(cross-product)을 계산한 다음, `WHERE` 조건에 따라 결과 행을 필터링하고, 마지막으로 `count_rows` 집계를 계산합니다. 하지만 이는 끔찍한 계획입니다! 고객이 10,000명이고 주문이 100,000건이라면, 크로스 곱은 10억 행을 생성하게 되며 그 대부분은 결국 필터링으로 버려질 것입니다. 엄청난 낭비죠.
여기서 옵티마이저의 가치가 드러납니다. 옵티마이저의 일은 시작 계획 트리를 _변환(transform)_ 하여, _논리적으로 동등한(logically equivalent)_ 계획 트리들을 연속적으로 만들어 낸 다음, 그중 비용이 가장 낮은 트리를 선택하는 것입니다. 그렇다면 “논리적으로 동등하다”는 것은 무슨 뜻일까요? 두 계획 트리가 논리적으로 동등하다는 것은, 실행했을 때 동일한 데이터를 반환한다는 뜻입니다(단, `ORDER BY` 절이 없다면 행의 순서는 달라질 수 있습니다). 즉, 정확성 관점에서는 옵티마이저가 어떤 계획을 고르든 상관없고, 선택은 오직 성능을 극대화하기 위한 것입니다.
Transformations
----------------------------------------------------------------------------------------------
옵티마이저는 논리적으로 동등한 계획 트리의 완전한 집합을 한 번에 생성하지 않습니다. 대신 초기 트리로 시작해 점진적인 변환을 연속으로 수행하며 대안 트리들을 생성합니다. 개별 변환 하나하나는 대체로 비교적 단순하지만, 많은 변환이 결합되면 복잡한 최적화 과제를 해결할 수 있습니다. 동작하는 옵티마이저를 지켜보는 일은 마법처럼 느껴질 수 있습니다. 사용하는 각 변환을 이해하고 있더라도, 종종 놀라운 조합을 찾아 예상을 벗어난 계획을 만들어 내기 때문입니다. 위에 나온 비교적 단순한 쿼리조차도, 옵티마이저는 최종 계획에 도달하기 위해 12개의 변환을 적용합니다. 아래는 그중 핵심 변환 4가지를 보여주는 다이어그램입니다.
[](https://images.ctfassets.net/00voh0j35590/01GDWKfugVMnFxn2Jn6RM/05190683714c5cd52016bd516f2f5674/cost-based-optimizer.jpeg)
필터 조건이 조인 안으로 “푸시다운(push down)”되어 최대 성능을 위해 scan 연산자의 일부가 되는 것을 볼 수 있습니다. 마지막 변환에서 옵티마이저는 보조 인덱스를 사용하는 lookup join을 사용하기로 결정하여 쿼리를 만족시킵니다.
이 글을 쓰는 시점 기준으로, 비용 기반 옵티마이저는 160개가 넘는 서로 다른 변환을 구현하고 있으며, 앞으로의 릴리스에서 더 많이 추가할 것으로 기대합니다. 그리고 변환이 새 옵티마이저의 핵심에 있기 때문에, 우리는 변환을 가능한 한 정의하기 쉽고, 이해하기 쉽고, 유지보수하기 쉽도록 만드는 데 많은 시간을 들였습니다. 이를 위해 변환의 구조를 표현하는 Optgen이라는 도메인 특화 언어(DSL)를 만들었고, 그 DSL로부터 프로덕션용 Go 코드를 생성하는 도구도 만들었습니다. 다음은 Optgen 언어로 표현된 변환의 예입니다:
[MergeSelectInnerJoin, Normalize] (Select $input:(InnerJoin $left:* $right:* $on:) $filter: ) => (InnerJoin $left $right (ConcatFilters $on $filter) )
이 변환은 `WHERE` 절의 조건을 `INNER JOIN`의 ON 절 조건과 병합합니다. 또한 변환이 전이적으로(transitively) 매칭되는 경우에도 적용되도록 보장하는 코드를 포함해 약 25줄의 Go 코드를 생성합니다. 앞으로의 블로그 글에서는 Optgen의 더 구체적인 내용도 다룰 예정인데, 다룰 것이 매우 많기 때문입니다. 그때까지 기다릴 수 없다면 [Optgen 문서](https://github.com/cockroachdb/cockroach/blob/master/pkg/sql/opt/optgen/lang/doc.go)를 살펴보세요. 또한 우리 [변환 정의 파일](https://github.com/cockroachdb/cockroach/tree/master/pkg/sql/opt/norm/rules) 일부도 확인해 볼 수 있습니다. 특히 의욕이 있다면, 우리가 놓치고 있는 새 변환을 직접 만들어 보는 데 도전해 보세요. 커뮤니티의 기여는 언제나 환영합니다.
The Memo
---------------------------------------------------------------------------------------
옵티마이저가 많은 동등한 계획을 생성하고, 비용 추정을 사용해 그중 하나를 선택하는 방식을 설명했습니다. 이론적으로는 좋아 보이지만, 실용적인 측면에서는 어떨까요? 그렇게 많은 계획을 저장하려면 잠재적으로 지수(exponential) 수준의 메모리가 필요하지 않을까요? 그 답은 _memo_ 라는 기발한 데이터 구조에 있습니다.
memo는 주어진 쿼리에 대한 계획 트리들의 숲(forest)을, 계획들 사이의 큰 중복성을 활용해 효율적으로 저장하도록 설계되었습니다. 예를 들어 조인 쿼리는, 하나는 hash join을 사용하고 다른 하나는 merge join을 사용하며 세 번째는 lookup join을 사용한다는 점만 빼면 모든 면에서 동일한 여러 논리적으로 동등한 계획을 가질 수 있습니다. 더 나아가 각 계획은 또 여러 변형을 가질 수 있습니다. 어떤 변형에서는 왼쪽 조인 입력이 기본 인덱스를 사용해 행을 스캔하고, 다른 변형에서는 동일한 일을 수행하기 위해 보조 인덱스를 사용할 수도 있습니다. 이런 것을 순진하게(naively) 인코딩하면, 결과적으로 계획의 지수 폭발(exponential explosion)이 발생해 저장에 지수적인 메모리가 필요하게 됩니다.
memo는 memo group이라 불리는 동치 클래스(equivalence class)들의 집합을 정의함으로써 이 문제를 해결합니다. 각 그룹에는 논리적으로 동등한 표현(expression)들의 집합이 들어 있습니다. 아래는 그 예시입니다:
[](https://images.ctfassets.net/00voh0j35590/AMQgLiRvDne0lIDadrfAq/c5168924c8f041980a0d89e681375cb6/cost-based-optimizer_memo.png)
계획을 만들려면, 먼저 그룹 #1에서 어떤 연산자(operator)든 하나를 고르고, 그 연산자의 왼쪽 입력은 그룹 #2에서, 오른쪽 입력은 그룹 #3에서 고르면 됩니다. 어떤 것을 고르든 합법적인 계획이 됩니다. 같은 그룹 안의 연산자들은 논리적으로 동등하다는 것이 보장되기 때문입니다. 간단한 산술로도 이 memo에는 12개의 가능한 계획(3 * 2 * 2)이 인코딩되어 있음을 알 수 있습니다. 이제 6개 테이블을 조인하고, 복잡한 집계와 많은 필터 조건을 포함하는 복잡한 리포팅 쿼리를 상상해 보세요. 계획의 수는 수천 개에 이를 수도 있지만, memo 구조를 모르는 상태에서 예상할 법한 것보다 훨씬 적은 공간에 인코딩됩니다.
물론 옵티마이저는 memo에서 가능한 계획 트리 중 하나를 무작위로 고르지 않습니다. 대신 각 memo group에서 비용이 가장 낮은 표현을 추적한 다음, 그 표현들로부터 재귀적으로 최종 계획을 구성합니다. 실제로 memo는 아름다운 데이터 구조이며, Dan Brown의 소설 “Angels and Demons”에 나오는 [illuminati diamond](http://www.johnlangdon.net/works/earth-air-fire-water/) 앰비그램(ambigram)을 떠올리게 합니다. 둘 다 가능해 보이는 것보다 더 많은 정보를 인코딩합니다.
Conclusion
------------------------------------------------------------------------------------------
우리 팀은 CockroachDB의 비용 기반 옵티마이저 내부에 관한 후속 블로그 글들을 작성할 계획입니다. 이번 글에서는 표면만 살짝 긁었을 뿐입니다. 여러분이 관심 있는 특정 주제가 있다면 알려 주세요. 아니면 더 좋은 방법으로, [Cockroach Labs에 합류](https://www.cockroachlabs.com/careers/#jobs)해서, 행성 규모(planet-scale)의 ACID 데이터베이스를 함께 만들어 주세요.
그리고 [distributed SQL](https://www.cockroachlabs.com/blog/what-is-distributed-sql/) 엔진을 만드는 것이 취향이라면, 좋은 소식이 있습니다 — 저희는 채용 중입니다! 채용 공고는 [여기](https://cockroa.ch/eng_hiring)에서 확인하세요.