[SQL] 23.Inverted Index 인버티드 인덱스란 무엇인가 ? 그리고 왜 Elastic Search 에서 인버티드 인덱스를 사용하는가 ?

[SQL] 23.Inverted Index 인버티드 인덱스란 무엇인가 ? 그리고 왜 Elastic Search 에서 인버티드 인덱스를 사용하는가 ?

1. Inverted Index 인버티드 인덱스란 무엇인가 ?

인버티드 인덱스는 SQL에서 데이터베이스를 빠르게 검색하기 위해 사용하는 인덱싱 기술입니다. 인버티드 인덱스는 문서 또는 레코드에 존재하는 단어 또는 기간에 대한 역색인입니다. 인덱스는 문서에 나타나는 모든 단어를 나열하며, 각 단어별로 해당 단어가 등장하는 문서 목록을 제공합니다. 이렇게 특정 키워드를 기반으로 데이터를 빠르게 검색하고 검색할 수 있습니다. 인버티드 인덱스는 일반적으로 풀 텍스트 검색 응용 프로그램 및 빠르게 텍스트 데이터를 검색해야하는 다른 데이터 검색 시스템에서 사용됩니다.

• 무슨말인지 너무 어렵다.

1-1 쉽게 이해해보자

directionality??

• 테이블을 풀스캔하려면 모든 테이블을 다 읽어야한다.
  • 만약 책을 읽을때 책을 전부 다 뒤져서 원하는 부분을 찾으려면 처음부터 하나씩 다 확인해야한다.
  • 근데 목차가 있다면 ?
    • 쉽게 쉽게 찾을수 있다.
  • 그때 이 목차에 해당하는 역할을 하는게 인덱스 INDEX 라고 할수있다.
• 우리가 기존에 아는 인덱스는 정규화된 컬럼에서 하나의 순서를 지정해 또다른 컬럼하나를 만들어 정해두는 것을 뜻했다. B + tree같은 개념은 설명하지 않겠다.
  • 예를 들어보자
  • 사용자들은 백만개가 넘게 쌓여진 document 에서 자신에게 필요한 document를 찾고자 한다. 예를들어 100만개의 글(documents)이 있는 게시판에서 User가 “Buying a Home” 이라고 검색을 한다고 가정해보자.
  • 기존의 전통적인(Traditional) 검색방식은 아래와 같다.

1) WHERE = 검색방식

**SELECT** * 
**FROM** `M_DOCUMENT` 
**WHERE** `bookname` = 'Buying a Home'

이 경우 검색어 'Buying a Home' 와 정확히 일치하는 문서만 선택이 된다.

즉, 문서 결과를 거의 얻지 못한다.

---

2) WHERE LIKE 검색방식

**SELECT** * 
**FROM** `M_DOCUMENT` 
**WHERE** `bookname` LIKE '%Buying a Home%'

이 경우 검색어가 문서내용(bookname 필드)에 포함되어 있는 경우 선택이 된다.

1번 방식보다 진화한 방식이지만 여전히 해당 문장이 정확히 일치하는 경우가 적기 때문에 결과를 거의 얻지 못한다.

---

3) Whitespace tokenizer AND 검색방식사용자의 쿼리를 Whitespace 로 쪼개서 AND 검색을 실시한다.

**SELECT** * 
**FROM** `M_DOCUMENT` 
**WHERE** `bookname` LIKE '%Buying%' 
    AND `bookname` LIKE '%a%' 
    AND `bookname` LIKE '%Home%'

문서내용(bookname 필드)에 사용자 검색어의 모든 단어가 포함된 경우를 찾는다.

이전 방식과 비교해서 상당히 많이 향상된 결과를 보여주지만
해당단어가 모두 포함된 문서가 아니면 결과에 포함되지 않는다.

---

4) Whitespace tokenizer OR 검색방식사용자의 쿼리를 Whitespace 로 쪼개서 OR 검색을 실시한다.

**SELECT** * 
**FROM** `M_DOCUMENT` 
**WHERE** `bookname` LIKE '%Buying%' 
    OR `bookname` LIKE '%a%' 
    OR `bookname` LIKE '%Home%'

문서내용(bookname 필드)에 사용자 검색어 중 하나라도 포함되는 경우를 찾는다.사용자가 원하는 문서를 찾아준다는 점에서 매우 우수한 검색방식이다. 하지만 어느하나의 단어만 포함되도 되기에 전혀 관계가 없는 문서도 결과물(result-set)로 추출된다.

---

• 문제가 뭐냐면
  • 넷 다 테이블 풀스캔을 한다는 점이다.
  • 전체 테이블을 뒤져서 원하는 결과값을 들고오는데 (물론 ‘Home%’이런식으로 인덱스를 타게 한다면 풀스캔을 하지 않을수 있겠지만) 결과값 또한 여러가지 경우의 수를 내재하고 있다
  • 즉, 의미없는 결과값도 나오고
  • 검색 대상이 누적되면서 (100만개 정도의 big data가 되면서) 검색부하가 엄청 오래 걸린다.

4번의 방식은 현재 한국 내 커뮤니티에서 가장 많이 사용하고 있는 검색방식이다.

따라서 국내 커뮤니티 검색엔진에서 좋은 결과를 얻고자 한다면 키워드 입력방식을 사용해야 한다.

