Das Prinzip des invertierten Index

Der invertierte Index stammt aus der Suchmaschinentechnologie und kann als Eckpfeiler von Suchmaschinen angesehen werden. Dank der invertierten Indextechnologie können Suchmaschinen effizient Operationen wie das Suchen und Löschen in Datenbanken durchführen. Bevor wir den invertierten Index näher erläutern, werden wir zunächst den relevanten Vorwärtsindex vorstellen und die beiden vergleichen.

Vorwärtsindex

In einer Suchmaschine verwendet die Vorwärtstabelle die Dokument-ID als Schlüsselwort, und die Tabelle erfasst die Positionsinformationen jedes Wortes im Dokument. Bei der Suche scannt das System die Wortinformationen in jedem Dokument in der Tabelle, bis alle Dokumente gefunden wurden, die das Abfrage-Schlüsselwort enthalten.

Die Struktur der Vorwärtstabelle kann durch das folgende Kastendiagramm dargestellt werden:

+--------------------+
| Vorwärtsindextabelle |
+--------------------+
| Dokument-ID | Positionsinformationen |
+--------------------+
| Doc1 | wort1@3 |
| | wort2@7 |
+--------------------+
| Doc2 | wort1@2 |
| | wort3@5 |
+--------------------+
| Doc3 | wort2@4 |
| | wort4@6 |
+--------------------+

Diese Organisationsmethode hat eine relativ einfache Struktur beim Aufbau des Index, und sie ist bequem zu erstellen und leicht zu warten. Da der Index auf Dokumenten basiert, muss beim Hinzufügen eines neuen Dokuments nur ein neuer Indexblock für dieses Dokument erstellt und an das Ende der ursprünglichen Indexdatei angehängt werden; wenn ein Dokument gelöscht wird, können die dem Dokument zugehörigen Indexinformationen direkt gefunden und gelöscht werden. Beim Abfragen müssen jedoch alle Dokumente gescannt werden, um Auslassungen zu vermeiden, was die Abrufzeit erheblich verlängert und zu einer geringen Abrufeffizienz führt.

Obwohl das Funktionsprinzip der Vorwärtstabelle sehr einfach ist, ist ihre Abrufeffizienz zu gering, und sie hat nur in bestimmten Situationen einen praktischen Wert.

Invertierter Index

Die invertierte Tabelle verwendet Wörter oder Begriffe als Schlüsselwörter für die Indizierung, und die Datensatzeinträge, die den Schlüsselwörtern in der Tabelle entsprechen, erfassen alle Dokumente, in denen dieses Wort oder dieser Begriff vorkommt.

Die Struktur der invertierten Tabelle kann durch das folgende Kastendiagramm dargestellt werden:

+--------------------+
| Invertierte Indextabelle |
+--------------------+
| Schlüsselwort | Dokumentliste |
+--------------------+
| wort1 | Doc1,Doc2 |
+--------------------+
| wort2 | Doc1,Doc3 |
+--------------------+
| wort3 | Doc2 |
+--------------------+
| wort4 | Doc3 |
+--------------------+

Da sich die Anzahl der Dokumente, die jedem Wort oder Begriff entsprechen, dynamisch ändert, sind die Erstellung und Wartung der invertierten Tabelle relativ komplex. Da jedoch beim Abfragen alle Dokumente, die dem Abfrage-Schlüsselwort entsprechen, auf einmal abgerufen werden können, ist die Effizienz höher als bei der Vorwärtstabelle. Bei der Volltextsuche ist die schnelle Reaktion des Abrufs eine entscheidende Leistung. Obwohl die Indexerstellung relativ langsam ist, da sie im Hintergrund erfolgt, beeinträchtigt sie nicht die Effizienz der gesamten Suchmaschine.

Der Gin-Index in PostgreSQL

Überblick

GIN ist die Abkürzung für Generalized Inverted Index, also den sogenannten invertierten Index. Die Werte der Datentypen, die er verarbeitet, sind nicht atomar, sondern setzen sich aus Elementen zusammen, die wir zusammengesetzte Typen nennen. In (hank, 15:3 21:4) bedeutet dies beispielsweise, dass hank an den Positionen 15:3 und 21:4 vorkommt. Das Folgende wird uns helfen, den GIN-Index anhand von Beispielen besser zu verstehen.

GIN-Indexstruktur

Physische Struktur

Die physische Speicherung des GIN-Index enthält die folgenden Inhalte:

1. Eintrag: Ein Element im GIN-Index, das als Wortposition betrachtet werden kann und auch als Schlüssel verstanden werden kann.
2. Eintragsbaum: Ein B-Baum, der auf dem Eintrag aufgebaut ist.
3. Posting-Liste: Eine verkettete Liste der physischen Positionen (heap ctid, heap table row number), an denen ein Eintrag vorkommt.
4. Posting-Baum: Ein B-Baum, der auf der verketteten Liste der physischen Positionen (heap ctid, heap table row number) aufgebaut ist, an denen ein Eintrag vorkommt. Der KEY des Posting-Baums ist also ctid, und der KEY des Eintragsbaums ist der Wert der indizierten Spalte.
5. Pending-Liste: Eine temporäre Speicher-Kette von Indextupeln, die für Einfügeoperationen im Fastupdate-Modus verwendet wird.

