RDB indexscan 탐색 과정 공부 하면서 알게된 것들

결합 인덱스에서 all equal 조건절에서는 칼럼 순서가 중요하지 않다

인덱스 쪽에서 유명한 틀린 예제가 있다.

SELECT 이름, 성별
FROM 사원
WHERE 성별='여자'
  AND 이름='유관순'

위 예제에서 (성별, 이름) 인덱스를 사용하는 것과 (이름, 성별) 인덱스를 사용했을 때의 성능이 다르다는 것이다. 따라서 결합 인덱스에서 컬럼 순서가 중요하다는 것을 말한다.

 

그 이유는 사원 50명 중, 여자가 25명 유관순이 2명이라면

• (성별, 이름) 인덱스: 성별로 거르기(25명 남음) -> 이름으로 거르기(25명 중 2명만 남기기)
• (이름, 성별) 인덱스: 이름으로 거르기(2명 남음) -> 성별로 거르기(2명 중 2명 남음)

위 순서로 필터링하기 때문에 B-Tree를 타고 내려가면서 필터링하는 수가 줄어들어 (이름, 성별) 인덱스가 더 효율적이라는 논리다.

 

나도 이렇게 알고 있었는데, 이번에 인덱스 구조를 공부하면서 잘못 이해했다는 걸 알게 되었다. 좀 더 정확히는 브랜치 노드 구조에 대해서 잘 이해 못했다는 생각이 들었다.

 

내가 잘 몰랐던 포인트들을 짚어보자면 다음과 같다. 문제의 답은 이 포인트들을 짚고 나서 마지막에 공개하도록 하겠다.

1. 인덱스에서 중요한 것은 리프 노드 탐색 시작점과 끝점을 아는 것이다.

여기서 시작점을 찾는 행위를 수직탐색, 끝점까지 찾는 행위를 수평탐색이라고 한다. 여기서 중요한 점은 수직탐색은 조건을 만족하는 첫번째 레코드를 찾는 과정을 의미한다. 또한 수평탐색은 찾고자 하는 데이터가 더 안 나타날 때까지 리프 블록을 스캔하는 과정을 의미한다.

 

리프노드들 간 수평탐색은 공간적으로 인접해 있어 Sequential하기 때문에 더 효율적인 것도 알아두면 좋다.

위 그림은 인덱스의 구조를 나타낸 것이다. 그림은 친절한 SQL 튜닝 내용을 참고해 다시 그렸다.

 

여기서 LMC는 Left Most Child라고 인덱스 탐색 시작점의 처음을 의미한다. 만약 여기서 강덕승 & 남을 찾는다면 어떤 인덱스 리프블록을 조회해야 할까? 바로 리프 인덱스 1, 2를 조회해야 한다. 강덕승은 저 2개 리프 노드에 존재할 수 있기 때문이다.

 

아까 말했듯, 수직탐색은 조건을 만족하는 첫번째 리프블록을 의미하고, 수평탐색은 조건을 찾고자 하는 데이터가 더 안 나타날 때까지 스캔한다. 따라서 탐색하는 그림은 다음과 같다.

여기서 재밌는 점은 = 검색이기 때문에 리프블록 하나만 검색할 것 같지만, 값이 여러 개 나올 수 있기 때문에 여러 리프 블록을 탐색할 수 있다. 만약 unique 칼럼이라면 disk에서 읽어와야 하는 blcok i/o의 수가 1개 뿐이라 더 빠르게 조회할 수 있다는 의미도 된다.

 

또한 만약 강덕승 & 남이 엄청나게 많아진다면? 값의 분산도가 낮아지게 되고 읽어야 할 리프 노드들이 많아질 것이다. 그렇게 되면 수평 탐색으로 읽어야 할 리프블록들의 수가 많아진다. 인덱스 탐색시 카디널리티가 중요한 이유이다.

2. Balanced Tree와 sparsity

