[Database] DB 검색 성능 개선을 위한 INDEX와 FTS

인덱스(INDEX)란?

 

인덱스는 데이터베이스에서 데이터를 빠르게 조회하기 위해 사용되는 자료 구조입니다. 데이터가 많아지면 테이블을 순차적으로 검색하는 방식(선형 탐색)은 시간이 오래 걸려 성능이 저하됩니다. 인덱스는 이 문제를 해결하기 위해 특정 열에 대해 빠르게 데이터를 찾을 수 있도록 도와주는 구조입니다.

 

인덱스를 사용하면 빠른 검색이 가능하며, 그 차이는 테이블의 크기가 커질수록 더 두드러지게 나타납니다. 또한 인덱스는 조인 성능을 향상시키고, 집계 함수의 처리 속도도 개선시킬 수 있습니다.

 

하지만 인덱스를 생성하고 유지하는 데 추가적인 비용이 들어가며, 데이터 삽입, 삭제, 업데이트 시 성능이 저하될 수 있습니다. 이는 인덱스를 갱신해야 하는 추가 작업이 발생하기 때문입니다. 예를 들어, 데이터 삽입 시 새로운 데이터가 인덱스에 반영되어야 하고, 삭제 시에는 해당 인덱스 항목을 제거해야 하며, 업데이트 시에는 기존 인덱스를 수정해야 합니다. 이와 같은 작업은 시간이 소모되고 성능에 영향을 미칩니다. 또한, 인덱스를 유지하기 위해 추가적인 저장공간이 필요하게 되어 시스템 자원을 더 많이 차지하게 됩니다.

 

이번 글에서는 인덱스에 대해 자세히 알아보겠습니다.

 

 

트리 구조란?

 

인덱스의 자료 구조에 대해 살펴보기 전에 먼저 트리 구조에 대해 간단하게 짚고 넘어 가겠습니다.

 

트리 구조는 계층적으로 데이터를 저장하고, 효율적인 검색과 삽입, 삭제를 가능하게 하는 자료 구조입니다. 트리 구조는 일반적으로 노드(Node)와 간선(Edge)으로 구성됩니다. 여기서 노드는 데이터를 저장하는 기본 단위이며, 간선은 노드 간의 연결을 나타냅니다. 트리 구조의 각 노드는 내부 노드(Internal Node)와 리프 노드(Leaf Node)로 구분될 수 있습니다.

그리고 트리에서 가장 상위에 위치한 노드는 루트 노드(Root Node)라고 하며, 트리 구조에서 단 하나만 존재합니다.

 

트리 구조는 부모-자식 관계를 바탕으로 데이터를 계층적으로 저장하는 구조입니다. 이때, 루트 노드에서 가장 깊은 리프 노드까지의 경로 길이를 높이(Height)라고 하며, 특정 노드에서 루트 노드까지의 경로 길이는 깊이(Depth)라고 합니다.

 

이러한 트리 구조에서 중요한 점은 정렬된 상태로 데이터를 저장한다는 것입니다. 정렬된 상태를 유지하는 트리 구조는 탐색을 빠르게 하도록 도와주며, 삽입과 삭제 연산 시에도 트리의 균형을 잘 맞출 수 있도록 합니다. 

트리의 주요 종류로는 이진 트리(Binary Tree), B-Tree, B+Tree가 있습니다.

 

 

인덱스 자료 구조 (B-Tree)

 

PostgreSQL에서 제공하는 인덱스의 자료구조는 B-Tree, Hash Index, GIN(Generalized Inverted Index),  GiST(Generalized Search Tree),  SP-GiST(Space-partitioned Generalized Search Tree), BRIN(Block Range INdexes) 가 있습니다. 그 중에서 기본 인덱스로 사용되는 B-Tree에 대해 살펴보겠습니다.

 

