SQLite가 바이트코드를 사용하는 이유

SQLite가 바이트코드를 사용하는 이유 (Why SQLite Uses Bytecode)

SQLite가 SQL을 준비된 문(prepared statement)으로 컴파일할 때 왜 바이트코드 방식을 사용하는지, 그리고 이를 객체 트리(tree-of-objects) 방식과 비교해 장단점을 설명하는 문서예요.

출처: Why SQLite Uses Bytecode (sqlite.org)

본문

1. 소개 (Introduction)

모든 SQL 데이터베이스 엔진은 거의 같은 방식으로 동작해요. 먼저 입력된 SQL 텍스트를 "준비된 문(prepared statement)"으로 변환해요. 그다음 준비된 문을 "실행(execute)"하여 결과를 만들어요.

준비된 문은 입력된 SQL을 수행하는 데 필요한 단계를 나타내는 객체예요. 다른 말로 하면, 준비된 문은 컴퓨터가 더 이해하기 쉬운 형태로 변환된 SQL 문이에요.

SQLite에서 준비된 문은 sqlite3_stmt 객체의 인스턴스예요. 다른 시스템에서 준비된 문은 보통 응용 프로그래머에게 직접 보이지 않는 내부 데이터 구조예요. 다른 SQL 데이터베이스 엔진의 개발자들이 반드시 이런 객체를 "준비된 문"이라고 부르는 것은 아니에요. 하지만 어떤 이름으로 부르든 그런 객체는 존재해요. 이 문서에서는 "준비된 문"이라는 용어를 사용할게요.

준비된 문을 구현하는 방법은 무수히 많아요. 이 문서에서는 가장 흔한 두 가지 방법을 살펴볼게요:

  1. 바이트코드 (Bytecode) → 입력된 SQL을 가상 머신 언어로 변환한 다음, 가상 머신 인터프리터로 실행해요. SQLite가 사용하는 기법이에요.

  2. 객체 트리 (Tree-Of-Objects) → 입력된 SQL을 수행할 처리를 나타내는 객체 트리로 변환해요. 이 트리를 걷기(walking) 방식으로 SQL을 실행해요. MySQL과 PostgreSQL이 사용하는 기법이에요.

이 두 준비된 문 표현 각각에는 장점과 단점이 있어요. 이 문서의 목적은 그런 장단점 중 일부를 명확히 설명하는 것이에요.

1.1. 의견을 제공하는 방법 (How To Provide Feedback)

이 문서는 SQLite의 원저자 관점에서 작성되었어요. 이 문서에서 제공된 의견 중 일부에 동의하지 않는다면, SQLite 포럼에서 정정 및/또는 반대 의견을 제시하는 것을 환영해요. 또는 저자에게 직접 이메일을 보낼 수도 있어요.

1.2. "바이트코드"의 정의 (Definition Of "Bytecode")

SQLite가 생성하는 바이트코드는 많은 독자가 생각하는 바이트코드와는 조금 다를 수 있어요. 예를 들어 Java 가상 머신이나 WebAssembly가 사용하는 바이트코드는 물리 CPU가 구현하는 것과 유사한 거의 전적으로 저수준 연산(기본 수학 연산자, 비교, 조건부 점프, 서로 다른 메모리 위치 사이의 내용 이동 명령)으로 구성돼요. SQLite 바이트코드에도 이런 종류의 저수준 명령이 있어요. 하지만 SQLite 바이트코드에는 데이터베이스 엔진의 요구에 특화된 고수준 연산도 포함돼 있어요. 몇 가지 예를 들면:

  • OP_Column → 특정 커서가 현재 가리키는 데이터베이스 행의 N번째 열에서 값을 추출해요.

  • OP_CreateBtree → 데이터베이스 파일에 새 B-Tree를 위한 공간을 할당해요.

  • OP_ParseSchema → sqlite_schema 테이블의 전체 또는 일부를 다시 읽고 다시 파싱해 내부 심볼 테이블을 갱신해요.

  • OP_SeekGE → 특정 B-Tree의 커서를 주어진 키보다 크거나 같은 첫 번째 항목으로 이동해요.

  • OP_Next → 특정 B-Tree의 커서를 B-Tree의 다음 항목으로 진행하고 점프하거나, B-Tree에 더 이상 항목이 없으면 통과해요.

