[DataBase] 검색은 어떻게 작동할까?

검색창을 보고 "검색 기능은 어떻게 작동하는걸까?" 라는 의문이 생겼습니다.

그래서 검색을 하면 백엔드 서버에서 어떻게 가져오는지에 대해 조사를 해보았습니다.

작은 서비스의 경우

작은 서비스의 경우에는 데이터가 적어서 성능 문제가 거의 없기 때문에 데이터베이스에서 직접 검색합니다.

LIKE 사용

SELECT * FROM user WHERE name LIKE '%인간%';

대신 이 방식은 앞에 %가 있으면 인덱스를 사용을 못해서 처리 시간이 느려집니다.

FULLTEXT 사용

SELECT id, name,
    MATCH(name) AGAINST ('인간' IN NATURAL LANGUAGE MODE) AS score
FROM user
WHERE MATCH(name) AGAINST ('인간')
ORDER BY score DESC
LIMIT 10;

user 테이블의 name 칼럼을 대상으로 자연어 검색(NATURAL LANGUAGE)을 수행해서 '인간' 이라는 검색어와의 관련성 점수(score)를 계산합니다.

큰 서비스의 경우

큰 서비스의 경우에는 데이터베이스에 엄청난 양의 데이터가 존재하기 때문에 검색마다 데이터베이스에서 직접 검색을 하면 매우 처리가 느립니다.

그래서 사용하는 방식이 바로 단어가 들어간 문서 목록을 미리 만들어두는 역색인(Inverted Index) 구조입니다.

ex1: "개발자가 되고싶은 인간"
ex2: "백엔드 개발자"
ex3: "개착한 인간"

 

// 역색인
"개발자": [ex1, ex2]
"인간": [ex1, ex3]
"백엔드": [ex2]

이런식으로 역색인이 있다면 "개발자 인간"을 검색한다면,
개발자 목록 ∩ 인간 목록으로 검색해서 공통 문서인 ex1을 찾을 수 있습니다.

질의 처리

1. 전처리

사용자가 입력한 문자열을 표준화한 뒤 검색을 합니다.

• 대소문자 통일 : Hello -> hello
• 특수문자 제거 : Hello!! -> Hello
• 불용어 제거 : "은/는/이/가"와 같이 의미 없는 단어 제거

2. 토큰화

검색어를 단어 단위로 나누ㅂ니다.

• 영어 : 공백 기준
  "Hello world" -> [Hello, world]
• 한글 : 형태소 분석기 이용
  "검색을 한다" -> [검색, 하다]

3. 질의 해석

검색어가 단순 단어 모음인지, 연산자가 있는지 구분합니다.

• Boolean Query (AND/OR/NOT)
  "헬로 AND 월드" → 두 단어 다 들어간 문서
  "헬로 OR 월드" → 둘 중 하나만 들어간 문서
  "헬로 -코틀린" → "헬로" 포함, "코틀린"은 제외
• Phrase Query (문구 검색)
  "헬로 월드" → 두 단어가 연속으로 등장해야 함

이것들은 구글 검색에 실제로 사용이 되고 있습니다.