TL;DR
- **Inverted Index = 검색 엔진의 심장**: 단어 → 문서 ID 리스트 매핑. 책 뒷면 색인의 디지털 버전
- **BM25 > TF-IDF**: 문서 길이 정규화 + 항 빈도 포화. Lucene/Elasticsearch의 기본 알고리즘
- **Lucene이 모든 것의 기반**: Elasticsearch, Solr, Vespa, OpenSearch 모두 Lucene 기반
- **Vector Search의 부상**: 의미 기반 검색. RAG, 추천 시스템의 핵심
- **Hybrid Search가 표준**: BM25 + Vector를 RRF(Reciprocal Rank Fusion)로 결합
1. 검색의 본질적 어려움
1.1 데이터베이스 LIKE의 한계
SELECT * FROM articles WHERE content LIKE '%redis%';
**문제점**:
1. **느림** — 100만 문서면 100만 번 비교, full table scan
2. **순서 없음** — 어떤 결과가 더 관련 있는지 모름
3. **단순 문자열만** — 어형 변화, 동의어, 오타 처리 못 함
4. **언어 무관** — "고양이"와 "고양이들"이 다른 단어
전통적 RDB는 검색에 부적합합니다. **전용 검색 엔진**이 필요합니다.
1.2 검색 엔진이 해결하는 것
| 문제 | 검색 엔진의 해결 |
|---|---|
| 느림 | Inverted Index — O(1) 단어 검색 |
| 순서 | 관련성 점수 (TF-IDF, BM25) |
| 어형 | Stemming/Lemmatization |
| 오타 | Fuzzy 매칭 (Levenshtein) |
| 동의어 | Synonym filter |
| 다국어 | Language-specific analyzers |
| 의미 | Vector embeddings |
2. Inverted Index — 검색의 심장
2.1 직관
책 뒷면의 색인을 생각해보세요:
Apple ............ 23, 47, 89
Banana ........... 12, 34
Cherry ........... 5, 67, 102
Inverted Index도 같은 원리:
"redis" → [doc1, doc5, doc100, doc234, ...]
"database" → [doc2, doc5, doc89, doc234, ...]
"cache" → [doc1, doc100, doc500, ...]
**검색 "redis AND database"**:
1. "redis"의 문서 리스트 가져오기 → [doc1, doc5, doc100, doc234]
2. "database"의 문서 리스트 가져오기 → [doc2, doc5, doc89, doc234]
3. 교집합 → [doc5, doc234]
**O(1) 단어 룩업** + 리스트 교집합. 100만 문서에서도 밀리초.
2.2 Posting List 구조
각 단어의 문서 리스트를 **posting list**라고 합니다:
"redis":
- doc1: positions=[5, 23], frequency=2
- doc5: positions=[12], frequency=1
- doc100: positions=[3, 17, 45], frequency=3
추가 정보:
- **frequency**: 문서 내 등장 횟수 (TF-IDF 계산용)
- **positions**: 문서 내 위치 (phrase 검색용)
- **offsets**: 원본 텍스트의 byte offset (highlighting용)
2.3 압축
수백만 문서 = 거대한 posting list. **압축**이 필수:
- **Delta encoding**: `[1, 5, 7, 12]` → `[1, 4, 2, 5]` (차이만 저장)
- **VByte encoding**: 작은 숫자에 적은 byte
- **PForDelta**: Lucene이 사용하는 알고리즘
- **Roaring Bitmaps**: 매우 sparse한 set에 효율적
**효과**: 원본 대비 10-20% 크기. 수십억 문서를 GB 단위에 저장 가능.
2.4 디스크 vs 메모리
전체 인덱스를 메모리에 못 담으면:
- **mmap**: OS가 페이지 단위로 자동 캐싱
- **cold posting**: 자주 안 쓰이는 단어는 디스크에서 로드
- **warm posting**: 자주 쓰이는 단어는 메모리에 캐시
**Lucene은 mmap을 광범위하게 사용** — OS의 페이지 캐시를 활용.
3. TF-IDF에서 BM25로
3.1 단순 카운트의 문제
"redis"가 들어간 문서 100개를 어떻게 정렬?
**naive**: 등장 횟수로 정렬 → 긴 문서가 무조건 위로 (불공정).
3.2 TF-IDF — 첫 번째 시도
**TF (Term Frequency)**: 문서 내 단어 빈도
TF(t, d) = count(t in d) / total words in d
**IDF (Inverse Document Frequency)**: 단어의 희귀성
IDF(t) = log(N / df(t))
- `N`: 전체 문서 수
- `df(t)`: 단어가 들어간 문서 수
**TF-IDF**: `TF × IDF`
**의미**:
- TF 높음: 이 문서에 자주 나옴
- IDF 높음: 다른 문서에는 잘 안 나옴
- 둘 다 높음: 이 문서에 매우 특징적
3.3 TF-IDF의 문제
1. **선형 TF**: 100번 나오면 50번 나오는 것의 2배 점수 → 비현실적
2. **문서 길이 무시**: 긴 문서가 자연스럽게 더 많은 키워드 포함
3. **이론적 근거 부족**: 휴리스틱
3.4 BM25 — Okapi BM25
1994년 등장. TF-IDF의 모든 문제를 해결:
BM25(D, Q) = Σ IDF(qi) × (f(qi, D) × (k1 + 1)) / (f(qi, D) + k1 × (1 - b + b × |D|/avgdl))
- `f(qi, D)`: qi가 D에 나오는 횟수
- `|D|`: D의 길이
- `avgdl`: 평균 문서 길이
- `k1`: TF 포화 파라미터 (보통 1.2~2.0)
- `b`: 길이 정규화 강도 (보통 0.75)
3.5 BM25의 핵심 속성
**1. TF 포화 (Saturation)**:
- 첫 번째 등장: 큰 점수 증가
- 두 번째: 작은 증가
- 100번째: 거의 증가 없음
**의미**: "redis가 5번 나옴 vs 1번 나옴"은 큰 차이지만, "redis가 100번 vs 50번"은 작은 차이.
**2. 문서 길이 정규화**:
- 평균보다 긴 문서는 점수 페널티
- 평균보다 짧은 문서는 점수 보너스
- `b=0.75`가 보통 최적
**3. 이론적 근거**: Probabilistic Information Retrieval 모델 기반.
3.6 왜 BM25가 25년 후에도 표준인가?
- **단순함**: 파라미터 2개 (k1, b)
- **튜닝 쉬움**: 대부분 기본값으로 충분
- **빠름**: 인덱싱 시 미리 계산 가능
- **언어 독립적**: 토큰화만 잘 하면 모든 언어
- **벤치마크 챔피언**: TREC 등 공식 벤치마크에서 강력
**Elasticsearch, Solr, Lucene, Vespa, Tantivy** 모두 BM25 기본.
3.7 BM25F — 다중 필드
문서가 title, body, tags 등 여러 필드를 가질 때:
BM25F = Σ field_boost × BM25(field)
**예시**:
- title boost: 3.0
- body boost: 1.0
- tags boost: 2.0
"redis"가 title에 나오면 body보다 3배 점수.
4. Tokenization과 Analyzer
4.1 텍스트 → 토큰
검색 엔진은 텍스트를 직접 다루지 않습니다. **토큰**으로 변환:
"Redis is a fast in-memory database!"
↓ tokenize
["redis", "is", "a", "fast", "in-memory", "database"]
↓ lowercase + stop words
["redis", "fast", "in-memory", "database"]
↓ stemming
["redis", "fast", "in-memori", "databas"]
4.2 Analyzer 구성
Elasticsearch/Lucene의 Analyzer:
Character Filter → Tokenizer → Token Filter
**Character Filter**: 원본 문자 변환
- HTML 태그 제거
- Unicode 정규화
**Tokenizer**: 토큰으로 분리
- Standard (공백 + 구두점)
- Whitespace (공백만)
- N-gram
- Korean nori, Japanese kuromoji, Chinese smartcn
**Token Filter**: 토큰 변환
- Lowercase
- Stop words 제거
- Stemming (Porter, Snowball)
- Synonym
- ASCII folding (é → e)
4.3 한국어 처리 — Nori
{
"settings": {
"analysis": {
"analyzer": {
"korean": {
"type": "custom",
"tokenizer": "nori_tokenizer",
"filter": ["nori_part_of_speech", "lowercase"]
}
}
}
}
}
**Nori의 처리**:
"한국어 형태소 분석기"
→ ["한국어", "형태", "소", "분석", "기"]
**조사, 어미 제거** → 더 정확한 검색.
4.4 색인 시간 vs 쿼리 시간 분석
**원칙**: 같은 analyzer를 양쪽에 적용해야 함.
색인: "Running shoes" → ["run", "shoe"] (stemming)
쿼리: "runs" → ["run"] (같은 stemming)
매치! ✅
만약 다르면:
색인: "Running shoes" → ["running", "shoes"]
쿼리: "runs" → ["run"]
매치 안 됨 ❌
5. 쿼리 종류
5.1 Boolean Query
{
"bool": {
"must": [
{ "match": { "content": "redis" } },
{ "match": { "content": "performance" } }
],
"should": [
{ "match": { "tags": "tutorial" } }
],
"must_not": [
{ "match": { "status": "draft" } }
],
"filter": [
{ "range": { "year": { "gte": 2024 } } }
]
}
}
- **must**: AND, 점수에 영향
- **should**: OR, 점수 boost
- **must_not**: NOT, 점수 X
- **filter**: AND, 점수 X (캐시 가능)
5.2 Phrase Query
정확한 구문 매칭:
{ "match_phrase": { "content": "redis cluster" } }
**posting list의 position 정보** 활용 — "redis"가 위치 5, "cluster"가 위치 6이면 매치.
**slop**: 단어 사이 거리 허용
{ "match_phrase": { "content": { "query": "redis cluster", "slop": 2 } } }
"redis hash cluster"도 매치 (slop=2).
5.3 Fuzzy Query (오타 허용)
{ "fuzzy": { "content": { "value": "rediis", "fuzziness": "AUTO" } } }
**Levenshtein distance** 기반:
- 1 = 1글자 차이
- 2 = 2글자 차이
**AUTO**: 단어 길이에 따라 자동
- 1-2글자: 0
- 3-5글자: 1
- 6+글자: 2
5.4 Wildcard / Prefix
{ "prefix": { "name": "redis" } } // "redis", "redis-cluster", ...
{ "wildcard": { "name": "re*is" } } // "redis", "remis", "rebis", ...
**주의**: 와일드카드는 느릴 수 있음. **N-gram 인덱스**가 더 효율적.
5.5 Range Query
{ "range": { "price": { "gte": 100, "lte": 500 } } }
{ "range": { "created_at": { "gte": "2024-01-01" } } }
**숫자/날짜용**. BKD-Tree 인덱스 사용 (Lucene 6+).
6. Lucene 내부 구조
6.1 Segment 기반 아키텍처
Lucene은 데이터를 **segment**로 저장:
- 각 segment는 **immutable**
- 새 데이터는 새 segment에
- 주기적으로 segment merge
Index/
├─ segment_001/
├─ segment_002/
├─ segment_003/
└─ segment_004/
**쓰기**: 새 segment 생성. 빠름.
**읽기**: 모든 segment 검색 후 결합.
**Merge**: 작은 segment들을 큰 것으로 통합. 백그라운드.
**왜 immutable?**: 동시성, 캐싱, 압축에 유리. Append-only는 항상 빠름.
6.2 Refresh와 Flush
| 작업 | 의미 | 시간 |
|---|---|---|
| **Refresh** | 새 데이터를 검색 가능하게 (in-memory segment) | 1초 |
| **Flush** | 디스크에 기록 (translog clear) | 30분 |
| **Commit** | 디스크 fsync | flush 시 |
| **Merge** | 작은 segment 합치기 | 백그라운드 |
**Near-real-time search**: 1초 후에는 검색 가능. 진정한 real-time은 아님.
6.3 BKD-Tree
Lucene 6+의 숫자 인덱스. K-dimensional Block Tree.
**왜?**: 숫자에 대해 효율적인 범위 쿼리.
`price >= 100 AND price <= 500` 같은 쿼리가 매우 빠름.
6.4 doc values
원본 문서를 byte offset으로 저장. 정렬, 집계, 필드 액세스에 사용.
**columnar storage** — 같은 필드의 값들이 연속 저장 → 캐시 친화적.
7. Vector Search — 의미 기반 검색
7.1 키워드 검색의 한계
**쿼리**: "강아지에게 좋은 음식"
**키워드 매치**:
- ✅ "강아지에게 좋은 음식"
- ❌ "반려견 사료 추천" (같은 의미, 다른 단어)
- ❌ "puppy food guide" (다른 언어)
키워드 검색은 **표면적 매칭**만 합니다.
7.2 Embedding 기반
텍스트를 **벡터(임베딩)**로 변환:
"강아지에게 좋은 음식" → [0.12, -0.34, 0.78, ..., 0.45] (768차원)
"반려견 사료 추천" → [0.15, -0.32, 0.81, ..., 0.42] (비슷한 벡터)
**의미가 비슷하면 벡터 거리가 가깝다**.
7.3 코사인 유사도
cos_sim(A, B) = (A · B) / (|A| × |B|)
- 1.0 = 같은 방향 (매우 비슷)
- 0.0 = 직각 (관련 없음)
- -1.0 = 반대 (반대 의미)
7.4 ANN — Approximate Nearest Neighbor
수백만 벡터에서 가장 가까운 것 찾기. 정확한 검색은 O(N) → 너무 느림.
**ANN 알고리즘**:
- **HNSW** (Hierarchical Navigable Small World) — 가장 인기
- **IVF** (Inverted File) — Faiss
- **PQ** (Product Quantization) — 압축
- **DiskANN** — 디스크 기반
**HNSW**: log N 시간, 95%+ recall.
7.5 Vector DB
| | Pinecone | Weaviate | Qdrant | Milvus | pgvector | Vespa |
|---|---|---|---|---|---|---|
| 유형 | SaaS | OSS | OSS | OSS | PG 확장 | OSS |
| ANN | HNSW | HNSW | HNSW | IVF/HNSW/...등 | HNSW | HNSW |
| 메타데이터 필터 | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ |
| 멀티텐트 | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ |
| Hybrid 검색 | ✅ | ✅ | ✅ | ✅ | 부분적 | ✅ |
**선택 가이드**:
- **간편함**: Pinecone (관리형)
- **PostgreSQL 사용 중**: pgvector
- **자체 호스팅 + 성능**: Qdrant, Milvus
- **Hybrid 검색 + 검색 엔진**: Vespa, Elasticsearch + dense vector
8. Hybrid Search — BM25 + Vector
8.1 왜 Hybrid?
**BM25만**: 정확한 키워드는 잘 찾지만 동의어, 의미를 못 잡음.
**Vector만**: 의미는 잘 잡지만 정확한 키워드(고유명사, 제품 코드)에 약함.
**Hybrid**: 두 방법 결과를 결합. **둘 다의 장점**.
8.2 RRF — Reciprocal Rank Fusion
RRF_score(doc) = Σ 1 / (k + rank(doc, list_i))
- `k`: 보통 60
- `rank(doc, list_i)`: i번째 검색 결과의 doc 순위
**예시**:
BM25 결과: [doc5, doc1, doc3, doc7, doc2]
Vector 결과: [doc1, doc3, doc8, doc5, doc4]
RRF (k=60):
doc5: 1/(60+1) + 1/(60+4) = 0.0319
doc1: 1/(60+2) + 1/(60+1) = 0.0325 ← 1위
doc3: 1/(60+3) + 1/(60+2) = 0.0319
doc7: 1/(60+4) = 0.0156
doc2: 1/(60+5) = 0.0154
doc8: 1/(60+3) = 0.0159
doc4: 1/(60+5) = 0.0154
**장점**:
- 점수 정규화 불필요
- 안정적
- 단순
8.3 Elasticsearch에서 RRF
{
"retriever": {
"rrf": {
"retrievers": [
{
"standard": {
"query": { "match": { "content": "redis cluster" } }
}
},
{
"knn": {
"field": "embedding",
"query_vector": [0.1, 0.2, ...],
"k": 50
}
}
],
"rank_window_size": 100,
"rank_constant": 60
}
}
}
**Elasticsearch 8.8+**부터 RRF 네이티브 지원.
9. 검색 품질 평가
9.1 Precision vs Recall
- **Precision**: 검색 결과 중 관련된 비율
- **Recall**: 관련된 모든 것 중 검색된 비율
Precision = relevant ∩ retrieved / retrieved
Recall = relevant ∩ retrieved / relevant
**트레이드오프**: 둘 다 높이기 어려움.
9.2 NDCG (Normalized Discounted Cumulative Gain)
순서를 고려한 점수:
- 상위에 있는 결과가 더 중요
- log 감쇠로 가중치
- 이상적 순서로 나누어 정규화 (0~1)
def ndcg_at_k(predicted, ideal, k=10):
dcg = sum((2**rel - 1) / log2(i + 2) for i, rel in enumerate(predicted[:k]))
idcg = sum((2**rel - 1) / log2(i + 2) for i, rel in enumerate(ideal[:k]))
return dcg / idcg if idcg > 0 else 0
9.3 MAP (Mean Average Precision)
여러 쿼리에 대한 평균 정밀도. 검색 품질의 단일 지표.
9.4 A/B 테스팅
실제 사용자에게 두 알고리즘 비교:
- **클릭률 (CTR)**
- **첫 클릭까지 시간**
- **장바구니 추가율** (e-commerce)
- **세션 길이**
10. 실전 — 검색 시스템 만들기
10.1 단계
1. **요구사항 분석**: 무엇을 검색? 얼마나 빠르게? 얼마나 정확하게?
2. **데이터 소스**: 어떤 문서들?
3. **인덱싱 파이프라인**: 데이터 → 토큰 → 인덱스
4. **쿼리 인터페이스**: API 디자인
5. **튜닝**: BM25 파라미터, analyzer
6. **평가**: NDCG, A/B 테스트
7. **개선**: 의미 검색 추가, hybrid
10.2 작은 시스템 (수만 문서)
- **Tantivy** (Rust) 또는 **Whoosh** (Python)
- 단일 머신
- BM25만으로 충분
10.3 중간 시스템 (수백만 문서)
- **Elasticsearch** 또는 **OpenSearch**
- 3노드 클러스터
- BM25 + 한국어 analyzer
- 주기적 재인덱싱
10.4 대규모 (수십억 문서)
- **Vespa** (Yahoo, 가장 강력)
- 또는 자체 시스템 (Google, Bing 수준)
- BM25 + Neural Ranking
- ML 기반 personalization
- 분산 인덱스
10.5 RAG용 검색
- **Vector DB** (Pinecone, Qdrant, pgvector)
- **Hybrid Search** (BM25 + Vector + RRF)
- **Re-ranking** (Cohere, Voyage)
- **Query expansion** (LLM 기반)
퀴즈
**답**: LIKE는 모든 문서의 모든 텍스트를 스캔합니다 — O(N × M). Inverted Index는 단어 → 문서 ID 매핑이 미리 만들어져 있어 단어 룩업이 **O(1)**입니다. "redis"를 검색하면 즉시 해당 단어를 포함한 문서 ID 리스트를 가져옵니다. 100만 문서에서도 밀리초. 추가로 posting list는 압축되어 있어 메모리 효율도 좋습니다.
**답**: (1) **TF 포화** — 100번 나오는 것이 1번 나오는 것의 100배 점수가 아니라 약 2배 (현실적). (2) **문서 길이 정규화** — 긴 문서가 자동으로 더 많은 키워드를 포함하는 부조리 해결. (3) **이론적 근거** — Probabilistic IR 모델 기반. (4) **튜닝 쉬움** — k1, b 두 파라미터로 제어. 25년이 지난 지금도 Lucene/Elasticsearch의 기본 알고리즘인 이유입니다.
**답**: **아닙니다**. Vector는 **의미 기반**이지만 정확한 키워드(고유명사, 제품 코드, 인용)에 약합니다. "iPhone 15 Pro"를 검색할 때 의미 검색은 "Galaxy S24"같은 비슷한 의미를 반환할 수 있지만, 사용자는 정확한 모델을 원합니다. **Hybrid Search** (BM25 + Vector)가 표준이며, **RRF (Reciprocal Rank Fusion)**로 두 결과를 결합합니다. 2024년 Elasticsearch 8.8+가 RRF를 네이티브 지원합니다.
**답**: (1) **동시성** — 락 없이 여러 스레드가 읽기 가능, (2) **캐싱** — segment가 변하지 않으면 캐시 무효화 없음, (3) **압축 효율** — 한 번 만들고 영원히 같음, (4) **단순함** — append-only는 항상 빠름. 새 데이터는 새 segment에 추가되고, 작은 segment들은 백그라운드에서 merge됩니다. 단점은 segment merge 비용과 디스크 사용량.
**답**: **순서를 고려한** 검색 품질 점수입니다. 상위 결과에 더 큰 가중치(log 감쇠), 각 결과의 관련성 점수(`2^rel - 1`)를 합산합니다. 마지막으로 **이상적 순서**(완벽한 순위)의 점수로 나누어 0~1로 정규화. NDCG@10 = 상위 10개의 NDCG. **0.8 = 매우 좋음, 0.5 = 평범, 0.3 = 나쁨**. Precision/Recall과 달리 **순위**도 평가합니다.
참고 자료
- [Lucene Documentation](https://lucene.apache.org/core/) — 공식
- [Elasticsearch: The Definitive Guide](https://www.elastic.co/guide/en/elasticsearch/guide/current/index.html)
- [BM25 원논문](http://www.staff.city.ac.uk/~sb317/papers/foundations_bm25_review.pdf) — Robertson et al.
- [Introduction to Information Retrieval](https://nlp.stanford.edu/IR-book/) — Stanford 무료 책
- [Tantivy](https://github.com/quickwit-oss/tantivy) — Rust 검색 엔진
- [Vespa](https://vespa.ai/) — Yahoo의 강력한 검색 + ML
- [Faiss](https://github.com/facebookresearch/faiss) — Facebook ANN 라이브러리
- [HNSW 원논문](https://arxiv.org/abs/1603.09320) — Malkov & Yashunin
- [Reciprocal Rank Fusion](https://plg.uwaterloo.ca/~gvcormac/cormacksigir09-rrf.pdf) — Cormack et al.
- [Sentence-Transformers](https://www.sbert.net/) — 임베딩 라이브러리
- [TREC](https://trec.nist.gov/) — 검색 엔진 벤치마크
현재 단락 (1/350)
- **Inverted Index = 검색 엔진의 심장**: 단어 → 문서 ID 리스트 매핑. 책 뒷면 색인의 디지털 버전