LoginSignup
25
9

More than 3 years have passed since last update.

フューチャーAdvent Calendar 2019Day 9future
@bubu_sukeinSumally Inc.

今更SQL これでスッキリ！テーブル結合方式！~手続き型言語で表現してみた~

Last updated at Posted at 2019-12-08

0. はじめに

フューチャーAdvent Calendar 2019 9日目のエントリーです！張り切っていきます！

最近、競技プログラミングを始めたのをきっかけに、
テーブル結合アルゴリズム（テーブル結合方式）1を手続き型言語（C++）で表現してみました。

テーブル結合方式の特徴について、かなり理解が深まったので記事投稿します2。

＃これまでいろんな図解説明記事はありますので そちら もご参考に。
＃相補的にみていただければよいかと。

1. 手続き型言語でテーブル結合方式説明

1-0. 題材

今回の説明のために以下のテーブルとデータを使います。
レジで売り上げたデータ保存するt_sales テーブルと、商品マスタのm_itemです。
t_salesは1回のレジ取引をpos_transaction_idで管理し、その中で、どの商品をいくつ買って、いくらで売ったかを記録してます。
例えば、pos_transaction_id = 1 では 1001,1002,1003 の商品をそれぞれ2個、1個、1個売ったことがわかります。
image.png

今回は以下のSQLを題材にして、各結合方式を説明します。

販売数量.sql　
SELECT
    *
FROM
   t_sales sl
INNER JOIN
   m_item  it
ON
   it.item_code = sl.item_code
;

1-1. ネステッドループ結合

解説

nestedLoop.cpp
// vector は動的配列の型
// salesEntity はt_sales の構造体
// itemEntity はm_item の構造体
// resultEntity はt_sales, m_item の結合結果の構造体。salesEntity とitemEntity を要素に持つ。

vector<resultEntity> joinByNestedLoop( vector<salesEntity> sales, vector<itemEntity> items){
    vector<resultEntity> responseEntity; 
    int N = sales.size();
    int M = items.size();

    for (int i = 0; i < N; i++){  //N回ループ
        for(int j = 0; j < M; j++){ //M回ループ
            if (sales[i].itemCode == items[j].itemCode) {
                responseEntity.push_back({sales[i],items[j]});  //結果セットに1件加える
            }
        }
    }
    return responseEntity; //計算量:O(NM)
}

for ループ2重だから「ネステッドループ（入れ子ループ）」。
よくネステッドループに出てくる外部表・内部表（forの外側・内側）もこれでみるとスッキリ明快。

性能改善アプローチ

上記だと2重ループでめちゃくちゃ遅いように見えます。
が、Primary KeyやIndexを使うと、劇的に変わります。

nestedLoopWithPK.cpp
vector<resultEntity> joinByNestedLoopWithPK( vector<salesEntity> sales, vector<itemEntity> items){
    vector<resultEntity> responseEntity;
    int N = sales.size();

    for (int i = 0; i < N; i++){  //N回ループ

        itemEntity item = items[sales[i].itemCode];  //PKだとループ不要= O(1)
        responseEntity.push_back( {sales[i] , item });

    }
    return responseEntity; //計算量:O(N)
}

PKだと、内側のループは実質なくなり、計算量はO(N)。

nestedLoopWithIndex.cpp
vector<resultEntity> joinByNestedLoopWithIndex( vector<salesEntity> sales, vector<itemEntity> items){
    vector<resultEntity> responseEntity;
    int N = sales.size();

    for (int i = 0; i < N; i++){  //N回ループ

        itemEntity item = binarySearch(sales[i].itemCode, items);  //二分探索: O(log M)
        responseEntity.push_back( {sales[i] , item });

    }
    return responseEntity; //計算量:O(NlogM)
}

INDEXだと、二分探索になるため、計算量はO(NlogM)。

二分探索の効果と計算量の補足

・二分探索の効果
　Mが1億の場合、logMの値（底は2）は25.6です。計算量が劇的変わります。

