역 인덱스의 원리

역 인덱스는 검색 엔진 기술에서 비롯되었으며 검색 엔진의 초석으로 간주될 수 있습니다. 역 인덱스 기술 덕분에 검색 엔진은 데이터베이스 검색 및 삭제와 같은 작업을 효율적으로 수행할 수 있습니다. 역 인덱스에 대해 자세히 설명하기 전에 먼저 관련 순방향 인덱스를 소개하고 두 가지를 비교합니다.

순방향 인덱스

검색 엔진에서 순방향 테이블은 문서 ID를 키워드로 사용하고 테이블은 문서 내 각 단어의 위치 정보를 기록합니다. 검색 시 시스템은 쿼리 키워드가 포함된 모든 문서를 찾을 때까지 테이블의 각 문서에서 단어 정보를 스캔합니다.

순방향 테이블의 구조는 다음 상자 다이어그램으로 나타낼 수 있습니다.

+--------------------+
| 순방향 인덱스 테이블 |
+--------------------+
| 문서 ID | 위치 정보 |
+--------------------+
| Doc1 | word1@3 |
| | word2@7 |
+--------------------+
| Doc2 | word1@2 |
| | word3@5 |
+--------------------+
| Doc3 | word2@4 |
| | word4@6 |
+--------------------+

이 구성 방법은 인덱스를 구축할 때 비교적 간단한 구조를 가지며 구축하기 편리하고 유지 관리가 쉽습니다. 인덱스는 문서를 기반으로 구축되므로 새 문서가 추가되면 이文書에 대한 새 인덱스 블록을 생성하여 원래 인덱스 파일의 끝에 첨부하기만 하면 됩니다. 문서를 삭제한 경우 문서 번호에 해당하는 인덱스 정보를 직접 찾아 삭제할 수 있습니다. 그러나 쿼리할 때는 누락을 방지하기 위해 모든 문서를 스캔해야 하므로 검색 시간이 크게 늘어나고 검색 효율이 낮아집니다.

순방향 테이블의 작동 원리는 매우 간단하지만 검색 효율이 너무 낮아 특정 상황이 아니면 실질적인 가치가 거의 없습니다.

역 인덱스

역 테이블은 단어 또는 용어를 인덱싱하기 위한 키워드로 사용하고 테이블의 키워드에 해당하는 레코드 항목은 이 단어 또는 용어가 나타나는 모든 문서를 기록합니다.

역 테이블의 구조는 다음 상자 다이어그램으로 나타낼 수 있습니다.

+--------------------+
| 역 인덱스 테이블 |
+--------------------+
| 키워드 | 문서 목록 |
+--------------------+
| word1 | Doc1,Doc2 |
+--------------------+
| word2 | Doc1,Doc3 |
+--------------------+
| word3 | Doc2 |
+--------------------+
| word4 | Doc3 |
+--------------------+

각 단어 또는 용어에 해당하는 문서 수는 동적으로 변하므로 역 테이블의 설정 및 유지 관리는 비교적 복잡합니다. 그러나 쿼리할 때 쿼리 키워드에 해당하는 모든 문서를 한 번에 얻을 수 있으므로 순방향テーブル보다 효율성이 높습니다. 전체 텍스트 검색에서 검색의 빠른 응답은 매우 중요한 성능입니다. 인덱스 설정은 백그라운드에서 수행되므로 비교적 느리지만 전체 검색 엔진의 효율성에 영향을 미치지 않습니다.

PostgreSQL의 Gin 인덱스

개요

GIN은 Generalized Inverted Index의 약자로, 소위 역 인덱스입니다. 처리하는 데이터 유형의 값은 원자성이 아니지만 요소로 구성되어 있으며 이를 복합 유형이라고 합니다. 예를 들어, (hank, 15:3 21:4)에서 hank는位置 15:3과 21:4에 나타납니다. 다음은 특정 예를 통해 GIN 인덱스를 더 명확하게 이해하는 데 도움이 됩니다.

GIN 인덱스 구조

물리적 구조

