레이블이 full-text search인 게시물을 표시합니다. 모든 게시물 표시
레이블이 full-text search인 게시물을 표시합니다. 모든 게시물 표시

2020년 5월 20일 수요일

IR - Inverted Index(역색인) 컨셉

정보검색(IR)에서 다루는 내용중에 하나인 역색인은 검색엔진이나 혹은 데이터베이스에서 많이 언급된다.

단어(term)가 등장하는 문서(Document)를 찾기 위해 Inverted Index가 고안되었다.

예를 들어 SQL Server에서는 다른 DB와 마찬가지로 컬럼에 적절한 인덱스를 생성하는 경우는 많이 봤을 것이다. 하지만 컬럼이 BLOB Type으로 정의되고 여기에는 책의 내용, 신문 기사 내용, 노래 가사같이 Document가 담겨 있을 수 있다. 그럼 이 컬럼에서는 어떤식으로 내용을 빠르게 찾을 수 있을까?

전에 포스팅한 내용 참고하면 좋을 것 같다. (SQL Server Full-Text Search)
https://parksuseong.blogspot.com/search?q=Full+Text+Search

그럼 색인(Index)와 역색인(Inverted Index)의 차이는 무엇인가?

Inverted Index란 Term의 집합을 dictionary, Term이 등장하는 문서들의 집합을 posting이라고 하면 Dictionary와 posting을 Vector화 하면 찾고자 하는 단어가 어떤 문서에서 등장하는지 쉽게 찾고자 고안되었다. 쉽게 생각하면 목차(색인)와 비슷하지만 동작하는 방식이 조금 다를 뿐이다. 책의 내용이 끝나고 맨 뒤에 단어들이 나와있고 이 단어가 몇 페이지에 나오는지를 알려주는 것을 볼 수 있는데 이것이 Inverted Index(역색인)이다. 즉 Term을 가지고 Document를 찾는 것이다.

Inverted Index를 만드는 방법은 다음과 같다.

1. 문서에서 등장하는 단어(Term, 혹은 token)를 구분해서 리스트를 만든다. (tokenization)
어떠한 Term이 어떤 Doc에 나오는지 찾는 과정이다.

2. 검색 시 무의미한 단어들은 제거하고(조사, 관계사 등) 대소문자, 과거형, 복수형 등을 일반화(Nomalization)시켜주는 과정을 거친다. Stop words, Equivalence class, Lemmatization, Stemming 등을 사용할 수 있다. 언어라는게 근원적으로 룰이니까 뭔가 룰베이스적인 처리가 필요하겠다.

3. Posting을 만든다.(Term, DocID)


4. posting을 sorting한다.

sorting 결과 중복되기도 하고, docID만 다른 것이 존재하는 Term들이 보인다.

5. term의 frequency를 계산하고 Posting을 list로 만든다.
(BRUTUS -> [1,2,4,11] 이런식으로 BRUTUS는 doc1, doc2 doc4 doc11에 등장)


6. 5번까지 작업하면 term List가 dictionary가 되고(dictionary 파일에 저장), document list가 posting list가 된다(이것도 posting 파일에 저장). 그럼 dictionary와 posting이 벡터라고 치면 dictionary를 통해 document를 쉽게 검색할 수 있게 된다.





기본적인 컨셉(?)만 간단하게 정리했다.

2019년 5월 19일 일요일

SQL Server Full-Text Search Using AdventureWorksDW2017

SQL Server의 전체 텍스트 검색 기능을 써보자.

일반적으로 컬럼에 인덱스를 만들면 되지 않느냐 라고 반문할 수도 있지만 예를 들어서 컬럼이 varchar(8000)이고 책, 혹은 신문 기사의 전체 내용이 들어간 경우 인덱스를 만드는 의미가 없어진다. 가령 content varchar(max)라는 컬럼에 인덱스를 만들고 like '%human%'을 조회할 경우 아무런 효과를 볼 수 없기 때문이다.

이런 경우 전체 텍스트 인덱스를 생성해서 키워드 별로 조회할 경우 효과를 볼 수 있으며 일반 인덱스는 테이블에 여러개를 생성할 수 있지만 전체 텍스트 인덱스는 테이블 당 1개만 생성 가능하다.

전체 인덱스는 varchar, text, image, xml, filestream 등의 컬럼 타입에 생성이 가능하고 테이블에 PK나 Unique key가 반드시 존재하여야 한다.

전체 텍스트 인덱스는 초기에 전체 채우기를 하고 이후에 diff 기반 채우기나 timestamp 기반 증분 채우기를 사용한다.

또한 중지 단어 및 중지 목록을 지정할 수 있는데 검색할 필요가 없는 단어를 제외시킬 수 있다. 예를 들어서 '반드시', '꼭', '너무' 등 검색할 필요가 없는 단어를 사용할 수 있다.

전체 텍스트 검색 기능을 사용하기 위해서는 검색을 위한 전체 텍스트 및 의미 체계 추출 기능을 설치해야한다.


설치 후에 구성 관리자에서 SQL Full-text Filter Daemon Launcher를 실행한다.


샘플 DB를 통해 간단하게 성능 테스트를 해보도록 하자.

