16. Query Optimization Part 1 - Rule-based (Bigdata and Knowledge Management Systems 1, SNU GSDS)

서울대학교 데이터사이언스대학원 정형수 교수님의 "데이터사이언스 응용을 위한 빅데이터 및 지식 관리 시스템" 강의를 필기한 내용입니다.

• 목차

Query Optimizer Overview §

• SQL 은 relational calculus 에 기반하고 있는데, 이것은 declarative 하고 “어떤 순서로” 이것을 처리할 지에 대해서는 명시하지 않는다.
  • 따라서 이런 relational calculus 에 “어떤 순서로” 처리할지를 결정해야 하고, 이것을 통해 생성된 relational algebra 에 기반한 결과물이 query plan 이다.
• 어떤 plan 을 사용하냐에 따라 음청나게 성능이 달라질 수 있고, 따라서 좋은 plan 을 정하는 것이 중허다 이거야.
• 이렇게 query plan 을 짜주는 component 를 Query Optimizer 라고 한다.
  • 참고로 첫 query optimizer 는 셀린저 optimizer (IBM system R) 라고 한다.
• 크게 (1) heuristic, rule-based (2) cost-based search 두 가지 방법을 사용한다.

Architecture §

• 위 그림이 SQL 이 입력되었을 때부터 실행의 모든 부분이 명세된 Physical Plan 이 나오기까지의 과정을 나타낸 그림이다.
• 일단 Logical Plan 은 logical 한, relational algebra expression 이다.
• 그리고 이것과 동등하지만 더 빠르고, 각 operator 마다 어떻게 data 에 접근해야 하는지에 대한 access strategy 까지 전부 명세되어 있는 relational algebra expression 이 Physical Plan 인 것.
• 그래서 간단하게 살펴보면
  1. SQL Query 는 SQL Rewriter 에 의해 parsing 전에 조금 변형되는 것이 가능하다. 하지만 흔한 일은 아닌 것.
  2. Rewrite 된 SQL 은 Parser 에 의해 AST 로 바뀌고, Binder 에 의해 table name 등의 “이름” 에서 system catalog 에 명시된 ID 로 변환되어 Logical Plan 으로 바뀐다.
  3. 그 다음에 Tree Rewriter 가 이 Logical Plan 을 보고 plan tree 를 좀 변형하게 된다. 이것은 보통 수행된다.
  4. 마지막으로 rewrite 된 Logical Plan 는 Optimizer 에 의해 system catalog 및 cost model 을 고려해 Physical Plan 으로 바뀌게 된다.
  • 참고로 system catalog 를 보는 것은 schema check 의 용도도 있지만, statistics 를 위해서도 있다.

• SQL 부터 relational algebra, logical plan, physical plan 까지의 변환 과정 예시이다. 한번 보고 넘어가자.

N-P Hard §

• Join table 이 15개 정도 이전까지는 dynamic programming 으로 cost model 을 다 돌려 가장 최적의 plan 을 찾지만
• 이후부터는 optimize 자체가 너무 오래걸리기 때문에 적정선에서 optimize 를 멈춘다.
  • 즉, estimation 을 하는셈
• 이것은 query optimization 이 N-P hard problem 이기 때문이다. 즉, problem size 가 커질수록 정답을 찾는 cost 가 기하급수적으로 커져서 정답을 찾을 수 없다는 것임.

Relational Algebra §

• Relational calculus 은 set-based notation 으로 조건에 맞는 set 을 정의하는 것을 의미한다.
  • 즉, 이것은 declarative 한 표현 방법이다.
• Relation algebra: 그 set 을 구하기 위한 계산 순서로, operational 한 표현방법이다.
• SQL 을 단순히 relational algebra 로 바꾸어서 AST 로 만들면 그게 logical plan 가 되고
• 그것을 최적화해서 실제 수행할 연산 및 취할 전략같은 것들이 모두 명시된 상태가 physical plan 이 되는 것.
• SQL 은 relational calculus 에 기반을 두기 때문에, 이것만으로는 어떻게 수행할지 알 수 없어 algebra (plan) 으로 바꾼다.
• 근데 이걸 막 바꿔도 되나? -> (Relational algebra 의 창시자인) Codd’s theorem 에 따르면 calculus 와 algebra 가 1:1 로 대응되고 이때 성능상의 차이는 없다고 한다.

Property §

