요약먼저


목표

몇천만건의 데이터를 바탕으로 ES없이 MySQL만으로 검색엔진 구현


구현 방식

1. 초기에는 LIKE '%keyword%' 방식으로 시작하여 Full Table Scan으로 인한 성능 문제를 확인 할 예정

2. 이후 인덱스 최적화, FULLTEXT 인덱스 적용을 거칠 예정

3. 한국어 형태소 분석의 한계에 부딪히고 이를 해결하기 위해 Komoran 형태소 분석기를 연동하고 역색인 테이블을 직접 설계,  BM25+ 스코어링 알고리즘을 구현예정

4. 검색 품질 향상을 위해 동의어 처리, 구절 검색, PageRank, 앵커텍스트 기반 랭킹을 추가예정

5. 성능 최적화를 위해 COUNT 추정치 적용, 페이지네이션 제한, 역색인 압축, 캐싱 등을 적용 예정


결과 

각 단계마다 k6 부하테스트로 평균 응답시간, P95/P99, TPS, CPU/메모리 사용률을 측정하여 개선율을 정량적으로 검증 예정

최종적으로 단일 서버 환경에서 실용적인 검색 성능을 확보했으며, 이후 분산 시스템으로 확장할 예정


------

(글이 너무 많아질 것 같아서 검색에 관한 것만 적어둠)


한국어 위키피디아 216만건 + 영문 위키피디아 2,528만건


데이터를 기반으로 다국어 검색엔진을 구현하고 단계별 성능 최적화를 구현하는게 목표


초기 구현에서는 %keyword%로 검색.


매 검색마다 Full table scan 이 발생하여 평균 응답시간이 ???ms에 달하고

CPU 점유율은 ???에

메모리 점유율은 ???% 수준으로 높아


동시 사용자 증가 시 병목 현상이 예상되는 과정


이를 해소하기 위해 성능 최적화 프로젝트 진행


---


v1모델. 1단계


기본 검색기능 구현 (LIKE '%keyword%')

검색어 자동완성 기능 구현 (LIKE 'prefix%')


테이블 설계하고 약 2800만건에 달하는 위키피디아 데이터 한곳에 다넣기.


자동완성 예상 쿼리




예상 한계점 : 

prefix%는 인덱스를 타지만 여전힌 ㅡ림

제목만 검색 가능(본문 키워드 자동완성 불가)

인기도 기반 정렬 시 추가 정렬 비용 발생


NOTE : 역인덱스 term 기반 자동완성으로 개선 , 캐싱 적용, 나중에 분산캐시로 확장



Baseline 부하테스트 진행


k6 스크립트로


1. 평균 응답시간

2. p95 응답시간

3. p99 응답시간

4. TPS

5. 에러율

6. CPU 사용률

7. 메모리 사용률  측정


추가로 GC 시간이나 DB 커넥션 수도 지표가 될 수 있음


---


v1.모델 2단계


모니터링 구축


performance_schema 설정

slow_query_log 설정

모니터링 쿼리 스크립트 작성

Baseline 측정 및 기록

---


v1.모델 3단계


like 검색의 full table scan 문제 대응


목표 (2개)


1. 느린 쿼리 식별 및 원인 분석

2. 실행 계획 분석


문제

검색 기능 초기 구현 시 LIKE %keyword% 방식으로 본문 검색을 구현


예상 쿼리






2,744만 건 테이블에서 매 검색마다 Full Table Scan이 발생하여 평균 응답시간 ???ms, CPU 점유율 ???%로 서비스 품질에 심각한 영향을 미침


특히 동시에 여러 검색 요청이 들어올 경우 CPU 자원 경합으로 인해 전체적인 응답 지연이 발생하고, 무거운 검색 쿼리 수행 시 다른 CRUD 작업까지 영향을 받는 병목 현상이 관찰되었음


라는 시나리오 작성.



분석


performance_schema 쿼리 통계 조회:






조회 결과 측정


EXPLAIN ANALYZE 결과 측정


- type: ALL (Full Table Scan)

- rows: 27,440,000 (전체 행 스캔)

- key: NULL (인덱스 미사용)

- Extra: Using where


이런식으로 나올 듯


원인 분석


LIKE 검색에서 와일드카드가 앞에 위치(%keyword)하면 B-Tree 인덱스를 활용할 수 없어 전체 테이블을 스캔해야 합니다.

본문 검색 특성상 부분 문자열 검색이 필수이므로 LIKE 방식으로는 근본적인 해결이 불가능


성과


문제 쿼리 수 : ??? <- 식별 완료

주요 병목 : LIKE Full Scan <- 원인 파악 완료


---


v1.모델 4단계


인덱스 최적화


목표


단일/복합 인덱스 설계

커버링 인덱스 적용

Before/After 적용


