[postgreSQL] order by와 limit이 걸린 슬로우 쿼리 해결 방법

limit이 걸린 쿼리는 limit이 안걸린 쿼리보다 항상 빠르다? ----- (X)

모든 조회쿼리에서 limit이 걸리면 특정 개수만 조회하기에 항상 빨라질거라 생각했지만 limit을 해제하니 오히려 쿼리 속도가 더 빨라졌습니다. 어떻게 이런 일이 발생했는지 확인해보겠습니다.

해결 과정에서 헛다리도 짚었는데 그 과정 또한 기록했습니다. 결론만 보고싶으신 분은 아래로 가주시면 됩니다. 

가정

우선 예시 테이블 구조를 설명해드리겠습니다. 

history테이블은 5억이상의 데이터가 적재되어있고 복합 인덱스가 걸려있습니다.

CREATE TABLE history (
    id INT AUTO_INCREMENT PRIMARY KEY,
    active_id INT NULL,
    event_type VARCHAR(255) NOT NULL,
);

CREATE INDEX idx_active_id_event_type ON history(active_id, event_type);

 

그리고 아래 쿼리를 날려보았는데, 20초가 넘어도 조회가 되지 않았습니다. 심지어 select절에 id만 조회하도록 하여, 커버링 인덱스를 이용하도록 했음에도 불구하고 마찬가지였습니다.

select * from history where active_id is null and event_type = 'done' order by id desc limit 100

그래서 실행계획을 살펴보았습니다. 아래처럼 cost가 저렴함에도 불구하고 나오지 않아 의문이었습니다. 다만 걸렸던 것은 Index Scan BackWard using history_pkey on history 였습니다. (여기서 실행계획을 더 자세히 봤어야했습니다..)

Limit  (cost=0.57..6637.16 rows=100 width=56)
  ->  Index Scan Backward using history_pkey on history  (cost=0.57..25093747.04 rows=378112 width=56)
        Filter: ((active_id IS NULL) AND (event_type = 'done'::ck_event_type))

PostgreSQL은 mySQL의 innodb와 마찬가지로 리프 노드가 더블 링크드 리스트로 이어져있습니다. 그렇기에 인덱스 스캔 순서가 큰 영향이 없을걸로 판단했습니다. 그래서 관련 문서를 더 찾아보았습니다.

https://www.postgresql.org/docs/current/indexes-ordering.html

11.4. Indexes and ORDER BY

NULLS LAST

해당 문서에서는 아래와 같이 적혀있습니다.

An index stored in ascending order with nulls first can satisfy either ORDER BY x ASC NULLS FIRST or ORDER BY x DESC NULLS LAST depending on which direction it is scanned in.

Null이 먼저 오름차순으로 저장된 인덱스는 스캔되는 방향에 따라 ORDER BY x ASC NULLS FIRST 또는 ORDER BY x DESC NULLS LAST를 충족할 수 있습니다.

즉,

NULL, NULL, 1, 2, 3, 4, 5 이렇게 인덱스가 저장되어 있을때,

ORDER BY x ASC NULLS FIRST

이 쿼리는 인덱스를 정방향으로 스캔합니다.결과 >> NULL, NULL, 1, 2, 3, 4, 5

 

ORDER BY x DESC NULLS LAST

이 쿼리는 인덱스를 역방향으로 스캔합니다.결과 >> 5, 4, 3, 2, 1, NULL, NULL

 

속는셈 치고 해당 문서에 따라 NULLS LAST를 추가하여 아래 쿼리를 날려보았습니다. 그리고 놀랍게도 빠르게 조회가 되는 것을 확인할 수 있었습니다.

select * from history where active_id is null and event_type = 'done' order by id desc NULLS LAST limit 100

마찬가지로 실행 계획을 분석해봤고 아래처럼 나왔습니다.

Limit  (cost=998715.69..998715.94 rows=100 width=56)
  ->  Sort  (cost=998715.69..999660.97 rows=378112 width=56)
        Sort Key: id DESC NULLS LAST
        ->  Index Scan using ix_history_active_id_event_type on history  (cost=0.57..984264.52 rows=378112 width=56)
              Index Cond: ((active_id IS NULL) AND (event_type = 'done'::ck_event_type))

pk인데 NULLS LAST를 추가한 것이 어떤 원인으로 개선되었는지 파악할 필요는 있을것 같습니다. 다만 확실히 Index Scan BackWard 가 사라진것을 확인했고 이것이 느린 원인이라고 생각했습니다. 

Index Scan BackWard

MySQL Innodb

index scan backward가 더 느린이유는 2가지가 있다고 합니다.

• 페이지 잠금이 Forward index scan에 적합한 구조
• 페이지 내에서 인덱스 레코드는 단방향으로만 연결된 구조 (Forwarded single linked link)

자세한 이야기는 카카오 기술 블로그에 적혀있기에 참고해주시길 바랍니다. 요약하자면  페이지 잠금 과정에서 데드락을 방지하기 위해서 B-Tree의 왼쪽에서 오른쪽 순서(Forward)로만 잠금을 획득하도록 하고 있습니다. 따라서 backward scan은 이전 페이지 잠금을 획득하는 과정은 상당히 복잡한 이유라고 합니다.

