4.3Behind the Scenes of Indexes

인덱스의 작동에 대해 보다 깊이 알아보자. 지난 포스팅에서 만든 users_username_idx는 디스크와 메모리에서 각각 아래와 같이 저장되고 로드된다.

인덱스 내부 조회하기

인덱스 정보는 직접 쿼리로 조회할 수 있는데, extension(확장)이 하나 필요하다. pageinspect 익스텐션을 아래 쿼리로 설치하자.

sql
CREATE EXTENSION pageinspect;

이후, b-tree meta page를 의미하는 bt_metap 테이블에서 인덱스를 조회할 수 있다.

sql
SELECT * FROM bt_metap('users_username_idx');

이렇게 조회된 데이터에서 root 컬럼은 루트 노드가 저장된 페이지 번호를 의미한다. 우리 데이터에는 3이 나오는데, 이는 우리의 root node가 3번 인덱스(페이지)에 있다는 의미다. 루트 노드 역시 쿼리로 조회가 가능하다.

root node 조회하기

sql
SELECT * FROM bt_page_items('users_username_idx', 3);

이렇게 조회하면 여러 개의 ctid컬럼과 data 컬럼을 포함한 테이블이 나오는데, data 컬럼은 인덱스를 찾기 위한 일종의 조건(인덱싱된 키 값)이고, ctid는 해당 조건을 만족할 때 찾아갈 노드 페이지 번호를 의미한다. 아래는 조회결과를 캡처한 스크린샷인데, ctid에 (1,0), (2,1), (4,1)... 식으로 가는 것은 3번 인덱스가 바로 이 노드, 즉 root node이기 때문이다.

data에 보이는 값은 실제 인덱스 키 값을 이진 포맷(바이너리)로 저장한 것이다. 즉, 데이터 컬럼에 있는 16진수 값을 텍스트로 변환하면 저장한 유저명 값이 나온다. 예를 들어, (2,1)에 있는 data를 변환하면 Alyson14가 나온다. 즉, 이 값은 해당 페이지에 있는 첫번째 유저명을 나타내며, 하위 노드의 목차 역할을 한다.

leaf node 조회하기

실제 인덱스 페이지로 들어가보자.

sql
SELECT * FROM bt_page_items('users_username_idx', 1)

조회한 결과는 아래의 스크린샷처럼 나온다.

두 번째 열의 25 41 61...(ctid가 (41,11))는 16진수를 텍스트로 변환하면 Aaliyah_Treutel76이 나온다. 이 페이지의 ctid는 Heap File내에서의 실제 Tuple(테이블의 각 행) 위치를 의미한다.

Aaliyah_Treutel76의 ctid가 정말 (41,11)일까? ctid는 실제로 조회할 수 있는데, 별다른 익스텐션 없이 users 테이블에서 바로 조회가 가능하다. 물론 우리는 해당 컬럼을 보거나 만든 적이 없지만, 메타데이터기 때문에 PostgreSQL은 직접 요청하기 전엔 해당 컬럼을 숨기는 것이다. 아래와 같이 쿼리로 조회하면 ctid를 직접 확인할 수 있다.

sql
SELECT ctid, * FROM users
WHERE username = 'Aaliyah_Treutel76'

인덱스의 포인터 항목

방금 굳이 첫 번째 행을 건너뛰고 두 번째 행부터 조회한 것과, 앞서 본 root node의 첫번째 행이 다른 (n,1)과 같은 ctid가 아니라 (1,0)인 것에서 약간 수상함을 느꼈을 분들이 있는데, 이는 인덱스의 첫번째 행이 다음 leaf node의 위치를 가리키는 포인터 행이기 때문이다. 즉, 인덱스는 단일 트리 구조가 아니라 양방향 연결 리스트 형태이며, leaf node간 탐색을 최적화하기 위해 포인터가 존재한다.

이 구조로 인해 범위 검색(range query)에서 인덱스 페이지를 빠르게 순회할 수 있게 된다.

---

🤠 개인 탐구

각 leaf node에는 포인터 항목들이 있는데, 왜 존재할까? 여러가지 성능의 이점을 위해서다.

1. 범위 검색(Range Scan) 최적화

예를 들어, 아래의 쿼리를 보자.

sql
SELECT * FROM users
WHERE username BETWEEN 'Alex' and 'Zoe';

만약 각 페이지별로 포인터가 없다면, 우선 루트 노드에서 Alex가 있는 leaf node를 찾고, 다시 루트 노드에서 인덱스를 통해 Zoe가 있는 노드를 찾아야 한다. 하지만 leaf node들이 서로를 가리키고 있다면, Alex가 있는 leaf node를 찾고, 루트 노드로 돌아갈 필요 없이 다음 페이지(노드)로 이동하고, 다음으로 이동하고... 해서 Zoe가 있는 노드를 찾을 수 있다.

이런 방식으로 디스크 탐색 횟수가 줄어들고, 성능이 향상된다.

2. 정렬된 순회(Order by)에 유리

위와 같은 이유로, 정렬이 있다면 인덱스만 따라가며 정렬된 순서대로 값을 읽을 수 있다.

sql
SELECT * FROM users
ORDER BY username;