BigQueryã§ã‚¯ã‚¨ãƒªã‚’æ›¸ã„ãŸã¨ãã«ãƒãƒžã£ãŸç½ é›†

自分がなんとなくBigQueryのクエリを書いていてハマった罠について列挙しておきます。 ドキュメントをちゃんと読めば書いてあったりするのですが、普段はそこまで細かく見てなかったりするんですよね……。

BigQueryのカレンダー | Advent Calendar 2023 - Qiita の16日目の記事です。

CAST(value AS INT64) は切り捨てではない

他のプログラミング言語などをやっているとなんとなく整数型にキャストすると切り捨てのような気がしてしまいますがBigQueryは違います。 四捨五入的な挙動になります。

SELECT CAST(1.5 AS INT64)
-- => 2

Returns the closest integer value. Halfway cases such as 1.5 or -0.5 round away from zero. https://cloud.google.com/bigquery/docs/reference/standard-sql/conversion_functions#cast_as_integer

DATE_DIFF(date1, date2, YEAR) の値が増えるのは1年後ではない

https://cloud.google.com/bigquery/docs/reference/standard-sql/date_functions#date_diff

1年後ではないというと語弊がありますが、DATE_DIFFでは差を計算したい部分の差を出してるだけっぽいので大晦日と元旦を比べると1日しか経ってないのにDATE_DIFF(date1, date2, YEAR) の値は1になります。

SELECT DATE_DIFF('2024-01-01', '2023-12-31', YEAR);
-- => 1

ちゃんと365日ぐらい経過したかどうかを判定したければ日数を見たほうがよさそうです。

同じWITH句を一つのクエリ内で複数回参照してもそれぞれ違う結果になる

BigQueryではWITH句を使ってサブクエリに名前を付けて扱うことができます。 同じ名前のWITH句を参照した場合同じ結果になるのを期待したくなりますが、それぞれ個別に実行されるので乱数やランダムな順序でSELECTしてLIMITした結果などはそれぞれ別々になります。

WITH x AS (
  SELECT RAND() AS r
)

SELECT *
FROM x
UNION ALL
SELECT *
FROM x
-- => 同じWITH句のxを参照しているのに1つ目のxと2つ目のxで結果が異なる

対策としてはWITH句ではなくCREATE TEMP TABLEで一旦テーブルを作ってしまってそれを参照したり、少しトリッキーな方法だとWITH RECURSIVEを使うものがあります。 WITH RECURSIVE は再帰的なWITH句を書くための記法ですが、これを使うとWITH句の結果がマテリアライズされるので一旦テーブルを作るのと同様の効果があります。

WITH RECURSIVE x AS (
  SELECT RAND() AS r
  UNION ALL
  SELECT * FROM x WHERE FALSE
)

SELECT *
FROM x
UNION ALL
SELECT *
FROM x
-- => WITH RECURSIVEを使うとWITH句の結果がマテリアライズされるので等しくなる

NULL との比較はNULL(falsy)になる。特にNOT IN の挙動がわかりづらい

BigQueryに限った話ではないですが値がNULLの時に!=などでそれと比較をすると結果もNULLになってしまいWHEREの部分で意図せずfalsyになって困ることがあります。 特にvalue NOT IN (values) の挙動はわかりづらくvaluesにNULLが含まれている場合、valueがvaluesに含まれていればFALSE、含まれていなければNULLを返し、つまり常にTRUEではないfalsyな結果になってWHEREなどに書いた場合条件を満たすことはありません。

SELECT
  1 NOT IN (1, NULL, 2), -- => FALSE
  2 NOT IN (1, NULL, 2), -- => FALSE
  3 NOT IN (1, NULL, 2), -- => NULL

上の例ぐらいなら考えれば気付けると思うのですが、valuesの部分がサブクエリになっていたりするとNULLが含まれていることまで頭が回らずうっかりしがちです。

, UNNEST([]) するとその行が消える

BigQueryでは配列を展開するためのUNNEST(ARRAY)という記法があり、, UNNEST(ARRAY) とすると配列のそれぞれの要素をCROSS JOINできます。

WITH x AS (
  SELECT 1 AS n
)

SELECT
  *
FROM x, UNNEST([1, 2, 3]) AS i
-- 以下の結果が得られる
-- 1, 1
-- 1, 2
-- 1, 3