GIN 인덱스의 물리적 스토리지는 다음 내용을 포함합니다.

항목: GIN 인덱스의 요소로, 단어 위치로 간주할 수 있으며 키로 이해할 수도 있습니다.
항목 트리: 항목에 구성된 B-트리입니다.
게시 목록: 항목이 나타나는 물리적 위치(힙 ctid, 힙 테이블 행 번호)의 연결된 목록입니다.
게시 트리: 항목이 나타나는 물리적 위치(힙 ctid, 힙 테이블 행 번호)의 연결된 목록에 구성된 B-트리입니다. 따라서 게시 트리의 KEY는 ctid이고, 항목 트리의 KEY는 인덱싱된 열의 값입니다.
보류 중인 목록: fastupdate 모드에서 삽입 작업에 사용되는 인덱스 튜플의 임시 저장 연결 목록입니다.

위에서 볼 수 있듯이 GIN 인덱스는 주로 항목 트리와 게시 트리(또는 게시 목록)로 구성되며, 항목 트리는 GIN 인덱스의 주요 구조 트리이고, 게시 트리는 보조 트리입니다.

항목 트리는 b+트리와 유사하고 게시 트리는 b-트리와 유사합니다.

또한 항목 트리와 게시 트리는 모두 KEY에 따라 정렬된 방식으로 구성됩니다.

논리적 구조

논리적으로 GIN 인덱스는 관계로 간주할 수 있으며 이 관계에는 두 가지 구조가 있습니다.

기본 테이블의 열 하나만 인덱싱

키	값
key1	게시 목록(또는 게시 트리)
key2	게시 목록(또는 게시 트리)
…	…

기본 테이블의 여러 열 인덱싱(복합, 다중 열 인덱스)

column_id	키	값
Column1 num	key1	게시 목록(또는 게시 트리)
Column2 num	key1	게시 목록(또는 게시 트리)
Column3 num	key1	게시 목록(또는 게시 트리)
…	…	…

이 구조에서는 기본 테이블의 서로 다른 열에 있는 동일한 키에 대해 GIN 인덱스에서 다른 키로 처리된다는 것을 알 수 있습니다.

전체 텍스트 검색

GIN의 주요 응용 분야는 전체 텍스트 검색을 가속화하는 것입니다. 따라서 여기서는 전체 텍스트 검색의 예를 사용하여 GIN 인덱스를 소개합니다.

테이블을 만들고 doc_tsv는 자동으로 정렬하고 дубликат 요소를 제거할 수 있는 텍스트 검색 유형입니다.

pg_study=# create table ts(doc text, doc_tsv tsvector);
CREATE TABLE

pg_study=# insert into ts(doc) values
 ('Can a sheet slitter slit sheets?'),
 ('How many sheets could a sheet slitter slit?'),
 ('I slit a sheet, a sheet I slit.'),
 ('Upon a slitted sheet I sit.'),
 ('Whoever slit the sheets is a good sheet slitter.'),
 ('I am a sheet slitter.'),
 ('I slit sheets.'),
 ('I am the sleekest sheet slitter that ever slit sheets.'),
 ('She slits the sheet she sits on.');
INSERT 0 9

pg_study=# update ts set doc_tsv = to_tsvector(doc);
UPDATE 9

pg_study=# create index on ts using gin(doc_tsv);
CREATE INDEX

이 GIN 인덱스의 구조는 다음과 같습니다. 검은색 사각형은 TID 번호이고 흰색 사각형은 단어입니다. 이는 B-트리의 이중 연결 목록과 다른 단일 연결 목록입니다.

+--------+ +--------+ +--------+
| sheet |---->| slit |---->| slitter|
+--------+ +--------+ +--------+
 |
 v v v
+--------+ +--------+ +--------+
| (0,10) | | (0,10) | | (0,10) |
+--------+ +--------+ +--------+
 |
 v v v
+--------+ +--------+ +--------+
| (0,11) | | (0,11) | | (0,11) |
+--------+ +--------+ +--------+
 |
 v v v
 ... ... ...

다른 예를 살펴보겠습니다.

