次ページの取得


最初のページを効率的に取り出すために、パイプライン化された最初のN件のみを選択するクエリを 実装できたら、次ページ以降を取りだすクエリも必要になるでしょう。 それを実現するためのチャレンジは、前のページの行をどのようにスキップするかです。 これには2つの方法が考えられます。まず1つ目は、先頭から行に番号を付けて、 必要なページよりも前の行番号のデータをフィルタする、 オフセット法です。2つ目は、私がシーク法と 呼んでいる、全ページの最後のエントリを検索し、それ以降の必要な行を 読み出す方法です。

以下は、最も広く使われているオフセット法の例を表したものです。 この方法の利点は簡単に使える所にあるでしょう。専用のキーワード (offset)が用意されているデータベースでは特にそうです。 このキーワードは、fetch first拡張の一部として SQL標準にも採用されています。

DB2

DB2はSQL標準のoffset文法をサポートしていません。 標準に従う動作をする代わりの仕組みとして、ROW_NUMBER()窓関数 (次の節を参照)があります。また、推奨はされていませんが オフセットの機能を実現する2つの方法があります。 (1) db2set DB2_COMPATIBILITY_VECTOR=MYSを使い、 MySQLがサポートしているのと同じようなlimitoffsetを使えるようにできます。しかしこの場合、 fetch firstoffsetは 組み合わせて使えません。 (2) db2set DB2_COMPATIBILITY_VECTOR=ORAを使い、 OracleのROWNUM疑似列(Oracleの例を参照)を有効に できます。

MySQL

MySQLとPostgreSQLは、最初のN行のみを選択するクエリで、 始めの何行を切り捨てるか指定するのに、offset句が用意されています。 その後にlimit句が適用されます。

SELECT *
  FROM sales
 ORDER BY sale_date DESC
 LIMIT 10 OFFSET 10
Oracle

Oracleでは、結果セットに自動的に番号付けをした ROWNUMという疑似列がサポートされています。ただし、 この疑似列には>=のフィルタは 適用できません。この結果を得るには、列にエイリアスを付けて行番号を 「マテリアライズ」する必要があります。

SELECT *
  FROM ( SELECT tmp.*, rownum rn
           FROM ( SELECT *
                    FROM sales
                   ORDER BY sale_date DESC
                ) tmp
          WHERE rownum <= 20
       )
 WHERE rn > 10

下限にはエイリアスのRNを使い、 上限にはROWNUM疑似列を使うことに注意しましょう (Tom Kyteに感謝)。

PostgreSQL

fetch first拡張では、 offset ... rowsも使えるように定義されています。 PostgreSQLでは、offsetrowsは 付けてはいけません。MySQLの例に出てきたのと同じように、 limit/offsetが使えます。

SELECT *
  FROM sales
 ORDER BY sale_date DESC
OFFSET 10
 FETCH NEXT 10 ROWS ONLY
SQL Server

SQL Serverのtop句では、 オフセットを実現する機能はありませんでしたが、 SQL Server 2012(“Denali”)から、fetch first拡張が 使えるようになりました。標準ではオプションとされている offset句が必須です。

SELECT *
  FROM sales
 ORDER BY sale_date DESC
OFFSET 10 ROWS
 FETCH NEXT 10 ROWS ONLY

シンプルなのに加えて必要なページを取りだすのに 行のオフセットだけしか指定しなくて良いのも、この方法の利点でしょう。しかし、 必要なページにたどり着くまでに、データベースは最初からそこまでの全ての行を 数えなくてはなりません。図 7.2で、取り出すページ数を大きくして行った時に インデックスのスキャンの範囲が増える様子を表しています。

図7.2 オフセット法を使ったアクセス


この方法には、2つの欠点があります。(1) 順序付けはクエリが呼び出される 度にやり直されるので、新しい売上が挿入されるとページがずれてしまいます。 (2) 先のページを見るほど、応答時間が長くなります。

このウェブサイトにぴったりのカップは僕たちのショップにあります。
#見た目もいい感じだし、ここでの僕の仕事を支えてくれています

シーク法では、 ページの区切りに前のページのを使うので、 これらの問題を排除できます。つまり、全ページの最後のエントリの 1つ後に来るべき値を検索するのです。これは、 シンプルにwhere句で表現することができます。 逆に言うと、シーク法では既に表示した値を選択しなくて済むのです。

次の例は、シーク法を表したものです。例示のために、1日に売上は 1回しかないと仮定してみましょう。そうすると、SALE_DATEは 一意なキーと言うことになります。ある日の後の売上を選択したい時には、 降順のソートになるのでより小さい(<)を条件にします。 昇順の場合、より大きい(>)を条件ににします。それから、 fetch firstによって結果を10行に絞れば良いのです。

