플래너/옵티마이저

플래너/옵티마이저 (Planner/Optimizer)

같은 SQL 질의라도 실제로 실행될 수 있는 방법은 엄청나게 많아요. 그리고 그 방법들은 전부 같은 결과 집합을 만들어내죠. 플래너/옵티마이저(planner/optimizer) 가 하는 일은 이 가능한 실행 계획들 중에서 가장 빠르게 실행될 것으로 예상되는 계획을 골라내는 거예요. 이번에는 플래너가 어떤 후보들을 만들고, 어떤 전략으로 조인을 처리하며, 어떤 기준으로 최선의 계획을 고르는지 따라가 볼게요.

출처: PostgreSQL 공식 문서 — 51.5. Planner/Optimizer

모든 계획을 일일이 검사하지는 않는다

계산이 가능하다면 옵티마이저는 각 실행 계획을 검토한 뒤 가장 빠를 것으로 예상되는 계획을 골라요. 하지만 어떤 경우엔 가능한 모든 실행 방법을 검토하는 것 자체가 지나치게 많은 시간과 메모리를 요구해요. 특히 조인 연산이 아주 많은 질의에서 그렇죠. 그래서 조인 수가 임계값을 넘으면(초과 기준은 geqo_threshold), PostgreSQL은 합리적인(꼭 최적은 아닐 수 있는) 계획을 합리적인 시간 안에 찾기 위해 유전적 질의 옵티마이저(Genetic Query Optimizer) 를 사용해요.

플래너의 탐색 과정은 사실 path 라고 부르는 데이터 구조로 동작해요. path는 결정을 내리는 데 필요한 정보만 담은 계획의 축소판이에요. 가장 저렴한 path가 정해지면, 실행기에 넘겨줄 완전한 plan tree를 만드는데, 실행기가 돌리기에 충분한 상세도를 갖춘 실행 계획이에요. (여기서 path와 plan의 구분은 편의상 무시하고 넘어갈게요.)

가능한 계획 만들기

플래너/옵티마이저는 질의에 쓰인 각 테이블(관계)을 스캔하는 계획을 만드는 것부터 시작해요. 가능한 계획은 각 관계에 정의된 인덱스에 따라 결정돼요. 관계를 순차 스캔(sequential scan) 하는 가능성은 항상 있으므로 순차 스캔 계획은 항상 만들어져요. 관계에 인덱스(예: B-tree)가 정의돼 있고 질의가 relation.attribute OPR constant 같은 제약을 담고 있다면, relation.attribute가 B-tree 인덱스의 키와 일치하고 OPR이 인덱스의 연산자 클래스(operator class) 에 나열된 연산자 중 하나일 때 B-tree 인덱스로 관계를 스캔하는 또 다른 계획이 만들어져요. 추가 인덱스가 있고 질의 제약이 인덱스 키와 일치한다면 더 많은 계획이 고려돼요. 질의의 ORDER BY 절과 맞는 정렬 순서를 가지거나(있다면) 병합 조인에 쓰일 수 있는 정렬 순서를 가진 인덱스도 인덱스 스캔 계획이 생성돼요.

세 가지 조인 전략

질의가 두 개 이상의 관계를 조인해야 한다면, 단일 관계 스캔의 모든 실현 가능한 계획을 찾은 뒤 조인 계획을 고려해요. 사용 가능한 조인 전략은 세 가지예요.

  • nested loop join(중첩 루프 조인) — 왼쪽 관계에서 찾은 각 행마다 오른쪽 관계를 스캔해요. 구현이 쉽지만 매우 시간이 걸릴 수 있어요. 다만 오른쪽 관계를 인덱스 스캔으로 훑을 수 있으면 좋은 전략이 될 수 있어요. 왼쪽 관계의 현재 행 값을 오른쪽 인덱스 스캔의 키로 쓸 수 있거든요.
  • merge join(병합 조인) — 조인이 시작되기 전에 각 관계를 조인 속성 기준으로 정렬해요. 그런 다음 두 관계를 병렬로 스캔하며 일치하는 행을 합쳐 조인 행을 만들어요. 각 관계를 한 번만 스캔하면 된다는 게 매력이에요. 필요한 정렬은 명시적 정렬 단계로 하거나, 조인 키의 인덱스를 이용해 적절한 순서로 관계를 스캔해서 이룰 수 있어요.
  • hash join(해시 조인) — 먼저 오른쪽 관계를 스캔해 조인 속성을 해시 키로 써서 해시 테이블에 넣어요. 그다음 왼쪽 관계를 스캔하고, 만나는 각 행의 적절한 값을 해시 키로 써서 테이블에서 일치하는 행을 찾아요.

질의가 두 개 이상의 관계를 다루면 최종 결과는 각 단계에 입력이 두 개씩인 조인 단계 트리로 구성돼요. 플래너는 여러 가능한 조인 순서를 검토해 가장 저렴한 것을 찾아요.

질의가 쓰는 관계 수가 geqo_threshold보다 적으면 최선의 조인 순서를 찾기 위해 거의 완전 탐색에 가까운 조사를 해요. 플래너는 WHERE 조건에 해당하는 조인 절(예: where rel1.attr1=rel2.attr2 같은 제약)이 존재하는 임의의 두 관계 사이의 조인을 우선 고려해요. 조인 절이 없는 조인 쌍은 다른 선택지가 없을 때만 고려돼요. 플래너가 고려하는 각 조인 쌍에 대해 모든 가능한 계획이 생성되고, (추정상) 가장 저렴한 것이 선택돼요. geqo_threshold를 넘으면 고려되는 조인 순서는 휴리스틱에 의해 결정돼요.

완성된 계획 트리

완성된 계획 트리는 기본 관계의 순차 또는 인덱스 스캔에, 필요에 따라 nested loop·merge·hash 조인 노드, 그리고 정렬 노드나 집계 함수 계산 노드 같은 보조 단계로 구성돼요. 대부분의 계획 노드 유형은 추가로 선택(selection) — 지정된 불리언 조건을 만족하지 않는 행을 버리는 것 — 과 투영(projection) — 주어진 열 값에 기반한 파생 열 집합 계산, 즉 필요할 때 스칼라 표현식을 평가하는 것 — 을 할 수 있어요. 플래너의 책임 중 하나는 WHERE 절의 선택 조건과 필요한 출력 표현식의 계산을 계획 트리의 가장 적절한 노드에 붙이는 거예요.

더 알아보기