Postgresのページネーションの5つの方法、基本的なものから異様なものまで

Webアプリケーションで一般的なページネーションは、非合理的に簡単に実装できるという事実に驚くかもしれません。 この記事では、さまざまなサーバー側のページネーション方法を試して、PostgreSQLで使用する場合の便利さについて説明します。 この記事は、これまで見たことのない手法、つまり物理クラスタリングとデータベース統計コレクターに依存する手法など、状況に応じてより適切な手法を理解するのに役立ちます。



続行する前に、アプリケーション側のページネーションに言及してください。 一部のアプリケーションは、サーバー情報のすべて（またはほとんど）をクライアントに転送し、そこのページで共有します。 少量のデータの場合、アプリケーション側のページネーションが適切な選択となり、HTTP呼び出しの数が減ります。 レコードが数千になり始めると、このアプローチは実用的ではなくなります。 サーバー側のページネーションには次の利点があります。

• スタートページの読み込みを高速化
• 共有データが変更されたときのより高い精度
• 大量のデータの高速操作
• ビジネスロジックのカプセル化
• 限られたリソースのクライアントでのパフォーマンスの向上

PostgreSQLは、特定のページのアクセスパターンのサポートと同様に、速度、整合性（レコードを失わない）が異なる、サーバー側の特定のページネーション技術を提供します。 すべてのメソッドがすべての状況で機能するわけではなく、一部のメソッドは特別なデータまたはクエリを必要とします。 メソッドを一般的な順序で検討します。すべてのクエリで機能するメソッドから開始し、順序付けされたデータを必要とするメソッドで継続します。 最終的に、内部のPostgreSQLデバイスに基づいたいくつかのエキゾチックな方法になります。

カスタムクエリの分割

限界オフセット

最も単純なページネーション方法であるリミットオフセットも最も危険です。 残念ながら、これはWeb開発チュートリアルの基礎の1つです。 オブジェクトリレーショナルマッピング（ORM）ライブラリにより、SQLAlchemy .slice（1、3）からActiveRecord .limit（1）.offset（3）からSequelize .findAll（{オフセット：3、制限：1}） 。 どこでもlimit-offsetが使用されることは偶然ではありません。それ以上の変更をせずに、リクエストに添付できます。



制限とオフセットのORMメソッドは1つですが、ページネーションの補助ライブラリはさらに欺くことができます。 たとえば、人気のあるKaminari Rubyライブラリはデフォルトでlimit-offsetを使用し、高レベルのインターフェースの背後に隠しています。



この手法には、結果の一貫性とバイアスの非効率性という2つの大きな問題があります。 一貫性は、結果を渡すことで、省略や繰り返しをせずに各要素を厳密に1回受け取る必要があるという事実によるものです。 バイアスの非効率性は、結果を大きなバイアスにシフトするときに発生する遅延に関連しています。



リミットオフセットページネーションが矛盾する可能性がある方法を次に示します。 ユーザーがページnからページn + 1に移動し、同時に新しい要素がページnに挿入されたとします。 これにより、複製（ページnの最後の要素がページn + 1に押し出される）とスキップ（新しい要素）の両方が発生します。 あるいは、ユーザーがページn + 1に移動した時点で要素nが削除されたとします。 ページn + 1のプリロードされた開始要素はページnに移動し、スキップされます。



今、非効率性のトピックについて。 大きなシフトは本当に高価です。 インデックスがある場合でも、データベースは行全体をカウントしてストレージ全体をスキャンする必要があります。 インデックスを使用するには、値で列をフィルタリングする必要がありますが、この場合、列の値に関係なく、特定の行数が必要です。 さらに、行は保存中に同じサイズである必要はなく、それらの一部はディスク上に存在する場合がありますが、削除済みとしてマークされているため、データベースは単純な算術を使用してディスク領域を見つけ、結果の読み取りを開始できません。 スローダウンを測定しましょう。

--        CREATE TABLE medley AS SELECT generate_series(1,10000000) AS n, substr(concat(md5(random()::text), md5(random()::text)), 1, (random() * 64)::integer + 1) AS description; --        VACUUM ANALYZE; --     EXPLAIN ANALYZE SELECT * FROM medley LIMIT 100;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

