검색 최적화기의 목표는 효율적인 계산 요청 결과를 찾는 검색 실행 계획입니다.이 논문에서 우리는 규칙에 기반한 최적화, 즉 현대 최적화기가 사용하는 등효 계획을 탐색하는 흔한 모델을 논의할 것이다.그리고 우리는 몇 가지 가장 선진적인 규칙을 바탕으로 하는 최적화기의 실현을 탐구할 것이다.그리고 Apache 방해석,Presto,CockroachDB에서 규칙에 기반한 최적화를 분석했다.

바꾸다

검색 최적화기는 공간 등 효과의 실행 계획을 탐색하고 최선의 실행 계획을 선택해야 한다.직관적으로 말하면 B계획이 모든 가능한 입력에 대해 같은 결과를 낸다면 B계획은 A계획과 같다.
같은 효과가 있는 실행 계획을 만들기 위해서, 우리는 원시 계획에 하나 이상의 전환을 적용할 수 있다.변환은 하나의 계획을 받아들이고 0개, 1개 또는 여러 개의 등효 계획을 생성한다.조회 엔진 개발자로서 당신은 수백 가지의 다른 전환을 실현하여 충분한 수량의 등효 계획을 생성할 수 있습니다.
어떤 변화는 계획의 대부분, 심지어 전체 계획에 영향을 줄 수 있다.예를 들어 동적 계획을 사용하여 연결 순서 선택을 실현하면 계획의 모든 연결을 열거하고 대체 연결 서열을 생성하며 가장 좋은 연결 서열을 선택할 수 있다.

다른 전환은 상대적으로 고립될 수 있다.필터 조작부호를 집합 조작부호의 변환을 미루는 것을 고려합니다.그것은 나무의 고립된 부분에서 일하기 때문에 전체적인 상하문이 필요하지 않다.

규칙.

모든 최적화기는 일부 알고리즘을 따르는데 이런 알고리즘은 언제 특정한 전환을 응용할 것인지, 그리고 새로 만든 등효 계획을 어떻게 처리할 것인지를 결정한다.변환 수량이 증가함에 따라 그것들을 단일 프로세스에 저장하는 것은 불편해졌다.상상해 보아라, 큰 크기의if-else 코드가 몇 십 개의 관계 연산자에 어떻게 백 개의 변환을 적용할 것인가를 결정한다.
엔진의 발전을 촉진하기 위해서, 당신은 공공 인터페이스 뒤에서 약간의 전환을 추상화하기를 원할 수도 있습니다.모든 변환에 대해 사용자는 하나의 모델을 정의할 수 있습니다. 이 모델은 우리가 변환을 계획의 주어진 부분에 적용할 수 있는지 여부를 정의할 수 있습니다.패턴과 변환의 대칭은 규칙이다.
규칙 추상은 최적화 논리를 서로 독립적으로 발전할 수 있는 삽입 가능한 부분으로 나누어 최적화기의 개발을 크게 간소화할 수 있습니다.규칙을 사용하여 등효 계획을 생성하는 최적화기를 규칙을 바탕으로 하는 최적화기라고 한다.

규칙은 우선 하나의 모델로 최적화기의 코드 라이브러리를 분해하는 데 도움을 줄 수 있음을 주의하십시오.규칙의 사용은 화산/급 연결 같은 특정한 최적화 프로그램을 따르도록 강요하지 않는다.그것은 매거진을 연결하는 동적 계획 같은 특정한 최적화 기술을 사용하는 것을 막지 못할 것이다.그것은 네가 계발식이나 원가에 기초한 방법 사이에서 선택할 필요가 없다.그러나 규칙의 고립성은 엔진의 일부 부분, 예를 들어 가입 계획을 복잡하게 할 수 있다.

예.

이제 규칙 기반의 최적화 배후의 생각을 이해할 때 Apache Calcite,Presto,CockroachDB 등 몇 가지 실제 세계의 예를 살펴보자.

아파치 방해석

Apache Calcite는 동적 데이터 관리 프레임워크이다.Apache Calcite의 핵심은 두 개의 규칙 기반 최적화기와 하나의 변환 규칙 라이브러리입니다.
HepPlanner는 변환이 불가능할 때까지 규칙을 하나하나 적용하는 계발식 최적화기이다.
VolcanoPlanner는 원가 기반의 최적화기로서 여러 개의 등효 계획을 생성하여 비망록 데이터 구조에 넣고 원가를 사용하여 최상의 계획을 선택할 수 있다.VolcanoPlanner는 임의의 순서로 규칙을 촉발할 수도 있고 최근에 도입된 등급 연결 방식, 예를 들어 top-down 스타일을 사용할 수도 있다.
rule interface 이 모델을 받아들이고 onMatch(context) 방법을 요구합니다.이런 방법은 사람들이 기대하는 것처럼 새로운 관계 트리로 돌아가지 않는다.반대로, 이것은 void 되돌아오지만, 상하문에 새로운 변환을 등록할 수 있는 능력을 제공합니다. 이것은 한 규칙에서 여러 개의 등효 트리를 호출할 수 있도록 합니다.Apache Calcite는 사용자 고유의 규칙을 추가할 수 있는 다양한 기본 규칙을 제공합니다.

class CustomRule extends RelOptRule {
    new CustomRule() {
        super(pattern_for_the_rule);
    }

    void onMatch(RelOptRuleCall call) {
        RelNode equivalentNode = ...;

        // Register the new equivalent node in MEMO
        call.transformTo(equivalentNode);
    }
}

Apache Calcite에서 하나 이상의 최적화 단계를 정의할 수 있습니다.각 단계마다 자신의 규칙과 최적화기를 사용할 수 있다.많은 아파치 방해석을 기반으로 한 제품들은 여러 단계를 사용하여 최적화 시간을 최소화하는데 그 대가로 가장 좋은 계획이 생길 수 있다.ApacheCalcite를 사용하여 쿼리 최적화기를 만드는 방법에 대한 자세한 정보는 이전 library 을 참고하십시오.
계획에 가입하는 몇 가지 규칙을 살펴봅시다.모든 정글 연결 나무를 탐색하려면 blog post와JoinCommuteRule를 사용할 수 있다.이 규칙들은 상대적으로 간단하여 단일 연결에 적용된다.문제는 이들이 본문JoinAssociateRule에서 말한 바와 같이 중복된 파생을 촉발할 수 있다는 것이다.
paper
또는 Apache Calcite는 하나의 규칙을 사용하여 여러 연결을 단일 연결으로 변환한 다음 계발식 알고리즘을 적용하여 n번 연결에서 단일 최적화 연결 순서를 생성할 수 있습니다.이것은 이 규칙의 예로서, 하나의 조작부호가 아니라 나무의 대부분에 적용된다.당신은 유사한 방법으로 규칙을 실현하고 동적 계획으로 연결 계획을 진행할 수 있습니다.
n-way join
아파치 방해석의 예는 규칙 기반 최적화는 계발식과 비용 기반 탐사 전략에 사용될 수도 있고 복잡한 연결 계획에 사용될 수도 있음을 나타낸다.

급박히

는 빅데이터에 사용되는 분포식 조회 엔진이다.Apache Calcite와 마찬가지로 규칙을 사용하여 변환을 수행합니다.그러나 Presto는 비용 기반 검색 알고리즘이 없고 최적화 절차 사이의 전환은 계발식에 의존한다.Presto 쿼리 최적화기에 대한 자세한 내용은 DellPresto을 참조하십시오.
Presto는 여러 개의 등가 계획을 동시에 탐색할 수 없기 때문에 더욱 간단한 previous blog를 가지고 새로운 등가 트리만 생성한다.

interface Rule {
    Pattern getPattern();
    Result apply(T node, ...);
}