B-Tree는 균형 잡힌 이진 검색 트리로, 트리의 높이가 항상 일정하게 유지되도록 설계되어 있어 검색, 삽입, 삭제 연산에서 일정한 시간 복잡도(logN)를 보장합니다. 일반적인 이진 트리(Binary Tree)와 달리, 각 노드가 두 개 이상의 자식 노드를 가질 수 있어 더 적은 수의 레벨로 데이터를 효율적으로 저장할 수 있습니다.

 

B-Tree에서는 내부 노드와 리프 노드는 구분하지 않고, 모든 노드가 데이터를 저장합니다. 각 노드는 key와 데이터를 저장하며, 검색은 루트 노드에서 시작해 트리를 따라 내려가면서 데이터를 찾는 방식으로 이루어집니다.

 

 

위 그림은 3차 B-Tree를 사용하여 20에서 80까지의 키 값과 A에서 G까지의 데이터를 갖는 인덱스를 나타낸 것입니다.

N차 B-Tree
- 노드는 최대 M개의 자식 노드와 M-1개의 key를 가질 수 있다.
- 노드는 최소 [M/2]개의 자식 노드와 [M/2]-1개의 key를 가진다.

 

이 경우, 인덱스를 사용하지 않고 데이터를 조회할 때의 최악의 시간 복잡도는 O(N)이며, 이는 O(7)입니다.

O(N) : N은 데이터의 수

 

반면, 인덱스를 적용한 경우 최악의 시간 복잡도는 O( logₘ N)로, 이는 O(log₃ 7) ≈ O(1.77)입니다.

O(logₘ N) : m은 트리의 차수, N은 전체 노드의 수

 

이 간단한 예시를 통해 인덱스를 사용했을 때 성능 차이를 예상해 볼 수 있습니다.

 

 

인덱스 자료 구조 (B+Tree)

 

MySQL의 InnoDB 엔진에서 사용되는 기본 인덱스 자료구조는 B+Tree입니다. B+Tree는 B-Tree의 변형으로, 데이터베이스에서 자주 사용되는 인덱스 자료구조 중 하나로, B-Tree의 특징을 유지하면서도 몇 가지 중요한 차이점이 있습니다.

 

B+Tree는 균형 잡힌 트리 구조로, B-Tree와 유사하지만 주요 차이점은 모든 데이터가 리프 노드에만 저장된다는 점입니다. 즉, 내부 노드는 데이터 자체를 저장하지 않고 key만 저장하며, 실제 데이터는 리프 노드에 저장됩니다. 또한, 리프 노드들은 LinkedList 형태로 서로 연결되어 있어, 순차적인 접근이 용이합니다. 이러한 특성 덕분에 범위 쿼리에 매우 유리한 구조입니다.

 

 

위 그림은 3차 B+Tree를 사용하여 20에서 80까지의 키 값과 A에서 G까지의 데이터를 갖는 인덱스를 나타낸 것입니다.

N차 B+Tree
- 노드는 최대 M개의 자식 노드와 M-1개의 key를 가질 수 있다.
- 노드는 최소 [M/2]개의 자식 노드와 [M/2]-1개의 key를 가진다.

 

이 경우, 시간 복잡도는 B-Tree와 동일하게 O(log₃ 7) ≈ O(1.77)입니다.

O(logₘ N) : m은 트리의 차수, N은 전체 노드의 수

 

 

데이터 조회 비교

 

위에서 설명한 인덱스를 실제로 적용하여 조회 시간에 어떤 차이가 발생하는지 확인하기 위해 MySQL 데이터베이스에서 간단한 accounts 테이블을 생성하고, 20만 개의 샘플 데이터를 삽입하여 테스트를 진행했습니다.

 

인덱스 생성과 삭제는 아래와 같은 쿼리문을 사용하여 할 수 있습니다

CREATE INDEX idx_name ON table_name(column1);

DROP INDEX idx_name ON table_name;

 

》 Index가 없을 때

테스트 결과 실행 시간(execution)은 84ms, 페칭 시간(fetching)은 17ms 가 걸렸습니다.

 

