LIKE 조회보다 1000배 이상 빠른 부분검색
아래의 Task를 고민해보겠습니다.
상황 품번이 N개, 상품명은 M개 있다품번은 “CAMA0534A0 UTV975 DSX99” 와 같이 깨끗이 정리된 문자열이다. 상품명은 “한글 CAMA0534A0 UTV975 DSX99 한글” 이런 식으로 상품 관련된 내용과 품번에 대한 정보가 있다. 상품명에는 품번이 없을 수도 있고 잘못 입력될 수도 있다.
태스크 상품명으로부터 품번을 찾아 품번 데이터에 매핑하려고 한다. 우리가 가진 품번 데이터에 상품명이 부분일치한다면 상품명에 품번명을 할당하는 방식이다. 데이터는 대량으로 품번 360000개, 상품명 5000000개 set을 매핑해야 한다.
문제 정의
위 문제는 품번과 상품명 간의 부분 문자열 매칭을 효율적으로 처리하는 방법에 대한 고민입니다. 품번은 36만 건, 상품명은 500만 건에 이르며, 상품명에 품번이 포함되어 있을 수도 있고 그렇지 않을 수도 있습니다. 이때 품번이 포함된 상품명을 찾아 품번을 할당하고자 하는 목적이 있습니다.
이 문제의 본질은 긴 문자열 집합(상품명)에서 짧은 문자열 집합(품번)을 빠르게 찾아내는 것으로, 단순 이중 for-loop 구조로는 O(N x M)의 시간 복잡도로 인해 성능상 문제가 발생하게 됩니다. 따라서 단순히 데이터베이스로는 시간 상 어려운 점이 있습니다. 품번 데이터 전체를 상품명 하나 하나에 대입해가며 맞는 품번이 나올 때까지 for loop을 돌려야 되는 구조입니다.
특히 운영 환경에서는 상품 등록 시마다 빠르게 품번 매핑을 해야 하므로 실시간 대응이 어려울 수 있습니다. 해결 방안으로는 데이터베이스와 스크립트를 통한 메모리 기반 연산 방식이 있으며, 아래는 주요 시도 방법과 벤치마크 결과입니다.
결론
위 문제를 성능을 고려하면서 해결하고자 할 때 1회성 배치작업 뿐 아니라 운영에서도 아호코라 알고리즘을 사용하는 것이 효과적입니다. 품번 360000개, 상품명 5000000개 set을 작업할 때도 로컬 컴퓨터에도 실행 시에도 충분히 빠른 시간에 실행이 가능했습니다.
like 검색으로 단순 부분검색하는 것 대비 1000배 이상 성능이 빨랐으며 이는 데이터가 많으면 많을수록 그 격차가 벌어질 수 있습니다.
다만 운영 시에는 트라이 구조를 메모리에 올려두고 검색을 해야 하며, 추가되는 데이터가 있을 경우 배치로 업데이트 관리를 해야 하는 번거로움이 있습니다.
검색 방법에 대해서 전략적인 고민이 필요합니다. 위에 제시한 문제는 긴 문자열에서 짧은 문자열의 부분 일치를 빠르게 확인하는 방법입니다. 그러나 Fulltext index나 Elastic Search와 같이 어절 단위로 분류해서 검색결과를 찾는 방법도 가능합니다. 다만 두 검색 방식은 각기 다른 결과를 가져올 수 있는데 가장 큰 차이는 부분 검색이나 어절 단위 단어 검색이냐에 있습니다. 만약 어절 단위 단어 검색으로도 충분하다면 기존에 구현되어 쉽게 사용할 수 있는 Elastic Search cloud나 AWS의 Open search를 통해 검색하는 것도 충분히 고민해볼 수 있습니다.
사용한 방법
데이터베이스 방식
LIKE 조회: 품번을 포함하는 상품명을 검색하는 단순 방법이나 %패턴% 구조로 인해 인덱스를 제대로 활용하지 못하며, 데이터셋이 증가할수록 속도가 급격히 느려집니다.
Fulltext 검색: 단어 단위 검색이기 때문에 부분 문자열 검색에는 부적합합니다. 또한 MATCH AGAINST는 다른 테이블의 컬럼을 직접 비교 대상으로 사용할 수 없어 운영에 적합하지 않습니다.
Script 방식 (메모리 기반)
기본 이중 루프 검색: 비효율적이며, 소규모 데이터셋에서도 매우 느립니다.
Swifter 적용: Pandas apply() 방식보다 나은 결과를 보였지만, 내부에서 전체 상품명 데이터프레임을 계속 스캔하므로 병렬화 이점이 크지 않았습니다.
Pandas 벡터 연산: .str.contains()를 활용하여 성능 향상을 이루었으며, 병렬 처리 없이도 효과적입니다.
Pandas + Multiprocessing: 병렬 프로세싱을 통해 실행 시간을 대폭 줄였으며, 데이터셋 규모가 클수록 효과가 두드러집니다.
Numpy + Multiprocessing: np.char.find()를 통해 Pandas보다 빠른 성능을 보이며, 문자열 벡터 연산 측면에서 매우 효율적입니다.
아호코라식 + Multiprocessing: Trie 기반의 아호코라식 알고리즘을 활용해 가장 빠른 성능을 기록했습니다. 품번 36만 건, 상품명 500만 건의 실 데이터에서 약 26초 내에 처리 가능하였습니다.
아호코라식 알고리즘 개요
아호코라식은 Trie(접두사 트리) + FSM 기반의 다중 패턴 검색 알고리즘입니다.
시간 복잡도는 전처리 O(N), 검색 O(M)으로, 기존 O(N x M)보다 매우 효율적입니다.
실패 링크(Failure Link)를 통해 검색 중단 없이 진행할 수 있으며, 출력 링크(Output Link)를 통해 다중 결과를 동시에 반환할 수 있습니다.
검색 전략 선택 고려 사항
부분 문자열 매칭이 필수적인 경우 → 아호코라식 알고리즘이 가장 적합합니다.
상품명에 포함된 품번이 어절 단위로 잘 정리되어 있는 경우 → ElasticSearch, OpenSearch 등 Fulltext 기반 솔루션도 고려 가능합니다.
예를 들어, 품번이 공백 없이 붙어 있다면 부분 문자열 매칭이 필요하지만, 어절 단위로 잘 구분된 품번이라면 어절 단위로 역인덱싱한 검색으로 충분할 수 있습니다.
결론적으로, 본 문제의 성능 병목은 반복적인 부분 문자열 검색에서 기인하며, 아호코라식 알고리즘은 이러한 문제를 해결하기 위한 최적의 솔루션으로 판단됩니다. 운영 시에는 메모리에 Trie 구조를 상주시켜 신규 데이터 발생 시 배치로 업데이트를 수행하면 안정적인 운영이 가능합니다.
벤치마크 결과
벤치마크 환경
MacBook M1 Pro 14 / 32GB memory
벤치마크 결과
벤치마크 데이터셋 준비
품번 1000개, 상품명 10000개 set
품번 5000개, 상품명 50000개 set
품번 360000개, 상품명 5000000개 set (실 데이터)
1. 데이터베이스 - Like 조회
query code
result
데이터베이스에 저장시켜 부분 일치 검색을 하려면 Like 조회를 떠올릴 수 있습니다. 그러나 이 경우 원하는 문자열이 상품명의 중간에 있을 수 있고 Like 조회 시 LIKE '%패턴%'은 일반 B-TREE 인덱스를 제대로 사용할 수 없습니다. 그래서 Full Table Scan을 해야 합니다. 실행 결과를 보면 데이터 셋이 늘어날수록 시간이 지수적으로 증가함을 알 수 있습니다.
2. 데이터베이스 - Fulltext 검색
query code
위 쿼리 코드는 Fulltext index를 만든 후 Match Against 패턴을 이용한 풀텍스트 검색입니다. FULLTEXT INDEX는 문장을 개별 단어로 분리하여 검색하는 방식을 사용합니다. 단어 단위 검색을 하며 부분 문자열(Substring) 검색을 기본적으로 지원하지 않습니다. 즉, MATCH() AGAINST()는 LIKE '%패턴%'처럼 동작하지 않고, 전체 단어 기준으로 검색을 수행하게 됩니다. 예를 들어 위 코드에서 serial_no 값이 “A123” 이고 catalog_name에 “제품 A12345”인 경우 A123은 A12345의 부분 문자열이지만 검색되지 않습니다. 따라서 부분 문자열로 검색하는 방식으로 수행할 수 없다는 점을 염두에 두고 사용해야 합니다.
또한 사실 위 코드는 동작하지 않습니다. AGAINST에 따라오는 문자열은 정적인 문자열을 쓰거나 같은 테이블의 컬럼 값만 허용합니다. 즉 다른 테이블의 값을 동적으로 할당할 수가 없습니다. 그에 따라 SQL 쿼리만으로 해결할 수 없고 결국 for loop을 통해 상품명을 하나씩 검색해야 합니다.
아래와 같은 코드로 이 케이스에서 풀텍스트를 검색을 실행할 수 있습니다. serial_no로 상품명을 하나씩 찾기 때문에 여러 상품명을 반복해서 처리하기 위해 두 번의 for loop이(O(NxM)) 필요합니다.
code
result
결과를 보면 Fulltext로 검색을 했을 때 Script에서 for loop을 실행했기 때문에 데이터가 많아질수록 속도가 더 느려지는 것을 볼 수 있습니다. 검색 결과 역시 부분일치로 한 다른 테스트와 상대적으로 좋지 않은 결과를 가져오게 됩니다.
3. Script 기본 검색
base code
code
result
품번 1000개, 상품명 10000개 set로 실행 시에도 이미 150.6초가 소요됩니다. 이 방법보다는 like 조회를 선택하는 것이 차라리 낫습니다. 품번 5000개, 상품명 50000개 set은 따로 테스트하지 않았습니다.
4. Swifter 병렬처리 적용
code
result
swifter.apply()를 사용했습니다. 기존에 사용했던 for loop을 제거하고 swifter.apply()를 사용하여 멀티 프로세싱을 적용한 방법입니다. 그러나 find_matches()가 각 행마다 호출되므로 병렬화 이점이 사라집니다. swifter는 행(row) 단위 작업을 병렬화하는 데 최적화되어 있습니다. 그러나 현재 find_matches()는 각 품번에 대해 df_c 전체를 검색하기 때문이 효율이 떨어집니다. 즉, 벡터 연산을 한 번만 하면 되는 문제에서 apply()를 사용하면 오히려 느려지는 결과를 가져옵니다. 결과는 조금 빨라졌지만 병렬처리를 사용한 이점을 오롯이 챙겼다고 보기는 어렵습니다.
5. Pandas 벡터 연산
code
result
기존 방식이 개별 행마다 in 연산을 수행하여 매우 비효율적이었다면 Pandas 벡터 연산으로 전체 데이터를 검색하는 방법입니다. Pandas는 내부적으로 최적화된 문자열 검색 (벡터 연산, Cython 기반) 을 수행합니다. 다중 스레드와 SIMD (Single Instruction Multiple Data) 연산을 활용하여 속도를 극대화할 수 있습니다. 따라서 in 연산자를 활용한 Python for-loop 연산 보다 빠릅니다. 그 결과는 swifter 병렬처리보다 조금 더 나은 성능을 보여줍니다.
6. Pandas 벡터 연산 + Multiprocessing 병렬처리
code
result
Pandas 벡터 연산을 유지하고 multiprocessing.Pool()을 활용하여 여러 CPU 코어에서 병렬 처리할 수 있도록 코드를 수정했습니다. 그 결과로 성능이 많이 빨라진 것을 확인할 수 있습니다. 품번 5000개, 상품명 50000개 set으로도 11.9초가 소요되었습니다.
7. Pandas 벡터 연산 + Multiprocessing + Multithreading 병렬처리
code
result
이번에는 멀티프로세스에 멀티쓰레딩까지 적용한 병렬처리 방식입니다. 멀티프로세싱을 병렬로 실행한 후, 각 프로세스에서 멀티스레딩을 활용하여 검색 속도를 극대화했습니다. 더 빨라질 것을 기대했으나 속도 향상이 있지 않았습니다.
왜 이런 결과가 나왔을까요?
1) multiprocessing.Pool()은 여러 개의 프로세스를 사용하여, GIL을 우회하고 진정한 병렬 실행이 가능합니다. ThreadPoolExecutor()는 멀티스레딩을 사용하지만, Python의 GIL(Global Interpreter Lock)로 인해 동시에 한 개의 스레드만 실행됩니다.
2) executor.submit()는 비동기 처리(async)를 위해 사용되지만, 각 호출마다 추가적인 오버헤드가 발생합니다.
3) Pandas 벡터 연산(str.contains())은 자체적으로 최적화되어 있어 멀티스레딩의 이점을 거의 받지 못합니다.
4) future.result()를 호출하면 각 str.contains() 작업이 완료될 때까지 기다려야 하므로 오히려 속도가 느려질 수 있습니다.
5)I /O 작업(파일 읽기/쓰기)은 ThreadPoolExecutor가 더 유리하나 CPU 연산이 많은 본 계산에서는 큰 이점이 없습니다.
8. Numpy + Multiprocessing
code
result
멀티프로세싱을 유지하면서 Pandas의 백터방식 대신 numpy.char.find()를 사용했습니다. 그리고 그 결과는 훨씬 개선된 것을 볼 수 있습니다. 이는 Numpy의 벡터 방식에 기인합니다. NumPy는 C 기반 벡터 연산이라 Python 인터프리터의 GIL을 거의 사용하지 않습니다. 반면 Pandas .str.contains()는 multiprocessing과 함께 사용할 때 GIL의 영향을 받아 성능이 크게 향상되지 않습니다. 또한 Python 기반의 벡터 연산은 str.contains()로 실행되는데 내부적으로 re.search() 사용합니다. re.search는 정규식을 지원하나 본 알고리즘에서는 정규식을 굳이 사용할 필요가 없습니다.
9. 아호코라식 + Multiprocessing
code
result
마지막으로 오늘 소개하고자 하는 아호코라식 알고리즘입니다. 결과는 보다시피 가장 빨랐던 Numpy + Multiprocessing보다 15배 이상 빠른 성능을 보입니다. 아호코라식은 1:N 부분 검색에 있어 가장 훌륭한 알고리즘 중의 하나입니다. 트라이(Trie) + 유한 상태 기계(FSM, Finite State Machine) 기법을 활용하여 O(N x M)에서 O(N + M) 시간 복잡도로 빠르게 검색합니다.
아호코라식(Aho-Corasick) 알고리즘은 문자열 검색 알고리즘 중 하나로, 여러 패턴을 한 번에 검색할 수 있는 매우 효율적인 알고리즘입니다. 기본 원리는 트라이(Trie)와 유한 상태 기계(Finite State Machine, FSM)를 결합하여 부분 문자열 검색 속도를 비약적으로 향상시키는 것입니다. 전처리 시간 O(N)은 트라이에 저장할 패턴의 길이 총합이며 검색 시간은 O(M)으로 빠르게 이루어집니다.
Trie(트라이) 구조
여러 개의 문자열을 트리 형태로 저장하는 자료구조입니다. 각 경로는 문자열의 접두사를 표현하며, 공통 접두사를 가지는 문자열은 하나의 경로를 공유합니다. 검색 속도는 저장된 문자열 길이에 비례하여 O(N)이 됩니다.
Failure Link (실패 링크)
검색 중에 일치하지 않는 문자가 나타나면, 미리 계산된 실패 링크를 따라 이동하여 다시 검색을 시작합니다. 이러한 링크는 KMP 알고리즘의 LPS 테이블과 비슷한 역할을 합니다. 이로 인해 다시 처음부터 검색하지 않고 효율적으로 넘어갈 수 있습니다.
Output Link (출력 링크)
한 번에 여러 패턴이 일치할 수 있기 때문에, 중간 상태에서도 검색이 완료될 수 있습니다. 이러한 결과를 출력하기 위해 출력 링크를 관리합니다.
아호코라식의 동작 과정은 다음과 같습니다.
트라이 구조를 구축하여 모든 패턴을 저장한다.
실패 링크와 출력 링크를 생성하여 검색 속도를 최적화한다.
주어진 텍스트를 한 글자씩 읽어가며 상태를 이동한다.
일치하는 패턴이 있으면 결과를 출력한다.
아호코라식을 사용할 때 저장할 데이터는 이 경우 품번처럼 짧은 데이터가 좋습니다. 메모리 사용도 적게 들고 검색 결과도 트리 구조 내에서 짧은 길이의 문자열을 더 빠르게 찾아낼 수 있습니다. 대량 데이터의 부분일치를 빠르게 검색할 때는 아호코라식을 활용하는게 좋습니다.
여담으로 매칭하는 전략을 다르게 구성할 수 있습니다. 부분일치가 아닌 어절 단위 단어 검색일 경우는 데이터베이스의 Fulltext index나 Elastic Search와 같이 어절 단위로 분류해서 검색결과를 찾는 방법도 빠르게 가능합니다. 두 검색 방식은 각기 다른 결과를 가져올 수 있는데 그 전략이 부분일치 검색인지 어절 단위 단어 검색인지의 차이에 있습니다.
예시
상품명: 여성 오버사이즈 크루넥 로컬 허니 맨 US22WI0DBW00JE S919Y VINTAGEWHITE
품번: US22WI0D BW00JE S919Y
검색 결과
부분일치 검색에서는 공백을 제거한다면 US22WI0DBW00JE S919Y와 US22WI0D BW00JE S919Y가 일치함을 찾아낼 수 있으나, 어절단위 검색은 ‘US22WI0DBW00JE’을 찾아낼 수 없습니다. 상품명에 사용되는 품번이 충분히 잘 정제되어 있다면 Elastic Search로도 충분히 관리가 가능할 것이라 생각됩니다.