• Relational algebra 는 다음과 같은 특징을 가진다:
  • Closed property: Relational algebra 의 연산은 항상 input 과 output 이 모두 relational schema 이다.
    • 따라서, relational algebra 의 연산 결과를 또 다른 relational algebra 에 피연산자로 넣는 것이 가능하다 이말이야.
  • Typed property: 각 값들은 “자료형 (type)” 을 가지는데, 이때의 자료형은 Attribute 를 말한다.
    • 연산에 자료형이 있다는 것은 예를 들어 column $A$ 로 projection 하고 싶으면 input, output 에 모두 column $A$ 가 있어야 한다는 소리이다.
• 그리고 relational algebra 엄밀하게는 set-based 이고, SQL 는 bag (순서 없는 중복 허용 자료구조) 이라고 한다.

Operators §

Unary §

• Projection ($\pi$): SELECT …
  • 원하는 column 을 고르는 것 (전체 schema 에서 원하는 column 을 vertical 로 filtering).
  • Output schema 는 input schema 와 다를 수 있다 (schema change).
  • 실제 DBMS 에서는 그렇지 않지만, Relational algebra 에서의 projection 은 중복 제거 때문에 row 의 개수가 줄어들 수 있다.
• Selection ($\sigma$): WHERE predicate
  • 조건에 따라 원하는 tuple 을 고르는 것 (즉, horizontal filtering).
  • Select 는 schema change 가 일어나지 않는다.
  • 알다시피 predicate 는 우선 실행하는게 유리하다 (Predicate pushdown): 먼저 filtering 하는 것이 당연히 데이터 사이즈를 줄여놓고 시작하기 때문.
    • 여기에 깔린 생각은 output 이 동일하다면 빨리 실행되는 것이 와따라는 것이다.
    • 어차피 언젠가는 filtering 한다면 이것을 먼저 수행해버려 빨리 실행될 수 있게 하는 것.
• Rename ($\rho$): Column name 바꾸는 것 (즉, aliasing).
  • 여러 table 에 같은 이름의 column 이 있을 수 있기 때문에 이런 rename operation 이 존재한다.
  • 물론 내부적 (system catalog) 에서는 고유한 ID 가 있긴 하다.
  • Self-join, relationship table 에서 모호성이 발생할 수 있기 때문에 이런 operation 이 있는 것.
  • ${\rho }_{columnNo.\to alias}(R)$ 으로 명시된다: 즉, 예를들어 ${\rho }_{column1\to studentName}(R)$ 등.

Binary §

• Union ($\cup$): 뭐 너가 아는 합집합.
  • 인데, 좀 다른점은 relational algebra 는 typed 라는 것이다. 즉, 두 피연산자는 동일한 schema 를 가져야 한다.
  • 그리고 SQL 에서는 중복제거를 하지 않는 UNION ALL 이 있다.
• Set-difference ($-$): 이것도 너가 아는 차집합.
• Cross-product ($\times$): 너가 아는 cartesian product.

Compound §

• Compound operator 는 복잡한 expression 에 대한 “macro” 라고 생각하면 된다.
• Intersect ($\cap$): 너가 아는 교집합.
  • $A\cap B=A-(A-B)$ 이기 때문.
• Join ($\bowtie$): 너가 아는 join.
  • 이건 Theta join 이라고도 한다.
    • Join 은 cartesian product 이후 theta 로 selection 하는 것이기 때문 (${\sigma }_{\theta }(A\times B)$).
    • 따라서 보통 ($\bowtie$) 이 join 기호지만, (${\bowtie }_{\theta }$) 라고 적기도 한다.
  • Natural join: 같은 이름의 column 으로 join 을 한 다음 두 column 이 중복되어 output 에 들어가기 때문에 이것을 projection 하는 것을 의미한다.
    • 즉, ${\pi }_{uniq.co{l}_A}({\sigma }_{eq.co{l}_A}(A\times B))$.
  • Join 을 Condition Propagation 라고 부르기도 한다. 왜냐면 Dimension table 에 predicate 를 걸고 Fact table 에 projection 해서 query 하는 경우가 많고, 이때 저 dimension 에 걸린 predicate 이 fact 로 “전파” 되는 것이기 때문.

Relational Algebra Equivalences §

• 두 relational algebra expression 은 “동일한 set” 을 결과로 가질 때 그 둘이 Equivalent 하다고 한다.
• 이 점을 이용하여 cost model 을 돌리지 않고 어느정도 query plan 을 변경할 수 있고, 이것을 Query rewriting 이라고 한다.
• 사례? 를 몇가지 알아보자면

