(번역) 카크로치디비(CockroachDB) 블로그 / 비용기반 SQL 옵티마이저는 어떻게 만들어졌나

원문: https://www.cockroachlabs.com/blog/building-cost-based-sql-optimizer/

Written by Andy Kimball on Nov 8, 2018

Cockroach 연구소는 성능과 확장성 향상에 지속해서 주력하고 있습니다. 이를 위해 2.1 릴리즈에는 새로운 비용기반 SQL 옵티마이저가 포함되었습니다. 먼저 연관 서브쿼리에 대한 기능이 적용되었고, 다음 릴리즈에 더 복잡한 쿼리에 대한 성능향상을 하기 위해 유연한 최적화 프레임워크를 준비했습니다. 더 빨라질 필요가 있는 쿼리가 있으면 우리에게 알려주십시오! 우리는 옵티마이저 최적화 작업을 위한 라이브러리를 작성하고 이후 작업의 우선순위를 정하는 중입니다.

엔지니어로서 저는 새로운 옵티마이저의 작동방식을 자세히 살펴보고 싶습니다.(TL;DR 매우 멋진 일) 먼저, 비용기반 SQL 옵티마이저가 무엇인지 알아보고, 우리가 어떻게 그중 하나를 선택했는지 말씀드리겠습니다. 4명의 엔지니어를 Slack 방에 모아놓고, CockroachDB의 주요 컴포턴트를 처음부터 다시 작성하게 했습니다. 다음으로 정말 흥미로운 부분인 새로운 옵티마이저의 내부동작을 살짝 살펴보겠습니다. 한 글에서 깊게 알아볼 수 없기 때문에 살짝 엿보기만 하겠지만 실망하지 마십시오. 이어지는 글에서는 옵티마이저의 내부동작에 대해 더 깊이 알아보겠습니다. 계속 살펴봐 주십시오.

SQL 옵티마이저란 무엇입니까?

SQL 옵티마이저는 SQL 쿼리를 분석하여 가장 효율적인 실행계획을 선택합니다. 간단한 쿼리는 한가지 실행계획만 가질 수 있지만, 복잡한 쿼리는 수천 수백만 가지의 계획을 세울 수 있습니다. 옵티마이저가 좋을 수록 최적의 실행계획을 선택하는데 더 가까워지며, 이는 쿼리를 실행하는 가장 효율적인 방법입니다.

다음은 매우 단순한 쿼리입니다.

SELECT *
FROM customers c, orders o
WHERE c.id=o.cust_id AND c.name < ’John Doe’

