Effectuer une récupération efficace des k meilleurs résultats

De nombreuses applications interrogent une base de données pour remplir une seule page de leurs applications. Dans de telles applications, l'application n'a pas besoin de toutes les correspondances, mais uniquement des k premières correspondances en fonction de l'ordre de tri de l'index. Les index de recherche peuvent implémenter ce type de recherche de manière très efficace. Cette page explique comment créer et rechercher un index avec une correspondance top-k.

Créer des index de recherche pour les correspondances top-k

Pour configurer un index de recherche pour la correspondance top-k, utilisez ORDER BY afin de trier l'index de recherche par une colonne spécifique. Les requêtes doivent comporter une clause ORDER BY qui correspond exactement à l'ordre de tri de l'index de recherche (y compris l'ordre croissant ou décroissant) et une clause LIMIT qui demande à la requête de s'arrêter après avoir trouvé k lignes correspondantes.

Vous pouvez également implémenter la pagination à l'aide de ces clauses. Pour en savoir plus, consultez Paginer les requêtes de recherche.

Dans certains cas d'utilisation, il peut être judicieux de conserver plusieurs index de recherche triés par différentes colonnes. Comme le partitionnement, il s'agit d'un compromis entre le coût de stockage et d'écriture, et la latence des requêtes.

Prenons l'exemple d'une table qui utilise le schéma suivant :

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

Interroger les index de recherche pour obtenir les k correspondances les plus pertinentes

Comme indiqué précédemment, les requêtes doivent comporter une clause ORDER BY qui correspond exactement à l'ordre de tri de l'index de recherche (y compris le sens croissant ou décroissant) et une clause LIMIT qui demande à la requête de s'arrêter après avoir trouvé k lignes correspondantes.

La liste suivante analyse l'efficacité de certaines requêtes courantes.

  • Cette requête est très efficace. Il sélectionne l'index AlbumsRecordTimestampIndex. Même s'il existe de nombreux albums contenant le mot "happy", la requête n'analyse qu'un petit nombre de lignes :

    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

  • La même requête, demandant un ordre de tri par ReleaseTimestamp dans l'ordre décroissant, utilise l'index AlbumsReleaseTimestampIndex et est tout aussi efficace :

    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

  • Une requête qui demande un ordre de tri par ListenTimestamp n'exécute pas efficacement une requête top-k. Il doit extraire tous les albums correspondants, les trier par ListenTimestamp, et renvoyer les 10 premiers. Une telle requête utilise plus de ressources s'il existe un grand nombre de documents contenant le terme "heureux".

    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

  • De même, une requête ne s'exécute pas efficacement si elle demande que les résultats soient triés par ordre croissant à l'aide de la colonne RecordTimestamp. Il analyse toutes les lignes contenant le mot "heureux", malgré la présence d'un LIMIT.

    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

Étapes suivantes