네임스페이스별 문서 조회 기능에서 특정 조건에서 간헐적으로 성능이 급격히 저하되는 현상이 발생

[네임스페이스란 위키에 있는 데이터 분류로 본문,토론,사용자,사용자 토론 이런식으로 나눠짐]






동일한 쿼리임에도

네임스페이스의 값에 따라 ???ms ~ ??? ms 까지 큰 편차를 보임


분석


네임스페이스별 데이터 분포 조사





데이터가 namespace(0) 본문 <- 집중되어 있어서 심각한 불균등 분포를 보임





실행 계획 비교 



웡닌분석


MySQL 옵티마이저는 통계 정보를 기반으로 실행 계획을 선택.

namespace = 0 의 경우 전체 데이터의 ???%를 차지

인덱스를 사용하는 것보단 FULL SCAN 이 더 효율적이라고 판단


그러나 실제로는

ORDER BY + LIMIT 조합에서 인덱스를 활용하면 전체 스캔 없이 상위 20개만 빠르게 조회 가능

옵티마이저의 판단이 최적이 아님



해결


복합 인덱스 추가, 쿼리 힌트 적용


성과


실행계획이 안정화되어 namespace 값에 관계없이 일관된 응답시간 보장 가능


----


v1.모델 5단계


목표

1. 비효율적인 쿼리 패턴 개선 (서브쿼리 최적화)

2. 페이지네이션 최적화 (OFFSET -> OFFSET + 페이지 제한 (LIMIT + 1))

3. 검색 결과 수 최적화 (COUNT -> 추정치)



문제 1 : 서비스 초기에는 문제가 없었으나, 사용자들이 뒤쪽 페이지를 조회하는 경우가 증가하면서 페이지 번호가 증가할수록 응답시간이 급격히 증가하는 현상 시나리오


Note. 페이지별 응답시간 측정


원인 분석

MySQL의 OFFSET 처리 방식은 OFFSET + LIMIT 개수만큼의 행을 읽은 후 앞의 OFFSET 개수만큼 버리는 방식으로 동작

따라서 OFFSET이 커질수록 불필요하게 읽는 행 수가 증가하여 성능이 저하하는 문제


해결 : 최대 페이지 수 제한


이유 : 1. Deep pagination은 성능 저하의 주요 원인

2. 사용자의 90%는 1~3페이지에서 결과를 찾음

3. 50페이지 이후 결과는 거의 조회되지 않음



문제 2: 카운트 병목


총 N개 결과 표시를 위해 매 검색마다 COUNT() 쿼리가 실행


몇천만건 테이블에서 COUNT(*)는 Full Table Scan이 발생하여 단일 쿼리만으로 ???ms가 소요


구글의 해결책 참고


구글 검색에서 "약 OO개 결과"라고 표시되는 숫자는

정확한 COUNT가 아닌 추정치

페이지를 넘기면 결과 수가 바뀌는 현상도 이 때문


방법1.

information_schema 활용 (테이블 전체 건수)





즉시 응답함. 단 INNODB는 추정치


방법2.

역색인 구현 후에는 df 합계로 추정

term_stats.df 를 활용하여 검색 결과 수를 추정





df는 해당 term이 등장하는 문서 수임


예시로


삼성전자 검색 시


mind(df("삼성"), df("전자")) = min(15000, 8000)  = 약 8000개


mysql로 만드는거임



방법3.

상한선 설정 + 페이지 수 보정




정확한 COUNT가 필요 없는 이ㅠ


1. 대부분의 사용자는 1~3페이지에서 원하는 결과 찾음

2. 정확히 1000만개 vs 100만개 -> 사용자 경험 차이 없음

3. COUNT() 제거로 검색 응답시간 ???% 개선


성과


조회 시간 , 정확도 ,사용자 체감(동일)


--


v1.모델 6단계


목표 : 1. LIKE -> FULLTEXT 전환

2. 한국어/영어 검색 특성 확인

3. FULLTEXT의 한계 파악



수행결과 해결시도


1. FULLTEXT 인덱스 적용


결과 응답시간 , rows_examined 확인


2. 영어 검색 결과

(MYSQL FullTEXT는 공백 기반 토큰화를 사용함. 영어 검색은 상대적으로 잘 작동함)


단 영어 FULLTEXT도 한계 존재


1. 어간 추출 미지원

2. 동의어 처리 불가

3. 불용어 커스텀마이징 제한


3. 한국어 검색 결과


FULLTEXT 인덱스 적용으로 성능은 개선되엇으나 한국어 형태소 분석 지원x

검색 품질 문제 발생


한국어 FULLTEXT 한계


1. 형태소 분석 미지원 (공백 토큰화만 가능)

2. 조사/어미 처리 불가

3. 복합어 분해 불가


결론


영어/한국어 통합 검색을 위해 역색인 직접 구현 필요


---


v1.모델 7단계


