Effiziente Top-K-Suche durchführen

Viele Anwendungen fragen eine Datenbank ab, um eine einzelne Seite in ihren Anwendungen zu füllen. In solchen Anwendungen benötigt die Anwendung nicht alle Übereinstimmungen, sondern nur die Top-K-Übereinstimmungen basierend auf der Indexsortierung. Suchindexe können diese Art der Suche sehr effizient implementieren. Auf dieser Seite wird beschrieben, wie Sie einen Index mit Top-K-Abgleich erstellen und darin suchen.

Suchindexe für die Top-K-Übereinstimmungen erstellen

Wenn Sie einen Suchindex für die Top-K-Übereinstimmung konfigurieren möchten, ordnen Sie den Suchindex mit ORDER BY nach einer bestimmten Spalte an. Abfragen müssen eine ORDER BY-Klausel enthalten, die genau mit der Sortierreihenfolge des Suchindexes übereinstimmt (einschließlich aufsteigender oder absteigender Richtung), und eine LIMIT-Klausel, die angibt, dass die Abfrage beendet werden soll, nachdem k übereinstimmende Zeilen gefunden wurden.

Sie können die Paginierung auch mit diesen Klauseln implementieren. Weitere Informationen finden Sie unter Suchanfragen paginatisieren.

Für einige Anwendungsfälle kann es sinnvoll sein, mehrere Suchindizes zu verwalten, die nach verschiedenen Spalten sortiert sind. Wie bei der Partitionierung ist es ein Kompromiss zwischen Speicher- und Schreibkosten und Abfragelatenz.

Betrachten Sie beispielsweise eine Tabelle mit dem folgenden Schema:

GoogleSQL 

CREATE TABLE Albums (
  AlbumId STRING(MAX) NOT NULL,
  RecordTimestamp INT64 NOT NULL,
  ReleaseTimestamp INT64 NOT NULL,
  ListenTimestamp INT64 NOT NULL,
  AlbumTitle STRING(MAX),
  AlbumTitle_Tokens TOKENLIST AS (TOKENIZE_FULLTEXT(AlbumTitle)) HIDDEN
) PRIMARY KEY(AlbumId);

CREATE SEARCH INDEX AlbumsRecordTimestampIndex
ON Albums(AlbumTitle_Tokens, SingerId_Tokens)
STORING (ListenTimestamp)
ORDER BY RecordTimestamp DESC

CREATE SEARCH INDEX AlbumsReleaseTimestampIndex
ON Albums(AlbumTitle_Tokens)
STORING (ListenTimestamp)
ORDER BY ReleaseTimestamp DESC

PostgreSQL 

CREATE TABLE albums (
  albumid character varying NOT NULL,
  recordtimestamp bigint NOT NULL,
  releasetimestamp bigint NOT NULL,
  listentimestamp bigint NOT NULL,
  albumtitle character varying,
  albumtitle_tokens spanner.tokenlist
      GENERATED ALWAYS AS (spanner.tokenize_fulltext(albumtitle)) VIRTUAL HIDDEN,
PRIMARY KEY(albumid));

CREATE SEARCH INDEX albumsrecordtimestampindex
ON Albums(albumtitle_tokens, singerid_tokens)
INCLUDE (listentimestamp)
ORDER BY recordtimestamp DESC

CREATE SEARCH INDEX albumsreleasetimestampindex
ON Albums(albumtitle_tokens)
INCLUDE (listentimestamp)
ORDER BY releasetimestamp DESC

Suchindexe nach den Top-K-Übereinstimmungen abfragen

Wie bereits erwähnt, müssen Abfragen eine ORDER BY-Klausel enthalten, die genau mit der Sortierreihenfolge des Suchindexes übereinstimmt (einschließlich aufsteigender oder absteigender Richtung), und eine LIMIT-Klausel, die angibt, dass die Abfrage beendet werden soll, nachdem k übereinstimmende Zeilen gefunden wurden.

In der folgenden Liste wird die Effizienz einiger gängiger Abfragen analysiert.

  • Diese Abfrage ist sehr effizient. Der Index AlbumsRecordTimestampIndex wird ausgewählt. Selbst wenn es viele Alben mit dem Wort „glücklich“ gibt, wird bei der Abfrage nur eine kleine Anzahl von Zeilen gescannt:

    GoogleSQL 

    SELECT AlbumId
FROM Albums
WHERE SEARCH(AlbumTitle_Tokens, 'happy')
ORDER BY RecordTimestamp DESC
LIMIT 10

    PostgreSQL 

    SELECT albumid
FROM albums
WHERE spanner.search(albumtitle_tokens, 'happy')
ORDER BY recordtimestamp DESC
LIMIT 10

  • Die gleiche Abfrage, bei der die Sortierung nach ReleaseTimestamp in absteigender Reihenfolge angefordert wird, verwendet den Index AlbumsReleaseTimestampIndex und ist ebenso effizient:

    GoogleSQL 

    SELECT AlbumId
FROM Albums
WHERE SEARCH(AlbumTitle_Tokens, 'happy')
ORDER BY ReleaseTimestamp DESC
LIMIT 10

    PostgreSQL 

    SELECT albumid
FROM albums
WHERE spanner.search(albumtitle_tokens, 'happy')
ORDER BY releasetimestamp DESC
LIMIT 10

  • Bei einer Abfrage, bei der die Sortierung nach ListenTimestamp angefordert wird, wird eine Top-K-Abfrage nicht effizient ausgeführt. Es muss alle übereinstimmenden Alben abrufen, nach ListenTimestamp, sortieren und die Top 10 zurückgeben. Bei einer solchen Abfrage werden mehr Ressourcen benötigt, wenn es eine große Anzahl von Dokumenten gibt, die den Begriff „glücklich“ enthalten.

    GoogleSQL 

    SELECT AlbumId
FROM Albums
WHERE SEARCH(AlbumTitle_Tokens, 'happy')
ORDER BY ListenTimestamp DESC
LIMIT 10

    PostgreSQL 

    SELECT albumid
FROM albums
WHERE spanner.search(albumtitle_tokens, 'happy')
ORDER BY listentimestamp DESC
LIMIT 10

  • Ebenso wird eine Abfrage nicht effizient ausgeführt, wenn die Ergebnisse in aufsteigender Reihenfolge nach der Spalte RecordTimestamp sortiert werden sollen. Es werden alle Zeilen mit dem Wort „glücklich“ gescannt, obwohl sie ein LIMIT enthält.

    GoogleSQL 

    SELECT AlbumId
FROM Albums
WHERE SEARCH(AlbumTitle_Tokens, 'happy')
ORDER BY RecordTimestamp ASC
LIMIT 10

    PostgreSQL 

    SELECT albumid
FROM albums
WHERE spanner.search(albumtitle_tokens, 'happy')
ORDER BY recordtimestamp ASC
LIMIT 10

Nächste Schritte