즉, SQLite가 사용하는 "바이트코드"는 CPU 명령 집합이라기보다는 특정 순서로 실행될 데이터베이스 프리미티브(primitive) 목록에 가까워요.

1.3. "추상 구문 트리" 또는 "AST"의 정의 (Definition Of "Abstract Syntax Tree" or "AST")

"추상 구문 트리"(AST)는 어떤 정형 언어로 된 프로그램이나 문을 기술하는 데이터 구조예요. 우리의 맥락에서 정형 언어는 SQL이에요. AST는 일반적으로 객체 트리로 구현되며, 각 객체가 전체 SQL 문의 작은 부분 하나를 나타내요. AST는 정형 언어용 파서에서 자연스럽게 나와요. 보통 LALR(1) 파서를 사용해요. 이런 파서에서 각 터미널 심볼은 AST의 잎이 될 메타데이터를 담고, 각 비터미널 심볼은 전체 AST의 하위 분기가 될 메타데이터를 담아요. 문법 규칙이 파서에 의해 "축약(reduce)"되면서 AST의 새 노드가 할당되고 하위 노드에 연결돼요. 파싱이 끝나면 문법의 시작 심볼이 AST의 루트를 담고 있게 돼요.

AST는 객체의 트리예요. 하지만 AST는 준비된 문으로는 적합한 형태가 아니에요. 생성된 후 AST는 실행되기 전에 여러 방식으로 변환되어야 해요. 심볼이 해석되어야 하고, 의미 규칙이 검사되어야 하고, 입력 SQL 문을 더 빨리 실행되는 다른 형태로 변환하는 최적화가 적용되어야 해요. 마지막으로 AST는 실행에 더 적합한 대체 표현으로 변환되어야 해요.

일부 사람들은 MySQL과 PostgreSQL의 실행 가능한 형태로 사용되는 객체 트리를 AST라고 부르기도 해요. 이는 "AST"라는 용어를 잘못 사용한 것일 수 있어요. 실행될 준비가 된 객체 트리 시점에는 원래 SQL 텍스트와 거의 닮지 않게 많이 바뀌었기 때문이에요. 혼동은 부분적으로 최종 준비된 문 객체와 원래 AST가 모두 객체 트리이기 때문에 발생해요. 보통 파서에서 직접 나온 원래 AST가 여러 패스(pass)를 거쳐 조금씩 변형되어, 마지막에는 더 이상 엄밀히 AST는 아니지만 결과를 생성하도록 평가될 수 있는 객체 트리로 완전히 변환돼요. 이 과정에서 객체 트리가 AST로 그치고 준비된 문이 되는 명확한 지점이 반드시 있는 것은 아니에요. 그리고 AST와 준비된 문 사이에 명확한 경계가 없기 때문에, 사람들은 객체 트리로 표현된 준비된 문을 (정확한 설명은 아님에도) 종종 "AST"라고 부르곤 해요.

1.4. 데이터플로우 프로그래밍 (Dataflow Programming)

데이터플로우 프로그래밍은 각 노드가 전체 계산의 작은 한 부분을 전담하는 프로그래밍 스타일이에요. 각 노드는 다른 노드에서 입력을 받고 자신의 출력을 다른 노드로 보내요. 따라서 노드들은 입력을 출력으로 전달하는 방향 그래프를 형성해요.

SQL 데이터베이스 엔진이 준비된 문으로 사용하는 객체 트리를 "AST"보다는 "데이터플로우 프로그램"이라고 부르는 것이 더 적절한 설명일 수 있어요.

2. 바이트코드로 컴파일하는 장점 (Advantages To Compiling Into Bytecode)

SQLite는 바이트코드로 컴파일하고, SQLite 개발자들은 이 접근 방식에 매우 만족해요. 이유는 다음과 같아요:

2.1. 바이트코드는 이해하기 더 쉽다 (Bytecode Is Easier To Understand)

평평한 opcode 목록은 SQL 문이 정확히 어떻게 구현되고 있는지 보기 위해 쉽게 출력할 수 있어요. SQLite에서 SQL 문 앞에 "EXPLAIN" 키워드를 붙이면 이런 일이 일어나요. SQL을 실제로 실행하는 대신, 그 SQL을 구현하는 데 사용되었을 바이트코드 목록이 결과로 나와요.

바이트코드는 테이블로 쉽게 표현되기 때문에 이런 작업에 적합해요. SQLite 바이트코드에서 각 명령어는 하나의 opcode와 다섯 개의 피연산자(operand)를 가져요. 따라서 준비된 문은 6개 열 테이블에 대한 쿼리인 것처럼 표현될 수 있어요.

객체 트리 표현은 사람이 읽을 수 있는 형태로 공개하기가 더 어려워요. 트리를 구성하는 객체들은 모두 매우 달라서, 객체들을 표시할 일관되고 단순한 테이블 표현을 고안하기가 까다로워요. 상상해낸 어떤 테이블 표현도 거의 확실히 6개보다 많은 열을 가지게 될 거예요. 아마 훨씬 더 많을 거예요. 객체 트리를 테이블로 렌더링하는 문제는 충분히 어려워서, 내가 아는 한 아무도 하지 않아요. 따라서 객체 트리 데이터베이스 엔진은 그들의 "EXPLAIN" 출력에서 SQLite가 제공하는 수준의 상세함을 제공하지 못해요.

2.2. 바이트코드는 디버그하기 더 쉽다 (Bytecode Is Easier To Debug)

바이트코드는 SQL 문의 프런트엔드 파싱·분석과 백엔드 평가 사이를 명확히 분리해줘요. 문제가 발생하면(잘못된 답 및/또는 낮은 성능) 개발자는 바이트코드를 검사해 문제의 원인이 프런트엔드 분석인지, 제품의 백엔드 데이터 저장 부분인지 빠르게 판단할 수 있어요.

SQLite 디버깅 빌드에서 PRAGMA vdbe_trace=ON; 명령은 콘솔에 바이트코드 실행 추적이 나타나게 해요.

2.3. 바이트코드는 증분 실행할 수 있다 (Bytecode Can Be Run Incrementally)

바이트코드로 작성된 SQL 문은 증분적으로 평가될 수 있어요. 예를 들어, 문은 첫 번째 출력 행만 생성할 때까지 실행될 수 있어요. 그다음 문은 다시 단계(step)될 때까지 일시 정지해요. 첫 번째 출력 행을 검사하기 전에 문을 완료까지 실행할 필요가 없어요.

이것은 객체 트리 설계에서 달성하기가 더 어려워요. 준비된 문이 객체 트리일 때 실행은 보통 트리를 걷는(walking) 것으로 이루어져요. 계산 중간에 문을 일시 정지한다는 것은 스택을 호출자까지 풀어내면서, 평가를 이전에 중단한 지점부터 재개할 수 있을 만큼 상태를 저장한다는 뜻이에요. 이는 불가능한 일은 아니지만, 실제로 이루어지는 것을 본 적이 없을 정도로 어려워요.

대부분의 SQL 데이터베이스 엔진은 준비된 문의 증분 실행이 정말로 필요하지 않아요. 대부분의 SQL 데이터베이스 엔진이 클라이언트/서버이기 때문이에요. 클라이언트/서버 엔진에서는 단일 SQL 문이 서버로 보내지고, 완전한 응답이 한 번에 통신 회선을 통해 돌아와요. 따라서 각 문은 한 번에 완료까지 실행돼요. 하지만 SQLite는 클라이언트/서버가 아니에요. SQLite는 응용 프로그램과 같은 주소 공간에서, 같은 스택을 사용하며 실행되는 라이브러리예요. SQL 문의 증분 실행을 쉽고 안정적으로 수행할 수 있는 것은 SQLite에게 중요해요.

2.4. 바이트코드는 더 작다 (Bytecode Is Smaller)