》 Index가 있을 때

테스트 결과 실행 시간(execution) 은 8ms, 페칭 시간(fetching) 은 47ms 가 걸렸습니다.

 

실행 시간은 데이터베이스 쿼리가 실제로 실행되는 시간으로, 쿼리가 분석되고 최적화된 후 결과를 생성하는 데 소요되는 시간입니다.
페칭 시간은 실행된 쿼리의 결과가 애플리케이션으로 전달되는 데 걸리는 시간입니다.

 

테스트 결과를 비교해보면, 인덱스가 있을 때 실행 시간이 약 10배 빠르다는 것을 확인할 수 있습니다.
하지만, 인덱스가 있을 때 페칭 시간이 더 길어진 이유는 인덱스를 기반으로 다시 테이블에 접근하는 Index Lookup 과정이 추가되었기 때문입니다.

그러나 페칭 시간을 고려하더라도, 실행 시간에서 큰 차이가 나는 것을 볼 수 있습니다.

또한, 해당 쿼리에 인덱스가 적용되었는지 확인하려면 쿼리 앞에 EXPLAIN 키워드를 추가하여 실행하면 됩니다

 

 

복합 인덱스

 

복합 인덱스는 여러 개의 열을 결합하여 하나의 인덱스를 생성하는 방식입니다. 즉, 단일 열이 아닌 두 개 이상의 열을 기준으로 데이터를 빠르게 검색할 수 있도록 하는 방법입니다. 이는 복잡한 쿼리에서 유용하게 사용됩니다. 예를 들어, 여러 조건을 포함한 WHERE 절, 정렬(ORDER BY), 그룹화(GROUP BY) 작업을 처리하는 데 효과적입니다.

 

복합 인덱스를 사용할 때 가장 중요한 점은 인덱스의 순서입니다. 예를 들어, 복합 인덱스를 (A, B)로 설정했다면, 쿼리에서 조건을 사용할 때에도 A, B 순서로 사용해야 합니다. 이유는 복합 인덱스가 내부적으로 A 값을 먼저 정렬하고, 그 후에 동일한 A 값을 가진 레코드들끼리는 B 값을 기준으로 정렬되기 때문입니다. 따라서 인덱스를 효율적으로 활용하려면, 인덱스를 생성한 순서대로 열을 사용하는 것이 중요합니다.

 

 

FTS(Full Text Search)란?

 

FTS란 단어 그대로 전체 텍스트 검색을 의미합니다. 이는 데이터베이스에서 텍스트 데이터를 검색하는 방법 중  하나로, 특정 단어, 문구, 또는 패턴이 포함된 데이터를 효율적으로 찾을 수 있게 해줍니다.

 

FTS는 텍스트를 단어 단위로 분석하고, 사용자가 입력한 검색어와 관련된 모든 텍스트를 검색하여 결과를 제공합니다. 단순히 단어 일치 여부를 확인하는 것에 그치지 않고, 형태소 분석, 불용어 처리, 정렬 및 랭킹, 부분 일치 검색 등의 기능을 제공하여, 자연어 처리(NLP, Natural Language Processing)와 유사한 기능을 지원합니다. 이를 통해 가장 관련성이 높은 결과를 반환할 수 있습니다.

 

일반적으로 텍스트 길이가 100자 미만인 경우에는 인덱스를 추가하여 효율성을 높일 수 있지만, 텍스트 길이가 그 이상일 경우에는 FTS가 더 효율적인 방법입니다.

 

MySQL에서는 FTS를 FULLTEXT를 사용하여 구현하고, PostgreSQL에서는 GIN 인덱스나 GiST 인덱스를 사용해 검색 성능을 최적화할 수 있습니다.

 

MySQL에서 FULLTEXT를 추가하는 방법은 다음과 같습니다

ALTER TABLE table_name ADD FULLTEXT (column1, column2);

 