Balanced Tree는 트리의 depth가 유지된다. insert가 아무리 많이 입력되어도 블록들이 분기하면서 일정 depth를 유지하여, 균등한 수직 탐색 속도를 보장한다는 의미이다. 그렇다면 update와 delete는 어떨까?

 

일단 delete가 수행되면 해당 데이터를 물리적으로 삭제하진 않고, 지운셈 친다. lsm-tree에서는 이러한 전략을 tombstone이라고 불렀던 것 같은데 여기서도 같게 부르는진 모르겠다.

따라서 delete가 많이 수행된다고 해서 index가 rebalancing 된다고 하는 내용은 틀린 내용들이다.

 

delete가 많이 수행되면 인덱스 리프블록에 구멍이 나는 셈이다. 리프노드 i/o 효율이 떨어진다. 블록당 존재하는 실질적인 데이터 수가 줄어들기 때문이다. 이를 index sparsity라고 부르는데, 이런 경우에는 index rebuild까지 해야할 수도 있다.

 

update는 delete 1번, insert 1번 한 것과 동작이 같다.

3. index full scan은 table full scan과 비교해서 어떤 장점이 있을까?

내가 처음 생각했을 때 index full scan은 정말 의미 없는 작업이라고 생각했다. 그 이유는 index scan은 disk에서 block i/o할 때 single block i/o 하기 때문에, OS에서 퍼나를 수 있는 block size가 8kb이다. 이에 반해 full scan은 multi block i/o하기 때문에 1mb씩 퍼나를 수 있다. 퍼나를 수 있는 양이 128배 가량 차이난다는 것이다.

 

여기서 간과했던 점은, index full scan시에는 스캔해야 할 "컬럼의 수가 적다"는 것이다. 우리는 사각형의 넓이를 구할 때 가로 * 세로의 길이로 구한다. 테이블의 구조는 이 구조와 정확하게 대응한다. column(가로) * row(세로)가 곧 데이터의 크기인 것이다. 따라서 index에 넣는 column의 수가 적다면 더 많은 데이터를 밀어넣을 수 있다.

이는 full scan해서 원하는 몇개의 적은 block들을 찾아내고, 그것들 각각에서 single block i/o하는 전략에서 유용하다. 각 블록에 담긴 데이터 수가 table record block보다 훨씬 많기 때문에 원하는 데이터의 row_id(disk에 존재하는 레코드의 주소)를 적은 양의 disk i/o만으로 얻어올 수 있다. 만약 많은 block들을 disk에서 읽어와야 한다면 부적합할 수 있다.

 

그렇다면 disk i/o를 덜 하면 어떤 게 좋을까? 속도가 엄청나게 차이난다. disk i/o는 메모리에서 읽어오는 것과 비교해 약 10만배 정도 느린 것으로 여긴다. (옛날 자료라서 정확한 수치라서 지금은 꽤 차이날 것이기도 하고, HDD 기준인 수치다.)

 

제프 딘의 개발자가 알아야 하는 latency에서는 Read 1 MB sequentially from memory를 250,000 ns, Read 1 MB sequentially from disk를 20,000,000 ns라고 표현한다.

 

따라서 매번 disk i/o 요청하는 것은 메모리에서 읽어오는 것에 비해 엄청난 기다림을 요구하는 작업인 것이다. 250us job(메모리 작업) 잠깐 하고, 20ms 기다리고(disk i/o), 250us job 잠깐 하고, 20ms 동안 기다리고 ... 반복하면 엄청 느릴 것이다. 250us job은 많이 해도 겉으로 티 나지 않는다.

 

친절한 sql 튜닝 책에서도 쿼리 튜닝의 본질은 불필요한 disk i/o를 줄이는 것이라고 한 마디로 표현한다. 그만큼 중요한 것이다.

 

글을 쓰다가 생각난 건데, 예전에 포스팅했던 글중에 pk를 세컨더리 인덱스로 선언해 COUNT(*) 개선하는 전략도 이러한 block size를 줄이는 걸 응용한 것이라는 걸 느꼈다.

4. clustered index는 clustering factor에 대해 고려하지 않아도 된다.

