약 7만개의 외부 데이터를 이용해 검색 기능을 구축하는 프로젝트를 진행하면서, 검색 기능을 향상하기 위해 고민했던 과정을 담았습니다.
목차
문제 상황
- Django Debug Toolbar를 이용하여 profiling 해봤을 때, 검색 기능을 위한 Query가 8.19s나 걸리나 걸리는 문제가 있었습니다.
- 이를 본 리드님께서 Index를 적용해보자고 해서 아래와 같이 index를 적용해봤습니다.
Index의 원리 및 종류
- Index란?
구글 검색에서 볼 수 있듯이 Index란, 데이터베이스에서 테이블에 대한 동작의 속도를 높여주는 자료 구조를 일컫습니다.
- Index는 책의 색인과 같은 역할입니다.
책에서 필요한 내용이 있다고 했을 때, 모든 페이지를 찾아보는 대신 맨 앞 혹은 맨 뒤에 색인을 이용하여 찾을 경우 더 빠른 속도로 원하는 내용을 찾을 수 있습니다.
DB에서도 책의 예시처럼 데이터와 데이터의 위치를 포함한 자료구조를 생성하여 빠르게 조회할 수 있게 하는게, 이것이 바로 Index입니다.
- Index가 없으면 Full scan을 통해 탐색하게 됩니다 O(n).
적절한 인덱스가 있으면 효율적으로 탐색 가능
Index가 없으면 책의 모든 페이지를 다 찾아봐야 하는 것처럼 모든 내용을 Full Scan을 통해 탐색하게 됩니다. 이 경우 최악의 경우 O(n) 의 시간복잡도를 가질 수 있습니다. 반면, 적절한 인덱스가 있으면 효율적으로 탐색을 하는 것이 가능해집니다.
- Index의 구조
- Index에는 Data Page를 어디에 저장하냐에 따라 Clustered Index와 Non Clustred Index로 나눌 수 있습니다.
Clustered index : Data page = Leaf Nodes, PK(default), 테이블당 1개만 설정 가능,
Non Clustered index : Data Page != Leaf Nodes, 별도의 장소에 인덱스 페이지 생성, 테이블당 249개 설정 가능
Clustered Index는 (맨 앞 색인) 페이지를 알고 있어서 바로 그 페이지를 피는 것이라면, Non Clustered Index는 (맨 뒤 색인) 색인에서 찾고자 하는 내용의 페이지를 찾고 그 페이지로 이동하는 것이라고 할 수 있습니다. Clustered Index는 Non Clustered Index에 비해 빠르지만, 테이블 자체를 정렬하는 것이기 때문에 테이블 당 1개의 index밖에 적용하지 못한다는 단점이 있습니다.
두 개념에 대한 자세한 내용은 이 글을 참조하시면 좋을 것 같습니다.
Non Clustered Index는 왜 최대 개수가 249개일까요?
발표 중 팀원분께서 왜 Non Clustered Index는 최대 개수가 2의 배수가 아닌 249개일까에 대해 좋은 질문을 해주셨습니다. 그 후 찾아보니, DB 시스템 내부적으로 index를 저장하는 특정 column의 값과 관련이 있었습니다. (참고)
DB에서는 sysindexes table라는 system table에 index에 관한 정보를 저장합니다. sysindex 테이블은 내부적으로 다음과 같은 column들이 있다고 합니다. (참고)
이 중 index ID를 저정하는 indid 라는 column은 0~255 범위를 가지는데, 이 범위중에는 0, 1, 255의 예약/하드코딩된 값이 있습니다. 0,1,255의 경우 text와 image data를 저장하고, 또한 251–254의 범위는 어떤 값을 나타내는지 명확히 정해진게 없기 때문에 이를 제외한 2~250값만을 이용하게 됩니다. 따라서 총 249개의 Non Clustered Index를 이용할 수 있습니다.
문제 상황
- 야심차게 index를 적용했지만..
그래도 속도가 3.89s로 빠른편은 아니었습니다.
성에 안차는 속도라 더 빠르게 하고 싶은데, 여러가지 검색했지만 뚜렷한 방법을 찾지 못해서 포기할 뻔 했었습니다.
그러던 중에 우연히 읽던 책에서 full text search 란 단어를 보고, 힌트를 얻었습니다. full text search를 검색하다보니, Django에서 containslookup을 이용한 like 검색시 index가 적용되지 않는다는 내용을 찾게 됐습니다 (참고) 더불어 Gin index를 이용하여 성능개선을 하였다는 부분까지도 얻을 수 있었습니다.
Django like 쿼리 성능 개선결과 — GIN Index
참고글대로 Gin Index를 적용한 후의 결과는 다음과 같습니다. 다만 데이터 개수가 적은 특정 API의 경우 Index를 적용하기 전보다, Index 적용 시 오히려 비용이 더 늘어나는 단점이 있었으나 나머지 API의 성능개선이 뚜렷해서 감안하고 넘어가도 될 부분이라고 판단했습니다.
그래서 Gin Index를 이용하여 성능은 많이 개선하였는데, 도대체 Gin Index가 무엇인지에 대한 의문이 들어서 찾아봤습니다.
PostgreSQL Index 종류
- ⭐️ B-Tree Index
- Hash Index
- GIN(Generalized Inverted Index)
- GiST(일반화 검색 트리)
- GiST(SP-GiST)
- BRIN(Block Range Index)
PostgreSQL에서 쓰이는 index 종류는 다음과 같습니다. 이 중 특정 index를 선언하지 않을 시 기본값으로 B-Tree Index가 사용됩니다. Gin Index 이전에 처음 index를 사용했을 시, B-Tree Index가 사용됐습니다.
B-Tree Index
- 데이터의 값을 비교 가능한 트리 형태로 저장하여 순차적 비교가 가능합니다.
- 데이터의 삽입과 삭제에 대해 항상 균형 트리를 유지하는 자료구조를 이용해, 순차 비교에 대해 최악의 경우에도 탐색의 시간복잡도가 O(logN)이 되도록 합니다.
- 인덱스를 적용하는 column의 값을 변형하지 않고(값의 앞부분만 잘라서 관리) 원래의 값을 이용하는 알고리즘입니다.
- = 연산에는 효과적이지만, ‘%Like%’ 연산과 같이 데이터 중간에 속한 값에 대한 인덱스 적용이 어렵습니다.
B-Tree Index는 left-to-right으로 왼쪽에 작은 값, 오른쪽에는 큰 값이 정렬되기 때문에 데이터의 중간 값을 비교하기 어렵습니다.
Gin Index(Generalized Inverted Indexes)
- 반면 Gin Index는 like 검색이 어려운 B-Tree 문제점을 해결해줄 수 있는, 기본적으로 full text search(어떤 게시물의 내용이나 제목 등과 같이 문장이나 내용에서 키워드를 검색하는 기능)을 위해 만들어진 Index 입니다.
- 인덱스를 적용하는 column의 값을 일정한 규칙에 따라 쪼개고(split)하고, 쪼갠 요소들을 활용하는 방식을 이용합니다.
- 데이터내의 각 요소(문장이라면 단어, 비정형 데이터라면 각 요소들)을 indexing하여 등장위치와 상관없이 해당 찾고자 하는 값이 데이터의 중간에 등장하더라도 인덱스가 가능하게 해줍니다.
- Gin Index에서 Inverted라는 의미는 일반적인 테이블과 index에서 데이터를 찾는 방식과 반대로, 단어를 해당 테이블에 위치에 매핑시켜 역순으로 데이터를 찾아가기 때문입니다.
Gin Index vs B-Tree
- Gin Index는 B-Tree index에 비해 indexing 속도가 좀 더 느리고 디스크 용량도 더 차지하게 됩니다.
- Gin Index는 모든 열 값의 테이블을 포함하는 트리를 구축하는 방식을 말하고, 그 단일 행은 트리내의 여러 위치에 표시될 수 있습니다. 이에 비해 B-Tree index는 일반적으로 index 항목이 특정 행을 가리키는 위치가 하나 있습니다.
Gin Index
- 다음과 같은 문장이 있다고 했을 때
TIDs << Posting List << Postin Tree
- 데이터를 table rows(TIDs) 단위로 보관하면서 각 row의 주소값을 배정하여 보관하게 된 것이 검은색 도형 , 즉 posting tree입니다.
- 여러번 나오는 sheet, slit, sitter 이외에 모든 어휘소에는 각 고유 TIDs에 맞춰 배정하고, 각 페이지에 자주 나오는 어휘소들을 배정합니다.
- 크기가 커서 텍스트 데이터를 각 페이지에 모든 정보를 넣을 수 없거나 여러번 나오는 어휘소들을 여러번 사용해야 할 시, 해당 데이터에 대해서 Posting List보다 더 큰 단위의 Posting 집합(해당 어휘소를 가지고 있는 모든 TIDs 집합)을 부여하는데 이를 Posting Tree라고 합니다(B-Tree임).
위의 예시에서 many와 slitter 를 찾아볼때,
many는 Posting list 하나뿐임으로 바로 찾을 수 있습니다.slitter는 T/F로 해당 단어가 있는 TIDs를 조회한 후, 조회할 단어가 모두 있는 TID를 선정하여 결과를 나타냅니다.
배운점
- PK, unique=True 옵션을 넣어주면 자동으로 Index(Clustered index)가 생성된다는 점
모든 DB상에서 Clustered index == PK라고 인식합니다.
그래서 PK로 정렬되는게 아닐까 궁금해져서 찾아봤는데, order_by절을 사용하지 않는 이상 어떠한 순서도 보장할 수 없다고 합니다. 클러스터형 인덱스 순서대로 record가 반환될 수는 있으나, 복잡한 쿼리(join, view, sub query)는 결과들을 다르게 정렬할 수 있기 때문입니다.
-MySQL에서는 <기본 순서는 쿼리에 사용된 인덱스와 사용 순서에 따라 다릅니다. 데이터 통계가 변경되고 옵티마이저가 다른 계획을 선택함에 따라 변경될 수 있다>고 되어 있다.
- Django model에 UniqueConstraint을 걸면 Index(Non Clustered Index)가 생성된다는 점.
Functional unique constraints have the same database restrictions as Index.expressions.
- Django.contrib.postgres.search module을 이용하면 PostgreSQL의 full text search 이용 가능한 점
(단일필드) Search lookup을 이용하면 바로 이용 가능
DB로부터 검색어를 plainto_tsquery 하고 검색 field를 to_tsvector한 것을 생성하여 query와 vector를 일치시켜 검색한다.
(다중필드) SearchVector를 이용
등등등 공식문서에 있음
위의 방법을 써야하나? 고민한 결과
- 위의 방법들을 즉석에서 SearchVector를 이용하여 tsvector를 만드는 것
- tsvector를 저장할 수 있는 column을 만들어야 실시간으로 변환하는 것이 아니기 때문에 성능 향상이 도움이 됨
- 결론적으로는 Gin Index를 이용하는 것이 맞다는 판단을 내렸습니다.