그리고 검색은 MATCH와 AGAINST 키워드를 사용하여 다음과 같이 할 수 있습니다

SELECT * FROM table_name
WHERE MATCH(column_name) AGAINST('search_term' IN NATURAL LANGUAGE MODE);

 

여기서 IN NATURAL LANGUAGE MODE는 기본값이므로 생략이 가능합니다.

그리고 보다 세밀한 조정을 위해서는 IN BOOLEAN MODE를 사용할 수 있습니다.

 

 

FTS와 LIKE 연산자

 

FTS(Full Text Search)와 LIKE 연산자는 둘 다 데이터베이스에서 텍스트 검색을 수행하는 방법이지만, 각기 다른 방식으로 동작하고 성능과 용도에 차이가 있습니다.

 

LIKE 연산자는 문자열 패턴 매칭을 통해 주로 문자열이 정확히 일치하거나 부분적으로 일치하는지 확인하는 데 사용됩니다. 와일드카드(%, _)를 이용해 부분 일치 검색이 가능하지만, 자연어 처리 기능이나 텍스트의 의미를 고려하지 않습니다. 또한 LIKE 연산자는 인덱스를 효율적으로 활용하지 못하며, 특히 와일드카드(%, _)를 문자열의 앞이나 중간에 사용할 경우 성능이 크게 저하될 수 있어 대용량 데이터에서는 시간이 오래 걸릴 수 있습니다.

 

반면, FTS는 대규모 텍스트 데이터를 처리하는 데 뛰어난 성능을 보이며, 자연어 처리와 관련성 기반 검색을 지원합니다. 따라서 FTS는 대량의 텍스트 데이터를 효과적으로 검색하고, 의미를 고려한 검색이 필요한 경우 유용합니다.

 

결론적으로, LIKE 연산자는 간단한 문자열 매칭에 적합하고, FTS는 대량의 텍스트 데이터를 다루고 자연어 처리 기반의 검색이 필요한 경우에 이상적입니다.

 

 

FTS와 Elasticsearch

 

FTS(Full Text Search)와 엘라스틱서치(Elasticsearch)는 모두 텍스트 검색을 위한 도구지만, 목적, 기능, 아키텍처에서 차이가 있습니다. 각기 다른 요구 사항에 맞는 강점을 제공합니다.

 

엘라스틱서치는 오픈소스 검색 엔진으로, 분산 시스템을 기반으로 다양한 형태의 데이터(텍스트, 로그, 메트릭 등)를 실시간으로 검색하고 분석할 수 있습니다. 엘라스틱서치에 대한 자세한 내용은 추후 별도로 다룰 예정이므로, 이 글에서는 간략히 설명하겠습니다.

 

엘라스틱서치는 FTS에 비해 뛰어난 자연어 처리(NLP), 관련성 기반 검색, 페이징, 집계 등 고급 검색 기능을 제공합니다. 이를 통해 더 정교한 검색이 가능해집니다. 또한 분산형 시스템으로 설계되어 클러스터 구성이 용이하고 수평 확장이 가능하여, 대규모 데이터셋을 처리하는 데 탁월한 성능을 자랑합니다.

 

결론적으로, 엘라스틱서치는 대규모 데이터 처리, 고급 검색, 실시간 분석이 필요한 환경에서 뛰어난 성능을 발휘하며, FTS에 비해 복잡한 검색 요구 사항이나 대용량 데이터를 처리하는 데 적합합니다.

 

 

마치며

 

이번 글에서는 DB 검색 성능 개선을 위한 INDEX와 FTS에 대해 살펴보았습니다. 두 기능을 적절히 활용하면 데이터베이스의 검색 성능을 크게 향상시킬 수 있으며, 복잡한 쿼리 처리에서도 빠르고 효율적인 결과를 얻을 수 있습니다. 추후에는 검색 기능 향상을 위해 레디스와 엘라스틱서치에 대해 자세히 알아보겠습니다.