최근 백오피스에서 특정 쿼리의 성능이 너무 낮아 해당 쿼리의 실행계획을 보게 됐다. 이 과정속에서 알게된 내용을 기록하고자 한다.
보통 우리는 데이터를 영구적으로 저장하기 위해서 db를 사용한다. (파일 시스템을 써도 되기는 하지만.. dbms가 제공해주는 기능들을 생각하면 파일 시스템을 쓸 생각은 하지 못할 것이다)
이 때 데이터는 컴퓨터의 디스크에 저장이 된다. 아래는 제프딘의 컴퓨터 자원 레이턴시 표를 기반한 그림인데, 디스크 작업이 느린 것을 확인할 수 있다.
그래서 이 느린 작업을 조금이라도 더 빠르게 하기 위해 dbms에 있는 옵티마이저는 적절한 실행 계획을 세운다. 여기서 개발자는 옵티마이저가 더 빠른 실행계획을 세울 수 있게 쿼리를 더 적절한 방향으로 수정하거나 적절한 인덱스를 태운다.
인덱스를 태울 때 알아야 할 점이 있는데, 같은 양의 데이터를 스캔할 때 인덱스를 통해 스캔하는 작업은 일반적인 스캔 방식에 비해 약 4배 느리다. 왜냐하면 인덱스 스캔은 random io, 일반 스캔(풀 스캔)은 sequential io 가 발생하기 때문이다. 당연하게도 테이블의 위에서부터 아래로 스캔하는 풀 스캔 방식은 순차적으로 io 가 발생하고 인덱스 스캔을 통해 읽은 데이터는 흩어져 있기 때문에 랜덤한 io가 발생하는 것이다. 이러한 사연으로 인덱스를 걸 때 카디널리티가 높은 컬럼에 거는 것이 좋다.
보통 실행 계획에서 join 방식, row 스캔 방식, 스캔한 row의 양, 실행 시간 정도를 보고 이를 성능이 좋은 방향으로 개선하려고 한다.
먼저 postgresql에서 join은 3가지 방식이 존재한다. (inner, outer와는 다른 개념. 알고리즘에 가까움)
- nested loop join
- hash join
- merge join
각각 어떤 방식으로 조인을 수행하는지 다음의 쿼리를 통해 살펴보자
select * from employee
join salery
on employee.id = saleray.employee_id
각 테이블에는 로우가 아래와 같이 저장되어 있다.
Nested Loop Join
nested loop join 을 할 경우 다음과 같이 동작한다.
1. id = 1 인 로우를 salary에서 순차적으로 스캔
2. id = 2 인 로우를 salary에서 순차적으로 스캔
3. id = 3 인 로우를 salary에서 순차적으로 스캔 ...
시간복잡도는 왼쪽 테이블의 row * 오른쪽 테이블의 row 만큼 걸리는 성능이 안좋은 테이블이다. 코드로 보면 아래와 같은 느낌인 셈이다.
for (int i = 0; i < employee.length; i++) {
for (int j = 0; j < salary.length; j++) {
if (employee[i].id = salary[i].employee_id) {
result.add(${데이터});
}
}
}
Merge Join
다음으로 merge join 의 동작 과정을 살펴보자 -> sort merge join이라고 불리기도 한다.
merge join이 적용되려면 한가지 조건이 있는데, 조인 조건의 컬럼을 기준으로 정렬이 되어 있어야 옵티마이저가 merge join을 채택할 가능성이 높아진다. 동작 과정을 보면 왜 그래야만 하는지 이해가 될 것이다.
다음과 같은 방식으로 동작한다.
1. id = 1 인 로우를 salary에서 순차적으로 스캔
2. id = 2 인 로우를 1에서 마지막으로 스캔한 다음 로우부터 스캔
3. id = 3 인 로우를 1에서 마지막으로 스캔한 다음 로우부터 스캔(2번 과정에서 스캔 결과가 없기 때문)
이렇게 되면 시간복잡도는 log(왼쪽 테이블의 row) * log(오른쪽 테이블의 row) 가 되는 셈이다. 이를 정말 간소화 한 코드로 나타내면 아래와 같다. (문법적으로는 어긋나지만 직관적이라 작성한다.)
시간복잡도는 정렬하는데 걸리는 시간 + 조인하는데 걸리는시간이 걸리기 때문에 O(nlogn + mlogm) 이 걸리게 된다. 하지만 일반적으로 정렬된 경우 옵티마이저가 머지 조인을 선택하기 때문에 O(n + m)이 걸리게 되며 슈도코드는 아래와 같다.
Table1_sorted = table1.sort()
Table2_sorted = table2.sort()
Row1 = table1_sorted.first()
Row2 = table2_sorted.first()
while row1 is not Null and row2 is not Null:
while row1 >= row2:
if row1 == row2:
Add_to_result(row1, row2)
Row2++
Row1++
Hash Join
다음으로 hash join 은 그림으로 보는게 나은데, 아래 그림으로 동작 방식을 확인 가능하다.
먼저 데이터의 개수가 더 적은 테이블을 기준으로 해시 테이블(지금 상황에서는 오른쪽 테이블)을 만들고 왼쪽 테이블의 해시키가 해시테이블에 존재하면 결과에 포함하는 식으로 동작한다. 가장 빠른 조인 방식이다.
근데 해시 테이블을 메모리에 올려두기 때문에, 충분한 크기의 메모리가 있을 때 해시 조인을 사용하게 할 수 있다. 공간복잡도가 O(table1.size())로 매우 큰 메모리를 사용한다. (join 서브쿼리를 사용하면 결과가 적어지니 해시 조인을 사용할 가능성이 높아질 것이다.) 이 분도 이러한 점을 이용해 hash join을 하도록 한 듯 싶다. (링크)
select * from employee e
join (
SELECT *
FROM salary
WHERE s.deleted = false and s.created_at > '2023-06-30'
) s
on e.id = s.employee_id
시간복잡도는 O(n + m)만큼 걸리며 슈도코드로 나타내면 아래와 같다.
For row1 in table1:
hashtable.add(row1.id, row1)
For row2 in table2:
Row1 = hashtable.get(row2.id)
If (row1 == row2):
Add_to_result(row1, row2)
다음으로는 데이터를 스캔하는 방식에 대해 살펴보자. postgresql에는 5가지 스캔 방법이 있는데 아래와 같다.
- Sequential Scan
- Index Scan
- Index Only scan
- Bitmap Scan
- TID Scan
각 스캔을 설명하기에 앞서 용어 정리를 하고 넘어가자
HEAP: Postgresql에서 HEAP은 테이블의 전체 행을 저장하는 저장 영역을 의미한다. 이는 여러 페이지로 나뉘며(그림 참고) 각 페이지 크기는 기본적으로 8KB이다. 각 페이지 내에서, 각 항목 포인터(예: 1, 2, …)는 페이지 내의 데이터를 가리킨다.
Index Storage: 인덱스에 포함된 열 값을 저장한다. 이것도 여러 페이지로 나뉘며 각 페이지 크기는 기본적으로 8KB이다.
Tuple Identifier (TID): TID는 두 부분으로 구성된 6바이트 숫자이다. 첫 번째 부분은 4바이트 페이지 번호이고, 나머지 2바이트는 페이지 내의 튜플 인덱스이다. 이 두 숫자의 조합은 특정 튜플의 저장 위치를 고유하게 가리킨다.
아래와 같은 쿼리를 실행해보면 쉽게 이해될 것이다.
select a.ctid from account a;
이제 각 스캔 방법을 살펴보자
Sequential Scan
먼저 Sequential Scan이다.
순차스캔인 Sequential Scan은 모든 로우를 하나씩 순서대로 살펴보는 방식이다. 매우 느린 스캔이다.
postgres=# explain SELECT * FROM demotable WHERE num < 21000;
QUERY PLAN
--------------------------------------------------------------------
Seq Scan on demotable (cost=0.00..17989.00 rows=1000000 width=15)
Filter: (num < '21000'::numeric)
(2 rows)
Index Scan
다음으로 Index Scan 이다.
순차 스캔(Sequential Scan)과는 달리, 인덱스 스캔(Index Scan)은 모든 레코드를 순차적으로 가져오지 않는다. 대신, 쿼리에 포함된 인덱스에 따라 해당 인덱스와 관련된 다른 데이터 구조를 사용하여 최소한의 스캔으로 필요한 데이터를 찾는다. 인덱스 스캔을 통해 찾은 항목은 힙 영역의 데이터에 직접 연결되는 TID를 반환하며, 이 데이터를 가져와서 격리 수준에 따라 가시성(실제 로우에 이런 메타 데이터가 있음)을 확인한다.
따라서 인덱스 스캔에는 두 단계가 존재한다.
1. TID를 가져오는 과정
2. 실제 데이터를 가져오는 과정
근데 인덱스 스캔은 랜덤 io 가 발생하므로 항상 더 빠른 스캔이 아닐수도 있다. (근데 옵티마이저가 순차 스캔보다 인덱스 스캔이 더 빠르다고 판단하면 인덱스 스캔을 사용하니깐 순차 스캔에 비해 항상 빠르다고 봐도 무방할 것 같다.)
다음으로 Index only scan이다.
이 옵션은 커버링 인덱스랑 동일한데 아래 쿼리를 보면 한눈에 이해가 될 것이다.
create index account_idx on account(name);
select a.name from account a;
위 쿼리를 보면 굳이 account 테이블의 힙에 접근할 필요가 없다. 걸려있는 인덱스(name) 만으로 충분히 정보 제공이 가능하기 때문이다. 이를 index only scan이라고 한다.
Bitmap Scan
다음으로 bitmap 스캔이다.
이 스캔 방법은 index 스캔, 순차 스캔을 약간씩 변형한 스캔 방법인다. 이런 곤란한 상황에서 발생한다.
인덱스 스캔을 하기에는 스캔할 데이터가 너무 많아 랜덤 io 때문에 성능 걱정이 되고 그렇다고 순차 스캔을 하기에는 모든 튜플(레코드)를 다 읽는 것은 너무 비효율적이고.. 이런 고민으로 인해 나온 방식이 비트맵 스캔 방법이다.
비트맵 스캔은 다음의 과정을 겪는다.
1. 비트맵 인덱스 스캔
2. 비트맵 힙 스캔
1번 과정에서는 인덱스 데이터 구조에서 모든 데이터를 가져온 후 해당 데이터의 tid의 비트맵을 생성한다.
2번 과정에서는 앞서 생성한 비트맵을 읽으면서 힙 데이터를 스캔한다. 이 때 1번 과정에서 tid를 기반으로 비트맵을 만들었기 때문에 순차 io가 발생하게 된다.
예를 들어 다음과 같은 쿼리가 있을 때
SELECT a.name
FROM account a
WHERE a.status = 'active' AND a.balance > 1000;
아래와 같은 방식으로 비트맵이 생성된다.
행 번호: 1 2 3 4 5 6 7 8 9 10
status: A I A A I A I I A I # A는 active, I 는 inactive
비트맵: 1 0 1 1 0 1 0 0 1 0
그렇게 되면 힙 스캔 과정에서 데이터는 1, 3, 4, 6, 9 순서로 스캔이 된다.
Tid Scan
마지막으로 tid 스캔이다.
아래와 같은 where 조건에 tid가 있는 특별한 쿼리에서 발생한다.
postgres=# select ctid from demotable where id=21000;
ctid
----------
(115,42)
(1 row)
postgres=# explain select * from demotable where ctid='(115,42)';
QUERY PLAN
----------------------------------------------------------
Tid Scan on demotable (cost=0.00..4.01 rows=1 width=15)
TID Cond: (ctid = '(115,42)'::tid)
(2 rows)
아래는 실제 문제가 있었던 쿼리의 실행 계획이다.
순차 스캔을 하는 과정도 있고, nested loop join을 하는 과정도 있다. 이제 이 계획을 보고 위 정보를 바탕으로 적당하게 쿼리를 튜닝하거나 인덱스를 태우면 성능이 개선될 것이다.
pg_trgm이라는 확장 기능을 추가한 후 %like 연산에 인덱스가 적용되게 한 후 아래와 같이 개선된 실행계획을 볼 수 있다. (사용할만한 정도로 어느정도 개선이 돼서 이정도로 만족,, 더 큰 공수를 들이기엔 다른 일을 하는게 나을듯)
순차 스캔 -> 비트맵 스캔으로 변경된 것이 보이며 스캔 과정에서 보였던 245 -> 12 로 변경된 것이 확인가능하다.
위 내용에 대한 자세한 구현이 궁금하다면 아래 경로에서 코드를 읽어보는 것이 좋아보인다. 시간도 오래걸리고 어려우니 주석정도만 봐도 괜찮을 것 같다.
https://github.com/postgres/postgres/blob/master/src/backend/executor
참고한 글
https://www.postgresql.org/docs/7.2/sql-syntax-columns.html (지금 버전이랑은 다른 버전의 문서인데 변경 사항이 없어서 일단 인용)
https://pganalyze.com/docs/explain/scan-nodes/bitmap-index-scan
https://severalnines.com/blog/overview-various-scan-methods-postgresql/
https://blog.bytebytego.com/p/ep22-latency-numbers-you-should-know