・計算量
　ちらほら書いている計算量というのはCPU負荷や処理時間の目安になるものです。
　計算量オーダーの求め方を総整理！ 〜 どこから log が出て来るか 〜
　B-treeインデックス入門

1-2. ソートマージ結合

解説

sortMergeJoin.cpp
vector<resultEntity> joinBySordMerge( vector<salesEntity> sales, vector<itemEntity> items){
    vector<resultEntity> responseEntity;

    //ソートしてその結果を保持(sales)・・・★１
    vector<salesEntity> sortedSales(sales); //データのソート結果を保持するために値をコピー
    sort(sortedSales.begin(),sortedSales.end(),salesItemCodeCmp); //結合キー（itemCode）でソート※計算量: O(NlogN)

    //ソートしてその結果を保持(items)・・・★２
    vector<itemEntity> sortedItems(items); //データのソート結果を保持するために値をコピー
    sort(sortedItems.begin(),sortedItems.end(),itemsItemCodeCmp); //結合キー（itemCode）でソート※計算量: O(MlogM)

    int index_sales = 0;
    int index_items = 0;
    while(index_sales < sales.size() && index_items < items.size()){ //salesかitemsのどちらかの全スキャンが終われば終了。※計算量: O(N+M)

        if(sortedSales[index_sales].itemCode == sortedItems[index_items].itemCode){
            responseEntity.push_back( {sortedSales[index_sales], sortedItems[index_items] });
            index_sales++; //次のindexに進む
            continue;
        }

        //小さい方のindexをインクリメント
        if(sortedSales[index_sales].itemCode < sortedItems[index_items].itemCode){
            index_sales++;
            continue;
        }
        if(sortedSales[index_sales].itemCode > sortedItems[index_items].itemCode){
            index_items++;
            continue;
        }
    }
    return responseEntity; //計算量:O(NlogN) + O(MlogM) + O(N + M)　※厳密には計算量は足し算しませんがわかりやすさのため
}

ソートした結果を実テーブルとは別に準備してから比較していきます。
結合に必要なテーブルのデータ量が多いと、メモリにデータを抱えきれなくなり、とたんに処理が遅くなります。

性能改善アプローチ

結合キーに対して、Indexをつくっておくと、このソート処理とソート結果の保持（ソースコードの★１、★２の箇所）が不要になります。
※Indexはデータをソートして保持しているため。
sales, item　ともにIndexを持っていたとすると、計算量は O(N+M) になります。

また、以下のようにソート前に各テーブルのデータを絞り込んでおくようにすると、ソート対象の件数が減り性能が改善します。

improveMerge.sql
-- ソート・マージ結合の場合、SQL1よりもSQL2のほうが効率的に処理できる。

--SQL1
SELECT
    *
FROM
    t_sales s
INNER JOIN
    m_items i
ON
    i.item_code = s.item_code
WHERE
    s.item_code IN(1001, 1002)
;
--SQL2
SELECT
    *
FROM
    t_sales s
INNER JOIN
    m_items i
ON
    i.item_code = s.item_code
WHERE
    s.item_code IN(1001, 1002)
AND i.item_code IN(1001, 1002) --違いはここ！
;

1-3. ハッシュ結合

解説

Hash.cpp
string convertHashkey(int itemCode){
    return to_string(itemCode);//今回は簡単のために特にロジックなし！
}

vector<resultEntity> joinByHash( vector<salesEntity> sales, vector<itemEntity> items){
    vector<resultEntity> responseEntity;

    unordered_map<string, itemEntity> hashTable;  // JavaでいうHashMapです。

    // ハッシュテーブルに格納 計算量:O(M)
    for(int i = 0; i < items.size(); i++){
        string hashKey = convertHashkey(items[i].itemCode);
        hashTable.insert({hashKey, items[i]});
    }

    //ハッシュテーブルとの結合 計算量: O(N)
    for(int i = 0; i < sales.size(); i++){
        string joinKey = convertHashkey(sales[i].itemCode);
        responseEntity.push_back( {sales[i], hashTable[joinKey]} );
    }

    return responseEntity; //計算量: O(N) + O(M)　※厳密には計算量は足し算しませんがわかりやすさのため
}

