bird雪, お仕事, ガクガクブルブル, SQL チューニング

雪

天気予報じゃ「積もらない」なんていってたのに、じゃかじゃか降ってるよ…（涙。
都心でこの状況だと八王子に帰るころにはひざ位まで積もってるかもしれないなぁ。

お仕事

今日が仕事納めなのです。といってももうほとんど年内にやることはないんだけれども…（笑。納会でお酒を飲むために出社してるようなものだなぁ。

ガクガクブルブル

ひと月ほど前、とある人がこんなことをおっしゃっておりました。
彼「PSX 格安で入手しちゃったよー。7500 を 4 万円台。」
僕「へーすごく安いですね。どこのお店です？」
彼「ヤフオクだよ、ヤフオク」
実はこの方、ほんのちょっと前にも「Cybershot T3」をやっぱりヤフオクで格安で手に入れた、と喜んでいたのです。僕は「ヤフオクはリスキーだけど、やっぱりそれなりに安く買えることもあるのだなぁ」と普通に感心して聞いていました。
ところが先日、その人が浮かない顔をしています。
彼「落札した PSX なんだけど、納期が急に 2 週間から 8 週間になっちゃったんだよ…。届くのは 2 月だって」
そ、それってモロ「チャリンカー」なのでは…。

SQL チューニング

次のようなテーブルがあったとして、

CREATE TABLE check_list (  
  product_id_start integer,  
  product_id_end   integer  
  CONSTRAINT check_list_check_1 CHECK (  
    product_id_start <= product_id_end  
  )
);

「ある product_id を含む範囲を持つレコードが上記テーブルに存在するか判定する」というような処理を考えます。つまり、テーブルの内容が下記の通りだとして、

  product_id_start | product_id_end  
 ------------------+----------------  
                 0 |           1000

product_id = 100 の場合は真、product_id = 1001 の場合は偽であるような判定を行わせたいとします（境界値は含まれるものとします。つまり 0 や 1000 も真）。

まず、ごく素直に書けば次のような SQL になると思います。

SELECT * FROM check_list  
 WHERE '探したい product_id' BETWEEN product_id_start AND product_id_end  
 LIMIT 1;  
結果が 0 行か 1 行かで判定。

（LIMIT というのは PostgreSQL 特有の書き方で、結果セット行数の上限を指定する句です。Oracle なら rownum に相当。）上記 SQL はシンプルで良いのですが、check_list に大量の行が存在する場合、INDEX をどう作成してもかなりの確率で全表走査、もしくは INDEX 走査が発生してしまい1、性能が急激に悪化してしまいます。特に「該当する行がない」product_id の場合の性能劣化が激しく（最後まで走査しないと分からないため）、処理としてこちらがメインの場合は致命的です。

行数が増えた場合もコストをかけず検索する方法はないものか、と考えた結果、次のような方法を思い付きました。

まず、check_list に挿入される行に、「範囲の重なるレコードは挿入出来ない」という制約を一つ追加します。つまり例えば、上記内容のテーブルに対して、(100, 2000) という行は挿入出来ず、(1001, 2000) とう行ならば挿入出来る、というような制約を追加するわけです2。範囲の重なるレコードが入れられないとしても、テーブルとしての表現力には差は生じません（管理が少し面倒になるだけ）。また、product_id_start に INDEX を張っておきます。

その上で、次のような SQL により判定します。

SELECT * FROM  
 (SELECT * FROM check_list  
   WHERE product_id_start<='探したい product_id'  
   ORDER BY product_id_start DESC LIMIT 1) sub_check_list  
 WHERE product_id_end>='探したい product_id';  
結果が 0 行か 1 行かで判定。

最初の query と比較するとちょっと複雑ですね。簡単に説明すると、

まず sub query 部で、探したい product_id よりも等しいか小さい product_id_start 値を持つ行の内、もっとも大きな product_id_start 値を持つ行を 1 行選択します。product_id_start 列には INDEX があるため、sub query 部の WHERE 句も ORDER BY 句も全て INDEX により処理され低コストです。

ここで「範囲の重なる行が存在しない」という前提条件を設けてあるため、ある product_id を含む範囲の行が存在するとすれば、sub query 部で得られた 1 行以外はありえないことが保証されます。そこで、その得られた 1 行に対して product_id_end をチェックすれば、該当する行が存在するかどうかが分かるわけです。

こちらの query の場合、check_list の行数がたとえ増えたとしても、sub query 部は INDEX 完全ヒット3、外側の処理も常に 1 行が対象となり、ほぼ一定のコストで検索することが出来ます。

これにて一件 complete です。よかったよかった。

コメント

SAK (Fri, 31 Dec 2004 02:51:41)
start-endやめて全ID展開挿入にしとけば、こんなややこしい事考えんでもよかったのにな（´ー｀)y─┛~~
Digitune (Fri, 31 Dec 2004 11:31:10)
単純 ID マッチにするのは基本だけど、該当 ID の order が下手すりゃ数百万とかいう可能性もある状況ではあまりに単純すぎる設計だと思う。

どちらかというと求められる要件の方が「チェックにマッチするかどうか」という単純なものであるのだし、上程度のコードで済むなら可能なかぎり柔軟に指定できるようにしておくのには大きな意味がある。つーか「こんなややこしい事」というほどややこしくないよ…。この程度の SQL ならプロは普通に使ってるでしょ(俺はヘボなのでいちいち書いてるけど)。

  1. それぞれの列に独立に INDEX を張った場合も 2 つの列を含む複合 INDEX を作成した場合も、start 側の選択には INDEX が利用されますが、end 側は順に走査せざるを得ない状況となります。 ↩︎

  2. 実際は INSERT/UPDATE TRIGGER により実現しました。 ↩︎

  3. B-tree INDEX なのでオーダーは O(log(n)) かな？ ↩︎

Prev | Next