Help us understand the problem. What is going on with this article?

5分で試せる、10億件×8.5億件をBigQueryで1分でJOINする方法

More than 5 years have passed since last update.

Google BigQueryは普通の検索もそこそこ速いけど、大規模なテーブル同士のJOINも同様に速い。その実力をお金をかけずに誰でも5分で試せる手順をまとめてみた。

BigQueryを初めて使う

BigQueryには無償枠があって、Googleアカウントさえあれば誰でも毎月1TB分までタダでサンプルテーブルに対するクエリを試せる(ただしテーブル作成やデータのインポートはできない)。初めて使うまでの手順は以下のとおりで、所要時間は1〜2分くらい。

Google Developer Consoleで新規プロジェクト作成

Googleアカウントにログインした状態でGoogle Developer Consoleを開き、Create Projectボタンをクリック。プロジェクト名とIDはそのままでCreateをクリック。30秒ほどでプロジェクトが作成される。つづいて、左側のナビゲーションメニューからBig Data - BigQueryをクリックし、BigQueryブラウザツールを開く。

kobito.1409236235.879308.png

クエリを投げてみる

左側のナビゲーションメニューからpuglicdata:samplesをクリックすると、すぐに使えるサンプル用のテーブル一覧が出てくる。例えばwikipediaテーブルには、Wikipediaのコンテンツの更新履歴を記録した3億件のデータが入っている。

kobito.1409236515.211443.png

まずは小手調べに、titleで正規表現マッチを試してみよう。COMPOSE QUERYをクリックし、New Queryフィールドに以下のSQLを入力してRUN QUERYをクリックする。

SELECT title FROM [publicdata:samples.wikipedia] 
WHERE REGEXP_MATCH(title, r'.*Query.*')
LIMIT 100

すると数秒ほどして、こんな結果が返ってくるはず。

kobito.1409237203.121104.png

3億件の正規表現マッチは3〜4秒くらいで返ってくる。試しに1000億件のテーブルで正規表現マッチを実行してみたら、さすがに時間がかかって20秒くらい待たされた。

12億×8.5億のJOINを試す

では、大規模JOINを試してみよう。デフォルトで表示されるサンプルテーブルにはそれほど大きなデータがないが、ブラウザツール上にデフォルト表示されている他にもいくつか大きなサンプルテーブルが用意されており、誰でもクエリ可能だ。今回は、そうしたテーブルであるWiki1BWiki10Bを使ってみる。どちらもWikipediaのページビュー数が記録されたテーブルで、それぞれ12億行と100億行を保持している。

COMPOSE QUERYをクリックし、以下のSQLを入力、RUN QUERYをクリックしてみよう。

SELECT COUNT(a.title)
FROM [helixdata2:benchmark.Wiki1B] as a
JOIN EACH (
  SELECT title, SUM(views) as view
  FROM [helixdata2:benchmark.Wiki10B]
  GROUP EACH BY title
) as b
ON a.title = b.title;

1分ほど待っていると、以下のように結果が返ってくる。

kobito.1409237998.338970.png

このrowsカラムの数値は、JOINによって12億行が生成されたことを表している。また所要時間と処理データ量は右上に表示される。上記の例では、330GBのデータを読み込み58.2sで処理が完了したことが分かる。

ちなみに、このクエリを3回も実行すれば1か月分の無償枠を使いきってしまい「無償クォータ使いきったよ!」エラーが出てしまう。なので、もっといろいろBigQueryを試したいという方は、上記クエリの実行は1回だけに留めておくことをおすすめする。

12億×8.5億のJOINは1分で終了、1回およそ42円

現在のBigQueryの価格設定でのクエリのコストは$5/TBなので、有償アカウントで同じクエリを実行するとおおよそ1回170円かかる計算だ。ただし、実際はもっと安くなる。この例ではテーブル保存のできない無償アカウントを使ったため、JOIN相手の8.5億のテーブルをあらかじめ作成しておくことができなかった。そこで、以下のサブクエリを先に実行して、100億行のテーブルからGROUP BY titleで8.5億行のtitleマスターテーブルを作成してる。

SELECT title, SUM(views) as view
FROM [helixdata2:benchmark.Wiki10B]
GROUP EACH BY title