推定コストは非常に低いです。

  QUERY PLAN -------------------------------------------------------------------------------------------------------------------- Limit (cost=0.00..1.85 rows=100 width=38) (actual time=0.008..0.036 rows=100 loops=1) -> Seq Scan on medley (cost=0.00..185460.60 rows=9999660 width=38) (actual time=0.007..0.017 rows=100 loops=1) Planning time: 0.040 ms Execution time: 0.059 ms (4 rows)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

オフセット= 1000を選択すると、コストが19に、ランタイムが0.609ミリ秒に変更されます。 オフセット= 5000000になるとすぐに、コストはすでに92734になり、実行時間は758.484ミリ秒になります。



これらの問題は、リミットオフセット方式があなたの場合に適用できないことを必ずしも意味しません。 一部のアプリケーションでは、ユーザーは通常、結果内の多くのページを通過しません。また、サーバー側のページ制限を使用することもできます。 アプリケーションでデータの不整合とページ制限が問題にならない場合は、limit-offsetメソッドが非常に適しています。



使用する場合：Limit-Offset。 制限されたページネーションの深さと一貫性の許容範囲を持つアプリケーション。

カーソル

欠点にもかかわらず、limit-offsetメソッドには、サーバーに影響がないという形でプラスがあります。 このアプローチとは対照的に、ページネーションの別の方法であるカーソルがあります。 バイアスと同様に、カーソルはどのリクエストでも使用できますが、サーバーとHTTPクライアントを介したトランザクションからの個別の接続が必要であるという点で異なります。



カーソルの使用方法は次のとおりです。

 --      BEGIN; --     DECLARE medley_cur CURSOR FOR SELECT * FROM medley; --  10  FETCH 10 FROM medley_cur; -- ... --   10 ,   ,      FETCH 10 FROM medley_cur; --   COMMIT;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

カーソルには、クエリのページネーションの一貫性という望ましいプロパティがあり、トランザクションの開始時にデータベースに存在する結果を示します。 トランザクション分離レベルにより、ページ分割された結果が変わらないことが保証されます。



各ページネーションアプローチには弱点があり、カーソルも例外ではありません。それらはリソースの使用とクライアント/サーバーバンドルに依存しています。 開いている各トランザクションは、データベースに割り当てられたリソースを消費し、多数のクライアントに対応できません。 もちろん、トランザクションの外部に存在する可能性のあるWITH HOLDカーソルもありますが、データを具体化する必要があるため、これらのエラーにより、カーソルは内部ネットワークなどの狭い範囲の状況にのみ適しています。



カーソルへのHTTP通信の追加は複雑です。 サーバーは、トークンを通じて、またはセッション内のクライアントのIPアドレスなどの識別子を保存することによって、リクエスト間でクライアントを識別する必要があります。 サーバーは、ダウンタイムのためにトランザクションをいつ解放するかを決定する必要もあります。 最後に、クライアントは毎回特定のサーバーに接続する必要があるため、サーバーの負荷を分散することは困難になります。



使用する場合：カーソル。 特に結果の一貫性が重要な場合に、リクエストを変数と変数の順序でページに分割する、単一サーバー上のネットワーク内のアプリケーション。

順序付きクエリのページネーション

キーページネーション

上記の手法は、順序付けされていないクエリを含む、あらゆるタイプのクエリ結果をページ分割できます。 このコミュニティを放棄する準備ができていれば、最適化のメリットを享受できます。 特に、インデックス列でソートする場合、ユーザーは現在のページの値を使用して、次のページに表示するオブジェクトを選択できます。 これは、キーセットページネーションと呼ばれます。



たとえば、例に戻りましょう。

 --     (btrees  ) CREATE INDEX n_idx ON medley USING btree (n); SELECT * FROM medley ORDER BY n ASC LIMIT 5;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

私のランダムデータでは、次の結果が返されます。

  n | description ---+------------------------------------------------------------- 1 | 74f70e009396 2 | 8dac5a085eb670a29058d 3 | fce303a32e89181bf5df1601487 4 | fddcced2c12e83516b3bd6cc94f23a012dfd 5 | f51ae548dd27f51147e53e839eeceb6b0c92922145276d668e73d4a6621 (5 rows)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これで、ユーザーは結果から最大nを見て、それを使用して次のページを呼び出すことができます。

 SELECT * FROM medley WHERE n > 5 ORDER BY n ASC LIMIT 5;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