Presto는 내부 사용 비용으로 규칙 호출 범위 내의 여러 예비 방안을 탐색하는 몇 가지 규칙이 있다.하나의 예는 최근에 도입된 rule interface 규칙이다.상기 Apache Calcite의 n-way 연결 규칙과 유사하며, ReorderJoins 규칙은 먼저 연결 서열을 단일 n-way 연결로 전환한다.그 다음에 이 규칙은 등가의 연결 순서를 매거하고 비용이 가장 낮은 것을 선택한다. (Apache Calcite ReorderJoins 는 계발식을 사용하지 않는다.ReorderJoins 규칙은 우리가 규칙을 바탕으로 하는 최적화를 같은 최적화기에서 계발식과 원가를 바탕으로 하는 검색 전략을 어떻게 사용하는지 보여주기 때문에 매우 재미있다.

LoptopTimerJoinRule 바퀴벌레

CockroachDB는 현대 클라우드 애플리케이션에 사용되는 클라우드 네이티브 SQL 데이터베이스입니다.그것은 규칙에 기반한 등급별 조회 를 가지고 있다.
코크로치는 아파치 방해석이나 프레스토와 달리 일반적인 규칙 인터페이스가 없다.대신 사용자 정의 DSL을 사용하여 규칙의 패턴과 변환 논리를 정의합니다.코드optimizer는 DSL 파일을 분석하고 단일 슬라이스 최적화 루틴을 생성합니다.코드 생성은 규칙을 호출할 때 가상 호출을 피하기 때문에 더 빠른 최적화기 코드를 허용합니다.
다음은 유중합을 생성하려는 규칙 정의generator입니다.DSL만 사용하여 전체 규칙 논리를 작성할 필요는 없습니다.대신 Go(CockroachDB 주요 언어)로 작성된 유틸리티 방법을 규칙에 참조하여 DSL에 지정된 코드 양을 최소화할 수 있습니다.

[GenerateStreamingGroupBy, Explore]
(GroupBy | DistinctOn | EnsureDistinctOn | UpsertDistinctOn
        | EnsureUpsertDistinctOn
    $input:*
    $aggs:*
    $private:* & (IsCanonicalGroupBy $private)
)
=>
(GenerateStreamingGroupBy (OpName) $input $aggs $private)

CockroachDB에는 두 가지 규칙 유형이 있습니다.비망록을 삽입하기 전에example 관계 연산자를 규범적인 형식으로 바꾸어 후속 최적화를 간소화했다.예를 들어 normalization rules 규칙은 AND 표현식을 왼쪽 깊은 나무로 규범화한다.규범화 규칙을 순서대로 호출하여 규범화를 집행하다.두 번째 유형은 NormalizeNestedAnds 규칙으로 여러 개의 등가 계획을 생성한다.탐색 규칙은 원가를 바탕으로 하는 등급별 호출을 사용하는데 예를 들어 기억이 있는 위에서 아래로 최적화 전략을 사용한다.
CockroachDB는 가입 계획을 진행하는 exploration 규칙을 가지고 있다.이 규칙은 본고ReorderJoins에서 기술한 동적 기획 알고리즘의 변체를 사용하여 효과적인 연결 순서를 매거하고 이를 비망록에 추가한다.
따라서 CockroachDB는 규칙 기반 최적화를 사용하여 계발식 규범화, 원가 기반 탐색을 하고 기획과 동적 기획을 결합시킨다.

종이. 요약

규칙을 바탕으로 하는 조회 최적화는 매우 유연한 모델로 조회 최적화기를 설계할 때 사용할 수 있다.복잡한 변환 논리를 자체 포함된 부분으로 나누어 최적화기의 복잡성을 낮출 수 있습니다.
규칙을 바탕으로 하는 최적화는 당신이 계획을 어떻게 정확하게 최적화하는지를 제한하지 않는다. 아래에서 위로 하는 동적 계획이든, 위에서 아래로 하는 등급별 탐색이든, 원가를 바탕으로 하는 최적화든, 계발식 최적화든, 또는 기타 무엇이든지.
앞으로의 글에서 우리는 논리적 최적화와 물리적 최적화 간의 차이를 토론할 것이다.기대해주세요!