この時ARRAYが空配列だと空のデータとJOINしようとしたことになり対応するxのデータごと消えてしまいます。 うっかりこの挙動を失念しているとあるはずのデータがない状態になって困ります。

WITH x AS (
  SELECT 1 AS n
)

SELECT
  *
FROM x, UNNEST([]) AS i
-- => 空配列をUNNESTしたものをCROSS JOINするとxの方ごと消える

この場合LEFT OUTER JOINをすればxの方は消えずにJOINした方にはNULLが入って大丈夫になります。

WITH x AS (
  SELECT 1 AS n
)

SELECT
  *
FROM x
LEFT OUTER JOIN UNNEST([]) AS i
-- 以下の結果が得られる
-- 1, NULL

IN UNNEST(ARRAY) ができる

これはあんまり罠というわけではないですが、サブクエリをかかずとも IN に UNNEST(ARRAY) を指定すれば配列に含まれるかどうかが判定できます。最初はサブクエリを書く必要があるのかと思っていました。

[NULL] が作れる

BigQueryではクエリの最終結果にNULLを含む配列があるとエラーになります。 しかし上のNOT IN の例にも出てきましたがクエリの途中結果では配列にNULLが含まれていても特にエラーにはなりません。

SELECT [NULL] AS x
-- Array cannot have a null element; error in writing field x というエラーが出る

テーブル名に.が連続してても動く

これは完全にトリビアな話ですが、BigQueryのテーブル名の指定ではプロジェクト名やデータセット名のあとに . を付けますが、この . はなぜか複数ついていてもエラーなどにはならず普通に動くようです。文字列的にテーブル名を検索したらなぜかtypoで.が多くて見つからないということがありえます。

SELECT * FROM `bigquery-public-data...........github_repos...................languages` LIMIT 1000

最もシンプルで(驚くべき)ソートアルゴリズム？

こういうツイートを見かけたので元の論文を読んだり実装してみたりしました

世界一単純な? ソートアルゴリズム。
for i=1..n:
for j=1..n:
if a[i]<a[j]:
swap(a[i], a[j])
一見バブルソートのように見えるが、if判定の不等号の向きがバブルソートとは逆になっているのに、それでもソートされる。https://t.co/1qSnomUrUR

— 新山祐介 (Yusuke Shinyama) (@mootastic) 2021å¹´10月6æ—¥

注意点ですが、このアルゴリズム自体はよく使われるソートアルゴリズムと比べて特に利点があるわけではなくてネタ的な話です。

元論文
arxiv.org

実装(Python)

この記事のソートでは昇順に並べます

ICan’tBelieveItCanSort

というわけで論文で言うところのICan’tBelieveItCanSortを実装してみました。

Algorithm 1 ICan’tBelieveItCanSort (論文より)

https://arxiv.org/abs/2110.01111

二重ループして\(j\)番目の要素が\(i\)番目の要素よりも大きかったら交換するだけなので単純です。
冒頭のツイートでも書かれていたように、以下で実装している他のソートとひと目見比べてみると交換するときの大小の条件が逆になっているように見えなくもないです。

def i_cant_believe_it_can_sort(A: list):
  n = len(A)
  for i in range(n):
    for j in range(n):
      if A[i] < A[j]:
        A[i], A[j] = A[j], A[i]
  return A

ExchangeSort

論文中にはExchangeSortというのも出てきたのでそれも実装してみました。
ちなみに元の論文では、ExchangeSortの内側の\(i\)からのループを先頭からのループと間違えて実装したときにICan’tBelieveItCanSort)を発見したというふうに書かれていました(その場合は大小の条件が逆なので降順になる)

def exchange_sort(A: list):
  n = len(A)
  for i in range(n):
    for j in range(i + 1, n):
      if A[i] > A[j]:
        A[i], A[j] = A[j], A[i]
  return A

バブルソート

参考用に同様にバブルソートを実装してみました。
隣同士の要素を比べて順番が降順になっていたら入れ替えます。
実装的にはICan’tBelieveItCanSortとどっちがシンプルかというのはなんとも言い難いです

def bubble_sort(A: list):
  n = len(A)
  for i in range(n - 1):
    for j in range(n - 1):
      if A[j] > A[j + 1]:
        A[j], A[j + 1] = A[j + 1], A[j]
  return A

なんでソートできるの？

ICan’tBelieveItCanSortがどう動くか適当な配列を例に説明してみましょう。