목표 : 1. 형태소 분석기 연동(Komoran) 

2. 역색인 테이블 설계 및 구현

3. BM25 스코어링 구현






NOTE : 위 설계는 term,page_id 를 PK로 하여 문서당 1행을 저장.

대안-> doc_ids LONGTEXT에 posting list 전체를 저장하는 방식도 잇지만 몇천만건 규모에서는 고빈도 단어의

posting list가 수십만 건에 달할 수 있어 현재 설계가 더 적합

단 고빈도 단어 검색 시 많은 행을 읽어야 하니 조인 최적화가 필수


BM25 공식


score(D,Q) = Σ IDF(qi) × (tf × (k1 + 1)) / (tf + k1 × (1 - b + b × |D|/avgdl))


- IDF(qi) = log((N - df + 0.5) / (df + 0.5))

- k1 = 1.2, b = 0.75



하지만 난 위키피디아 문서라

문서 길이 편차가 클거라 예상

b25+를 적용하기로함


// BM25+ 공식 (Lv & Zhai, 2011)

score_BM25+(D,Q) = Σ IDF(qi) × ((tf × (k1 + 1)) / (tf + k1 × (1 - b + b × |D|/avgdl)) + δ)


- δ = 1 (기본값): 긴 문서도 최소 점수 보장


b25+를 사용 시 검색 누락을 방지할 수 있음



검색 쿼리






%Note : 리스트를 다룰 때 primitive타입을 사용하면 리팩토링 필요 x



왜 중요한가?


1. CPU는 캐시 라인 (64비트) 단위로 메모리 읽음

2. 참조 타입은 실제 데이터가 다른 메모리에 있어 캐시 미스 발생

3. 몇천만건 문서의 포스팅 리스트를 순회할 때 성능 차이가 큼


컬렉션도 ArrayList 선호 (연속 메모리)

List<PostingEntry> postings = new ArrayList<>();  // O(1) 랜덤 접근


LinkedList는 피하기 (노드마다 포인터 -> 캐시 미스)

List<PostingEntry> postings = new LinkedList<>();  // 느림



%% 중요 : 역색인 적용 후 부하테스트 진행


역색인 + BM25는 핵심 변경점이니 부하 테스트로 동시 사용자 환경에서의 성능을 측정


평균 응답시간,p95 ,p99 등등


개선율 확인


현재 v1의 문제점


제목만 검색 가능

'인공지능'을 입력해도 AI 관련 문서 추천 불가


자동완성 v2 개선


v1. like 방식 v2. 역인덱스 방식

검색 범위, 제안어 품질, 응답시간 비교


note :  Caffeine 캐싱, redis 분산 캐시


쿼리 확장 : 동의어 처리


사용자가 ai를 검색했을 때 인공지능도 같이 검색되도록 쿼리를 확장







1. 자바단에선 원본 쿼리를 동의어로 확장

2. BM25 검색에 적용

3. 자동 동의어 추출(선택)

위키피디아의 리다이렉트 정보를 활용하여 동의어를 자동 추출


쿼리 확장 시 주의사항


1. 동의어가 많으면 term 수 급증 (예상 해결 안 : 동의어 개수 제한)

2. 의미 변질 "Apple" 사과 애플 회사 <-  (에상 해결 안 : 문맥 기반 동의어 선택)

3.  term 수 증가 -> posting list 조회 증가 (예상 해결 : 동의어에 낮은 가중치 : 캐싱 적용)


쿼리 확장 시 효과 측정


확장 전 결과 수 , 확장 후 결과 수 , 정확도 변화 측정


note : 쿼리 확장은 재현율은 높이지만 정밀도가 떨어질 수 잇음. 최적의 가중치 조절해야함


Query Understanding (쿼리 이해) 적용


사용자 쿼리를 분석하고 의도를 파악하여 검색품질을 높이는 전처리 단계


출처 : https://wikidocs.net/blog/@newyark/6765/


쿼리 재작성, 오타 교정, 복합어 분리, 검색 의도 파악, 개체명 인식 기법


Note : 현재 적용 안하고 기본 검색 기능 안정화 후, 검색 품질 개선 단계에서 점진적으로 도입

----


자동완성,검색 v2 모델


8. 구절 검색 구현


목표 : 삼성전자 반도체 <- 연속된 단어로 검색 

, positions 필드 활용,

단어 간 거리 기반 점수 계산


구절 점수 공식

proximity_score = 1 / (1 + distance)


distance: 단어 간 위치 차이

연속(distance=1): 0.5점

근접(distance=2~5): 0.2~0.33점

원거리(distance>10): 낮은 점수




작업 항목


1. positions 필드 인덱싱

2. 구절 점수 계산 로직 구현

3. BM25 + 구절 점수 결합


결과


BM25만 , BM25 + 구절 점수