SQLite가 생성하는 바이트코드는 보통 파서에서 나오는 해당 AST보다 작아요. SQL 텍스트의 초기 처리 중(sqlite3_prepare() 호출 등)에는 AST와 바이트코드가 동시에 메모리에 존재하므로 그때는 더 많은 메모리를 사용해요. 하지만 그것은 일시적인 상태예요. AST는 sqlite3_prepare() 호출이 반환되기 전에도 빠르게 폐기되고 그 메모리가 재활용되므로, 결과 준비된 문은 AST일 때보다 바이트코드 표현에서 더 적은 메모리를 소비하게 돼요. 이는 중요해요. sqlite3_prepare() 호출은 일시적이지만, 준비된 문은 재사용을 위해 캐시되어 오랫동안 메모리에 남는 경우가 많기 때문이에요.

2.5. 바이트코드는 더 빠르다 (Bytecode Is Faster)

나는 바이트코드 표현의 준비된 문이 더 빠르게 실행된다고 생각해요. 계산의 각 단계마다 결정해야 할 것이 더 적기 때문이에요. 앞 문장의 "생각해요"에 강조를 두는 이유는 → 이 주장을 실험적으로 검증하기는 어려워요. 실제로 어느 쪽이 더 빨리 실행되는지 보기 위해 동등한 바이트코드와 객체 트리 표현의 준비된 문을 만드는 데 필요한 수년의 노력을 투자한 사람이 아무도 없기 때문이에요. 우리는 SQLite가 매우 빠르다는 것을 알지만, 다른 SQL 데이터베이스와 좋은 나란히(나란히) 비교는 하지 못해요. 다른 데이터베이스가 클라이언트/서버 메시지 처리에 많은 시간을 쓰고, 메시지 왕복 오버헤드와 실제 처리 시간을 분리하기 어렵기 때문이에요.

3. 객체 트리로 컴파일하는 장점 (Advantages Of Compiling Into A Tree Of Objects)

SQLite 개발자는 적어도 SQLite가 채우려는 사용 사례에서는 바이트코드 접근 방식이 최선이라고 생각해요. 하지만 SQL 처리에서 객체 트리 접근 방식은 바이트코드에 비해 몇 가지 장점이 있어요. 항상 트레이드오프가 존재해요.

3.1. 쿼리 계획 결정을 런타임까지 연기할 수 있다 (Query Planning Decisions Can Be Deferred Until Runtime)

준비된 문이 바이트코드일 때, 바이트코드가 생성되면 알고리즘이 고정되고, 바이트코드를 완전히 다시 쓰지 않고는 이후에 변경할 수 없어요. 객체 트리 준비된 문에는 그렇지 않아요. 객체 트리는 실행 중에 수정하기 더 쉽고, 쿼리 계획이 변경 가능하며 쿼리 진행 상황에 따라 실행 중에 조정될 수 있어요. 따라서 쿼리를 동적으로 자체 튜닝할 수 있어요.

3.2. 데이터플로우 프로그램은 병렬화하기 쉽다 (Dataflow Programs Are Easy To Parallelize)

데이터플로우 프로그램에서 각 처리 노드는 서로 다른 스레드에 할당될 수 있어요. 중간 결과를 한 노드에서 다음 노드로 전달하기 위한 일종의 스레드 안전 큐(queuing) 메커니즘이 필요해요. 하지만 프로그램의 각 노드 내부에는 일반적으로 동기화 프리미티브가 필요 없어요. 노드 스케줄링은 단순해요. 노드는 데이터가 있고 출력 큐에 공간이 있을 때 실행 자격이 생겨요.

이것은 대규모 다중 코어 서버에서 대규모 분석 쿼리(OLAP)를 실행하도록 설계된 데이터베이스 엔진에게 중요한 고려 사항이에요. SQLite의 주요 초점은 사물 인터넷에서의 트랜잭션 처리(OLTP)이므로, SQLite에서 준비된 문을 데이터플로우 프로그램으로 표현할 필요성은 더 적어요.

더 알아보기 (Learn more)