• 위에서 말한 predicate pushdown 이나 (위 그림)
• ${\sigma }_{p1\wedge p2}(A)\to {\sigma }_{p1}({\sigma }_{p2}(A))$ 처럼 selection 을 break 해서 더 간단한 것으로 바꾸거나
• Join 이 교환법칙 (commutative) 을 만족한다는 것을 이용해 IO 가 덜 발생하도록 순서를 바꾸는 등

• 또한 projection pushdown 도 있다 (위 그림): 사용하지 않는 attribute 들을 일찍 배제해버려 early materialization 에 비해 적은 양의 intermediate data 를 차지하도록 하는 것.

Heuristic, Rule-based Logical Query Optimization §

• Logical Query Optimization 은:
  • 일단 logical query 를 동등한 다른 logical query 로 바꾸는 것이고
  • 추후에 이어질 cost search 에서 optimal plan 을 찾기 쉽게 해주는 것이 목표이며
  • 다른 plan 과 비교는 하지 않고, pattern (heuristic, rule) 이 맞다면 그냥 바꿔버리는 형식이다.
• 가장 기본적인 아이디어는 predicate pushdown 이다: 즉, early pruning.
  • 그래서 predicate 을 type 이 맞는 한 최대한 내려버리게된다.
  • 이때 얼마나 털어내느냐를 Reduction Factor (RF) 라고 한다.
• 여기 나오는 기법들은 위에서도 언급한 내용들이다. 정식 명칭들과 함께 살펴보자.
• 이런 작업은 tree rewriter 에서 수행한다.
  • 즉, equivalent logical plan 으로 다 바꾸는 것.

Split Conjunctive Predicate §

• 말 그대로 연결되어 있는 (Conjunctive) Predicate 들을 분리 (Split) 하는 방법이다.
• 즉, 이 상태에서

• 이렇게 바꾸는 것.

• 이것의 목적은 당연히 이렇게 나눠서 predicate pushdown 을 하려는 것이다.

Predicate Pushdown §

• 위에서도 말한것처럼, predicate 을 일찍 적용해 early pruning 을 하는 것이다.
• 즉, 그림으로 보자면 아래와 같은 plan tree 가

• 이렇게 바뀌는 것.

Replace Cartesian Product §

• 당연히 Cartesian Product 후 predicate 을 적용하는 것은 inner join 과 동일하다. 따라서 이렇게 cartesian product 를 교체해주는 것이 Replace Cartesian Product 이다.
• 가령 아래와 같은 plan tree 는

• 이렇게 바뀌게 된다.

Projection Pushdown §

• 필요 없는 attribute 는 일찍 털어내서 intermediate data size 를 줄이는 것이 목적이다.
• 다만, intermediate operation 에서도 필요한 field 까지 projection 해주긴 해야 한다는 점에 주의하자.
• 가령 아래 plan tree 는

• ARTIST 에서는 ID 와 NAME 만, APPEARS 에서는 ARTIST_ID 와 ALBUM_ID 만, ALBUM 에서는 ID 만 필요하니까 얘네들만 남기고 전부 projection 을 걸어주면 아래처럼 된다:

Nested Subqueries §

• SQL 에서는 하나의 값만을 뱉는 query 를 WHERE clause 에서 마치 함수처럼 사용할 수 있다.
• 근데 이놈을 처리하지 않으면 문제가 된다. Volcano 에서 이 WHERE 을 통과할 때마다 nested query 를 실행하기 때문.
• 그럼 이때 이놈을 바꿔보자.
  • 이 nested subquery 를 바꾸는 작업은 SQL Rewriter 가 수행한다고 한다.

Rewriting §

• 위 그림과 같은 방식으로 결과는 같지만 nesting 을 빼도록 새로 작성 (rewrite) 하기도 한다.
  • 뭐 규칙이 있겠지만 자세히 다루지는 않는다; 이런게 있구나 정도로만 생각하자.

Decomposing §

• Nested query 가 복잡해질수록 rewrite 로는 힘들때가 많다. 따라서 그냥 nested query 를 temporary table (query 실행이 끝나면 삭제되는) 으로 바꾼 다음 처리하고, 이것을 Decomposing 이라고 한다.
• 즉, 아래와 같은 놈을

• 요래바꾼다.

Expression Rewriting §

• 뭐 WHERE 절에 있는 expression 을 더 optimal, minimal 한 expression 으로 바꾸는 작업도 한다.
• 이것에 관해서는 자세히 알아보지 않고 지나간다.