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

De nombreuses applications interrogent une base de données pour renseigner une seule page dans leurs applications. Dans ce cas, 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 indice avec une correspondance top-k.

Créer des index de recherche pour les correspondances k premières

Pour configurer un indice de recherche pour la mise en correspondance des k premières valeurs, utilisez ORDER BY pour trier l'indice de recherche par 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 par rapport à l'ordre 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 la section Pagination des requêtes de recherche.

Dans certains cas d'utilisation, il peut être judicieux de gérer plusieurs index de recherche triés par différentes colonnes. Comme pour 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 premières correspondances

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 l'ordre croissant par rapport à l'ordre décroissant) et une clause LIMIT qui demande à la requête de s'arrêter après avoir trouvé des lignes correspondant à k.

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 "heureux", 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, qui demande 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 une requête top-k de manière efficace. Elle doit extraire tous les albums correspondants, les trier par ListenTimestamp, et renvoyer le top 10. Une telle requête utilise plus de ressources si un grand nombre de documents contiennent 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 de manière efficace si elle demande que les résultats soient triés dans l'ordre croissant à l'aide de la colonne RecordTimestamp. Il analyse toutes les lignes contenant le mot "happy", même si elles contiennent 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

Étape suivante