'정확도 비교'


---

자동완성,검색 v2 모델

9. 동적 역색인 관리


목적


1. 문서 crud시 역색인 실시간 갱신

2. 삭제 처리(무효화 목록)

3. 가비지 컬렉션


문서 추가시



문서 삭제 시 (무효화 목록 방식)


가비지 컬렉션으로 매일 새벽3시


1. 삭제된 문서 역색인 제거

2. term_stats에서 df 재계싼

3. deleted_pages 비우기


수행 결과


1. 문서 1건 추가, 문서1건 샂게, 가비지컬렉션 

소요시간 측정


---

자동완성,검색 v2 모델

10. 색인 압축


목표


1. 역색인 저장 공간 최적화

2. Variable Byte Encoding 구현

3. 압축률/복호화 성능 측정

4. 메모리/디스크 트레이드오프 분석


예상 트레이드오프 포인트


1. 포스팅 리스트 크기 vs 검색 속도

2. 캐시 크기 vs 히트율

3. 인데스 갱신 빈도 vs 검색 성능


예상 선택


:


고빈도 term -> 포스팅 리스트를 메모리에 캐싱

저빈도 term -> 디스크(MYSQL)에서 직접 조회

positions 필드 -> VBite 압축으로 저장 공간 절감


압축 알고리즘 종류

VByte,Simple9,PForDelta,,Simple8b,Snappy/LZ4 등 있음


검색 시 매번 positions를 해제 해야 함(해제 속도가 제일 중요함)

VBite 선택할 듯


압축/해제 CPU 비용 측정할 듯


--


11. 페이지 랭크 + 앵커 텍스트 구현


목표

1. 위키 내부 링크 추출

2. 앵커 텍스트 추출 및 역색인 반영

3. 페이지랭크 점수 계산

4. BM25 + 페이지랭크 + 앵커 점수 결합


하는 이유?


링크가 많이 걸려져있는 페이지일 수록 중요도가 높은 문서



final_score = bm25_score * 0.5

            + anchor_score * 0.2

            + log(1 + pagerank * 1000) * 0.15

            + log(1 + view_count) * 0.1

            + log(1 + like_count) * 0.05


성과 비교


BM25만 -> P@10 -> 비고

BM25+ +인기도

b25+ + pageRank

b25+ + 앵커


전체결합



--

12. 검색 품질 평가


목표


1. 테스트 쿼리 셋 구축

2. 정밀도/재현율 측정

3. P@10, MAP 계산


작업 항목


1. 테스트 쿼리 셋 구축

2. 평가 코드 구현

3. 각 단계별 검색 품질 측정


검색방식

LIKE

FULLTEXT

BM25+

BM25+ +구절

최종





--

13. 역색인 조인 최적화




목표


1. 고빈도 단어 검색 시 성능 개선

2. 쿼리 분리 및 애플리케이션 레벨 조인


작업 항목


1. 고빈도 단어 식벽

2. 쿼리 분리 로직 구현

3. 커버링 인덱스 추가 


예상 문제


BM25+ 검색 구현 시 역색인 테이블과 문서 테이블 조인하는 쿼리에서 성능 문제가 발생





검색어 토큰이 많거나 고빈도 단어(df가 높은 단어)

가 포함될 경우 응답시간이 ???ms까지 증가


예상 해결


쿼리 분리 및 애플리케이션 레벨 조인 

커버링 인덱스 적용



성과 측정.



상위 K개 결과만 필요한 경우..

모든 posting list를 완전히 순회하지 않고도 결과 얻을 수 있음


1. ㅈWNAD 알고리즘


2. MaxScore 알고리즘


3. BMW 알고리즘


적용 판단 기준


1. 검색 결과가 상위 K개만 필요한가? -> yes - > WAND/MaxScore

2. 고빈도 term이 검색어에 자주 포함되는가? -> Yes -> MaxScore 적합

3. positing list가 메모리에 올라와 있는가? Yes -> WAND/MxScore


쿼리 분리 + 애플리케이션 레벨 조인이 MYSQL 환경에서 실용적

WAND/MaxScore는 posting list가 메모리에 있을 때 효과적


---


14. 캐싱


목표


1. 로컬 캐시 - caffeine

2. 캐시 적중률 측정

3. TTL/LRU 정책 적용


이 단계에선 단일 서버 완경의 로컬캐시를 구현



캐싱 적용 후 검색,자동완성 V3 모델이 완성될듯.



---


15. 검색 로그 기반 자동완성 고도화


이 기능이 추가되면 V3.5 모델로 업그레이드 할 정도의 고도화 작업


--


16. 부하 테스트 및 최종 평가


---


17. 여기서부턴 분산시스템으로 들어갈 듯




디씨 글 제한걸려서 걍 17이후도 있는데

17까지만 적었고 14부턴 걍 요약해서 적음