唯物是真 @Scaled_Wurm

プログラミング(主にPython2.7)とか機械学習とか

BigQueryで効率的なクエリを書いて高速化する

BigQueryでクエリを書く時に、クエリの書き方によって実行時間を高速化できたり処理するバイト数を節約したりできます
Googleが公式でBigQueryのベストプラクティス集(今はまだ未翻訳)を公開してくれているので、そのうちのクエリを書く時周りのノウハウを簡単にまとめておきます。別々のページの内容なので重複があったら端折ったりしています
誤訳や解釈の誤りがあったらコメントなどで教えてください

BigQueryのベストプラクティス(クエリ編)

入力されるデータの量を減らす

Managing Input Data and Data Sources  |  BigQuery  |  Google Cloud Platform

SELECT *を避ける

SELECT *はテーブル全体を読み込んでしまうのでよくない。できるだけ使うカラムを減らしましょう
Standard SQLを使っているならSELECT * EXCEPT (カラム名1, ...)と書くことで指定したカラム以外のカラムを取ってくることで少し節約ができる。
LIMITを付けても読み込まれるデータ量は変わらないので、テーブル全体を読み込んだのと同じバイト量で課金されてしまいます
もしもすべてのカラムにアクセスする必要があるのなら、あらかじめテーブルを日付でパーティショニングしておいたりして小さくしておくとよい

日付でパーティショニングされたテーブルの場合必要なパーティションだけを指定する

日付でパーティショニングされたテーブルにクエリを書く場合、必要な日付を指定することで計算に不必要な日付のデータを取ってくることがなくなります

WHERE _PARTITIONTIME
BETWEEN TIMESTAMP("2017-10-01") AND TIMESTAMP("2017-10-07")
可能な限り非正規化されたデータで扱う

非正規化されたデータはJOINが必要ないので効率的に並列にクエリを実行することができる

1対多の関係性をflattenされた形のデータで持つよりは(構造体の)配列のフィールドで持つべき。
(構造体の)配列のフィールドを使わずにflattenされたデータを扱う場合、GROUP BYが必要になってネットワーク通信(シャッフル)のせいでパフォーマンスが落ちることがある

外部リソースを入力にするのは高速ではない

BigQueryではGoogle Cloud StorageやGoogle DriveやGoogle Cloud Bigtableを入力にすることができるが、BigQueryのテーブルを参照するほうが基本的に高速なのでクエリのパフォーマンスが重要なときは使うべきではない

テーブル名をワイルドカードで指定するときは必要なテーブルだけを指定する

BigQueryではFROMで指定するテーブル名の末尾に*を指定することでプレフィックスにマッチした複数のテーブルからデータを取ってくることができる

パーティションの部分でも同じような話をしていたが、必要ないテーブルは取ってくる必要が無いので必要十分なできるだけ長いプレフィックスを指定するとよい
この記事の原文には書かれていないがWHERE _TABLE_SUFFIX BETWEEN '20171001'AND '20171007'のようにワイルドカード部分に条件を書いて絞り込むこともできる

通信の最適化

Optimizing Communication Between Slots  |  BigQuery  |  Google Cloud Platform

JOINする前にデータの量を減らす

JOINした後にデータをWHEREの条件などでフィルタリングするのと、JOINする前にフィルタリングするのではパフォーマンスが大きく変わることがある
JOINする前にデータ量を減らすことが可能ならできるだけやるべき

WITH句を使ってもクエリは効率的にならない

WITH句は主に可読性やコードの書きやすさのためのもので、複数のWITH句中に共通のクエリが含まれていてもそれぞれ実行される

日付ごとにテーブルを作るのを避ける

それぞれのテーブルごとにスキーマやメタデータを持ったり、パーミッションの確認をしないといけないので効率的ではない
もし日付ごとに分割しないならパーティションの機能を使うべき

計算の最適化

Optimizing Query Computation  |  BigQuery  |  Google Cloud Platform

同じ変換をSQLで何度もするのを避ける