SELECT *
  FROM sales
 WHERE sale_date < ?
 ORDER BY sale_date DESC
 FETCH FIRST 10 ROWS ONLY

行番号の代わりに、下限を指定するのに前のページの最後の値を使えば良い事が 分かります。データベースがSALE_DATE < ?をインデックスアクセスに 使えるようになるので、これはパフォーマンスの観点からすると非常に大きな利点です。 これにより、純粋な意味で前のページの行をスキップすることができるようになります。 さらに、新しい行が挿入されても常に同じ結果が得られるようになります。

しかし、この方法は1日に2つ以上の売上がある場合には、図 7.2にあるようにうまく動かなくなります。 最初のページにあった最後の日付(つまり昨日)を指定すると、 最初のページに既に表示されたものだけでなく、昨日の全ての結果が スキップされてしまうためです。これは、都度日付を指定するので最初のエントリからの 順番を、order by句が確定的に作れないためです。 しかし、改ページにシンプルな範囲条件を使うには、これは必須条件でもあります。

確定的な結果を返すorder by句なしでは、定義上、 データベースは行の順番を1つに決められません。大抵は 同じ順番で行が得られるのは、データベースが大抵は同じ方法で クエリを実行するからです。しかし、実際には同じSALE_DATEを 持つ売上の順序を変えても、order by句の条件は 満たされます。最近のデータベースでは、クエリを実行する度に順序が違うのも よくある事になりました。それは、データベースが意図的に行を 入れ替えているのではなく、データベースがクエリの並列実行を活用するように なったためです。スレッドの実行完了の順序が確定的でないため、 同じ実行計画でも異なる行の順序で結果が得られるということです。

重要

ページングの際は、並べ替えの順序は確定的である必要があります。

機能的には「最新の日付が最初」で並べ替えるというだけの仕様でも、 我々開発者としては、order byが行の順序を確定的に するのを確実にしておかねばなりません。そのために、行の順序を 確定的にする任意の列をorder by句に追加する必要が あるでしょう。パイプライン化されたorder byで使っているインデックスに 他の列が既にあるなら、order by句にその列を追加し、そのままパイプライン化された order byとして実行できるように しましょう。それでも行の順序が確定的にならない場合は、適宜、 一意な列をインデックスに追加していきましょう。

次の例では、行の順序を確定的にするために、プライマリキーである SALE_IDorder by句とインデックスに 追加しています。さらに、望む結果を得るために、どちらの列も 一緒に「その次の値」が得られるよう指定しています。

CREATE INDEX sl_dtid ON sales (sale_date, sale_id);
SELECT *
  FROM sales
 WHERE (sale_date, sale_id) < (?, ?)
 ORDER BY sale_date DESC, sale_id DESC
 FETCH FIRST 10 ROWS ONLY;

where句は、あまり知られていないであろう 「行値」式を使って書かれています(「SQLの行値式」のボックスを参照)。 複数の値を1つの論理単位にまとめ、通常の比較演算子を適用できるように したものです。スカラ値では、降順では未満を表す条件は「その次の値」を 表します。つまり、このクエリは与えられたSALE_DATESALE_IDのペアの次に来る売上のみを返します。

SQLの行値式

通常のスカラ値に加え、SQL標準ではいわゆる 行値コンストラクタを定義しています。これは、 「順序付きの値のセットを、行あるいは部分行に構成」します [SQL:92, §7.1: <row value constructor>]。構文的には、行値は括弧内に 列挙されます。insert文に使われているのが、 最も知られているものでしょう。

行値コンストラクタをwhere句内で使うのは あまり知られてはいませんが、完全に有効な方法です。SQL標準では、 行値コンストラクタに対する全ての比較演算子が定義されています。 例えば、未満を表す処理に関しては次の通りです。

"Rx < Ry" is true if and only if RXi = RYi for all i < n and RXn < RYn for some n.

全てのi < nでRXi = RYiかつ、あるnに対しRXn < RYnの時、 かつその時に限り、Rx < Ryは真となる。

[SQL:92, §8.2.7.2](日本語は訳者による)

inが値が列挙された中での インデックスの位置に対応します。ある値RXnが対応するRYnよりも小さく、かつ 先行する値のペアが同じ(i<nの時RXi = RYi)の時、 行値RXはRYより小さい、と言う事です。

この定義により、RX < RYという表現が「並べ替えるとRXはRYの前に来る」という シーク法に必要なロジックと同じ意味になります。

行値式はSQL標準の一部ではありますが、サポートされているデータベースは 少数に留まります。SQL Server 2012 (“Denali”) は行値式をサポートしていません。 Oracleでは基本的にはサポートされていますが、行値式に対する範囲条件の適用は できません(ORA-01796)。MySQLは行値式を正しく評価しますが、 インデックスアクセス時のアクセス述語としては使えません。 DB2(LUWのみ、10.1以降)とPostgreSQL(8.4以降)は行値式の述語をサポートしており、 かつ対応するインデックスがある場合は、インデックスへの アクセスにも使用可能です。

