▲

SQL 엔진의 구조 분석

 (dolthub.com)
1P by GN⁺ 17시간전 | ★ favorite | 댓글과 토론
  • SQL 엔진은 데이터베이스의 논리적 계층으로, 클라이언트와 저장소 사이에서 작동함
  • SQL 엔진의 주요 과정인 파싱, 바인딩, 플랜 단순화, 조인 탐색 및 비용 평가, 실행, 결과 스풀링에 대한 상세 설명
    • 파싱은 SQL 쿼리를 구조화된 추상 구문 트리(AST)로 변환
    • 바인딩은 AST의 필드를 현재 데이터베이스 카탈로그의 심볼과 매칭
    • 플랜 단순화는 SQL의 복잡한 구문을 단순화된 형식으로 정규화하여 실행 속도를 높임
    • 계획 탐색은 조인, 집계, 윈도우 함수의 다양한 변형을 탐색하여 최적의 실행 계획을 찾음
    • 실행 및 결과 스풀링은 최종 계획을 실행 가능한 형식으로 변환하고 결과를 클라이언트에 반환

SQL 엔진 개요

  • SQL 엔진은 클라이언트 요청과 데이터 저장소 사이의 논리적 중개 계층임
  • 주요 단계
    • Parsing: 쿼리를 AST(추상 구문 트리)로 변환함
    • Binding: AST의 식별자를 데이터베이스 카탈로그의 심볼과 연결함
    • Plan Simplification: 다양한 SQL 문법을 표준화된 플랜 형태로 단순화함
    • Join Exploration & Costing: 다양한 조인 순서를 탐색하고 비용을 평가함
    • Execution: 최적의 실행 플랜을 사용하여 쿼리를 수행함
    • Spooling Results: 결과를 클라이언트로 반환함

파싱(Parsing)

  • 파싱은 입력된 쿼리를 토큰화하고 AST로 변환하는 과정임
  • 우측 재귀 파서는 이해와 디버깅이 쉬운 반면, 스택 메모리를 많이 사용함
  • 좌측 재귀 파서(Yacc 기반)는 메모리 효율적이지만 복잡한 로직이 필요함
  • Dolt는 좌측 재귀 파서를 사용하여 빠른 파싱을 지원함
  • 파싱이 성공하면 AST 구조가 Yacc 규칙과 일치함

바인딩(Binding)

  • 바인딩은 AST의 필드를 데이터베이스의 실제 테이블, 컬럼 심볼에 연결하는 과정임
  • 주요 개념
    • 테이블 정의: 데이터의 소스 역할
    • 컬럼 정의: 테이블 소스에서 특정 컬럼을 참조
    • 별칭(Alias): 스칼라 값을 소스로도, 싱크로도 사용
    • 스칼라 서브쿼리: 부모 스코프를 공유하며 이름 바인딩을 수행
  • 바인딩 결과로 sql.Node 형식의 실행 플랜 노드를 생성함

플랜 단순화(Plan Simplifications)

  • 다양한 SQL 표현을 정규화된 형태로 변환하여 실행 최적화를 돕는 과정임
  • 대표적인 최적화
    • 필터 푸시다운(Filter Pushdown): 불필요한 로우 제거
    • 컬럼 프루닝(Column Pruning): 필요 없는 컬럼 제거
  • 서브쿼리 디코릴레이션(subquery decorrelation) 같은 변환을 통해 조인 플랜 최적화도 수행함

타입 강제 변환(Type Coercion)

  • 타입 강제 변환은 문맥에 따라 표현식 타입을 자동 변환하는 과정임
  • WHERE, INSERT 등 문맥에 따라 타입이 달라질 수 있음
  • Dolt는 타입 변환을 바인딩 단계에서 점진적으로 처리하고 있음

조인 탐색(Plan Exploration)

  • 조인 탐색은 다양한 조인 순서를 생성하고 검토하는 과정임
  • 두 가지 탐색 전략
    • 탑다운 백트래킹: 유효한 조인 순서만 탐색
    • 바텀업 동적 프로그래밍(DP): 모든 조합을 시도하여 최적 조인 순서를 찾음
  • 메모(Memo) 구조를 사용하여 중간 상태를 효율적으로 관리함

기능적 종속성(Functional Dependencies)

  • 5개 이상의 테이블 조인 시 비용이 급증할 수 있음
  • 기본 키(PK) 기반 조인처럼 "1:1 관계"를 활용하면 탐색 비용을 절감할 수 있음
  • LOOKUP_JOIN을 우선 고려하여 최적화함

중간 표현 요약(IR Intermission)

  • 지금까지 진행한 3단계 IR 요약
    • AST: 토큰 정리
    • 스코프 바인딩: 컬럼 참조 검증
    • 메모: 조인 탐색 및 비용 평가를 위한 표현

조인 비용 평가(Join Costing)

  • 조인 비용 평가는 모든 가능한 플랜에 대해 실행 비용을 추정하는 과정임
  • 비용 요소
    • 입력 테이블 크기
    • 결과 테이블 크기
    • 조인 연산자의 종류 (LOOKUP_JOIN, HASH_JOIN 등)
  • Dolt는 정확한 테이블 통계(histogram)를 기반으로 비용을 평가함

조인 힌트(Join Hints)

  • 사용자가 제시한 힌트에 따라 조인 전략을 우선 적용하려 시도함
  • 모순되거나 부적절한 힌트는 무시됨

실행(Execution)

  • 최적 플랜을 실제 실행 가능한 이테레이터(Volcano Iterator) 구조로 변환함
  • 특징
    • 비물질화(non-materializing) 이터레이터: 즉시 로우 반환
    • 물질화(materializing) 이터레이터: 모든 로우 수집 후 반환
  • 컬럼 참조는 실행 전에 인덱스 오프셋 기반으로 매핑됨

I/O 및 결과 스풀링(IO/Spooling)

  • 실행 결과를 MySQL 프로토콜 포맷으로 변환하여 클라이언트에 전달함
  • 키-값(KV) 저장소 레이어에서 바로 결과를 읽어 최적화하는 경우도 있음
  • 일괄처리(batch) 및 버퍼 재사용을 통해 처리 속도와 메모리 효율을 개선함

향후 계획(Future)

  • Dolt는 기본적으로 로컬 서버에서 행 기반 실행(row-based execution) 을 사용하고 있음
  • AST, 스코프 기반 바인딩, 메모 구조를 통한 조인 탐색 등의 3단계 중간 표현(IR) 을 활용하여 최적의 실행 계획 수립을 지원함
  • 조인 순서 탐색(Join Search) 과 조인 비용 평가(Join Costing) 를 통해 최적의 조인 전략을 결정함
  • 향후에는 IR 통합과 메모리 재사용 최적화를 통해 성능 개선을 계획하고 있음