- SQLite는 디스크에 B-트리 구조로 저장되는 행 기반 저장소로, VDBE라는 가상 머신을 사용하여 쿼리를 실행함. 플랫폼에 구애받지 않고 단일 스레드로 거의 모든 환경에서 실행 가능함
- 일반적인 용도의 데이터베이스이지만 OLTP 작업에 뛰어남. 2015년 버팔로 대학 연구진은 대부분의 쿼리가 간단한 키-값 조회와 복잡한 OLAP 쿼리임을 발견함
- 위스콘신-매디슨 대학 연구진은 분석 쿼리를 더 빠르게 만들기 위해 노력함. DuckDB와 Star Schema Benchmark(SSB)를 사용하여 성능을 비교함
원인
- SQLite가 느린 이유를 파악하기 위해
VDBE_PROFILE 옵션을 사용하여 VDBE의 각 명령어가 소모하는 CPU 사이클을 측정함.
-
SeekRowID와 Column이라는 두 개의 opcode가 주요 원인으로 밝혀짐.
데이터베이스 조인
- 데이터베이스가 조인을 구현하는 방법에는 중첩 루프 조인, 해시 조인, 정렬-병합 조인이 있음.
- SQLite는 가장 간단한 "중첩 루프 조인"을 사용함. 이는 B-트리 탐색과 유사하여 비용이 많이 듦.
조인 최적화의 중요성
- 조인 연산에서 테이블의 순서가 중요함. 순서를 바꾸면 연산 횟수를 크게 줄일 수 있음. 이는 NP-난해 문제임.
- 중첩 루프 조인보다 더 나은 두 가지 조인 알고리듬이 있지만, 해시 조인은 메모리를 많이 소모하며 SQLite는 메모리 제약 환경에서 주로 실행됨.
- 연구진은 Bloom 필터를 사용하여 공간 효율성을 높이고 CPU 캐시 라인에 맞도록 함.
Filter와 FilterAdd라는 두 개의 opcode를 추가함.
결과
- 최적화 후 CPU 사이클 분석에서 큰 블루 바가 거의 사라짐.
- SQLite는 7배에서 10배 더 빨라짐. 이 연구 결과는 SQLite v3.38.0에 적용됨.
- Bloom 필터는 최소한의 메모리 오버헤드로 SQLite의 간단한 구현과 잘 맞고 기존 쿼리 엔진 내에서 작동함