예를들어 “집을 살때 필요한 서류” 를 검색하고 싶으면 “집 서류” 라고 검색해야 가장 훌륭한 결과물을 얻어낼 수 있다.

쿼리 : 
SELECT * 
FROM `M_DOCUMENT` 
WHERE `bookname` LIKE ‘%집%’ 
OR `bookname` LIKE ‘%서류%’

진화 - Inverted index

INDEX?

index
는 "색인"이라는 뜻이다.

 

https://jiseok-woo.tistory.com/3

위에서 말한 테이블 풀스캔을 방지하고자 목차를 집어넣는것 !

 

index는 쉽게 말해 목차를 만든다고도 얘기들을 하지만 정확히 말하면 B+ Tree 구조로 별도의 index 테이블을 만든다.

따라서 해당 컬럼 값으로 데이터를 찾거나 정렬을 하게 될 경우 인덱싱이 되지 않았을 때보다 더 빠르게 접근이 가능해진다.

index가 뭔지 설명해보세요 (개발면접시간)

( Btree 와 Index에 대한 설명은 여기가 최고인듯 ,,, )

Inverted??

반전된 인덱스라고 했다.(역색인 이라고도 한다.)

보통 데이터가 저장되면 1번째 row에 어떤 데이터가 있다는 식으로 저장이 된다. inverted index는 반대로 어떤 데이터는 몇번째 row에 있다는 방식으로 저장한다.

Traditional SQL 에서는 LIKE 검색이 INDEX 기능을 이용할 수 없다는 단점이 있어서, 그 문제를 극복하기 위해서 단어(Term)로 인덱싱을 하는 Inverted Index 방식이 고안되었다.

기존의 데이터베이스가 하나의 구분자(Primary Key)가 여러 필드를 지정하고 있었다면Inverted Index에서는 하나의 값(Term)이 해당 Term이 들어간 document id 를 지정하고 있다.

 

문장이나 여러 단어들의 조합들이 저장될 때 큰 강점이 있다.

문장은 여러 단어들로 구성이 되어있고 그 중 중요한 키워드도 있고 큰 의미가 없는 단어들도 있다.

의미있는 단어들을 추출해 해당 단어들로 inverted index를 생성한다면 ?? .

그렇게 되면 단어를 검색할때 어떤 데이터들에 해당 단어가 포함되어 있는지 빠르게 확인이 가능해진다.

 

 

"나는 책을 읽는다."와 같은 문장들이 저장되어 있고 그 중 "영화"라는 단어가 들어간 데이터만 찾고 싶을때 옆의 inverted index 테이블을 보면 누가봐도 한눈에 아주 쉽게 "영화" 라는 단어가 어디에 있는지 확인할 수 있다. 이게 elasticsearch에서 말하는 inverted index이고 elasticsearch가 검색엔진으로써 빠른 검색이 가능한 이유이다.

무슨말이냐면 ?

즉

 

컨텐츠 필드의 단어들을 쪼개서 단어당 몇번째 Doc인지 분배하는 컬럼을 사용한다고 하자

오른쪽 inverted index table을 보고

becoming home 이라고 검색하면

becoming 과 home 으로 나눈 후에 빠르게 (8), (2,5,7,8) 이라는 결과가 반환이 되고8이 가장 유사한 결과물이라고 알게 된다.

인덱싱은 인덱싱인데 약간 다른 인덱싱을 하기 때문에 탐색 속도가 매우 빠르다.

ELASTIC SEARCH ??

elastcisearch는 데이터를 저장하기 전에 analyzer라는 친구가 해당 데이터를 분석하고 tokenizer로 적절히 짤라 키워드를 생성해 inverted index로 저장할 수 있도록 해준다.

예를들어 language analyzer의 경우엔 문장을 분석해 "가다", "간다", "갔다" 등을 "가다"로 통일해 키워드를 생성한다.

tokenizer는 분석된 문장을 공백이든 -든 기준을 잡아 키워드 단위로 짤라주는 역할을 한다. elasticsearch는 수많은 analyzer와 tokenizer가 존재하며 이를 잘 활용해야 elasticsearch를 제대로 활용한다 볼 수 있겠다.

• 그러니 엘라스틱서치가 핫한것 !! 댓글을 이렇게 저장한다고 생각하면 굉장히 파워풀하게 검색할수 있을것 같지 않은가??

Inverted index with Term position

• 여기서 Term이라는 위치정보를 저장할수도 있다.
• 무슨말이냐면

 

 

단어 값(Term)이 발견된 위치도 저장한다.

예시로 사용자가 new home 을 검색했다고 가정하면, 위의 그림에 따라 5번과 8번 document 를 반환하게 된다.

5번과 8번이 두 단어를 모두 포함하는 document 일뿐 아니라, new 다음에 home 이 나타나는 문서임을 알 수 있다. (Term position 순서비교)

단어가 연속되는지 (new home) 여부를 빠르게 파악이 가능하고 단어(Term) 사이의 값을 찾을 수도 있다.

이것을 활용해
new home, new brand home , new super cheap home 등이 결과에 나올 수 있게 된다.
(Proximity Search)

---

출처 및 참고

https://blog.lael.be/post/3056
https://jiseok-woo.tistory.com/3

Elasticsearch가 빠르다는데..? inverted index?

대용량 검색 처리를 위한 inverted index (역색인) 설명