同じデータの変換結果を何度も使うときは、途中結果を別のテーブルに保存すべき

JavaScript のユーザー定義関数(UDF)を避ける

JavaScriptのUDFを呼ぶとJava(原文ママ)のサブプロセスが実行されるので遅くなる。可能ならSQLのUDFを使うべき

近似的な集計関数を使う

統計的な近似による集計関数がいくつか実装されているので、正確な値が必要でないときはそれらを使ったほうが効率的

クエリの順番に気をつける

データをORDER BYでソートしてからフィルタリングするのと、フィルタリングしてからソートするのでは後者の方が圧倒的に速い。
ソートや正規表現などによる複雑な処理はできるだけ後の方で行ったほうがデータ量が減っているので効率的

JOINの順番に気をつける

ある程度はオプティマイザが配慮してくれるが、大きなテーブルに対して小さなテーブルをJOINするようにしていくと効率的になる

日付でパーティショニングされたテーブルの場合必要なパーティションだけを指定する

上の方で書いたのと同じ。処理するデータ量が減るので効率的になる

出力周りの最適化

Managing Query Outputs  |  BigQuery  |  Google Cloud Platform

繰り返しJOINやサブクエリをするのを避ける

何度も同じテーブルをJOINしたり何度も同じサブクエリを投げる場合は、そういったテーブルを作ってしまったほうが効率的になる

出力が大きい場合にはテーブルに保存することを考える

クエリの結果が大きすぎるとResponse too largeというエラーになる
この場合出力をフィルタリングしたりLIMITを指定してデータ量を少なくするか、テーブルに保存すればよい
ただしテーブルに保存する場合にはストレージ代がかかる

大きなデータをソートするときはLIMITを指定する

大量のデータに対してORDER BYを指定するとResources exceededのエラーが出てしまう
この場合LIMITを指定するとエラーがでなくなることがある

アンチパターンを避ける

Avoiding SQL Anti-Patterns  |  BigQuery  |  Google Cloud Platform

self joinを避ける

同じテーブル同士をJOINするself joinはデータの行数が大きく増えることが多い
できるだけself joinの代わりにウィンドウ関数を使うべき

データの偏り

GROUP BYJOINなどをする時にキーの値に偏りがあるとパフォーマンスに悪影響がある
例えばユーザーIDでGROUP BYして集計した時に、ほとんどのレコードのユーザーIDがnullで著しい偏りになったりする
偏りが激しいと、その値が割り当たったスロットのリソースを使い切ってresources exceededのエラーが出る
対策としては以下の2つがある

  • 近似的な集計関数を使う
  • できるだけあらかじめデータ量を減らしておく

同様にJOINのときも以下のような対策が考えられる

  • できるだけあらかじめデータ量を減らしておく
  • 可能なら2つのクエリに分ける

以下の記事の説明もわかりやすい
Query Plan Explanation  |  BigQuery  |  Google Cloud Platform

CROSS JOIN(デカルト積)

テーブルの行のすべての組み合わせでJOINするCROSS JOINをするとデータ量が非常に多くなって最悪クエリが終わらなくなる
できるだけCROSS JOINを使わずにウィンドウ関数を使ったり、もし可能なら集計してからCROSS JOINするとよい(この部分は翻訳が怪しい。原文→Use a GROUP BY clause to pre-aggregate the data.)

UPDATEやINSERTを1行ずつやらない

UPDATEINSERTは1行ずつやらずに複数行でまとめて行うのがよい

個人的な感想

非正規化されたデータの方が効率的という話とWITH句を使ってもクエリは効率的にならないという話が意外だった
日付ごとにテーブルを使うのではなくパーティション機能を使うのが強く推奨されていたが、テーブルを分けない場合パーティション指定し忘れるとテーブルのフルスキャンが動いて課金的に死ぬ可能性が怖くてなかなかパーティションに移行できていない
パーティションを指定しないクエリは投げられないようにする設定みたいなのができないのだろうか……