지루하게 옵티마이저의 모든 고려사항을 나열하는 대신 몇 가지 주요사항을 확인해보겠습니다.

  1. name 필터를 언제 해야합니까?(조인 전 또는 후)

  2. 해시조인, 머지조인 또는 인덱스를 이용한 네스티드 루프조인(CockroachDB에서 “lookup join"으로 불리는)을 사용해야 합니까?

  3. 룩업 또는 해시조인을 한다면, customers를 열거한 다음 orders를 룩업해야합니까? 아니면 orders를 열거한 다음 customers를 룩업해야 합니까?

  4. 만약 “name"에 보조 인덱스가 있는 경우 사용해야 합니까? 아니면 기본키인 id를 사용해야 합니까?

또한 옵티마이저가 이런 각각의 질문에 별개로 답하는 것으로는 충분하지 않습니다. 최적의 계획을 찾으려면 답의 조합을 확인해야 합니다. 룩업조인 선택 시는 보조 인덱스를 사용하는 것이 좋을 수 있지만, 머지조인의 경우 기본키 사용이 더 좋을 수 있습니다. 최적의 실행계획은 로우 수, 다양한 물리 연산의 상대적 성능, 데이터의 위치와 밀집도 등의 여러 가지 요소에 따라 달라집니다.

휴리스틱 VS 비용기반

그렇다면 어떻게 옵티마이저가 실행계획을 선택할까요? 많은 사람이 제가 산 세월보다 더 오랜시간 생각하고 글을 써 왔기 때문에 어떤 대답도 충분하지 못합니다. 하지만, 이 문제에 대한 대표적인 두 가지 접근방식을 논의하는 것은 여전히 가치가 있습니다.

첫 번째 방식은 처음으로 옵티마이저를 만드는 사람들이 취하는 방법입니다. 그들은 일반적인 원칙에 기초해 미리 설정된 경험된 규칙을 만듭니다. 예를 들어 같은 조건일 경우 중첩된 루프조인 대신 해시조인을 항상 사용하는 규칙이 있을 수 있습니다. 대부분 상황에서 그것은 더 나은 실행계획이고 좋은 예측입니다. 이와 같은 규칙에 기초한 옵티마이저를 휴리스틱 옵티마이저라고 합니다.

하지만 정적인 휴리스틱에는 단점이 있습니다. 이것은 대부분의 경우 잘 동작하지만, 특정 경우에는 최상의 계획을 찾지 못합니다. 예를 들어 룩업조인은 외부에서 내부 순으로 로우를 검색하여 일치하는 내부 로우를 찾습니다. 이는 외부 로우 수가 적을 때는 잘 작동하지만 그 수가 증가하고 각 로우에 대한 검색 오버헤드가 실행시간에 영향을 미칠 만큼 커지게 되면 성능이 저하되고 어떤 시점이 되면 머지조인이 더 나아집니다. 하지만 이러한 미묘함을 포착하는 휴리스틱을 고안하는 것은 어렵습니다.

비용기반 옵티마이저를 알아봅시다. 비용기반 옵티마이저는 실행 가능한 실행계획을 열거한 후 각 계획을 실행하는 데 필요한 시간과 리소스의 추정치를 할당한 후, 가장 낮은 비용의 계획을 선택하여 실행합니다. 비용 모델은 일반적으로 처리량을 최대화(예: 초당 쿼리 수)하도록 설계되지만 지연시간 최소화(첫 번째 로우 반환 시간) 또는 메모리 사용 최소화와 같은 다른 동작을 선호하도록 설계될 수 있습니다.

이 시점에서 여러분은 이렇게 생각할지도 모릅니다. “만약 그 비용모델이 틀리면 어떻게 하지?” 좋은 질문입니다. 그리고 비용기반 옵티마이저는 비용정확도 만큼만 유효합니다. 또한 비용정확도는 옵티마이저가 작성한 로우 개수 추정치의 정확도에 크게 좌우됩니다. 이는 다음을 의미합니다. 옵티마이저는 쿼리 계획의 각 단계에서 반환되는 로우 수를 추정합니다. 이것은 또 다른 수십 년간의 연구 주제인 데이터베이스 통계로 우리를 이끕니다.

데이터베이스 통계를 수집하는 목적은 옵티마이저에 정보를 제공하여 더 정확하게 로우 수를 추정할 수 있도록 하는 것입니다. 유용한 통계에는 테이블의 로우 수, 컬럼들의 값의 수와 값의 분포를 이해하기 위한 히스토그램이 있습니다. 이 정보는 비용모델로 제공되어 조인 종류, 조인 순서, 인덱스 선택 등의 결정을 돕습니다.

옵티마이저의 (재)탄생

CockroachDB는 시간이 지남에 따라 점점 복잡해지는 간단한 휴리스틱 옵티마이저로 시작했습니다. 2.0 릴리즈에서 우리는 쉽게 피할 수 없는 휴리스틱 디자인의 한계에 부딪히기 시작했습니다. 조심스럽게 조정된 휴리스틱 규칙은 서로 상충되기 시작했으며, 그 사이에서 결정을 내릴 명확한 방법이 없었습니다. 아래와 같은 간단한 휴리스틱 규칙이 있습니다.

“동일 조건일 경우 해시 조인을 사용한다.”

이렇게 변경되었습니다.

“동일 조건일 경우 해시 조인을 사용하지만 모든 조인 키가 정렬될 경우 머지조인을 사용한다.”

마지막에는 이렇게 되었습니다.

“동일 조건일 경우 해시조인을 사용하지만 모든 조인 키가 정렬될 경우 머지조인을 사용한다. 하지만 하나의 조인 입력이 적은 수의 행을 가지고 있고 다른 조인에 사용할 수 있는 인덱스가 있는 경우에는 룩업조인을 사용한다.”

우리가 추가하는 휴리스틱 규칙은 이미 존재하는 규칙과 어울리게 하기 위해 모든 규칙에 대해 조사되어야 했습니다. 비용기반 옵티마이저마저도 때때로 균형 잡혀있는 젠가 타워처럼 동작하지만, 휴리스틱 옵티마이저는 훨씬 낮은 높이에서 넘어졌습니다.

2017년 하반기까지 Cockroach 연구소 내에는 낡아가는 휴리스틱 옵티마이저를 대체하기 위한 모멘텀이 증가하고 있었습니다. 창립자 중 한 명인 피터 매티스는 외부 전문가들과 함께 데이터베이스 최적화에 대한 부트캠프를 운영하여, 개발자들에게 최첨단 옵티마이저가 어떻게 동작하는지 가르치고 위해 그 문제에 관한 주요 논문을 학습했습니다. 토론을 시작하고 모멘텀을 높이기 위해 피터는 opttoy라는 비용기반 옵티마이저 프로토타입을 제작하여 몇 가지 중요한 개념을 입증하고 이후 작업에 대한 정보를 제공했습니다.

2018년 초에 제가 입사했을 때, 회사는 다음 단계를 진행을 위한 의사결정을 했습니다. 이 주제에 대한 저의 배경과 관심을 고려하여, 저는 소규모(하지만 고도로 동기부여된)의 팀을 이끌고 비용기반 옵티마이저를 처음부터 만드는 일을 맡았습니다. 9개월간의 집중적인 노력 끝에 우리 팀은 CockroachDB 2.1 릴리즈의 일부로 옵티마이저의 첫 번째 버전을 출시할 예정입니다. 우리가 할 수 있는(그리고 할) 일은 훨씬 많지만, 이 첫 번째 릴리즈는 앞으로 나아갈 중요한 단계를 나타냅니다. 다음은 2.1 비용기반 옵티마이저에서 지원하는 몇 가지 중요한 새 기능입니다.

  • 상호연관 서브쿼리: 아래 예제처럼 외부 쿼리의 로우를 참조하는 내부 쿼리가 포함된 쿼리입니다.
SELECT *
FROM customers c
WHERE EXISTS (
	SELECT *
	FROM orders o
	WHERE o.cust_id = c.id
)

상호연관 서브쿼리를 최적화에 대한 내용은 이후 다른 글에서 소개하겠습니다.

  • 룩업조인 자동계획: 이제 조인 방법을 결정할 때, 머지와 해시조인에 추가하여 룩업조인을 추가로 고려합니다. 룩업조인은 한 입력에 로우가 적도 다른 입력은 같음 조건에 대한 인덱스가 있는 경우 신속하게 실행됩니다.
SELECT COUNT(*)
FROM customers c, orders o
WHERE c.id=o.cust_id AND c.zip='12345' AND c.name='John Doe'

위에서 옵티마이저는 먼저 zip 코드 “12345”(로우 수가 작은)에 사는 customers를 찾은 후, orders 테이블을 탐색하는 계획을 고려합니다.

내부동작

약속한 대로 옵티마이저의 내부동작을 잠깐 들여다보겠습니다. 먼저 실행계획을 각 노드가 실행계획의 스텝을 나타내는 트리로 생각하는 것이 유용합니다. 실제로 SQL EXPLAIN 문은 실행계획을 보여줍니다.

group                    |             |
 │                       | aggregate 0 | count_rows()
 │                       | scalar      |
 └── render              |             |
      └── filter         |             |
           │             | filter      | ((id = cust_id) AND
           │             |             | (zip = '12345')) AND
           │             |             | (name = 'John Doe')
           └── join      |             |
                │        | type        | cross
                ├── scan |             |
                │        | table       | customers@primary
                │        | spans       | ALL
                └── scan |             |
                         | table       | orders@primary
                         | spans       | ALL

이 출력은 최적화되지 않은 계획이 어떻게 실행되는지 보여줍니다. 먼저 customers와 orders 테이블의 전체 교차 제품을 계산하여 WHERE 조건에 따라 결과 로우를 필터링해 count_rows로 결과를 계산합니다. 이것은 끔찍합니다. 만약 10,000 customers와 100,000 ordes가 있다면, 이 교차는 10억 개의 로우를 생성한 후 대부분을 필터링합니다. 너무 낭비입니다.

여기서 옵티마이저가 그 가치를 입증합니다. 그것은 실행계획을 논리적으로 동등한 계획 트리로 변환한 다음 가장 낮은 값을 가진 트리를 선택합니다. “논리적으로 동등한"의 의미는 무엇일까요? 두 개의 트리가 같은 데이터를 반환하는 경우 논리적으로 같습니다(ORDER BY 절이 없으면 로우의 순서는 다를 수 있음). 즉, 정확성 측면에서 옵티마이저가 어떤 계획을 선택하는지는 중요하지 않습니다. 옵티마이저는 순수히 성능만 극대화합니다.

변환

옵티마이저는 한 번에 전체 계획 트리를 생성하지 않습니다. 대신 초기 트리에서 시작하여 일련의 증분 변환을 수행하여 대체 트리를 생성합니다. 각각의 개별 변환은 비교적 단순하며, 복잡한 최적화 과제를 할 수 있는 많은 변환의 조합입니다. 여러분이 개별적인 변환을 이해한다고 해도, 그것은 종종 예상치 못한 놀라운 계획을 만들어내며, 마법처럼 보일 수 있습니다. 위요 표시된 비교적 간단한 쿼리의 경우에도 옵티마이저는 최종 계획에 도달하기 위해 12번의 변환을 적용합니다. 아래 다이어그램은 4가지 주요 변환 내용을 보여줍니다.

최대 성능을 위해 필터가 조인 안으로 이동하고 스캔의 일부가 되는 것을 볼 수 있습니다. 최종 변환 중 옵티마이저는 보조 인덱스로 룩업조인을 하도록 결정합니다.

현재 비용기반 옵티마이저는 160개가 넘는 다양한 변환을 구현하고 있으며 향후 릴리즈에 더 많은 것을 추가 예정입니다. 변환은 새로운 옵티마이저의 핵심이기 때문에 최대한 쉽게 정의, 이해하고 유지보수 할 수 있도록 많은 시간을 투자했습니다. 이를 위해 변환의 구조를 표현하고 이로부터 Go 코드를 생성하는 도메인 고유 언어(DSL)인 Optgen을 만들었습니다. 다음은 Optgen 언어로 표현된 변환의 예입니다.

[MergeSelectInnerJoin, Normalize]
(Select
	$input:(InnerJoin $left:* $right:* $on:*)
	$filter:*
)
=>
(InnerJoin
	$left
	$right
	(ConcatFilters $on $filter)
)

이 변환은 WHERE절의 조건을 INNER JOIN의 ON과 결합합니다. 이것은 같은 동작을 보장하는 약 25줄의 Go 코드를 생성합니다. 이후 블로그 글에서 Optgen의 세부내용에 대해 더 알아보겠습니다. 기다릴 수 없다면 Optgen 문서나 변환 정의 파일을 살펴보실 수 있습니다. 만약 여러분이 야심적이라면, 우리가 놓치고 있는 새로운 변환을 위해 기여해주십시오. 우리는 언제나 커뮤니티의 기여를 환영합니다.

Memo

옵티마이저거 어떻게 많은 동등한 계획을 생성하고, 그중 하나를 선택하기 위해 예상비용을 사용하는지 설명했습니다. 이론적으로는 좋아 보이는데 실제는 어떨까요? 이 모든 계획을 저장하기 위해 잠재적으로 기하급수적인 메모리가 필요하지 않습니까? 그 대답은 memo라고 불리는 독창적인 데이터 구조입니다.

memo는 계획 전반에 걸쳐 상당한 중복을 사용하여 쿼리에 대한 계획 트리 그룹을 효율적으로 저장합니다. 예를 들어 다른 모든 면에서 동일하고 조인 방법만 해시, 머지, 룩업으로 나늬는 쿼리가 있을 수 있습니다. 또 이 계획은 한 변환에서 기본키를 사용하고 다른 변환에서는 보조 인덱스를 사용하는 등의 여러 가지 변환을 가질 수 있습니다. 그냥 인코딩한다면 기하급수적으로 늘어나는 계획으로 폭발적인 메모리가 사용됩니다.

memo는 memo 그룹이라고 하는 클래스 집합을 정의하여 이 문제를 해결합니다. 여기서 각 그룹은 논리적으로 동등한 표현식을 포함합니다.

계획을 작성하려면 그룹1에서 명령어를 선택한 후 그룹2와 3에서 입력을 선택합니다. 어떤 것을 선택하든 같은 그룹의 명령어는 논리적으로 같습니다. 간단한 산수는 12(3 * 2 * 2)개의 가능한 계획이 memo에 저장됨을 보여줍니다. 이제 6종류의 조인, 복잡한 통계, 다양한 필터 조건이 포함된 쿼리를 상상해보십시오. 계획 수가 수천 개에 달할 수 있지만 memo 구조를 사용한다면 훨씬 적은 공간이 사용됩니다.

물론 옵티마이저는 memo에서 가능한 계획 트리 중 하나를 무작위로 선택하지 않습니다. 대신 각 memo 그룹에서 가장 난은 이용의 명령어를 선택하여 최종계획을 구성합니다. 사실 memo는 댄 브라운의 소설 “천사와 악마"에 나온 일루미나티 다이아몬드 앰비그램을 연상시키는 아름다운 자료구조입니다. 둘 다 가능해 보이는 것보다 더 많은 정보를 가지고 있습니다.

결론

우리 팀은 CockroachDB에 있는 비용기반 옵티마이저 내부동작에 대한 블로그 글을 작성할 계획입니다. 이 글에서는 표면적인 부분만 확인했습니다. 관심 있는 특정 주제를 다루길 원하신다면 저희에게 알려주십시오. 또는 Cockroach 연구소에 들어오셔서 행성 규모의 ACID 데이터베이스를 만드는 것을 도와주시기 바랍니다.