Play With SQL Part 01 : minus/except

Motivation

次のような M:M のテーブルがあったとする。

Parent(parent_id) – Junction(parent_id, child_id) – Child(child_id)

child_id の組み合わせ (A, B, C) が与えられたときに、SQL で完全一致する parent_id を取得する方法

ナイーブ方式 : 計算量は O(N)

STEP1:parent_id の一覧を取得

  SELECT parent_id
    FROM Parent
ORDER BY parent_id;

STEP2:各 parent_id に対して parent_id をキーにして child_id の一覧を取得

  SELECT child_id
    FROM Junction
   WHERE parent_id = XXX
ORDER BY child_id;

STEP3:SELECT した child_id 一覧と (A, B, C) が完全一致するか比較。
一致すれば終了。 しなければ STEP2 に戻り、次の parent_id を試す。

SQLで頑張る方式 : 計算量は O(1)

SQL 一発で決める。

  SELECT parent_id
    FROM Junction jt1
   WHERE NOT EXISTS (
     SELECT child_id
       FROM Junction jt2
      WHERE jt2.parent_id = jt1.parent_id
      MINUS
     SELECT child_id
       FROM Child
      WHERE child_id IN (A, B, C) -- 可変長
        AND NOT EXISTS (
        SELECT child_id
          FROM Child
         WHERE child_id IN (A, B, C) -- 可変長
         MINUS
        SELECT child_id
          FROM Junction jt2
         WHERE jt2.parent_id = jt1.parent_id))
GROUP BY parent_id;

Result

一昔前のマシンで、各 parent_id に対して 3回実行し、最速の処理時間(ミリ秒)をプロット(線形回帰付き)したのが下図

code

R(ggplot2) で作成

> library(ggplot2)
> df <- read.csv('sql-membership-test.log') 
> head(df)
  Type  Id     Time
1  NEW 100 12.51912
2  NEW 101 14.95290
3  NEW 102 14.37616
4  NEW 103 14.22214
5  NEW 104 16.36386
6  NEW 105 13.79705
> png(file="sql-membership-pre-post.png", bg="transparent", width=600, height=600)
> qplot(Id, Time, data=df, geom=c("point", "smooth"), group=Type, color=Type, method="lm", main="SQL Membership Pre/Post", ylab="Time(millisecond )")
> dev.off()

Discussion

リリース時は Parent テーブルの数が少なかったのかもしれないが 一定の運用期間を経て、 Parent テーブルのデータ数も増えてきた。
parent_id が大きなものに対して、旧方式では該当する組みあわせにたどりつくまでに、何度も SQL を発行する必要があり、特に一括処理においてパフォーマンスに影響が出ていた。
SQL 一発で済ます新方式を採用することで、SQL の発行数を大幅に減らすことができた。

実務で Minus(Except) をうまくつかうことができ、気分がよい。

今回の SQL ではミックさんの「達人に学ぶ SQL徹底指南書」(翔泳社, 2008年)が非常に参考になった。

Advertisements
Tagged with: , , ,
Posted in database

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Archives
  • RT @__apf__: How to write a research paper: a guide for software engineers & practitioners. docs.google.com/presentation/d… /cc @inwyrd 4 months ago
  • RT @HayatoChiba: 昔、自然と対話しながら数学に打ち込んだら何かを悟れるのではと思いたち、専門書1つだけ持ってパワースポットで名高い奈良の山奥に1週間籠ったことがある。しかし泊まった民宿にドカベンが全巻揃っていたため、水島新司と対話しただけで1週間過ぎた。 それ… 4 months ago
  • RT @googlecloud: Ever wonder what underwater fiber optic internet cables look like? Look no further than this deep dive w/ @NatAndLo: https… 4 months ago
  • @ijin UTC+01:00 な時間帯で生活しています、、、 10 months ago
  • RT @mattcutts: Google's world-class Site Reliability Engineering team wrote a new book: amazon.com/Site-Reliabili… It's about managing produc… 1 year ago
%d bloggers like this: