Django - Inverted Index로 검색하기

1. filter로 검색 시의 문제점

장고 프로젝트에서 어떤것을 검색하는 것을 구현해야 할 때 filter()를 많이 사용하고, 가장 편한 방법이다.

하지만 이런 방식은 많은 문제점이 있다.

• db index 사용 불가능
  • filter() 에서 __contains를 사용하게 되면 LIKE 문이 실행되는데 이 경우는 Full Scan을 한다.
  • LIKE% (__startwith)를 사용하는 경우는 제외
• 제대로 된 검색이 불가능
  • 쿼리 한 키워드가 완벽히 일치해야지 검색된다.
  • 단어별로 검색이 불가능

여러 가지 이유로 검색엔진을 구현해서 검색기능을 사용하는 게 좋은 방법이다.

검색엔진에선 대표적으로 역인덱스(inverted index)를 사용하는 방법이 있다.

 

2. 역인덱스

역인덱스란, 각 단어들이 어떤 문서에 저장되어 있는지를 나타내는 인덱스이다.

일반 인덱스는 id -> 문서 방향으로 인덱스를 매핑한다. 1번에는 김밥, 2번에는 라면이 있다는 걸 알려준다.

역인덱스는 김밥이라는 단어는 1, 5 6번에 있고, 라면이라는 단어는 2, 9번에 있다는걸 알려준다.

이렇게 역인덱스는 인덱스와 반대로 어떤 내용이 몇번째 문서에 있는지 알려준다.

 

역인덱스를 만들기 위해선 토큰화 작업을 해야 한다.

사용자의 질문은 문장으로 올 텐데, 이 과정에서 텍스트를 단어로 분리하고, 필요 없는 단어를 제거하는 토큰화 작업이 필요하다. 

"국밥에 피순대는 진리"를 토큰화를 하면 ["국밥", "피순대", "진리"] 정도로 토큰화를 시킬 수 있다.

 

3. Full Text Search 구현 - PostgreSQL

class Food(models.Model):
    name = models.Charfield(max_length=20)
    search_vector = SearchVectorField(null=True)
    
    class Meta:
        indexes = [
            GinIndex(fields=['search_vector']),
        ]

search_vector 필드를 만들고 테이블에 postgres의 ginindex를 적용시키면 된다.

기존 데이터들의 search_vector를 초기화하려면 update문을 실행시키면 된다.

>>> from django.contrib.postgres.search import SearchVector
>>> from food.models import Food
>>> 
>>> Food.objects.update(search_vector=SearchVector('name'))
(0.016) UPDATE "food" SET "search_vector" = to_tsvector(COALESCE("food"."name", '')); args=('',); alias=default
9

실제 테이블을 확인해 보면 인덱스가 생성되었다.

 

4. filter() vs GinIndex

기존의 filter(), contains를 사용하면 Sequential Scan 즉 테이블의 데이터를 Full Scan을 한다.

>>> food = Food.objects.filter(name__contains='초밥')
>>> food.explain()
(0.008) EXPLAIN SELECT "food"."id", "food"."service_user_id", "food"."diet_id", "food"."name", "food"."weight", "food"."calories", "food"."image", "food"."search_vector" FROM "food" WHERE "food"."name"::text LIKE '%초밥%'; args=('%초밥%',); alias=default
"Seq Scan on food  (cost=0.00..336.19 rows=679 width=85)\n  Filter: ((name)::text ~~ '%초밥%'::text)"
>>>

 

목데이터를 많이 넣고 GinIndex를 사용해서 조회를 하면 인덱스를 사용하는 걸 볼 수 있다.

>>> search_query = SearchQuery('초밥')
>>> food = Food.objects.filter(search_vector=search_query)
>>> food.explain()
(0.002) EXPLAIN SELECT "food"."id", "food"."service_user_id", "food"."diet_id", "food"."name", "food"."weight", "food"."calories", "food"."image", "food"."search_vector" FROM "food" WHERE "food"."search_vector" @@ (plainto_tsquery('초밥')); args=('초밥',); alias=default
"Bitmap Heap Scan on food  (cost=102.28..106.54 rows=1 width=85)\n  Recheck Cond: (search_vector @@ plainto_tsquery('초밥'::text))\n  ->  Bitmap Index Scan on food_search__8006ed_gin  (cost=0.00..102.28 rows=1 wih=0)\n        Index Cond: (search_vector @@ plainto_tsquery('초밥'::text))"
>>>

 

Full scan은 336의 비용이 들지만 Index Scan은 106 정도의 비용이 드는 것을 보면 약 3배 차이가 나는 것을 볼 수 있다. 이 차이는 데이터셋이 점점 커질수록 효과가 더 커질 것이다.

 

5. 한글 Full Text Search

뽀로로의대모험 ->  뽀로로 의대모험 or 뽀로로의 대모험

한글은 워낙 특이해서 토큰화를 하기 애매한 상황이 많이 발생한다. 위에 예시에도 단어를 어떻게 나누냐에 따라서 뜻이 완전히 달라지기 때문에 토큰화를 할 방법을 정할 필요가 있다.
이 방법을 해결하기 위해서 Postgres의 익스텐션인 pg_bigm을 많이 사용한다.

pg_bigm 익스텐션은 2-gram 방식을 사용하여 토큰화를 한다.

뽀로로의 대모험을 2-gram 방식으로 토큰화를 하면 이런 결과가 나온다.

"뽀로로의 대모험" -> ["뽀로", "로로", "로의", "의대", "대모", "모험"]

이런 방식은 토큰화가 애매한 언어들에게 많이 사용되는 방식으로 한글에서도 많이 사용된다.

적용 방식은 모델 메타클래스에 인덱스를 수정하면 된다.

    class Meta:
        db_table = 'food'
        indexes = [
            GinIndex(name='food_name_gin_idx', fields=['name'], opclasses=['gin_bigm_ops']),
        ]

 

6. 결론

inverted index를 사용하면 검색이 더 정확히 되고 3배 정도 비용을 아낄 수 있기 때문에 한 번쯤 사용해 보면 좋을 것 같다.