Fazer recuperação top-k eficiente

Muitos aplicativos consultam um banco de dados para preencher uma única página nos aplicativos. Nesses aplicativos, não é necessário ter todas as correspondências, apenas as k principais com base na ordem de classificação do índice. Os índices de pesquisa podem implementar esse tipo de pesquisa com muita eficiência. Nesta página, descrevemos como criar e pesquisar um índice com correspondência top-k.

Criar índices de pesquisa para 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 da Pesquisa (incluindo a direção crescente e decrescente) e uma cláusula LIMIT que solicite a interrupção da consulta depois de 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.

Em alguns casos de uso, pode ser interessante manter vários índices de pesquisa classificados por colunas diferentes. Assim como o particionamento, é uma compensação entre o custo de armazenamento e gravação e a latência de 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 k

Como afirmado anteriormente, as consultas precisam ter uma cláusula ORDER BY que corresponda exatamente à ordem de classificação do índice de pesquisa (incluindo a direção crescente ou decrescente) e uma cláusula LIMIT que solicite a interrupção da consulta depois de 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ó analisa 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, solicitando 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 maneira eficiente. Ele precisa buscar todos os álbuns correspondentes, classificá-los por ListenTimestamp, e retornar os 10 melhores. Uma consulta assim 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 é executada de maneira eficiente se solicita que os resultados sejam ordenados usando a coluna RecordTimestamp em ordem crescente. Ele verifica todas as linhas com a palavra "feliz", 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