다만 위는 innodb에서의 케이스이기에 postgresql에서 케이스를 봐보겠습니다. 아마 비슷할 것으로 추측합니다.

PostgreSQL

postgreSQL 코드를 보면 주석에서의 설명에서는 아래와 같습니다. 즉, 순방향 스캔에서와의 차이가 크지 않다고 하는데요..🤔 

대부분의 경우 튜플의 인덱스 키를 검사하지 않고 다음 튜플로 건너뛰는 것이 좋습니다(이전에는 실제로 왜냐하면 우리는 거꾸로 스캔하고 있기 때문입니다). 그러나 이것이 페이지의 첫 번째 튜플인 경우 인덱스 키를 확인하여 불필요하게 왼쪽 페이지로 이동하는 것을 방지합니다. 이는 순방향 스캔에서 사용되는 하이 키 최적화와 유사합니다.

 

만약 backward index scan으로 인해 느리다는 가설이 맞으려면 order by x asc를 했을땐 빨라야할것 같다고 생각해서 해당 조건으로 테스트해봤습니다. 

select * from history where active_id is null and event_type = 'done' order by id limit 100

 

하지만 Index scan Backward가 없었지만 느렸습니다..! 이때 자세히 보니 조건절에서 Filter를 통해서 조건을 확인하는 것을 발견했습니다. 

Limit  (cost=0.57..6637.16 rows=100 width=56)
    ->  Index Scan using activity_pkey on activity  (cost=0.57..25097467.04 rows=378112 width=56)
        Filter: ((active_id IS NULL) AND (event_type = 'done'::ck_event_type))

LIMIT이 없으면 더 빨라진다?

추가적으로 처음 보여주었던 쿼리는 Limit이 걸려있지만, 여기서 limit을 제거하면 오히려 더 빨라집니다. 

처음 보여주었던 쿼리는 아래와 같았습니다. 

select * from history where active_id is null and event_type = 'done' order by id desc limit 100

여기서 limit을 제거하고 실행 계획을 봐보겠습니다.

select * from history where active_id is null and event_type = 'done' order by id desc

Sort  (cost=1032219.18..1033164.46 rows=378112 width=56)
  Sort Key: id DESC
  ->  Index Scan using ix_history_active_id_event_type on history  (cost=0.57..984264.52 rows=378112 width=56)
        Index Cond: ((active_id IS NULL) AND (event_type = 'done'::ck_event_type))

네, Filter가 아니라 Index Cond를 통해 조회하는 것을 확인할 수 있습니다. 그러면 두개가 무슨 차이일까요?

Index Cond vs Filter

• Index Cond
  • 인덱스 스캔(Index Scan) 또는 비트맵 인덱스 스캔(Bitmap Index Scan) 시 사용되는 조건을 나타냅니다. Index Cond는 인덱스를 사용하여 데이터를 검색할 때 적용되는 조건입니다.
• Filter
  • 인덱스 스캔이나 순차 스캔(Sequential Scan) 후에 적용되는 추가적인 필터링 조건을 나타냅니다. 즉, PostgreSQL이 이미 인덱스 조건(Index Cond)이나 다른 방식으로 데이터의 일부를 가져온 후, 그 결과 집합에 추가적으로 적용되는 조건입니다.

즉, 옵티마이저가 pk 인덱스를 타는게 더 빠르다고 판단해서 order by id로 전체 정렬을 한 후, filter로 조건에 따라 솎아내다보니 느려진것입니다. 그렇다면 어떻게 개선할수 있을까요? 이미 예전부터 많은 사람들이 겪은 문제였는지 해당 사이트에서 도움을 얻을 수 있었습니다.

 

pk에 변화를 가해서 인덱스를 타지 못하도록 한다. 이를 통해 조건으로 먼저 걸러낸 후 정렬하도록 합니다.

즉, 아래처럼 쿼리를 변경해줍니다.

select * from history where active_id is null and event_type = 'done' order by id+0 limit 100

 

실제 이렇게 쿼리를 날리면 우선 Index Cond를 통해 조건에 맞는 결과만 조회하고 이를 정렬하는 실행 계획을 확인할 수 있으며 실제 쿼리 속도 빨리진 것을 확인했습니다.

결론

slow query(order by + limit)

select * from history where active_id is null and event_type = 'done' order by id limit 100

fast query

select * from history where active_id is null and event_type = 'done' order by id
select * from history where active_id is null and event_type = 'done' limit 100
select * from history where active_id is null and event_type = 'done' order by id+0 limit 100

정렬하고 조건에 따라 구분하는 것보다 조건에 따라 구분하고 정렬하는 것이 더 빠른 쿼리였습니다. 하지만 옵티마이저는 pk인덱스를 우선 타는게 빠르다고 판단하여 쿼리를 실행했지만 더 느렸던 것입니다.

즉, 옵티마이저의 인덱스 선택에서 잘못된것이므로 옵티마이저의 선택을 바꾸도록 유도해서 해결할 수 있었습니다.

 

NULLS LAST를 넣어서 빨리진 것도 pk 인덱스에 정렬 방식에 변경이 가해져서 pk인덱스를 우선 타는것보다 인덱스 조건에따라 구분하는 것이 더 빠르다고 판단되어 우연히 맞아떨어진 것이였습니다..!