# SQL 엔진의 구조 분석

> Clean Markdown view of GeekNews topic #20588. Use the original source for factual precision when an external source URL is present.

## Metadata

- GeekNews HTML: [https://news.hada.io/topic?id=20588](https://news.hada.io/topic?id=20588)
- GeekNews Markdown: [https://news.hada.io/topic/20588.md](https://news.hada.io/topic/20588.md)
- Type: GN+
- Author: [xguru](https://news.hada.io/@xguru)
- Published: 2025-04-29T10:31:36+09:00
- Updated: 2025-04-29T10:31:36+09:00
- Original source: [dolthub.com](https://www.dolthub.com/blog/2025-04-25-sql-engine-anatomy/)
- Points: 2
- Comments: 0

## Topic Body

- **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 통합**과 **메모리 재사용 최적화**를 통해 **성능 개선**을 계획하고 있음

## Comments



_No public comments on this page._