SQLite improving performance with pre-sort

SQLite에서 무작위 데이터 삽입 성능이 느린 이유

SQLite를 포함한 대부분의 RDBMS는 내부적으로 B+ Tree 구조를 사용한다. B+ Tree의 핵심 특성은 정렬된 순서를 유지한다는 것이다. 순차적인 키 값이 들어오면 트리의 끝에 노드를 이어붙이는 방식으로 빠르게 처리되지만, 무작위 키가 삽입되면 이야기가 달라진다. 트리 중간 어딘가에 값을 끼워넣어야 하므로 페이지 스플릿(page split)과 트리 재균형(rebalancing) 이 빈번하게 발생한다.

세션 토큰처럼 보안상 예측 불가능해야 하는 값은 UUID7처럼 시간 기반으로 정렬된 식별자를 사용하기 어렵다. UUID7은 타임스탬프 정보를 포함하기 때문에 정보 유출 위험이 있고 엔트로피가 충분하지 않을 수 있다. 이런 경우 SecureRandom으로 생성한 160비트(20바이트) 무작위 값 같은 완전한 랜덤 식별자를 사용하게 된다. 아래는 해당 방식으로 백만 건 단위 삽입을 반복했을 때의 실측 결과다.

초당 약 10만 건 수준으로, 데이터가 쌓일수록 점점 느려지는 전형적인 B+ Tree 랜덤 삽입 패턴을 보인다.

Pre-sort: 삽입 전 정렬로 성능 회복하기

핵심 아이디어는 단순하다. 이미 배치로 묶어서 삽입하고 있다면, 삽입 직전에 정렬한 뒤 넣으면 된다. 무작위 데이터라도 배치 단위 내에서 정렬된 순서로 삽입하면 B+ Tree 입장에서는 훨씬 예측 가능한 쓰기 패턴이 된다. 페이지 스플릿 횟수가 줄고, 이미 메모리에 올라온 페이지를 재사용할 확률이 높아진다.

정렬 비교 시 20바이트 전체를 순회하면 오버헤드가 생기므로, 앞 8바이트만 추출해 long 타입으로 변환한 뒤 부호 없는(unsigned) 비교를 수행하는 것이 실용적이다. 전체 바이트 배열을 완전히 정렬하지 않아도, 충분히 유사한 순서를 만들어 낼 수 있다.

// 앞 8바이트를 long으로 변환하여 정렬 키로 사용
long sortKey(byte[] id) {
    long val = 0;
    for (int i = 0; i < 8; i++) {
        val = (val << 8) | (id[i] & 0xFF);
    }
    return val;
}

// 배치 정렬 후 삽입
List<byte[]> batch = generateBatch(1_000_000);
batch.sort(Comparator.comparingLong(id -> sortKey(id)));
insertAll(batch);

부호 없는 비교가 중요한 이유는 Java의 long은 기본적으로 signed이기 때문이다. 최상위 비트가 1인 값이 음수로 해석되어 정렬 순서가 뒤틀리지 않도록 Long.compareUnsigned()를 활용해야 한다.

실무 적용 시 고려할 점

이 기법은 배치 삽입 구조가 이미 갖춰진 환경에서 가장 효과적이다. 건별로 즉시 커밋해야 하는 실시간 트랜잭션에는 적용하기 어렵지만, 이벤트 수집, 로그 적재, 대량 데이터 마이그레이션처럼 묶음 처리가 가능한 파이프라인에서는 코드 몇 줄로 의미 있는 성능 향상을 기대할 수 있다.

또한 이 원리는 SQLite에만 국한되지 않는다. PostgreSQL, MySQL 등 B+ Tree 기반 인덱스를 사용하는 모든 데이터베이스에서 동일하게 적용된다. 특히 WITHOUT ROWID 옵션을 사용하는 SQLite 테이블처럼 기본 키가 곧 클러스터링 키가 되는 구조에서는 삽입 순서의 영향이 더욱 직접적으로 나타난다.

정리

• 무작위 기본 키는 B+ Tree의 페이지 스플릿과 재균형을 유발해 삽입 성능을 저하시킨다
• 배치 삽입 시 삽입 전 사전 정렬(pre-sort)만으로 랜덤 쓰기를 순차 쓰기에 가깝게 만들 수 있다
• 정렬 비교는 전체 바이트 배열 대신 앞 8바이트를 unsigned long으로 변환해 효율적으로 처리한다