사실 나는 innodb만 사용해 와서 non-clustering index에 대해서 잘 모르고 있었는데, 이쪽 세계에는 clustering factor라는 것이 존재한다.

 

clustering factor는 index scan하는 동안 access하는 table data block의 수를 의미한다.

 

non-clustered index는 인덱스를 통해 row-id를 찾고 여기서 table block을 찾아 데이터를 조회한다. 여기서 읽으려는 table data가 물리적으로 분리되어 있으면 random i/o가 발생한다.

 

여기서 신기한 건, 이전에 읽었던 block임에도, 직전에 읽은 block이 아니면 다시 읽는다. 따라서 index scan에서 clustering factor가 상당히 중요한 요소다. (정확한 이유는 모르겠다)

• 출처: http://www.gurubee.net/lecture/3858

위 사진은 clustering factor가 나쁜 경우이다. 이 경우 block을 12번 읽어야 한다. 실질적으로는 4번만 읽어야 함에도 그렇다.

 

하지만 clustered index의 경우 위 문제를 고려하지 않아도 된다. 이미 데이터와 index간의 (pk에 의한) 정렬이 보장되기 때문이다.

5. 결합 인덱스에서 인덱스 결정 범위는 선두 column이 결정한다. 선두 column은 검색 조건에 따라 달라진다.

앞에서 언급한 유관순 예제와 같은 주제의 이야기다. 앞에서 말한 틀린 예제를 다시 한 번 보자.

• (성별, 이름) 인덱스: 성별로 거르기(25명 남음) -> 이름으로 거르기(25명 중 2명만 남기기)
• (이름, 성별) 인덱스: 이름으로 거르기(2명 남음) -> 성별로 거르기(2명 중 2명 남음)

위 예제가 틀린 이유는 (이름, 성별)로 인덱스를 만들든, (성별, 이름)으로 인덱스를 만들든 리프 블록에 레코드가 2건만 존재하다는 점은 일치하다는 점이다.

앞에서 몇 번을 강조했던 내용에서 탐색은 1. 첫번째 레코드를 찾고 2. 찾고자 하는 데이터가 더 안 나타날 때까지 스캔한다.

수직탐색은 조건을 만족하는 첫번째 레코드를 찾는 과정을 의미한다. 또한 수평탐색은 찾고자 하는 데이터가 더 안 나타날 때까지 리프 블록을 스캔하는 과정을 의미한다.

따라서 어떤 인덱스를 사용하든 대상 레코드가 2건이므로 블록을 1개 읽어야 하는 것은 같다. 물론 레코드 끝에 걸리면 2개 읽을 수도 있겠지만 커다란 차이는 아니라고 생각한다.

 

물론 이러한 접근은 모든 조건절이 equal일 때만 적용된다. 부등호가 들어가는 range 조건일 때는 컬럼 순서가 중요해진다.

 

기본적으로 range 조건이 들어가면 range 조건은 후행 컬럼으로 들어가는 것이 좋다. 다음 2개의 쿼리를 보자.

SELECT 이름, 성별
FROM 사원
WHERE 성별<='여자'
  AND 이름='유관순'

위 쿼리 스캔 과정을 보자. 위에서 나왔던 all equal과 별 다를 바 없어 보인다. (사실 지금 보니 후행 컬럼을 남, 여밖에 설정할 수 없는 (생물학적) 성별로 만든 걸 후회중이다.)

 

그렇다면 다음 쿼리 스캔 과정을 보자.

SELECT 이름, 성별
FROM 사원
WHERE 성별='여자'
  AND 이름<='유관순'

우선 유관순보다 작은 이름을 모두 검색해야 한다. 따라서 관련 모든 블록들을 읽어와야 한다. index scan은 가뜩이나 single i/o라 읽을 block이 많아지면 느려지기 마련인데, 큰 낭패를 겪을 수 있다.

 

따라서, 결합 인덱스 만들 때 사용하려는 sql에서 범위 조건이 들어가면 후행 컬럼에 배치하도록 하자.