Aus dem Obigen geht hervor, dass der GIN-Index hauptsächlich aus dem Eintragsbaum und dem Posting-Baum (oder der Posting-Liste) besteht, wobei der Eintragsbaum der Hauptstrukturbaum des GIN-Index ist und der Posting-Baum der Hilfsbaum ist.

Der Eintragsbaum ähnelt dem b+tree, und der Posting-Baum ähnelt dem b-tree.

Darüber hinaus sind sowohl der Eintragsbaum als auch der Posting-Baum geordnet nach dem KEY.

Logische Struktur

Logisch gesehen kann der GIN-Index als eine Relation betrachtet werden, und diese Relation hat zwei Strukturen:

Indizierung nur einer Spalte der Basistabelle

Indizierung mehrerer Spalten der Basistabelle (zusammengesetzter Mehrspaltenindex)

Daraus lässt sich schließen, dass unter dieser Struktur für denselben Schlüssel in verschiedenen Spalten der Basistabelle dieser auch als ein anderer Schlüssel im GIN-Index behandelt wird.

Volltextabruf

Das Hauptanwendungsgebiet von GIN ist die Beschleunigung der Volltextsuche. Daher stellen wir hier den GIN-Index anhand eines Beispiels für die Volltextsuche vor.

Erstellen Sie eine Tabelle, und doc_tsv ist vom Textsuchtyp, der automatisch doppelte Elemente sortieren und eliminieren kann:

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

Die Struktur dieses GIN-Index ist wie folgt. Die schwarzen Quadrate sind die TID-Nummern, und die weißen sind die Wörter. Beachten Sie, dass dies eine einfach verkettete Liste ist, die sich von der doppelt verketteten Liste des B-Baums unterscheidet:

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

Schauen wir uns ein anderes Beispiel an:

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)

Aus dem Obigen geht hervor, dass sheet, slit und slitter in mehreren Zeilen vorkommen, sodass es mehrere TIDs gibt. In diesem Fall wird eine TID-Liste generiert, und es wird ein separater B-Baum dafür generiert.

Mit der folgenden Anweisung kann herausgefunden werden, in wie vielen Zeilen das Wort vorkommt.

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)

Abfragebeispiel

Wie wird die folgende Abfrage ausgeführt?

// Da die Datenmenge hier gering ist, ist die vollständige Tabellensuche deaktiviert
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)

Extrahieren Sie zuerst jedes Wort (Abfrageschlüssel) aus der Abfrage: mani und slitter. Dies wird von einer speziellen API erledigt, die die Strategien von Datentypen und Operatoren berücksichtigt:

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)

Suchen Sie im B-Baum, der die Wörter enthält, die TID-Listen, die den beiden Schlüsseln entsprechen:

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

Rufen Sie schließlich für jede gefundene TID nacheinander die Konsistenzfunktion auf. Diese Konsistenzfunktion kann bestimmen, ob die Zeile, auf die die TID verweist, die Abfragebedingungen erfüllt. Da die Wörter in der Abfrage durch und verbunden sind, ist die zurückgegebene Zeile nur (0,2).

 | | |
 | | Konsistenz
 | | Funktion
 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

Das Ergebnis ist:

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

Das Problem der langsamen Aktualisierungsgeschwindigkeit

Das Einfügen oder Aktualisieren von Daten im GIN-Index ist sehr langsam. Da jede Zeile normalerweise viele Wortelemente enthält, die indiziert werden müssen. Wenn wir also eine Zeile hinzufügen oder aktualisieren, müssen wir den Indexbaum sehr stark aktualisieren.

Wenn andererseits mehrere Zeilen gleichzeitig aktualisiert werden, können einige ihrer Wortelemente identisch sein, sodass die Gesamtkosten geringer sind als die Kosten für die zeilenweise Aktualisierung von Dokumenten.

Der GIN-Index hat einen Fastupdate-Speicherparameter, den wir beim Erstellen des Index angeben und später aktualisieren können:

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

Nachdem dieser Parameter aktiviert wurde, werden die Aktualisierungen in einer separaten ungeordneten Liste gesammelt. Wenn diese Liste groß genug ist oder während der Bereinigung (Garbage Collection), werden alle angesammelten Aktualisierungen sofort im Index verarbeitet. Die „groß genug“-Liste wird durch den Konfigurationsparameter „gin_pending_list_limit“ oder den Speicherparameter mit demselben Namen beim Erstellen des Index bestimmt.

Partielle Übereinstimmungssuche

