唯物是真 @Scaled_Wurm

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

BigQueryのSQLでなんとなく素数列挙を試した(実用性皆無)

GENERATE_ARRAY()関数を使うと等差数列が作れるので後はJOINしてがんばるだけ

前に以下の記事でエラトステネスのふるいなどを調べたが、SQLでは試し割りによる方法ぐらいしか書けそうになかった
sucrose.hatenablog.com

試し割り

ある数をその数よりも小さな1以外の数で実際割ってみて、割り切れなければ素数。
これをすべての数について確かめる
以下のクエリを動かしてみたら、判定したい最大の数を\(N\)とした時\(N\)を倍にしたら実行時間は4倍ぐらい増えていた(\(O(N^2)\)っぽい雰囲気)
なので最大でも数万ぐらいまでしか計算できなかった

#standardSQL

#数列を作る
WITH numbers AS (
  SELECT
    i
  FROM UNNEST(GENERATE_ARRAY(3, 20000, 2)) AS i
)
#割り切れるか試す
, divisible AS (
  SELECT
    a.i
    , MOD(a.i, b.i) = 0 AS is_divisible
  FROM numbers AS a
  JOIN numbers AS b
  ON SQRT(a.i) + 1 > b.i
)

#1回も割り切れていないものが素数
SELECT * FROM UNNEST([2, 3]) AS i
UNION ALL
SELECT
  i
FROM divisible
GROUP BY i
HAVING NOT LOGICAL_OR(is_divisible)
ORDER BY i

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.