pg_study=# select ctid,doc, doc_tsv from ts;
 ctid | doc | doc_tsv
--------+--------------------------------------------------------+---------------------------------------------------------
 (0,10) | Can a sheet slitter slit sheets? | 'sheet':3,6 'slit':5 'slitter':4
 (0,11) | How many sheets could a sheet slitter slit? | 'could':4 'mani':2 'sheet':3,6 'slit':8 'slitter':7
 (0,12) | I slit a sheet, a sheet I slit. | 'sheet':4,6 'slit':2,8
 (0,13) | Upon a slitted sheet I sit. | 'sheet':4 'sit':6 'slit':3 'upon':1
 (0,14) | Whoever slit the sheets is a good sheet slitter. | 'good':7 'sheet':4,8 'slit':2 'slitter':9 'whoever':1
 (0,15) | I am a sheet slitter. | 'sheet':4 'slitter':5
 (0,16) | I slit sheets. | 'sheet':3 'slit':2
 (0,17) | I am the sleekest sheet slitter that ever slit sheets. | 'ever':8 'sheet':5,10 'sleekest':4 'slit':9 'slitter':6
 (0,18) | She slits the sheet she sits on. | 'sheet':4 'sit':6 'slit':2
(9 rows)

위에서 sheet, slit 및 slitter가 여러 행에 나타나므로 여러 TID가 있음을 알 수 있습니다. 이 경우 TID 목록이 생성되고 별도의 B-트리가 생성됩니다.

다음 구문은 단어가 나타나는 행 수를 확인할 수 있습니다.

pg_study=# select (unnest(doc_tsv)).lexeme, count(*) from ts
group by 1 order by 2 desc;
 lexeme | count
----------+-------
 sheet | 9
 slit | 8
 slitter | 5
 sit | 2
 upon | 1
 mani | 1
 whoever | 1
 sleekest | 1
 good | 1
 could | 1
 ever | 1
(11 rows)

쿼리 예제

다음 쿼리는 어떻게 실행됩니까?

// 여기서는 데이터量が 적기 때문에 전체 테이블 스캔이 비활성화됩니다.
pg_study=# set enable_seqscan TO off;
SET

pg_study=# explain(costs off)
select doc from ts where doc_tsv @@ to_tsquery('many & slitter');
 QUERY PLAN
---------------------------------------------------------------------
 Bitmap Heap Scan on ts
 Recheck Cond: (doc_tsv @@ to_tsquery('many & slitter'::text))
 -> Bitmap Index Scan on ts_doc_tsv_idx
 Index Cond: (doc_tsv @@ to_tsquery('many & slitter'::text))
(4 rows)

먼저 쿼리에서 각 단어(쿼리 키)를 추출합니다. mani와 slitter. 이는 데이터 유형과 연산자 전략을 고려하는 특수 API에 의해 완료됩니다.

pg_study=# select amop.amopopr::regoperator, amop.amopstrategy
from pg_opclass opc, pg_opfamily opf, pg_am am, pg_amop amop
where opc.opcname = 'tsvector_ops'
and opf.oid = opc.opcfamily
and am.oid = opf.opfmethod
and amop.amopfamily = opc.opcfamily
and am.amname = 'gin'
and amop.amoplefttype = opc.opcintype;
 amopopr | amopstrategy
-----------------------+--------------
 @@(tsvector,tsquery) | 1
 @@@(tsvector,tsquery) | 2
(2 rows)

단어가 포함된 B-트리에서 두 키에 해당하는 TID 목록을 찾습니다.

mani: (0,2) slitter: (0,1), (0,2), (1,2), (1,3), (2,2)

마지막으로 찾은 각 TID에 대해 일관성関数를 차례로 호출합니다. 이 일관성 함수는 TID가 가리키는 행이 쿼리 조건을 충족하는지 여부를 판별할 수 있습니다. 쿼리의 단어가 and로 연결되어 있으므로 반환된 행은 (0,2)뿐입니다.

 | | |
 | | consistency
 TID | mani | slitter | slit & slitter