一方のテーブルからハッシュテーブルを作成後、もう一方のテーブルをそのハッシュテーブルに当てていきます。
結合は特別なハッシュ関数をつかうので、結合条件についてのインデックスの有無では性能は改善しません。

また、ハッシュテーブルのデータ量が多いと、メモリにデータを抱えきれなくなり、処理が遅くなります。

key指定しての検索になるため、※例えば以下のような範囲指定の結合にはハッシュ結合では対応できません。

HashUnavailable.sql
SELECT
    *
FROM
    t_sales s
INNER JOIN
    m_item_history ih
ON
    ih.item_code = s.item_code
AND 2019-12-09 BETWEEN ih.start_date AND ih.end_date
;

性能改善アプローチ

前述の通り、結合条件についてのインデックスの有無では、性能は改善しません。
結合までに如何にデータを絞り込んでおけるか、が鍵になります。

例えばPostgresではメモリにデータを抱えきれなくなると、一時ファイルに書き込んで処理しようとしますが、
一時ファイルにも書き込みきれない場合は以下のようなエラーが出ます。
could not write to hash-join temporary file: No space left on device
このエラーが出た際は、大量データ同士（テーブル or VIEW）をハッシュ結合しようとしていることが原因の可能性が高いです。
「結合までに如何にデータを絞り込んでおけるか」を考えましょう。

1-4. 結合方式まとめ

以上を踏まえて簡単にまとめておきます3。

  • ネステッドループ

    • 計算量（結合条件にINDEXが使える場合）：O(N) or O(NlogM)
    • 計算量（結合条件にINDEXが使えない場合）：O(N*M)
    • メモリ：ソートマージや、ハッシュとは違い、追加で確保するデータはない

  • ソートマージ

    • 計算量（結合条件にINDEXが使える場合）：O(N+M)
    • 計算量（結合条件にINDEXが使えない場合）：O(NlogN)+ O(MlogM)+ O(N+M)
    • メモリ：INDEXが使えない場合、結合テーブル同士のソート結果を格納する必要あり

  • ハッシュ

    • 計算量：O(N) + O(M)
    • メモリ：一方のテーブルデータをハッシュテーブルに格納する必要あり
    • その他：等価結合のみに対応

2. ネステッドループのススメ

以上を踏まえて、私はネステッドループを推します4。

理由は2つ。
1. DBサーバに優しい結合方式（ちゃんとINDEXとテーブルを用意すれば）
2. テーブル設計とSQLが整う

簡単に説明します。

2-1. 理由1: DBサーバに優しい結合方式

ネステッドループは前述した通り、メモリの使用が少ない処理です5。
INDEXが機能すれば、他の結合と引けを取らないほど高速に処理できるため、
特に大量データを扱う際は、DBサーバの負荷が他よりも低くなることが多いです。

RDBはACID特性を保つために、柔軟に拡張できないことが近年問題としてよく取り上げられます6。
簡単にスケールアウトできる他のアプリケーションよりもボトルネックになりやすいため、サーバ負荷を下げるアプローチが重要だと考えています。

2-2. 理由2: テーブル構成とSQLが整う

繰り返しになりますが、ネステッドループで効率的な検索ができるのはINDEXやPKが結合条件で指定されたときです。
副問い合わせ同士の結合ではINDEXは利用できません。このため、必然的にテーブルで結合するSQLを書くようになります。
また、テーブル結合でSQLを作成できるよう、適切なリレーションとINDEXをテーブルに持たせるようになります。

このようにネステッドループを念頭におくと、程よい縛りが生まれ、テーブル構成やSQLが綺麗になると考えています。

具体例

以下のテーブルを使って、具体例を説明します。
image.png

