Fazer recuperação top-k eficiente

Muitos aplicativos consultam um banco de dados para preencher uma única página nos aplicativos. Nesses aplicativos, o aplicativo não precisa de todas as correspondências, mas apenas das principais correspondências com base na ordem de classificação do índice. Os índices de pesquisa podem implementar esse tipo de pesquisa de maneira muito eficiente. Esta página descreve como criar e pesquisar um índice com correspondência top-k.

Criar índices de pesquisa para as correspondências top-k

Para configurar um índice de pesquisa para correspondência top-k, use ORDER BY para ordenar o índice de pesquisa por uma coluna específica. As consultas precisam ter uma cláusula ORDER BY que corresponda exatamente à ordem de classificação do índice de pesquisa (incluindo ordem crescente e decrescente) e uma cláusula LIMIT que solicite que a consulta seja interrompida após encontrar k linhas correspondentes.

Também é possível implementar a paginação usando essas cláusulas. Para mais informações, consulte Paginar consultas de pesquisa.

Para alguns casos de uso, pode ser interessante manter vários índices de pesquisa ordenados por colunas diferentes. Assim como o particionamento, é uma compensação entre o custo de armazenamento e gravação e a latência da consulta.

Por exemplo, considere uma tabela que usa o seguinte esquema:

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

Consultar índices de pesquisa para as principais correspondências

Conforme declarado anteriormente, as consultas precisam ter uma cláusula ORDER BY que corresponda exatamente à ordem de classificação do índice de pesquisa (incluindo ordem crescente e decrescente) e uma cláusula LIMIT que solicite que a consulta pare após encontrar k linhas correspondentes.

A lista a seguir analisa a eficiência de algumas consultas comuns.

  • Essa consulta é muito eficiente. Ele seleciona o índice AlbumsRecordTimestampIndex. Mesmo que haja muitos álbuns com a palavra "happy", a consulta só verifica um pequeno número de linhas:

    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

  • A mesma consulta, que solicita a ordem de classificação por ReleaseTimestamp em ordem decrescente, usa o índice AlbumsReleaseTimestampIndex e é igualmente eficiente:

    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

  • Uma consulta que solicita a ordem de classificação por ListenTimestamp não executa uma consulta top-k de forma eficiente. Ele precisa buscar todos os álbuns correspondentes, classificá-los por ListenTimestamp, e retornar os 10 primeiros. Essa consulta usa mais recursos se houver um grande número de documentos que contenham o termo "happy".

    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

  • Da mesma forma, uma consulta não será executada de forma eficiente se solicitar que os resultados sejam ordenados usando a coluna RecordTimestamp em ordem crescente. Ele verifica todas as linhas com a palavra "happy", apesar de ter um 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

A seguir