-------+------+---------+----------------
 (0,1) | f | T | f
 (0,2) | T | T | T
 (1,2) | f | T | f
 (1,3) | f | T | f
 (2,2) | f | T | f

결과는 다음과 같습니다.

pg_study=# select doc from ts where doc_tsv @@ to_tsquery('many & slitter');
 doc
---------------------------------------------
 How many sheets could a sheet slitter slit?
(1 row)

느린 업데이트 속도 문제

GIN 인덱스에서 데이터를 삽입하거나 업데이트하는 것은 매우 느립니다. 일반적으로 각行에는 인덱싱할 단어 요소가 많이 포함되어 있기 때문입니다. 따라서 행을 추가하거나 업데이트할 때 인덱스 트리를 많이 업데이트해야 합니다.

반면에 여러 행을 동시에 업데이트하면 일부 단어 요소가 동일할 수 있으므로 총 비용은 행별로 문서를 업데이트하는 비용보다 저렴합니다.

GIN 인덱스에는 인덱스를 만들 때 지정하고 나중에 업데이트할 수 있는 fastupdate 스토리지 매개변수가 있습니다.

pg_study=# create index on ts using gin(doc_tsv) with (fastupdate = true);
CREATE INDEX

이 매개변수를 활성화하면 업데이트가 별도의 정렬되지 않은 목록에 누적됩니다. 이 목록이 충분히 크거나 진공(가비지 수집) 중에 누적된 모든 업데이트가 인덱스에서 즉시 작동합니다. "충분히 큰" 목록은 인덱스를 만들 때 "gin_pending_list_limit" 구성 매개변수 або 같은 이름의 스토리지 매개변수로 결정됩니다.

부분 일치 검색

slit로 시작하는 doc 쿼리

pg_study=# select doc from ts where doc_tsv @@ to_tsquery('slit:*');
 doc
--------------------------------------------------------
 Can a sheet slitter slit sheets?
 How many sheets could a sheet slitter slit?
 I slit a sheet, a sheet I slit.
 Upon a slitted sheet I sit.
 Whoever slit the sheets is a good sheet slitter.
 I am a sheet slitter.
 I slit sheets.
 I am the sleekest sheet slitter that ever slit sheets.
 She slits the sheet she sits on.
(9 rows)

인덱스를 사용하여 가속화할 수도 있습니다.

pg_study=# explain (costs off)
select doc from ts where doc_tsv @@ to_tsquery('slit:*');
 QUERY PLAN
---------------------------------------------------
 Seq Scan on ts
 Filter: (doc_tsv @@ to_tsquery('slit:*'::text))
(2 rows)

키워드 빈도

일부 데이터 생성:

fts=# alter table mail_messages add column tsv tsvector;
fts=# update mail_messages set tsv = to_tsvector(body_plain);
fts=# create index on mail_messages using gin(tsv);
fts=# \timing on

-- 총 466125개의 데이터
ft=# select count(*) from mail_messages;
 count
--------
 356125
(1 row)

-- 여기서는 행에서 단어가 나타나는 횟수를 세기 위해 unnest를 사용하는 대신 データ량이 비교적 많기 때문에 ts_stat 関数를 사용하여 計算합니다.
ft=# select word, ndoc
ft=# from ts_stat('select tsv from mail_messages')
ft=# order by ndoc desc limit 3;
 word | ndoc
-------+--------
 wrote | 231174
 use | 173833
 would | 157169
(3 rows)

Time: 11556.976 ms

예를 들어 이메일 정보에 거의 나타나지 않는 단어 "tattoo"를 쿼리합니다.

ft=# select word, ndoc from ts_stat('select tsv from mail_messages') where word = 'tattoo';
 word | ndoc
--------+------
 tattoo | 2
(1 row)

Time: 11236.340 ms

두 단어가 같은 행에 나타나는 횟수 작성자 и tattoo가 동시에 나타나는 행은 하나뿐입니다.

ft=# select count(*) from mail_messages where tsv @@ to_tsquery('wrote & tattoo');
 count
-------
 1
(1 row)

Time: 0.550 ms