n> 5000000でフィルタリングする場合でも、limit-offsetの例よりも高速に機能します。

  QUERY PLAN -------------------------------------------------------------------------------------------------------------------------------- Limit (cost=0.43..0.62 rows=5 width=38) (actual time=0.101..0.103 rows=5 loops=1) -> Index Scan using n_idx on medley (cost=0.43..185579.42 rows=5013485 width=38) (actual time=0.100..0.102 rows=5 loops=1) Index Cond: (n > 5000000) Planning time: 0.071 ms Execution time: 0.119 ms (5 rows)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このページネーションは高速で、データの整合性を保証します。 現在のページに追加/削除しても、結果は変更されません。 この方法の2つの弱点は、ランダムアクセスの欠如と、クライアントとサーバー間の接続の可能性です。



一般に、前のページにアクセスして最大要素を決定せずに、選択したページに移動する方法はありません。 ただし、特定の条件下では、より良い結果が得られます。 インデックス付き列の値が均等に分散している場合（またはスペースを含まない隣接する数値の方が良い場合）、ユーザーは数学的な計算を実行して目的のページを見つけることができます。

 EXPLAIN ANALYZE SELECT max(n) FROM medley; QUERY PLAN ------------------------------------------------------------------------------------------------------------ Result (cost=0.46..0.47 rows=1 width=0) (actual time=0.021..0.021 rows=1 loops=1) InitPlan 1 (returns $0) -> Limit (cost=0.43..0.46 rows=1 width=4) (actual time=0.018..0.018 rows=1 loops=1) -> Index Only Scan Backward using n_idx on medley (cost=0.43..284688.43 rows=10000000 width=4) (actual time=0.017..0.017 rows=1 loops=1) Index Cond: (n IS NOT NULL) Heap Fetches: 0 Planning time: 0.087 ms Execution time: 0.042 ms (8 rows)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

キー値の改ページの別の問題であるクライアント/サーバー接続には注意が必要です。 最初は、ユーザーはどの列にインデックスが付けられているかを知りません。 サーバーは、クライアントに再注文を許可するのではなく、エンドポイントに一定の結果を提供する可能性があります。 クライアントに提供されるコードは、どの列が順序付けられているかを知らない場合があり、サーバーは次のページを要求する方法に関するヒントを提供する必要があります。 RFC5988は、前と次のHTTPリンクの関係を定義して、ユーザーが従うリンクをエンコードします。



通常、ユーザーは情報ページに直線的にアクセスするため、通常、負荷の高いWebサーバー上のレコードのページ付けにはキー値のページ付けが優先されます。



使用する場合：キー値によるページネーション。 比較のためにインデックスが付けられた列から順番にデータを提供するスケーラブルなアプリケーション。 フィルタリングをサポートします。

風変わりで専門的なページネーション

クラスター化TIDスキャン

低レベルのPostgreSQL関数を使用して、特別な状況向けのカスタムページネーションメソッドを取得できます。 たとえば、次の場合、データに本当にランダムにアクセスできます。

1. ページを同じサイズにする必要はありません
2. ページ区切り文字列の単一注文のみをサポートします

秘Theは、ディスク上のデータベースのページ、またはディスク上のこれらのページの特定の部分にリンクされている返されたページを選択することです。 PostgreSQLデータベースの各テーブルには、ctidと呼ばれる秘密の列が含まれ、その行を識別します。

 SELECT ctid, * FROM medley WHERE n <= 10; ctid | n | description --------+----+------------------------------------------------------------- (0,1) | 1 | 74f70e009396 (0,2) | 2 | 8dac5a085eb670a29058d (0,3) | 3 | fce303a32e89181bf5df1601487 (0,4) | 4 | fddcced2c12e83516b3bd6cc94f23a012dfd (0,5) | 5 | f51ae548dd27f51147e53e839eeceb6b0c92922145276d668e73d4a6621 (0,6) | 6 | eb9fe1dfe1e421903f96b3b5c5dfe1ee1253582d728c35b4ee7330b (0,7) | 7 | e95202d7f5c612f8523ae705d (0,8) | 8 | 6573b64aff262a2b940326 (0,9) | 9 | a0a43 (0,10) | 10 | 82cdc134bd249a612cfddd3088dd09e32de5f4fa33 (10 rows)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