このテーブル作成処理がコストの大半を占めているので、有償アカウントであればtitleマスターテーブルを事前に作成しておける。以下の様なJOINのみのクエリを実行し、その結果で生じる12億行を新しいテーブルに保存できる。

SELECT a.title, a.views, b.views
FROM [helixdata2:benchmark.Wiki1B] as a
JOIN EACH [your-project:your-dataset.wiki_titles_850M] as b
ON a.title = b.title;

この場合、テーブル保存を含めておよそ60秒で処理は完了し、処理データ量は80.8GB、コストは42円ほどに収まる。

100億×8.5億は140秒、1回およそ206円

このやり方で、今度は100億行×8.5億行のJOINを試してみた。上記クエリのWiki1BテーブルをWiki10Bに置き換えるだけである。

kobito.1409278593.170117.png

(なぜか日本語タイトルのデータが上位に...)

結果は、処理データ量407GB、所要時間は140.6秒、コストは206円であった。なお、BigQueryではテーブル保存を行うとストレージコストが発生するが、例えば今回の検証で使ったサンプルテーブルを1か月保持しておいた場合のコストは、

  • 100億件テーブル: 693GB
  • 8.5億件テーブル: 34.3GB
  • 100億件結果テーブル: 452GB
  • 合計: 1.2TB
  • ストレージコスト:1.2TB x 0.026/GB/month = $31.2

ということで、100億件テーブルを2つずっと放置しておいても1か月に3200円程度の出費である。

Hiveで数十分→BigQueryで数十秒がクラウドの実力

100億×8.5億のJOINがおよそ140秒、BigQueryは大規模JOINもそこそこ速い。大ざっぱに比較すれば、Hadoop/Hiveで数十分かかる規模のJOINがBigQueryでは数十秒で終わる。こうしたBigQueryの数ケタ違いの速さについて、BigQuery本の読書会を主催する@hakoberaさんがこんな分析をしていた。

BigQuery のアルゴリズムはすごくシンプルな分割統治処理です。速いのは、それをすごい台数のサーバーと高速ネットワーク上で行うから。アルゴリズムがわかっても、実行環境が構築できないので他者の追随を許さない完全なる力押しサービスです 

From https://twitter.com/hakobera/status/504612035833778177

数千台のサーバーと数万台のディスクを無償ユーザーの1つのクエリのために回せる完全なる力押しサービス。これはGoogle検索からYouTubeまですべてのサービスを膨大な数のサーバー上に薄く広くデプロイしているGoogleならではのアーキテクチャだ(いわゆるDatacenter as a Computer)。技術的には実はわりにシンプルなアルゴリズムであっても、この規模での実現は実運用体制やビジネス規模が伴っていないと不可能で、こういうのが本当の意味でのクラウドであると思う。 #マ

補足:大規模JOINにはJOIN EACHを付けるべし

ところで、この例のような大きなテーブル同士のJOINでは、通常のJOIN指定ではエラーが発生してしまう。なぜなら、JOINを指定すると検索を実行する数1000台のサーバーにJOIN先テーブルをブロードキャストしてハッシュジョインするBroadcast JOINが実行されるからだ。

kobito.1409280139.832935.png
BigQueryにおけるBroadcast JOIN / From Google BigQuery Analytics

この場合、JOIN先テーブルは圧縮後8MB以下である必要がある。このサイズに収まらない場合は、代わりにJOIN EACH指定を行う。すると、Hadoopと同様のshufflerが展開されて大規模データのハッシュ関数によるシャッフル処理が走る。

kobito.1409280288.775889.png
BigQueryにおけるShuffle JOIN / From Google BigQuery Analytics

このシャッフル処理のためにクエリ実行時間は伸びてしまうので、基本は通常のJOINを使い、エラーが出たらJOIN EACHを試す、という使い分けになる。

なお、GROUP BYにも同様に通常のGROUP BYとシャッフル版GROUP EACH BYの2種類が用意されている。通常GROUP BYは各ノードでオンメモリ処理されるので、対象カラムのカーディナリティがあまりに大きくノードのメモリ内に収まらない場合はエラーが発生してしまう。この場合もEACHを付けるとシャッフル処理によるGROUP BYが走りエラー発生を回避できる。


Disclaimer この記事は個人的なものです。ここで述べられていることは私の個人的な意見に基づくものであり、私の雇用者には関係はありません。

Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away