行値式を正しくサポートしていないデータベースでも、 シーク法に近い方法を使う事はできます。ただし、PostgreSQLのように エレガントでも効率的でもなくなってはしまいます。この近似法では、 必要なロジックを記述するために「普通の」比較のやり方を使います。 次は、Oracleでの例です。

SELECT *
  FROM ( SELECT *
           FROM sales
          WHERE sale_date <= ?
            AND NOT (sale_date = ? AND sale_id >= ?)
          ORDER BY sale_date DESC, sale_id DESC
       )
 WHERE rownum <= 10

where句は2つの部分からなっています。 最初はSALE_DATEに以下(<=)の条件を適用して いるだけです。ただし、これだけでは必要以上の行が選択されてしまいます。 where句のここは、データベースがインデックスに アクセスできるようにしているだけのシンプルな部分です。 where句の2番目の部分では、全ページで既に表示済みの 行を削除しています。「近似法のインデックス」という ボックスで、なぜwhere句がこのようになっているかを 説明しています。

近似法のインデックス

論理式は色々な方法で表現することができます。例えば、 前述のロジックは次のようにも実装できます。

WHERE (
         (sale_date < ?)
       OR
         (sale_date = ? AND sale_id < ?)
      )

このパターンの方が、少なくとも人間にとっては分かりやすいでしょう。 しかしデータベースは別の見方をします。SALE_DATEは どちらの部分にも共通していますが、データベースは、whereSALE_DATE/SALE_IDのペアから始まる全ての行を 選択するものとは認識してくれません。その代わり、データベースは where句全体をフィルタ述語として使おうとします。 我々としては、orで分けられた部分のどちらにもオプティマイザが 「SALE_DATE <= ?を適用してくれる」と期待したいところですが、 そのようなサービスをしてくれるデータベースはありません。

そのため、読みやすさは全く向上しませんが、冗長な条件を手動で 付け加える必要があります。

WHERE sale_date <= ?
  AND (
         (sale_date < ?)
       OR
         (sale_date = ? AND sale_id < ?)
      )

嬉しい事に、全てのデータベースでこのwhere句は アクセス述語として使われます。しかしこの書き換えのせいで、 これが前述の近似法であるとは気付きにくくなってしまいました。 さらに、元のロジックでは「不要な」(冗長な)部分が後から whereから削除されてしまう事が防止されていましたが、 それもなくなってしまいました。

実行計画から、where句の最初の部分が アクセス述語として使われている事が分かります。

---------------------------------------------------------------
|Id | Operation                      | Name    |  Rows | Cost |
---------------------------------------------------------------
| 0 | SELECT STATEMENT               |         |    10 |    4 |
|*1 |  COUNT STOPKEY                 |         |       |      |
| 2 |   VIEW                         |         |    10 |    4 |
| 3 |    TABLE ACCESS BY INDEX ROWID | SALES   | 50218 |    4 |
|*4 |     INDEX RANGE SCAN DESCENDING| SL_DTIT |     2 |    3 |
---------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   1 - filter(ROWNUM<=10)
   4 - access("SALE_DATE"<=:SALE_DATE)
       filter("SALE_DATE"<>:SALE_DATE
           OR "SALE_ID"<TO_NUMBER(:SALE_ID))

SALE_DATEのアクセス述語によって、データベースは 前のページで表示済みの日をスキップすることができます。 where句の2番目の部分は、フィルタ述語のみになっています。 つまり、データベースは全ページのエントリの内のいくつかをもう一度調査し、 すぐに捨てていると言う事が分かります。図 7.3で、そのアクセスパスを説明しています。

図7.3 シーク法を使ったアクセス


図 7.4では、 オフセット法とシーク法のパフォーマンスの特徴を比較しています。グラフの 左寄りでは、測定結果にばらつきがあってはっきり分かりませんが、 ページ数が20を超えてからはその違いは歴然としています。

図7.4 次ページを取得する際のスケーラビリティ


シーク法にも欠点はあり、最も大きいのは扱いが難しい事でしょう。 where句を注意深く構成しなければならないのに加え、 任意のページを取り出す事もできません。さらに、表示の順序を変える際は 全ての比較条件とソート処理を逆にする必要があります。ただし、 ページのスキップと逆順の表示という2つの機能は、ユーザインタフェースに 無限スクロール機能を使う場合には不要です。

この説明が気に入れば、きっと この本も 気に入るはず。

図7.5 データベースごとの機能表


Photo of Markus Winand
Markus Winand氏は、開発者がSQLパフォーマンスを改善するお手伝いをしています。 彼は、SQL Performance Explainedの 著者でもあり、出張トレーニングhttp://winand.at/での リモート講義も 行っています。