ライセンス周り

この記事は以下のURLのドキュメントに書かれている内容の翻訳を多く含みます

元のドキュメントはCreative Commons 3.0 Attribution Licenseで公開されているのでこの記事についても同様です

念のためSite Policiesのページにあった以下の表示も載せておきます
Site Policies  |  Google Developers

Portions of this page are modifications based on work created and shared by Google and used according to terms described in the Creative Commons 3.0 Attribution License.

ABテストの12の落とし穴

Twitterで見かけた以下の記事で紹介されていた論文がおもしろそうだったので読んだ感想と内容のてきとーな紹介(詳しく知りたい人は元論文を呼んでください)

内容が間違っている部分があったらコメントなどで教えていただけると嬉しいです

論文

このKDD2017の論文ではABテストの結果を解釈する時に陥りがちな12種類の罠についてMicrosoftの研究者が実例と対策を交えて説明しています
Pavel Dmitriev, Somit Gupta, Dong Woo Kim and Garnet Vaz, "A Dirty Dozen: Twelve Common Metric Interpretation Pitfalls in Online Controlled Experiments"

ちなみにイントロダクションで触れられていた「おそらく一番よくある罠は実装時のバグによって出たものだろう」的な話は「せやな……」って感じですね

ABテスト

ABテストとは何か大雑把に説明しておくと、一番シンプルな場合だとユーザーをランダムな2つのグループに分けて、片方には既存のシステム、もう片方には改良したシステムを使ってもらい、それらの2つのグループでユーザーの行動が改善しているかの結果を何らかの評価尺度の数値で比較するというものです
ユーザーをランダムに分けたことで、システムの違い以外の差がない状態でシステムの効果を検証できる

12の落とし穴

1. Metric Sample Ratio Mismatch(ABテストのそれぞれのグループでサンプルの比率が異なってしまう)

MSN.comでリンクをクリックした時に同じタブで開く/新しいタブで開くというA/Bテストを行った時の話が例として書かれている
新しいタブで開くようにした結果何故かページの平均ロード時間が8%も遅くなってしまった

よく調査すると「新しいタブで開くようにした」グループではページのロード回数が異常に減っていた
同じタブで開く場合ユーザーは戻るボタンを押すが、別のタブで開く場合には押さない。戻るボタンを押した場合にはキャッシュなどで早く読み込まれることが多いのでこのような差が出ていた

2. Misinterpretation of Ratio Metrics (比率の尺度の誤った解釈)

MSN.comのメインページはいくつかのモジュールで構成されている
モジュールをページのどの位置に置くかというABテストがよく行われている

上にある要素の方がクリックされやすいはずなのに、あるモジュールを上の方に移動したらCTR(ユーザーがクリックした回数を見られた回数で割ったもの)が40%も下がってしまうという結果が得られた

これが何故かというと、位置を上にしたことでユーザーがクリックした回数は増えたがそれよりも大きな増加量でユーザーが見る回数が増えてしまい、比率的には悪化したように見えてしまった
実際にはクリック数が大きく増えていてこの変更は良い結果が得られていることがわかった
このように比率の尺度は分母が変わる場合には誤った解釈を導いてしまう可能性があるので、比率ではなくそれぞれの数値も見るべき

ちなみにCTRの計算の方法には次の2種類がある。各々のユーザーについてCTRを出してユーザーごとのCTRの平均を取る。全体のクリック数と見られた回数でCTRを計算する。
この論文では前者のそれぞれのユーザーについて計算した値の平均を取るほうが変化に敏感でよいと言っている(分散も計算できる)

ちなみに上の2種類の計算は機械学習の分野だとマクロ平均マイクロ平均と呼ばれているのを見かける

3. Telemetry Loss Bias (遠隔測定ロスによるバイアス)

SkypeのiPhoneアプリのプッシュ通知がよりちゃんと届くように変更を行った話
この変更によってメッセージ関連の評価尺度に変化が起こるはずだったが、何故か通話関連の尺度に奇妙な改善が見られた