各ctidは次のとおりです：（ページ、行）。 PostgreSQLはctidによって非常に迅速に行を取得できます。実際、これがインデックスの仕組みです。列値をctidにバインドします。



PostgreSQLはtid型に基づいて順序関係を定義しますが、不等式からctidを効率的に取得できないことに注意してください

 EXPLAIN ANALYZE SELECT count(1) FROM medley WHERE ctid >= '(0,1)'::tid AND ctid < '(1,0)'::tid; QUERY PLAN ---------------------------------------------------------------------------------------------------------------------- Aggregate (cost=235589.00..235589.01 rows=1 width=0) (actual time=1241.851..1241.852 rows=1 loops=1) -> Seq Scan on medley (cost=0.00..235464.00 rows=50000 width=0) (actual time=477.933..1241.802 rows=116 loops=1) Filter: ((ctid >= '(0,1)'::tid) AND (ctid < '(1,0)'::tid)) Rows Removed by Filter: 9999884 Planning time: 0.047 ms Execution time: 1241.889 ms (6 rows)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

レンジングは機能しませんが、ディスク上のページからすべての行を効率的に照会する方法がまだあります。 各ページには、current_setting（ 'block_size'）データバイト（通常8k）が含まれます。 行は32ビットポインターによってリンクされているため、ほとんどの場合、block_size /ページあたり4行が必要です。 （実際、通常、行は最小サイズよりも広く、ブロックサイズの4分の1がページ上の行の上部境界を提供します。）次のシーケンスは、j番目のページですべてのctidを生成します。

 SELECT ('(' || j || ',' || si || ')')::tid FROM generate_series(0,current_setting('block_size')::int/4) AS s(i);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

それを使用して、ゼロページの例のすべての行を取得します。

 SELECT * FROM medley WHERE ctid = ANY (ARRAY (SELECT ('(0,' || si || ')')::tid FROM generate_series(0,current_setting('block_size')::int/4) AS s(i) ) );
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

スケジューラは、このリクエストを実行するコストをcost = 25.03..65.12に決定し、2.765msで実行します。 ページ番号10000をリクエストしても同じコストになります。 したがって、私たちは本当にランダムアクセスを取得します、なぜそれを愛しませんか？



3つのボトルネックがあります。

1. 行が削除されると、ページに穴が残ります。
2. 行の順序は重要ではありません。 データベースは、行を削除して残った穴に行を挿入します。これにより、行が順序どおりになりません。
3. サポートされていない場所

状況によっては、これは問題ではありません。 1つのケースはデータであり、自然な順序は、時間間隔の増分データのみなど、データベースに追加する順序と相関しています。 もう1つは、頻繁に変更されないデータです。 これは、CLUSTERコマンドを使用してページ上の行のレイアウトを制御できるという事実によるものです。



例に戻りましょう。 ディスク上のその行は、データベースに追加した順序であるため、昇順でn列ごとに並べられます。 しかし、説明列で並べ替える場合はどうでしょうか？ これを行うには、説明列にインデックスを作成し、クラスタリングしてテーブルを物理的に再構築する必要があります。

 CREATE INDEX description_idx ON medley USING btree (description); CLUSTER medley USING description_idx;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

最初のページからすべての行をフェッチすると、説明列でアルファベット順にソートされたデータが返されます。 テーブルが変更されると、新しい行はアルファベット順のリストから削除されますが、テーブルが変更されていない限り、返されるオブジェクトは完全な順序になります。 さらに、この操作はテーブルをブロックし、ユーザーがアクセスする必要がある場合は実行できないという事実にもかかわらず、変更後に定期的に再クラスター化できます。



最後に、バイト単位の合計サイズを使用して、テーブルのページの合計数を決定できます。

 SELECT pg_relation_size('medley') / current_setting('block_size')::int;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