Javaのクラス的にまとまりを作ってしまう例
Javaのクラス的にSQLの副問い合わせとしてまとめるようなSQLを紹介します。
この場合、副問い合わせ同士の結合となるため、m_product のPKのINDEXが使えません。
また、SQL自体も入り組んで読みにくくなります。

Javaのクラス的にまとまりを作ってしまう例.sql

SELECT
    product_summary.create_date
,   product_summary.product_id
,   product_info.product_name
,   product_info.color_name
,   product_info.size_name
,   product_summary.products
FROM
(   --日別・製品別の個数
    SELECT
        result.create_date
    ,   result.product_id
    ,   SUM(result.products) AS products
    FROM
        t_product_result result
    GROUP BY
        result.create_date
    ,   result.product_id
)   AS product_summary
INNER JOIN
(   --製品の情報をまとめたもの
    SELECT
        prd.product_id
    ,   prd.product_name
    ,   col.color_name
    ,   siz.size_name
    FROM
        m_product prd
    INNER JOIN
        m_color col
    ON
        col.color_id = prd.color_id
    INNER JOIN
        m_size  siz
    ON
        siz.size_id = prd.size_id
)   AS product_info
ON
    product_info.product_id = product_summary.product_id
;

上記SQLを書き換えたのが以下です。
これだとm_product, m_color, m_size の全てがPKでの結合が有効に機能します。
見た目もスッキリです。

理想.sql
SELECT
    product_summary.create_date
,   product_summary.product_id
,   prd.product_name
,   col.color_name
,   siz.size_name
,   product_summary.products
FROM
(   --日別・製品別の個数
    SELECT
        result.create_date
    ,   result.product_id
    ,   SUM(result.products) AS products
    FROM
        t_product_result result
    GROUP BY
        result.create_date
    ,   result.product_id
)   AS product_summary
INNER JOIN
    m_product prd
ON
    prd.product_id = product_summary.product_id
INNER JOIN
    m_color col
ON
    col.color_id = prd.color_id
INNER JOIN
    m_size  siz
ON
    siz.size_id = prd.size_id
;

3. まとめ

よくよく考えれば、みんな生まれてから使ってるのはVBAとかJavaとかCとかPythonとか、
所謂手続き型言語と言われているものですよね。
馴染みある手続き型言語で表現することで、テーブル結合方式が馴染みあるものに見えたのではないでしょうか。
もしそうならとても嬉しいです。

冒頭でも記載した通り、最近始めた競技プログラミングがこの記事のきっかけになってます。
新しいことを始めると思わぬところで線がつながるのが面白いですね。

今更SQLシリーズはこれからも数増やしていこうと思いますので、
これからもチェックして頂ければありがたいです。ありがとうございました。

過去記事

  1. 代表的なものに、ネステッドループ結合、ソートマージ結合、ハッシュ結合があります（今回はこれらを取り上げます）。 ↩

  2. テーブル結合方式の特徴を理解するという目的（と私の知識）の範囲でアルゴリズムを書いています。実際のアルゴリズムはもっと複雑だと思いますのでご了承ください。 ↩

  3. MySQLはソートマージ結合とハッシュ結合は実装していないので注意です。ORACLE, SQL Server, PostgreSQL は3つとも対応しています。 ↩

  4. ネステッドループにしてほしいと思ってSQL作成・実行しても、最終的に結合方式を決定するのはDBです。我々ができることは目的の結合方式が選択されるようにお膳立てすることです。（例えば、各結合方式の性能改善アプローチに記載した内容や、最新の統計情報を取得することがお膳立てに当たります）。ヒント句と言われるもので結合方式を指定することもできますが、ヒント句で指定しても尚、DBがその結合方式を選択しない場合もあります。 ↩

  5. メモリはDB全体で考える必要があります。処理単体で実行したときは問題なくても、夜間のバッチ処理時に複数処理が重なり、メモリが枯渇することがあります。 ↩

  6. 参考: RDBではうまくいかなくなってきた理由 ↩

25
9
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
25
9