created at 2024-01-22

Postgresql vs Mysql

인덱스 최적화 방법을 말씀드리기 전에 데이터 저장에 있어 Mysql 와 Postgresql 의 인덱싱 차이점을 먼저 말씀드리겠습니다.

Mysql 의 PK 인덱스는 클러스터링 인덱스로 되어있습니다. 클러스터링 인덱스는 데이터의 물리주소가 인덱스와 함께 정렬되어 있는 것이죠. 그래서 어떤 데이터가 삽입되거나 삭제될 때 인덱스가 재정렬되고, 이로인해 실제 데이터의 물리주소까지 변경됩니다. 실제 주소가 정렬되어있으니 Select 쿼리를 할 때 빠르게 데이터를 찾을 수 있겠죠? 반면 잦은 Insert, Update 는 매번 물리주소까지 변경되니 성능이 떨어집니다.

Postgresql 의 PK 인덱스는 물리주소와 인덱스가 따로 존재합니다. 그래서 어떤 데이터가 삽입되거나 삭제되어도 인덱스가 재정렬되지 않습니다. 단순히 포인터만 변경되는 방식이죠. 포인터로 데이터를 찾아가는 방식이니 Select 쿼리 시 여러개의 block 을 읽어야할 가능성이 존재합니다. 즉, 물리적으로 거리가 먼 위치의 데이터를 각각 읽어야하기때문에 읽기성능은 느린 반면 잦은 Insert, Update 는 물리주소가 변경되지 않으니 성능이 더 좋습니다.

이를 유념하면서 아래의 내용을 읽어주시면 감사하겠습니다!

DB Index 알고리즘 종류

B Tree

• 개념
  • 가장 대표적인 DB Index 알고리즘입니다. Postgresql 은 default index 생성 시 b-tree 로 생성합니다.
  • balanced tree 의 일종이며 노드는 여러개의 키를 가질 수 있습니다.
• 장점
  • 아무래도 노드가 여러개의 키와 value 를 가질 수 있다보니 block 단위로 저장하기 쉽고, 디스크의 IO 를 효율적으로 줄일 수 있습니다.
  • balanced tree 이기 때문에 최악, 최선, 평균의 시간복잡도가 O(logN)로 동일합니다. 그래서 쿼리 실행시간을 보장받을 수 있죠.
• 단점
  • 대부분의 인덱싱이 마찬가지겠지만, 삽입과 삭제에 비용이 추가로 발생합니다. 하지만 select 쿼리 비중이 일반적으로 80% 인 것을 감안한다면 삽입과 삭제에 비용이 추가로 발생한다고 해서 성능이 떨어지지는 않습니다.

B+ Tree

• 개념
  • B Tree 의 변형된 알고리즘입니다. 데이터포인터들은 모두 리프노드에만 존재합니다. B Tree 는 모든 노드에 포인터가 존재하구요.
  • 리프 노드가 모두 링크드 리스트로 연결되어있습니다.
• 장점
  • BETWEEN 쿼리의 경우 더 빠릅니다. 리프노드만 순회하면 되니까요! 즉 범위쿼리에 더 효과적이죠.

Hash

• 개념
  • 단방향 암호화 Hash 를 사용하여 인덱싱하는 방식입니다. 일반적으로 32비트 해시값을 사용하죠.
  • 최선, 평균은 O(1) 의 시간복잡도를 가집니다. 단 해시충돌이 매우 우연히 반복적으로 발생한 최악의 경우에는 O(N) 의 시간복잡도를 가집니다. Postgresql 은 링크드 리스트로 해쉬 충돌을 관리하기 떄문이죠. 사실 계속해서 해시 충돌이 일어날 확률은 0%에 가깝기때문에 최악의 경우는 거의 발생하지 않습니다.
• 장점
  • 어떠한 고유id 로 빠르게 단건 row 를 찾을 수 있습니다.
• 단점
  • 범위쿼리는 불가능합니다. 왜냐하면 해시값은 무작위 랜덤값이기 때문이죠.

GiST(Generalized Search Tree)

• 개념
  • Postgresql 가 독자적으로 제공하는 범용 인덱스 알고리즘이며 주로 공간데이터 복합키를 인덱싱하는데 최적화되어 사용됩니다.
  • balanced 한 트리 높이를 가집니다.
• 장점
  • 다차원 인덱스를 지원하기때문에 복합키를 인덱싱하는데 효과적이죠.
• 단점
  • B Tree 와 비교했을 때 GiST 는 더 많은 리소스 공간을 차지합니다. 이유는 정말 복잡한 데이터를 지원하기 위해서 노드 자체의 크기가 더 크기 때문이라네요. 단순한 키의 경우에는 B Tree 가 훨씬 효율적입니다.

Brin

• 개념
  • 블록범위를 기반으로해서 빠르게 찾는 인덱싱으로 각 블록의 최소값, 최댓값을 인덱싱합니다.
• 장점
  • 블록이 매우 많고 큰 대규모 데이터셋에서는 최솟값 최댓값만 저장하기 때문에 매우 적은 인덱싱 공간을 차지합니다.
  • 데이터가 물리적으로 저장된 순서에 따라 분포되어 있는 경우에 효과적입니다. 예를들어 created_at 칼럼에 적용하면 좋겠죠?
• 단점
  • 무작위 분포된 칼럼의 경우에는 인덱싱 효과가 떨어집니다.

각기 다른 Indexing 적용 이후의 성능차이

자 그러면 이런 인덱스를 적용했을 때, 성능차이를 말씀안드릴 수 없겠죠! 300만건이 저장된 채팅기록을 준비했고, created_at 칼럼에 ORDER BY LIMIT 를 수행해 보겠습니다. 해당 칼럼에는 대표적으로 BRIN, B Tree, Hash 인덱싱을 적용해보았습니다. 테이블의 모양은 아래와 같습니다.

실행쿼리 : roomId 에 기반하여 최대 1000개의 row 를 createdAt ascending.

No INDEX - 1447ms 소요

1000개 row 가져오면서 order by 로 created_at asc 정렬 시 1400 ms 가 소요되었습니다. 가운데 Parallel Seq Scan 이 있죠? 모든 row 를 정렬먼저하고 그다음 1000개 row 를 가져오는 것이죠. 그래서 꽤 오랜 시간이 소요되었습니다.

B Tree INDEX - 29.25ms 소요

이렇게 인덱싱을 적용시켜주고 이전 select ... order by 를 실행하게 된다면!!!!!

매우 빨라진 결과를 확인할 수 있었습니다!

위는 postgresql 쿼리 캐싱 이전 실제 쿼리값이구요. 동일쿼리 반복 수행 시 내부 메모리에 쿼리결과가 캐싱되어 훠어어얼씬 빠른 동작을 확인할 수 있었습니다)

BRIN 인덱싱 - 1618ms 소요

BRIN 은 해당 칼럼의 값이 물리적인 저장 순서에 따라 비교적 균일하게 분포되어 있을 때 가장 효과적입니다. 그래서 created_at 에 적용하면 빠른 인덱싱을 수행할 수 있겠죠?

그러나 데이터가 빈번하게 업데이트되거나 값의 분포가 균일하지 않은 경우에는 적합하지 않다고 합니다.

order by 에 인덱싱 적용되어 나타나지 않고, 시퀀셜 스캔이 실행되는 걸 확인하였습니다.

이상합니다… 분명 indexing 은 생성되었는데 말이죠.

그래서 찾아보니 ORDER BY 에서 BRIN 인덱싱 지원은 되지 않는다고합니다. 대신 WHERE 절에서는 아래와 같이 인덱싱이 적용된다고 하네요!

BRIN 인덱싱을 created_at 에 적용한다면 초기 sort 가 일어날 수 밖에 없기때문에 오랜 시간이 걸렸던 것이죠!

BTREE 와 BRIN Order by 지원여부 확인

HASH 인덱싱 - 1864ms 소요

마찬가지로 ORDER BY 에 인덱싱 적용되어 나타나지 않고, Seq Scan 이 실행되는 걸 확인하였습니다. 예상된 결과로 Hash 는 여러 row 의 순서를 가져오는데 전혀 적합하지 않았습니다!

결론은 order by 에서 인덱싱을 활용할 수 있도록 btree 를 적용시킴으로써 쿼리성능을 46배 이상 개선시킬 수 있었습니다!