狠狠撸

狠狠撸Share a Scribd company logo

カラムストアと整列（基础）

?
?
S
s5yata

カラムの値を基準として行 ID の一覧を整列する方法について，少しばかり調べてみたことを述べています．

1 of 20
Downloaded 17 times
カラムストアと整列 矢田 晋 @s5yata 有限会社未来検索ブラジル
自己紹介 ? 所属 – 有限会社未来検索ブラジル ? 仕事内容 – カラムストア＋全文検索（Grnxx）の開発 ? 公開物 – トライのライブラリ（darts-clone, marisa-trie） – 日本語 N-gram コーパス 2014年1月11日 カラムストアと整列 2
発表内容 カラムストアの ORDER BY について （独断と偏見により） 検討＆実験してみた 2014年1月11日 カラムストアと整列 3
カラムストアって何？ ? 縦に分割されているイメージ ROWID 1 ColumnA 100 ColumnB “Apple” ColumnC 1.73 2 3 … N–2 N–1 N 200 150 … 300 120 230 “Banana” “Orange” … “Melon” “Peach” “Lemon” 0.25 1.00 … 3.14 1.41 2.00 2014年1月11日 カラムストアと整列 4
カラムストアの検索 ? 条件に該当する行の一覧を作成する – 例：ColumnA < 200 => { 1, 3, N – 1 } ROWID ColumnA ColumnB ColumnC 1 100 “Apple” 1.73 2 200 “Banana” 0.25 3 150 “Orange” 1.00 … … … … N–2 300 “Melon” 3.14 N–1 120 “Peach” 1.41 N 230 “Lemon” 2.00 2014年1月11日 カラムストアと整列 5
カラムストアの整列 ? 行（ROWID）の一覧を整列する – 例：ORDER BY ColumnC => { 3, N – 1, 1 } ROWID ColumnA ColumnB ColumnC 1 100 “Apple” 1.73 2 200 “Banana” 0.25 3 150 “Orange” 1.00 … … … … N–2 300 “Melon” 3.14 N–1 120 “Peach” 1.41 N 230 “Lemon” 2.00 2014年1月11日 カラムストアと整列 6
問題を単純化しよう ? データ型 ? 整列条件 – ROWID: UInt64 – Column: Int64 – 単一カラム – 昇順固定 ? データ ? 整列範囲 – 擬似乱数（mt19937） – 上位 Limit 行 ? 行の一覧 – { 1, 2, 3, …, N – 1, N } 2014年1月11日 カラムストアと整列 7
サンプルコード std::vector<Int64> column; std::vector<RowID> rows; generate_data(&column, &rows); std::sort(rows.begin(), rows.end(), Comparer(column)); test_result (column, rows); ここの時間を 計測する 2014年1月11日 カラムストアと整列 8
std::sort の中身 ? 整列アルゴリズム – クイックソート＋挿入ソート ? クイックソートで絞り込み，挿入ソートで仕上げる – ヒープソート ? クイックソートで効率が悪いときに使う ? 時間計算量 – O(n log n) 2014年1月11日 カラムストアと整列 9
実際にやってみた ? 環境 – プロセッサ：Core2 Duo U9600 1.6GHz – コンパイラ：clang++-3.3 ? データ – 行数：1,000,000 – 値域：[ 0, 1,000,000] ? 結果 – 時間：0.293 秒 2014年1月11日 ベースライン カラムストアと整列 10
もっと速くするには ? ランダムアクセスを減らす – ROWID とデータを組にして整列する ? std::vector<std::pair<RowID, Int64>> ? 値の重複を利用する – 三分岐のクイックソートにする ? 整列範囲を利用する – 部分ソートを使う 2014年1月11日 カラムストアと整列 11
ランダムアクセスを減らす ? サンプルの実装 – 問題点 ? Column の参照がランダムアクセスになる ? ROWID とデータを組にする – 利点 ? Column の参照がシーケンシャルアクセスになる – 欠点 ? 組にする手間がかかる ? 整列結果を書き戻す手間がかかる 2014年1月11日 カラムストアと整列 12
さっそく試してみた ? 環境 – プロセッサ：Core2 Duo U9600 1.6GHz – コンパイラ：clang++-3.3 ? データ – 行数：1,000,000 – 値域：[ 0, 1,000,000] ? 結果 – 改良前：0.293 秒 – 改良後：0.192 秒 2014年1月11日 速くなった カラムストアと整列 13
値の重複を利用する ? 通常のクイックソート – 枢軸以下，枢軸，枢軸以上 ? 枢軸の同値は左右のどちらかに入る ? ほぼ二分岐になる ? 三分岐のクイックソート – 枢軸より小さい，枢軸と同じ，枢軸より大きい ? 値の重複が多ければ再帰が浅くなる ? 値の種類が少なければ再帰が浅くなる 2014年1月11日 カラムストアと整列 14
また試してみた ? データ – 最大値：10, 100, …, 1,000,000 最大値 改良前 [秒] 改良後 [秒] 10 0.132 0.067 100 0.145 0.095 1,000 0.160 0.122 10,000 0.165 0.154 100,000 0.186 0.181 1,000,000 0.192 0.212 2014年1月11日 カラムストアと整列 速くなった 遅くなった 15
整列範囲を利用する ? 全体ソート – 全体を整列して上位 Limit 行を取り出す ? 部分ソート（クイックソート） – 上位 Limit 行以外の整列を省略する ? クイックソートなら簡単に導入できる 2014年1月11日 カラムストアと整列 17
またまた試してみた ? 整列範囲 – Limit：10, 100, …, 1,000,000 Limit 改良前 [秒] 改良後 [秒] 10 0.212 0.036 100 0.213 0.036 1,000 0.212 0.036 10,000 0.214 0.039 100,000 0.212 0.051 1,000,000 0.212 0.207 2014年1月11日 カラムストアと整列 速くなった 18
狭い整列範囲を利用する ? 部分ソート（挿入ソート） – 手順 ? 先頭の Limit 行を整列する ? 先頭の Limit 行が上位 Limit 行となるように 残りの行をひとつずつ挿入していく – ポイント ? アクセスの局所性が高い ? 平均時間計算量は O(n) になる 2014年1月11日 カラムストアと整列 19
比べてみた ? 整列範囲 – Limit：10, 100, …, 1,000,000 Limit クイックソート [秒] 10 0.067 100 0.095 1,000 0.122 10,000 0.154 100,000 0.181 2014年1月11日 挿入ソート [秒] 0.004 0.005 0.016 1.064 – カラムストアと整列 速くなった 遅くなった 20
まとめ ? 話した内容 – 基本はクイックソート – データ?整列条件に応じた効率化 – 挿入ソートが大活躍 ? 話さなかった内容 – 整列の安定?不安定 – 整列範囲の Offset – 複数カラム対象の整列 – ヒープソートによる部分ソート 2014年1月11日 カラムストアと整列 21

More Related Content

カラムストアと整列（基础）