# Bloom 필터로 10배 빨라진 SQLite

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

## Metadata

- GeekNews HTML: [https://news.hada.io/topic?id=18399](https://news.hada.io/topic?id=18399)
- GeekNews Markdown: [https://news.hada.io/topic/18399.md](https://news.hada.io/topic/18399.md)
- Type: GN+
- Author: [neo](https://news.hada.io/@neo)
- Published: 2024-12-23T10:10:45+09:00
- Updated: 2024-12-23T10:10:45+09:00
- Original source: [avi.im](https://avi.im/blag/2024/sqlite-past-present-future/)
- Points: 13
- Comments: 3

## Summary

Bloom 필터를 사용하여 SQLite 데이터베이스의 성능을 7배에서 10배까지 향상시켰습니다. 연구진은 `SeekRowID`와 `Column` opcode가 성능 저하의 주요 원인임을 발견하고, Bloom 필터를 통해 공간 효율성을 높이며 CPU 캐시 라인에 맞도록 최적화했습니다. 이 결과는 SQLite v3.38.0에 적용되었으며, 최소한의 메모리 오버헤드로 기존 쿼리 엔진과 잘 작동합니다.

## Topic Body

- 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의 간단한 구현과 잘 맞고 기존 쿼리 엔진 내에서 작동**함

## Comments



### Comment 32652

- Author: porteleaf
- Created: 2024-12-24T11:13:47+09:00
- Points: 1

지금 버전을 확인해보니 지 시스템은 3.42.0을 사용하고 있네요. 현재기준 최신은 3.47.2 입니다

### Comment 32633

- Author: halfenif
- Created: 2024-12-24T06:53:02+09:00
- Points: 1

지금 사용중인 SQLite 버전을 확인 해 봐야겠군요.  
  
사실 이것보다 openpyxl을 사용해서 엑셀파일을 만들어내고있는데, 시간이 많이 걸려서 다른 라이브러리가 있을까 찾아보기는 해야합니다.

### Comment 32635

- Author: savvykang
- Created: 2024-12-24T09:25:47+09:00
- Points: 1
- Parent comment: 32633
- Depth: 1

프로파일링을 해보시는게 좋지 않을까요