실행 방법을 살펴보겠습니다. 위에서 언급했듯이 두 단어의 TID 목록을 얻으려면 검색 효율이 매우 낮습니다. 200,000개가 넘는 값을 탐색해야 하고 하나의 값만 가져오기 때문입니다. 그러나 통계 정보를 통해 알고리즘은 "wrote"가 자주 나타나는 반면 "tattoo"는 드물게 나타난다는 것을 알 수 있습니다. 따라서 자주 사용되지 않는 단어 검색이 실행된 다음 검색된 두 행에 "wrote"가 있는지 확인합니다. 이러한 방식으로 쿼리 결과를 빠르게 얻을 수 있습니다.

ft=# elect count(*) from mail_messages where tsv @@ to_tsquery('wrote & tattoo');
 count
-------
 1
(1 row)

Time: 0.419 ms

쿼리 결과 제한

GIN 인덱스의 한 가지 특징은 비트맵만 반환할 수 있고 각 TID를 하나씩 반환할 수 없다는 것입니다. 따라서 이 기사의 모든 계획은 비트맵 스캔을 사용합니다.

압축 방법

GIN의 장점 중 하나는 압축 기능입니다. 첫째, 동일한 단어가 여러 행에 나타나는 경우 인덱스에 한 번만 저장됩니다. 둘째, TID는 인덱스에 정렬된 방식으로 저장되므로 간단한 압축 방법을 사용할 수 있습니다. 목록의 다음 TID는 실제로 이전 TID와 다릅니다. 이 숫자는 일반적으로 매우 작으며 완전한 6바이트 TID와 비교할 때 필요한 비트 수가 훨씬 적습니다.

서로 다른 인덱스 크기를 비교합니다.

B-트리 인덱스 만들기: GIN은 다른 데이터 유형(텍스트 대신 tsvector)을 기반으로 구축되며 이 데이터 유형은 더 작습니다. 동시에 B-트리는 메시지를 2K 이내로 자릅니다.

ft=# create index mail_messages_btree on mail_messages(substring(body_plain for 2048));
CREATE INDEX
Time: 32709.807 ms

gist 인덱스 만들기:

ft=# create index mail_messages_gist on mail_messages using gist(tsv);
CREATE INDEX
Time: 14651.884 ms

gin, gist 및 btree의 크기를 각각 살펴보십시오.

ft=# select pg_size_pretty(pg_relation_size('mail_messages_tsv_idx')) as gin,
ft=# pg_size_pretty(pg_relation_size('mail_messages_gist')) as gist,
ft=# pg_size_pretty(pg_relation_size('mail_messages_btree')) as btree;
 gin | gist | btree
--------+--------+--------
 189 MB | 111 MB | 526 MB
(1 row)

Time: 2.961 ms

GIN 인덱스는 공간을 절약하므로 Oracle에서 PostgreSQL로 마이그레이션하는 동안 비트맵 인덱스 대신 GIN 인덱스를 사용할 수 있습니다. 일반적으로 비트맵 인덱스는 고유 값이 매우 적은 필드에 사용되며 GIN에도 매우 효과적입니다. 또한 PostgreSQL은 모든 인덱스(GIN 포함)를 기반으로 비트맵을 동적으로 구축할 수 있습니다.

Leapcell: 최고의 서버리스 웹 호스팅

마지막으로 웹 서비스를 배포하는 데 가장 적합한 플랫폼인 **Leapcell**을 추천합니다.

🚀 좋아하는 언어로 빌드

JavaScript, Python, Go 또는 Rust로 간편하게 개발하세요.

🌍 무제한 프로젝트를 무료로 배포

사용한 만큼만 지불하세요. 요청도 없고 요금도 없습니다.

⚡ 사용량에 따라 요금 부과, 숨겨진 비용 없음

유휴 요금 없이 원활하게 확장할 수 있습니다.

📖 문서 탐색

🔹 Twitter에서 팔로우하세요: @LeapcellHQ

검색 엔진으로 PostgreSQL 사용? 예, Elasticsearch가 필요 없을 수도 있습니다.