👉 [DB] B+Tree 인덱스는 왜 LIKE 연산시 Full Scan을 할까?

LIKE 연산은 Indexing 걸린 column 이라도, Full Scan을 한다!

라는 말은 올바른 답일까?

 

정확하게는 아래와 같은 명제가 참이다.

 

 

LIKE 연산은 Indexing 걸린 column 이라도, Full Scan 할수도 혹은 Index Scan 할수도 있다.

실제로 아래와 같은 3가지 방식의 코드는 각각 Full-Scan 과 Index Scan의 결과를 초래한다.

 

/* Full Scan */ 
SELECT * FROM table_name WHERE column_name LIKE '%X%';
SELECT * FROM table_name WHERE column_name LIKE '%X'; 

/* Index Scan */ 
SELECT * FROM table_name WHERE column_name LIKE 'X%';

 

이렇게 하고 넘어가지말고(...)

WHY에 대해서 좀 더 알아보고 싶었다.

 

왜 그럴까 찾아보지만 그 어디에서도 이유는 나오지 않았다...

공식 문서도 찾아보았지만 말이다. 내가 못 찾은건가(?)

 

그래서 고민해봤는데, 아래부터는 내 짧은 지식으로 고민해본 나름의 결과이다.

 

---

 

MySQL 기준으로 RDB의 인덱싱 기법에 대해서 접근해볼 필요가 있다.

 

대부분의 RDB는 B+ Tree 기반으로 인덱싱을 지원한다.

 

https://www.geeksforgeeks.org/difference-between-b-tree-and-b-tree/

 

B+ Tree의 특징은 Leaf Node 에만 data pointer를 저장해 놓았으며

같은 레벨의 노드 기준으로 좌 -우로 연결되어 있다는 점이다. 

 

이를 통해서 Range Query 를 매우 손쉽게 할 수 있다. 위의 이미지를 예시로 생각해보자.

 

3부터 N+2까지 N개의 Range로 결과를 받고 싶다면 어떻게 해야하는가?

단순히 3을 찾아서 Next Pointer를 타고 옆으로 N개 만큼 넘어가기만 하면 O(n) 접근이 가능하다.

 

이 방식을 통해서 B+ Tree 기반의 인덱스는 매우 깔끔하고 빠른 Range Query가 가능한 것이다.

 

그런데 다시 생각해보자. 우리가 위에서 고민 해본 부분...

 

/* Full Scan */ 
SELECT * FROM table_name WHERE column_name LIKE '%X%';
SELECT * FROM table_name WHERE column_name LIKE '%X'; 

/* Index Scan */ 
SELECT * FROM table_name WHERE column_name LIKE 'X%';

 

LIKE 연산은 특정 키워드를 갖는 데이터에 대해서 범위 연산을 수행한다.

 

Index Scan과 Full Scan의 차이는 좌측의 % 존재 유무이다.

좌측에 %가 붙어 있는 경우는 무엇이 다를까?

 

실제 예시 데이터를 기준으로 접근 해보자.

 

 

http://contents.kocw.or.kr/contents4/document/lec/2012/KonKuk/KimJeongJun/14.pdf

 

Leaf 노드의 데이터들을 보자. 어떤 순서로 정렬되어 있는가? 사전순이다.

왜냐하면 결국 문자열도 ASCI 혹은 유니코드 기반의 숫자로 치환이 가능하고,

사전순 정렬시 숫자의 오름차순으로 정렬되기 때문이다.

 

만약 좌측에 % 와일드카드가 붙어 있다면 어떻게 검색할 수 있을까?

불가능하다.

 

왜냐하면 LIKE '%X' 혹은  LIKE '%X% 검색의 경우

AX , BX , CX ,DX ... 모든 경우의 수가 존재하는데, 인덱스 값 자체가 사전순(좌측 문자 우선)으로 정렬되어 있기 때문에 Range  Query가 불가능하다.

 

패턴의 왼쪽에 위치한 와일드카드를 인덱스에서 활용하려면, 인덱스의 모든 키 값에 대한 접두사를 생성하고 정렬된 순서로 검색해야 합니다. 이는 인덱스 구조를 효과적으로 활용하지 못하고 전체 테이블을 스캔하는 Full Scan이 필요하게 됩니다.

 

반대로 인덱스 스캔을 지원하는 LIKE 'X%' 의 경우 경우의 수가

XA, XB, XC, XD ... 등으로 이루어져 있다.

그렇기 때문에 B+Tree 가 사전순으로 정렬해 놓은 인덱스 값을 통해 Scan 할 수 있다.

 

누군가도 나와 같은 고민을 했다면, 조금이나마 비슷한 정답을 얻어가시길 바란다.