데이터는 AdventureWorks DW 2017 을 사용하였고 아래 링크에서 다운받아서 복원했다.
https://docs.microsoft.com/ko-kr/sql/samples/adventureworks-install-configure?view=sql-server-2017

AdeventureWorksDW2017.dbo.FactAdditionalInternationalProductDescription 테이블이 예제로 쓰기에 적당해보인다.
PK 제약조건은 PK_FactAdditionalInternationalProductDescription_ProductKey_CultureName이고 ProductDescription 컬럼의 내용을 조회하는 것을 목표로 해본다.

현재 ProductKey + CultureName이 PK다.

-- 데이터 내용


SELECT *
FROM [AdventureWorksDW2017].[dbo].[FactAdditionalInternationalProductDescription]
where ProductDescription like '%헤드%'

쿼리를 실행한 실행계획은 다음과 같다.

Clustered Index Scan, 즉 Table Scan을 한 것과 같으며 테이블 전체를 조회하였다.
(읽은 행 수가 15168행으로 전체를 다 읽었다.)

이제 전체 텍스트 인덱스를 생성하여 비교해보자.

-- 카탈로그 생성(카탈로그가 저장될 공간)
CREATE FULLTEXT CATALOG TestCatalog AS DEFAULT

그리고 전체 텍스트 인덱스를 생성한다.
CREATE FULLTEXT INDEX ON FactAdditionalInternationalProductDescription(ProductDescription)
KEY INDEX PK_FactAdditionalInternationalProductDescription_ProductKey_CultureName
ON TestCatalog
WITH CHANGE_TRACKING AUTO;

하지만 아래와 같은 에러가 출력된다.

메시지 7653, 수준 16, 상태 2, 줄 8
'PK_FactAdditionalInternationalProductDescription_ProductKey_CultureName'은(는) 전체 텍스트 검색 키를 강제 적용하는 유효한 인덱스가 아닙니다. 전체 텍스트 검색 키는 고유하고 Null을 허용하지 않으며, 오프라인이 아니고 비결정적이거나 정확하지 않은 비지속형 계산 열에 정의되어 있지 않으며 필터를 포함하지 않는 최대 크기 900바이트의 단일 열 인덱스여야 합니다. 전체 텍스트 키로 사용할 다른 인덱스를 선택하십시오.

단일 열로 생성된 인덱스여야 하나보다.

테이블을 조금 바꿔본다.

-- identity 컬럼 추가
ALTER TABLE FactAdditionalInternationalProductDescription ADD id bigint identity(1,1)
-- pk 인덱스 drop
ALTER TABLE FactAdditionalInternationalProductDescription DROP PK_FactAdditionalInternationalProductDescription_ProductKey_CultureName
-- pk 인덱스 add
ALTER TABLE FactAdditionalInternationalProductDescription ADD CONSTRAINT pk_id PRIMARY KEY (id);


PK를 방금 추가한 Identity 속성의 id 컬럼으로 수정하였다.



CREATE FULLTEXT INDEX ON FactAdditionalInternationalProductDescription(ProductDescription)
KEY INDEX pk_id
ON TestCatalog
WITH CHANGE_TRACKING AUTO;


현재 필자는 중지 단어(제외 키워드)를 지정하지 않았고 따라서 전체 단어에 대해서 계산을 하였을 것이다. 

키워드는 아래 쿼리로 확인할 수 있다.

select * from sys.dm_fts_index_keywords(DB_ID(),OBJECT_ID('FactAdditionalInternationalProductDescription'))

document_count가 존재하는 것을 보니 키워드를 count 한 것으로 보인다.

위에서 Like 문으로 조회했던 N'헤드'를 전체 텍스트 인덱스를 사용하여 검색해보자.

SELECT *
FROM [AdventureWorksDW2017].[dbo].[FactAdditionalInternationalProductDescription]
where CONTAINS(ProductDescription, N'헤드');

쿼리 수행 결과는 같았으며 성능에서 차이가 많이 났다.


읽은 행 수가 3개뿐이다. 성능이 압도적으로 좋아진 것이다.

CONTAINS의 경우에는 키워드를 포함하는 데이터를 반환하는데 AND/OR 등의 조건을 같이 쓸 수 있다. 또한 FREETEXT는 비슷한 내용도 검색해준다.

SELECT *
FROM [AdventureWorksDW2017].[dbo].[FactAdditionalInternationalProductDescription]
where FREETEXT(ProductDescription, N'주유포트');



현재까지의 내용만 봤을 때는 키워드만 잘 만들어진다면 일반 인덱스보다 좋은 성능을 발휘할 것으로 보이며 어떤 경우에는 table full scan정도는 아니지만 거의 table full scan을 타서 성능 향상을 못 누린다. (모든 것은 잘 사용해야 좋은 것은 당연하겠지..)

이번 포스팅은 전체 텍스트 검색의 사용법 위주로 포스팅 했으며 추후에는 동작 방식에 대해서 다시 포스팅하도록 하겠다.


2022년 회고

 올해는 블로그 포스팅을 열심히 못했다. 개인적으로 지금까지 경험했던 내용들을 리마인드하자는 마인드로 한해를 보낸 것 같다.  대부분의 시간을 MLOps pipeline 구축하고 대부분을 최적화 하는데 시간을 많이 할애했다. 결국에는 MLops도 데이...