이전 목록:
SQLite 페이지 핸들링(1) - SQLite의 구조
SQLite 페이지 핸들링(2) - SQLite의 페이지 포맷
아마 페이지 핸들링 관련한 마지막 글이 될 것 같군요. B+ Tree에 대해 다룰까도 생각했는데 이건 워낙 유명한 알고리즘이고 하니 굳이 쓸 필요가 있을까 싶네요.
Record Format
예전 글들을 보시면 알겠지만 SQLite는 BTree의 leaf 페이지에 cell들을 저장한다고 표현했습니다. 이 cell이란 것이 테이블 페이지라면 곧 하나의 레코드가 되며, 인덱스 페이지라면 하나의 인덱스 엔트리가 됩니다.
search를 위한 자료구조는 보통 정렬 및 검색을 위한 key와 실제 값인 data의 페어로 하나의 아이템이 이루어지게 되는데 테이블 페이지의 경우 key는 row ID, data는 레코드가 되며 반대로 인덱스 페이지라면 key는 인덱스 키, data는 row ID가 됩니다.
row ID는 레코드를 구분하기 위해 레코드가 삽입될 때 DB 내부적으로 부여되는 숫자 키라고 보시면 되겠습니다. 즉 테이블은 row ID에 따라(결국 insert한 순서대로) 정렬되어 있고, 인덱스는 사용자가 지정한 키에 따라 정렬이 되어 있으며 데이터로는 실제 레코드의 위치를 찾기 위해 row ID를 갖고 있는 것입니다.
예를 들어 다음과 같은 스키마를 생각해 보죠.
CREATE TABLE employee (id INT, name TEXT, salary INT, title TEXT);
CREATE INDEX idx_title_salary ON employee(title, salary);
별로 좋은 예 같지는 않지만... 사원 테이블과 직급별 급여를 검색하기 위한 인덱스입니다 -_-;
그럼 위에 제가 설명한대로 페이지의 셀은
employee 테이블 페이지 : < rowID || id, name, salary, title >
idx_title_salary 인덱스 페이지 : < title, salary || row ID >
대략 이런 식이 되겠죠.
그럼 이게 끝? ...일 리가 없겠죠? -_-
데이터의 길이가 레코드마다 다르니 Cell의 길이도 레코드마다 다를 수 밖에 없고 그럼 페이지에서 읽어올 때 어디까지 읽어와야 될 지 알 방법이 없습니다. 게다가 어디까지가 key이고 어디부터가 data인지도 알 수가 없죠. 이런 정보들이 Cell Header에 포함됩니다.
실제 Cell의 포맷은 다음과 같습니다.
| Bytes |
내용 |
| 4 |
Left Child의 페이지 번호, leaf page에서는 생략 |
| varint |
data 부분의 바이트 길이, zerodata flag가 세팅되어 있으면 생략 |
| varint |
key 부분의 바이트 길이, intkey flag가 세팅되어 있으면 key값을 그대로 저장 |
| * |
Payload |
| 4 |
overflow 체인의 첫번째 페이지 번호. overflow가 아니면 생략 |
첫번째는 B+ Ttree의 internal 페이지일 때(leaf가 아닐 때) left child가 되는 페이지의 번호입니다. B+ tree에서 하나의 페이지에 매달리는 자식 페이지의 수는 (아이템 수+1)이 된다는 건 잘 아실겁니다. 가장 오른쪽 페이지 번호는 페이지 헤더에 저장되죠(이전 글 참조). 그러므로 leaf page에서는 필요없는 부분이구요.
두번째는 payload의 data 부분의 바이트 길이입니다. varint라고 표시되어 있는데 이는 Variable Integer를 의미하며 SQLite에서 사이즈를 줄이기 위해 구현한 특수한 Integer Type입니다. 이에 대해선 뒤에 다루겠습니다.
data 부분은 zerodata flag가 셋팅되어 있으면 생략됩니다만 거의 쓰이지 않습니다(이 flag는 바로 page header의 첫번째, 1바이트짜리 필드입니다).
세번째는 payload의 key 부분의 바이트 길이입니다. data 부분과 유사하게 intkey flag가 세팅되어 있으면 바이트 길이가 아니라 integer key 값을 그대로 저장합니다. 대신 payload의 key 부분이 생략되겠죠.
그리고 네번째의 payload는 실제 키/데이터 페어의 공간이며, 마지막의 overflow page number는 데이터가 오버플로우 될 경우 넘치는 부분의 데이터를 따로 오버플로우 페이지를 만들어서 저장하는데 그 첫번째 페이지 번호를 저장합니다. 물론 오버플로우가 아니면 생략이죠.
Variable Integer
여기서 varint란 것에 대해서 짚고 넘어가야겠네요.
예를 들어 row ID의 경우 최대값을 얼마로 잡아야 될까요? row ID 표현을 위해4바이트 int 타입을 쓸 경우, 웬만한 테이블의 경우 10만건을 넘는 경우가 드물다고 가정하더라도 대부분의 레코드에서는 각 레코드당 1~2바이트씩은 손해를 보게 되는 셈입니다.
이런 공간낭비를 절약하기 위해 SQLite에서는 Variable Integer라는 가변형 숫자 타입을 사용합니다.
기본 아이디어는 숫자 크기에 적절한 바이트를 사용하는 것이며 한 바이트의 첫번째 비트는 다음 바이트가 있는지 없는지를 표시합니다.
즉 한 바이트당 7비트를 사용해 수를 표시하는 거죠. 그리고 최대 9바이트를 사용하며 마지막 바이트는 8비트를 모두 쓰게 됩니다. 그러므로 7*8+8 = 64, 최대 9바이트를 써서 64비트 정수까지 표현하게 되는 겁니다.
로직을 다시 설명하면,
1. 한 바이트를 읽음
2. 첫 비트가 1이면 나머지 7비트를 저장해놓고 다음 바이트로 넘어감(1번에서 다시 반복)
3. 첫 비트가 0이면 저장된 값과 현재 바이트의 7비트를 합쳐 값 계산.
3-1. 9번째 바이트일 경우는 멈추고 저장된 값과 현재 바이트를 합쳐 값 계산.
대충 이런 식입니다.
물론 기본 int 타입에 비해 추가적인 오버헤드가 있겠지만 이 경우에는 공간 낭비를 줄이는게 더 현명한 선택이라고 판단한 거겠죠? 어떤 선택이든 trade-off는 있는 법입니다.
그럼 가볍게 -_- 일반 정수를 varint로 변환하는 함수를 한 번 살펴보겠습니다. 실제 소스의 util.c에 있습니다(주석은 물론 제가 단 거..).
/*
** varint의 인코딩 layout
**
** KEY:
** A = 0xxxxxxx 데이터 7비트와 플래그 1비트(다음 바이트 없음)
** B = 1xxxxxxx 데이터 7비트와 플래그 1비트(다음 바이트 있음)
** C = xxxxxxxx 데이터 8비트
**
** 7 bit 정수 - A
** 14 bit 정수 - BA
** 21 bit 정수 - BBA
** 28 bit 정수 - BBBA
** 35 bit 정수 - BBBBA
** 42 bit 정수 - BBBBBA
** 49 bit 정수 - BBBBBBA
** 56 bit 정수 - BBBBBBBA
** 64 bit 정수 - BBBBBBBBC
*/
/*
* @name : sqlite3PutVarint
*
* @args
* p : 변환된 varint 값(out)
* v : 변환시킬 정수값(in)
*/
int
sqlite3PutVarint(unsigned char *p, u64 v)
{
int i, j, n;
u8 buf[10];
/*
* v의 most significant 바이트에 값이 있는지 검사
* (즉, 가장 큰 바이트에 값이 있을 경우는 8바이트 정수이므로
* 무조건 9바이트의 varint가 필요)
*/
if( v & (((u64)0xff000000)<<32) )
{
/* v의 가장 작은 바이트 값이 p의 9번째 바이트에 assgin */
p[8] = v;
/* v를 1바이트 right shift */
v >>= 8;
/* 루프를 돌며 7비트씩 assign, 상위 1비트는 모두 1로 해줌 */
for(i=7; i>=0; i--)
{
p[i] = (v & 0x7f) | 0x80;
v >>= 7;
}
/* 바이트 길이(9)를 되돌려 주며 종료) */
return 9;
}
n = 0;
/*
* 8바이트 크기 정수가 아닌 경우는 첫번째 비트를 1로 하면서
* 7비트씩 차례로 buffer에 인코딩
* (현 시점에서는 바이트 길이를 판단하기 힘드므로 가장 마지막 바이트
* 를 buf[0]에 assign하면서 역순으로 처리)
*/
do{
buf[n++] = (v & 0x7f) | 0x80;
v >>= 7;
} while( v!=0 );
/*
* 인코딩 종료 후 마지막 바이트의 첫번째 비트를
* 다시 0으로 만듬
*/
buf[0] &= 0x7f;
assert( n<=9 );
/* output 변수에 바이트 순서를 뒤집어서 copy */
for(i=0, j=n-1; j>=0; j--, i++)
{
p[i] = buf[j];
}
return n;
}
어때요, 참 쉽죠? -_-;;;
사족을 달자면, 로직과 실제 구현은 디테일한 부분에 있어서 간극이 생길 수 밖에 없습니다. 예를 들면 바이트 순서를 뒤집어 카피하는 부분같은 거 말이죠.
로직이나 알고리즘 등이 전략이라면 저런 디테일한 부분은 전술에 비유될 수 있겠네요. 어느 쪽이든 엔지니어의 역량이 발휘되어야 겠지만, 양쪽에 필요한 능력은 약간은 다른 것 같기도 합니다.
Payload Format
그럼 마지막으로 실제 key와 data가 담기는 Payload의 포맷을 살펴보겠습니다.
key와 data가 각각 동일한 레코드 포맷을 갖고 있으므로 아래 살펴 볼 포맷 두 개의 연속쌍이 하나의 payload라고 보시면 되겠습니다.
물론 intkey 셋팅인 경우는 key 파트가 생략되거나 하는 예외는 있습니다.
하나의 레코드는 다음과 같이 구성됩니다.
| hdr-size |
type 0 |
... |
type N-1 |
data 0 |
... |
data N-1 |
N은 테이블 페이지라면 컬럼 갯수가 됩니다. 인덱스라면 키의 갯수겠죠.
hdr-size는 varint이며 레코드의 시작부터 data 0이 시작되는 부분까지의 바이트 길이입니다.
type 필드는 각각의 매치되는 data의 타입과 사이즈를 담고 있습니다. 역시 varint구요.
정수 타입 하나에 타입과 사이즈를 동시에 인코딩해 갖고 있다는게 이해가 살짝 안 될 수도 있지만 다음 설명을 보시면 알 수 있습니다. 여기서도 용량을 아끼기 위한 처절한 노력을 느낄 수 있습니다. -_-;;
각 타입의 번호와 설명입니다.
| type no. |
byte size |
type description |
| 0 |
0 |
NULL |
| 1 |
1 |
signed integer |
| 2 |
2 |
signed integer |
| 3 |
3 |
signed integer |
| 4 |
4 |
signed integer |
| 5 |
6 |
signed integer |
| 6 |
8 |
signed integer |
| 7 |
8 |
IEEE float |
| 8 |
0 |
integer 상수 0 (v3.3이상) |
| 9 |
0 |
integer 상수 1 (v3.3이상) |
| 10,11 |
|
예약 |
| 12이상의 짝수 |
(N-12)/2 |
BLOB |
| 13이상의 홀수 |
(N-13)/2 |
text |
다시 한 번 짚고 넘어가자면, SQLite는 data type 구분이 엄격하지 않습니다.
정수의 경우, 일반적인 RDBMS의 tiny int, short int, int, long int등은 SQLite에 존재하지 않으며 입력되는 시점에서 크기가 정해져서 insert됩니다.
고정길이 char 타입도 없으며 char(1)로 선언하든 varchar(10)으로 선언하든 모두 text 타입입니다(char (1)을 선언하고 긴 문자열을 insert해보세요). char나 varchar나 syntax는 받아들이지만 실제 처리는 다 같이 하는거죠 -_-;
그러므로 SQLite를 쓸 때는 data type의 사이즈를 어떻게 할 것인지 너무 고민할 필요는 없습니다.
표를 설명하자면, 0은 NULL이구요.
1~6까지는 바이트 길이에 따라 구분된 int 타입입니다.
7은 흔히 말하는 배정밀도 부동 소수(C의 double)입니다(아, 그러고보니 SQLite에는 Decimal 타입도 없습니다. 오라클의 NUMBER(M,N) 이런 거요).
8과 9는 v3.3 이후로 생긴 타입이라는데 integer 0과 1을 의미하는 상수입니다(1바이트라도 아끼려는 노력...-_-).
10과 11은 이후 버전의 확장성을 위해 비워놓은 타입이고요.
12 이후로 짝수는 BLOB, 홀수는 text 타입을 나타내는데 그 사이즈는 위에 보시는대로 각각 (N-12)/2, (N-13)/2입니다. 절묘하군요 -_-;
그래서 이 두 개의 variable length type이 타입번호에서 맨 뒤로 할당된 것입니다.
지금까지 살펴본대로 SQLite는 DB 페이지의 공간 절약을 위해 variable length data의 표현과 구현에 많은 공을 들인 것을 알 수 있습니다. 실제 데이터와 메타 데이터 양쪽에서 말이죠.
이 특징은 SQLite가 임베디드 분야에서 현재 높은 점유율을 보이는 중요한 특징 중의 하나가 아닐까 하는 생각이 듭니다. 임베디드 디바이스에서 DB를 쓴다면 데이터의 용량 문제는 피해갈 수 없는 난관이기도 합니다.
그러면서도 빠른 처리 속도를 유지하고 있다는 점은 역시 'Simple is the best'를 떠올리게 합니다. 네트웍 코드를 포함하지 않고 SQL 처리와 B+ tree 저장구조에 집중한 점은 바이너리 사이즈 역시 줄여주는 효과가 있었지요.
하지만 또 의외로, Full Text Search 인덱스나 R-tree 인덱스 같은 extension을 구현하여 용도를 다양하게 만드는 전략도 취하고 있는데요.
이후에 SQL을 파헤쳐 볼 지 extension을 다뤄볼지는 아직 고민중입니다만...
SQLite는 보면 볼 수록 재미있는 것 같습니다. 소스가 잘 되어 있는 편이라 오픈소스 입문용으로도 적당한 것 같고요.
다른 (잘 된) 소스를 많이 보는 것은 개발자의 skill level을 높이는데 큰 부분을 차지한다고 저는 생각하거든요 ^^