Abfrage des Dokuments, das mit Schlitz beginnt

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)

Der Index kann auch zur Beschleunigung verwendet werden:

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)

Die Häufigkeit von Schlüsselwörtern

Generieren Sie einige Daten:

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

-- Eine Gesamtzahl von 466125 Datensätzen
fts=# select count(*) from mail_messages;
 count
--------
 356125
(1 row)

-- Hier verwenden wir nicht unnest, um die Anzahl der Vorkommen eines Wortes in einer Zeile zu zählen, da die Datenmenge relativ groß ist, sondern verwenden die ts_stat-Funktion zur Berechnung
fts=# select word, ndoc
fts-# from ts_stat('select tsv from mail_messages')
fts-# order by ndoc desc limit 3;
 word | ndoc
-------+--------
 wrote | 231174
 use | 173833
 would | 157169
(3 rows)

Time: 11556.976 ms

Wir fragen beispielsweise das Wort ab, das in den E-Mail-Informationen selten vorkommt, z. B. „Tattoo“:

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

Time: 11236.340 ms

Die Häufigkeit, mit der zwei Wörter in derselben Zeile vorkommen. Es gibt nur eine Zeile, in der geschrieben und Tattoo gleichzeitig vorkommen

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

Time: 0.550 ms

Mal sehen, wie es ausgeführt wird. Wie oben erwähnt, ist die Sucheffizienz offensichtlich sehr gering, wenn wir die TID-Listen von zwei Wörtern erhalten möchten: weil wir mehr als 200.000 Werte durchlaufen müssen und nur ein Wert verwendet wird. Durch die statistischen Informationen kann der Algorithmus jedoch wissen, dass „wrote“ häufig vorkommt, während „tattoo“ selten vorkommt. Daher wird die Suche nach dem Wort ausgeführt, das nicht häufig verwendet wird, und anschließend wird geprüft, ob „wrote“ in den beiden abgerufenen Zeilen vorhanden ist. Auf diese Weise kann das Abfrageergebnis schnell erhalten werden:

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

Time: 0.419 ms

Einschränken von Abfrageergebnissen

Ein Merkmal des GIN-Index ist, dass er nur eine Bitmap zurückgeben kann und nicht jede TID einzeln zurückgeben kann. Daher verwenden alle Pläne in diesem Artikel den Bitmap-Scan.

Komprimierungsmethode

Einer der Vorteile von GIN ist seine Komprimierungsfunktion. Wenn dasselbe Wort in mehreren Zeilen vorkommt, wird es zunächst nur einmal im Index gespeichert. Zweitens werden TIDs geordnet im Index gespeichert, sodass wir eine einfache Komprimierungsmethode verwenden können: Die nächste TID in der Liste unterscheidet sich tatsächlich von der vorherigen TID; Diese Zahl ist normalerweise sehr klein, und im Vergleich zur vollständigen sechs Byte-TID ist die Anzahl der benötigten Bits viel geringer.

Vergleichen Sie die Größen verschiedener Indizes:

Erstellen Sie einen B-Baum-Index: GIN basiert auf einem anderen Datentyp (tsvector anstelle von Text), und dieser Datentyp ist kleiner. Gleichzeitig schneidet der B-Baum die Nachricht auf maximal 2 KB ab.

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

Erstellen Sie einen Gist-Index:

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

Sehen Sie sich die Größen von Gin, Gist und Btree an:

fts=# select pg_size_pretty(pg_relation_size('mail_messages_tsv_idx')) as gin,
fts-# pg_size_pretty(pg_relation_size('mail_messages_gist')) as gist,
fts-# 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

Da der GIN-Index mehr Speicherplatz spart, können wir während der Migration von Oracle zu PostgreSQL den GIN-Index anstelle des Bitmap-Index verwenden. Im Allgemeinen wird der Bitmap-Index für Felder mit sehr wenigen eindeutigen Werten verwendet, was auch für GIN sehr effektiv ist. Darüber hinaus kann PostgreSQL dynamisch eine Bitmap basierend auf jedem Index (einschließlich GIN) erstellen.

Leapcell: Das Beste vom Serverlosen Webhosting

Abschließend empfehlen wir eine Plattform, die sich am besten für die Bereitstellung von Webservices eignet: Leapcell

🚀 Entwickeln Sie mit Ihrer Lieblingssprache

Entwickeln Sie mühelos in JavaScript, Python, Go oder Rust.

🌍 Stellen Sie unbegrenzt Projekte kostenlos bereit

Zahlen Sie nur für das, was Sie nutzen – keine Anfragen, keine Gebühren.

⚡ Pay-as-You-Go, keine versteckten Kosten

Keine Leerlaufgebühren, nur nahtlose Skalierbarkeit.

📖 Entdecken Sie unsere Dokumentation

🔹 Folgen Sie uns auf Twitter: @LeapcellHQ