使用する場合：TIDスキャン。 高速ランダムアクセスが必要で、フィルタリングが不要な場合。 実質的に変化しないライン幅で、増加する時間データのみで特にうまく機能します。

評価タブ付きキーセット

これまで見てきたように、キーセットの通常のページネーションでは、ユーザーが推測した場合を除き、特定のページに移動できません。 ただし、PostgreSQL統計情報コレクターは列分布ヒストグラムをサポートします。 これらの推定値を制限と小さなオフセットと組み合わせて使用​​して、ハイブリッドアプローチによる高速ランダムアクセスのページネーションを取得できます。



最初に、この例の統計を見てみましょう。

 SELECT array_length(histogram_bounds, 1) - 1 FROM pg_stats WHERE tablename = 'medley' AND attname = 'n';
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

私のデータベースでは、列nには101の境界指数があります。 それらの間の100の範囲。 データが均等に分散されているため、特定の値は混雑していません。

 {719,103188,193973,288794, … ,9690475,9791775,9905770,9999847}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

数値は概算です。 最初の数字は正確に0ではなく、最後の数字は正確に1,000万ではありません。 範囲は、情報をサイズB = 10,000,000 / 100 = 100,000行のブロックに分割します。



PostgreSQL統計コレクタのヒストグラム範囲を使用して、確率的に正しいページを取得できます。 クライアント側でWと等しいページサイズを選択した場合、i番目のページを取得するにはどうすればよいですか？ ブロックIW / Bにあり、オフセットIW％Bを持ちます。



W = 20を選択して、テストパターンから270,000ページを要求しましょう。

 WITH bookmark AS ( SELECT (histogram_bounds::text::int[])[((270000 * 20) / 100000)+1] AS start, (histogram_bounds::text::int[])[((270000 * 20) / 100000)+2] AS stop FROM pg_stats WHERE tablename = 'medley' AND attname = 'n' LIMIT 1 ) SELECT * FROM medley WHERE n >= (select start from bookmark) AND n < (select stop from bookmark) ORDER BY n ASC LIMIT 20 OFFSET ((270000 * 20) % 100000);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これは超高速です（この場合、シフトはゼロに近い時間で発生することに注意してください）。 クエリは、n = 5407259から5407278の行を返します。ページ270,000の真の値は、n = 5400001から5400020に等しくなります。ミスは7239、つまり約0.1％です。



この場合のページの選択は幸運でした。 対照的に、74999ページには99980のオフセットが必要です。オフセットは100,000を超えないことがわかっています。妥協したい場合は、上限を制御できます。 PostgreSQL統計情報コレクターを設定することにより、より正確な列ヒストグラムを取得できます。

 ALTER TABLE medley ALTER COLUMN n SET statistics 1000; VACUUM ANALYZE;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これで、100個のヒストグラム値ではなく、1000個になりました。 私のデータベースでは、次のようになっています。

 {10,10230,20863, …, 9980444,9989948,9999995}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

同時に、シフトのステップは10000以下になります。トレードオフは、スケジューラがより多くの値をスキャンするようになりますが、速度が低下することです。 したがって、これはバイアスの非効率性と統計情報コレクタのオーバーヘッドの交差点です。



このハイブリッドな「キーセット/オフセット」方式は、おそらく多くの実際のページネーションアプリケーションには適していません。 そして、ここでは「どこ」条件は機能しません。 さらに、テーブルを変更するとき、および統計コレクターが長時間起動されていない場合、不正確であり、ますます不正確になります。



使用する場合：評価ブックマーク付きのキーのセット。 ユーザーが追加のフィルタリングなしで、深いが、おおよそのランダムアクセスを必要とする場合。

結論

他の多くのエンジニアリングソリューションと同様に、ページネーション技術を選択するには妥協が必要です。 キーセットのページネーションは、線形アクセスが順序付けられた中規模サイトに最も適していると確信できます。 ただし、制限/オフセット方式にも独自の長所があり、よりエキゾチックな方式は特定のタイプのデータに対して特別なパフォーマンス特性を提供します。 ご覧のとおり、かなりの数の可能性があります。 ジョブに適したツールを選択し、ページネーションを閉じた本にしないでください。