BigQuery上で64ビット整数をビットスワップする話
タイトルからしてマニアックですが…。
なぜそんな事を…
BigQueryにビットスワップ(ビットの値が逆順)な64ビット整数が入ってしまって、
SQLとユーザ定義関数でもとに戻す処理を実装しました。
同じ状況の人必見です！（そんな人いるんだろうか？）
そもそもBigQueryとは
このQiitaを読んでもらうと凄さがわかると思いますが、
120億行の正規表現マッチ付き集計が5秒でできたり。
ペタバイトクラスのデータを投入してもビクともしなかったりする、
規格外のデータウエアハウスです。
まさに、今のビッグデータ分析のトレンドのサービスとも言えるかなと思います。
そして、自分の主な仕事はこのBigQueryをいかにうまく使うかだったりします。
Qiita
ビットスワップ
ビットスワップとはビットの順序を逆順にすることです
例えば２進数表現で
1100 0101
があった場合にビットスワップすると
1010 0011
になります。
並び順を逆にするためビット反転結果の
0011 1010
とは違います。
方針
方針としては４つ考えました。
- Cloud Dataflowを用いてJavaで反転する
- 対象テーブルをGCSへ出力しローカル上で反転し再度テーブルを作成する
- SQLと標準関数だけでなんとかする
- BigQueryのユーザ定義関数を用いてビット反転処理を書く
まず１についてですが、
この６４ビット整数の反転がそもそもJavaのLongの関数を用いて行われていたため、
これを用いてもとに戻すのが一番バグもなく安定です。
ただ、その変換のためだけに非同期処理になるCloud Dataflowを用意するのは若干まどろっこしいかなと思いました。
２についてはJavaが動けばできるのでワンショットならいいですが定期的に必要になりそうなので流石に手動は辛そうです。
あと、レコード数が4000万行ほどあるのでなるべく外に出したくないです。
3については残念ながらBigQueryではビット演算系の関数が弱いためおそらく頑張ればできそうですが、
SQLを引き継いだときに保守性が悪そうです。
そこで、４番のユーザ定義関数をJavaScriptで書いてビットスワップする処理を実装しました。
BigQueryのユーザ定義関数は標準SQLの場合JavaScriptで書けます。
余談ですが、もしBigQuery内のJSONの値を加工する時に困っていたらユーザ定義関数で扱うのがおすすめです。
JavaScriptの64ビット整数
JavaScriptにおける数値型といえばNumberが思い浮かぶと思いますが、実は2018年ぐらいから一部ブラウザにてBigIntという数値型が実装されています。
MDN Web Docs
使い方は数値の最後にnをつけるか、BigIntのコンストラクタに64ビット数値を表す文字列などを入れることで宣言できます。
// Number型で定義すると丸め誤差が発生する
12345678901234567890
// = 12345678901234567000
// BigInt型の整数として宣言
12345678901234567890n
// = 12345678901234567890n
BigInt("12345678901234567890")
// = 12345678901234567890n
// 引数をNumber型で渡してしまうと丸め誤差が発生してしまうので注意
BigInt(12345678901234567890)
// = 12345678901234567168n
油断してNumberにすると丸め誤差が発生してしまうので要注意です。
そして、実はまだBigInt型はドラフト段階のため一部の演算が実装されていません。
BigQueryのユーザ定義関数
ユーザ定義関数(UDF)は以下のように作成しました。
CREATE TEMPORARY FUNCTION
reverce_binaly(argStr STRING)
RETURNS STRING
LANGUAGE js AS """
let argBin;
let arg = BigInt(argStr);
if(arg > 0n){
argBin = arg.toString(2);
}else{
// 符号部を0に変更
const argBinAbs = arg.toString(2).replace('-','0');
// Bit反転処理 (64ビット整数に対して未実装のため文字列処理)
const notArgBin = argBinAbs.replace(/0/g,'o').replace(/1/g,'0').replace(/o/g,'1');
// ２の補数を求めるため加算
const arg2c = BigInt(`0b${notArgBin}`) + 1n;
argBin = arg2c.toString(2);
}
// 64ビットに桁揃え
const padded = `0000000000000000000000000000000000000000000000000000000000000000${argBin}`.slice(-64);
// ビットリバース
const reversed = padded.split('').reverse().join('');
// ビットとして解釈されるようにフォーマット
const reversedBin = `0b${reversed}`;
const result = BigInt(reversedBin);
// 数値のまま値を返すとBigInt表現のnがついてしまうので文字列化
return result.toString();
""";
６４ビット整数を文字列にキャストして渡し
文字列のまま順序を反転して６４ビット整数として解釈する方針にしました。
ポイントは、以下の4つ。
- 文字列として処理
- 負の場合２の補数を算出
- 返り値を文字列にする
- 文字列のまま処理する
文字列として処理
まず、BigQueryの６４ビット整数のINT64は
UDFにてサポートされていないため
JavaScriptに値を渡す場合は文字列か浮動小数点として扱うことになります
ですので、誤差の発生しない文字列型として処理する必要があります。
また、必要に応じて数値化する場合には必ずBigInt型として扱わなければ
浮動小数点のNumber型とされてしまうため、注意が必要です。
標準 SQL ユーザー定義関数 | BigQuery | Google Cloud
負の場合２の補数を算出
引数に負の値が来た場合は
２進数化したときに符号部がビット演算の邪魔になってしまうので、
除去して２の補数表現にしてから処理します。
返り値を文字列にする
そして、返り値としてBigIntを指定したいところですが、
JavaScriptのBigIntを戻した場合末尾にBigInt表現を表すnがついてしまうので
UDF内で文字列にキャストしています。
文字列のまま処理する
ビット演算を使ってうまく反転させたほうが計算コストが低そうな気はしました。
ただ、JavaScriptの６４ビット整数のビット演算の符号付きビット反転などがまだ未実装のため
- ３２ビットごとに分割して処理を実装しないといけない
- ビット演算でもそれほど簡潔にならない
- 引数も返り値も文字列で扱う
などから、今回は文字列のままで処理しました。
paddingについて
paddingの部分はループ以下のように使ったほうが簡潔になりますが、
レスポンスが30秒ぐらい遅くなったのでスロット(BigQueryの処理単位)の負荷はあがるようですね。
// 配列に変換
let argBinArray = argBin.split('');
// 64ビットに桁揃え
while(argBinArray.length < 64){
argBinArray = ['0'].concat(argBinArray);
}
// ビットリバース
const reversed = argBinArray.reverse().join('');
SQL側の処理
上記のUDFを宣言したSQLと共に次のように
CREATE TEMPORARY FUNCTION
reverce_binaly(argStr STRING)
RETURNS STRING
LANGUAGE js AS """
let argBin;
let arg = BigInt(argStr);
// 省略
return result.toString();
""";
select
value,
reverce_binaly(CAST(value AS STRING)) as reverced_value
from
table
というように、SQLの関数と同様に呼び出すことが可能になります。
BigQueryのUDFのメリット
BigQueryのUDFを定義すると何が良いかというと
BigQueryの基盤を使ってすべてのレコードに対して処理を実行できるということです。
今回行った処理は約2,000万レコードあるテーブルに対して行いましたが、
結果は43.5秒後に返ってきました。
1秒あたり50万行以上の処理ができることになります。
このように変換処理などを大量のレコードに対して実行できる基盤としても
BigQueryはとても便利だと思います。