最初は[2, 5, 9, 7, 1, 7]とします。

\(j\)番目の要素が\(i\)番目の要素よりも大きかったら交換するので、最初の\(i=0\)のループ後は配列の先頭に最大の要素が入ります。
i=0, j=0, [2, 5, 9, 7, 1, 7]
i=0, j=1, [5, 2, 9, 7, 1, 7]
i=0, j=2, [9, 2, 5, 7, 1, 7]
i=0, j=3, [9, 2, 5, 7, 1, 7]
i=0, j=4, [9, 2, 5, 7, 1, 7]
i=0, j=5, [9, 2, 5, 7, 1, 7]
上の例を見てもわかるように\(i\)番目に最大の要素が来るとそれ以上交換は行われなくなります

\(i=1\)のループでは、最初が[9, 2, 5, 7, 1, 7]で
i=1, j=0, [2, 9, 5, 7, 1, 7]
i=1, j=1, [2, 9, 5, 7, 1, 7]
以下略

\(i=0\)のループで先頭に最大の要素があるのでこれ以降\(j\)に関するループは\(j=i-1\)までやれば十分になっています(それ以上やっても交換は行われない)
このことから\( j < i \)となっています。なので最初に大小の比較の条件が逆に見える、という話がありましたが、i番目の方に大きい要素が来るのは配列の後ろの方に大きい要素が来るのと同じなので大小の条件は逆ではなさそうというのがわかります

\(i=2\)のループでは、最初が[2, 9, 5, 7, 1, 7]で
i=2, j=0, [2, 9, 5, 7, 1, 7]
i=2, j=1, [2, 5, 9, 7, 1, 7]
以下略

\(i=3\)のループでは、最初が[2, 5, 9, 7, 1, 7]で
i=3, j=0, [2, 5, 9, 7, 1, 7]
i=3, j=1, [2, 5, 9, 7, 1, 7]
i=3, j=2, [2, 5, 7, 9, 1, 7]
以下略

\(i=4\)のループでは、最初が[2, 5, 7, 9, 1, 7]で
i=4, j=0, [1, 5, 7, 9, 2, 7]
i=4, j=1, [1, 2, 7, 9, 5, 7]
i=4, j=2, [1, 2, 5, 9, 7, 7]
i=4, j=3, [1, 2, 5, 7, 9, 7]
以下略

残りは同じ感じなので省略します。

上で試してみた結果のように、このアルゴリズムでは\(i\)のループが終わった時点では先頭から\(i\)番目までの要素について、次の要素の方が大きいもしくは等しい状態、つまり昇順の状態になります。
なので最後まで\(i\)のループを行うとすべての要素が昇順になることが言えます(論文には証明があります)

挙動を大雑把に理解するために\(i\)に関するそれぞれのループ後の配列をみると、\(i=1\)以降のループでは実質的には挿入ソートと同じ挙動になっていることがわかります。

i=0, [9, 2, 5, 7, 1, 7]
i=1, [2, 9, 5, 7, 1, 7]
i=2, [2, 5, 9, 7, 1, 7]
i=3, [2, 5, 7, 9, 1, 7]
i=4, [1, 2, 5, 7, 9, 7]
i=4, [1, 2, 5, 7, 7, 9]

挿入ソートでは\(i\)番目の要素をそれ以前の要素と見比べて適切な位置に挿入してそれ以降の要素を一つ後ろにずらします。
このアルゴリズムでは\(i\)番目の要素との交換を使って、挿入ソートでいうところの挿入して要素を一つずつ後ろにずらす操作を実現していることになります。
挿入ソート - Wikipedia

なのでコードからは想像しづらいですが\(i=0\)のループで最大値を先頭に持ってきて\(i=1\)以降のループでは挿入ソートのようなことをしているという挙動としては結構わかりやすいことをしていることがわかりました

コードを再掲

def i_cant_believe_it_can_sort(A: list):
  n = len(A)
  for i in range(n):
    for j in range(n):
      if A[i] < A[j]:
        A[i], A[j] = A[j], A[i]
  return A

おまけ

論文中にはIt is difficult to imagine that this algorithm was not discovered before,
but we are unable to find any references to it.と書かれていますが、検索などを使って調べた人によると今回のソートアルゴリズムと同じものの実装例や質問が結構見つかるらしいです
Some links to discussions and/or accidental discoveries of this algorithm: OP (2... | Hacker News