何故このような変化が起こったかというと、ユーザーのローカルの環境で起こったイベントはモバイルアプリ側でバッファに溜めておいて、wifi環境につながっている時に送信されていた。
バッファから溢れたイベントは捨てられていたが、プッシュ通知によってアプリが起動される時間が増えたためより多くのイベントが送られるようになった

このようなバイアスはWebサイトでもありえて、例えばリンクをクリックした時に同じタブで移動していたのを別のタブで開くように変えると元のページが開かれたままになるのでJavaScriptのクリックのイベントが正確に記録されるようになるようなことがありうる

データ収集や処理の流れのドキュメント化やちゃんと記録されていない場合の検出をやるべき

4. Assuming Underpowered Metrics had no Change

実験によってページビューが0.5%増加したが、統計的に有意な結果にならなかった
しかし0.5%の増加はビジネス上は大きな変化なので、効果があったのか知りたい

あらかじめ検出力(対立仮説が正しい時に帰無仮説を棄却する確率)を考えて必要なサンプルサイズを求めておく必要があった

5. Claiming Success with a Borderline P-value

ABテストでp値が0.029という統計的に有意な結果が得られた
重要な数値だったので確認のため、より大規模なABテストを行ったところ今度は統計的に有意な結果が得られなかった

ABテストは偶然有意な結果が得られることがあるので微妙なp値の時には気をつける必要がある

6. Continuous Monitoring and Early Stopping

2週間の予定のABテストを行う。1週目で統計的に有意な結果が出たから途中でABテストをやめたり、統計的に有意な結果が出なかったから期間を伸ばすというのをやってしまいがちだがこれはダメ

7. Assuming the Metric Movement is Homogeneous

数値の変化は等質的に起こるのではなく、例えばユーザーの国やブラウザなどが違えば異なった反応をする

8. Segment Interpretation

ユーザーを国やデバイスの種類などでセグメント分けをすることはよく行われる
2つのグループでABテストを行い、ユーザーをセグメントに分けてグループ間でセグメント同士を比べると統計的に有意な結果が得られているように見えた
しかしグループ全体で見ると何故か結果に差は見られなかった

これはグループ間でセグメントの割合が変わってしまったことでこういう奇妙な結果が得られた

ABテストで結果が差が得られなかった場合、どんどん差が得られるまでセグメント分けを試すというのをやってしまいがち

9. Impact of Outliers

外れ値の影響は大きいので対策すべき

  • trimming: 外れ値を取り除く
  • capping: 外れ値を固定の閾値で置き換える
  • windsorizing: 外れ値をあるパーセンタイルの値で置き換える

10. Novelty and Primacy Effects

システムの変更による効果には目新しさによる最初だけのものや、後からジワジワ効いてくるものがあったりする
こういったものを見分けるのは難しいが、何日目の結果か、何回目のアクセスの結果かといった風にセグメントを分けると何かがわかるかもしれない
最初のアクセスだけ効果があって、2回目以降急激に数値が下がったりする

11. Incomplete Funnel Metrics

ユーザーが目的の処理を行う各段階をステップに分けて数値を評価すべき

12. Failure to Apply Twyman’s Law

MSN.comのOutlook.comへのボタンをメールアプリのボタンに変えたら変更していないボタンまでクリック数の大きな増加が得られた

数日経つとこの数値の変化はどんどんなくなっていった。ユーザーが混乱してクリックが増えただけだと考えられる

予想外の数値の変化があったら疑ってかかるべき

感想

実例がいろいろあって興味深かった
ABテストの話とはあまり関係ないが、Google Analyticsのイベント機能を使っていてポップアップなどの表示に対してもnonInteractionを指定せずにイベントを送ってしまい直帰率などが異常な数値になるのをたまに見かけるのを思い出した(nonInteractionはイベントがユーザーの行動によるものでないことを表すフラグで、これを指定しない場合ユーザーが行動したとみなされて直帰率が激減する)