効率的な上位 k 個の検索を実行する

多くのアプリケーションは、データベースにクエリを実行して、取得したデータをアプリケーションの 1 つのページに表示します。このようなアプリケーションでは、すべての一致ではなく、インデックスの並べ替え順序に基づく上位 k 件の一致のみが必要です。検索インデックスを使用すると、このタイプの検索を非常に効率的に実装できます。このページでは、上位 k 件の一致を含むインデックスを作成して検索する方法について説明します。

上位 k 件の一致の検索インデックスを作成する

上位 k 件の一致の検索インデックスを構成するには、ORDER BY を使用して検索インデックスを特定の列で並べ替えます。クエリには、検索インデックスの並べ替え順序(昇順と降順)と完全に一致する ORDER BY 句と、一致する行が k 個見つかったらクエリを停止するようリクエストする LIMIT 句が必要です。

これらの句を使用してページネーションを実装することもできます。詳細については、検索クエリをページ分けするをご覧ください。

ユースケースによっては、異なる列で並べ替えられた複数の検索インデックスを維持するほうが良い場合があります。パーティショニングと同様に、ストレージおよび書き込みコストと、クエリ レイテンシの間にはトレードオフが存在します。

たとえば、次のスキーマを使用するテーブルについて考えてみましょう。

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

上位 k 件の一致の検索インデックスをクエリする

前述のように、クエリには、検索インデックスの並べ替え順序(昇順と降順)と完全に一致する ORDER BY 句と、k 個の一致する行が見つかったらクエリを停止するようリクエストする LIMIT 句が必要です。

次のリストは、一般的なクエリの効率性を分析したものです。

  • このクエリは非常に効率的です。AlbumsRecordTimestampIndex インデックスを選択します。「happy」という単語を含むアルバムが多数ある場合でも、クエリは少数の行のみをスキャンします。

    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
    
  • 同じクエリで、ReleaseTimestamp の降順での並べ替えをリクエストしています。AlbumsReleaseTimestampIndex インデックスを使用し、同じように効率的です。

    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
    
  • ListenTimestamp による並べ替え順序をリクエストするクエリは、上位 k 件を返すクエリを効率的に実行しません。一致するすべてのアルバムを取得し、ListenTimestamp, で並べ替えて、上位 10 件を返す必要があります。このようなクエリは、「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
    
  • 同様に、結果を RecordTimestamp 列で昇順に並べ替えるようにリクエストすると、クエリは効率的に実行されません。LIMIT が設定されていても、「happy」という単語を含むすべての行がスキャンされます。

    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
    

次のステップ