BigQueryで簡単にbit全探索

福岡でデータ基盤エンジニアしている荒木です！
日々の業務の中でクエリを書いていると、SQLでbit全探索 が書きたいなーと思うことってありますよね？僕は一度もないです。
BigQueryの関数とWith句を使うとbit全探索が意外と簡単に書けたのでご紹介したいと思います。
例題として、価値と重さが設定された20個品物を一定の重さ以下で価値を最大化する問題（いわゆる　ナップザック問題）を考えてみたいと思います。
（前提知識として通常のプログラミング言語でbit全探索を理解している方を対象としています = bit全探索についての説明はしません。）

bit.sql

WITH nimotu AS (
  -- テストケース
  SELECT 0  AS id,   2 AS value,  9 AS weight UNION ALL
  SELECT 1  AS id,   5 AS value,  5 AS weight UNION ALL
  SELECT 2  AS id,   4 AS value,  1 AS weight UNION ALL
  SELECT 3  AS id,   1 AS value,  5 AS weight UNION ALL
  SELECT 4  AS id,   3 AS value,  5 AS weight UNION ALL
  SELECT 5  AS id, 100 AS value, 20 AS weight UNION ALL
  SELECT 6  AS id,   2 AS value,  9 AS weight UNION ALL
  SELECT 7  AS id,   5 AS value,  5 AS weight UNION ALL
  SELECT 8  AS id,   4 AS value,  1 AS weight UNION ALL
  SELECT 9  AS id,   1 AS value,  2 AS weight UNION ALL
  SELECT 10 AS id,   3 AS value,  5 AS weight UNION ALL
  SELECT 11 AS id, 100 AS value, 20 AS weight UNION ALL
  SELECT 12 AS id,   2 AS value,  9 AS weight UNION ALL
  SELECT 13 AS id,   5 AS value,  5 AS weight UNION ALL
  SELECT 14 AS id,   4 AS value,  1 AS weight UNION ALL
  SELECT 15 AS id,   1 AS value,  2 AS weight UNION ALL
  SELECT 16 AS id,   3 AS value,  5 AS weight UNION ALL
  SELECT 17 AS id, 100 AS value, 20 AS weight UNION ALL
  SELECT 18 AS id,   2 AS value,  9 AS weight UNION ALL
  SELECT 19 AS id,   5 AS value,  5 AS weight 
), solve AS(
  SELECT
    SUM(
      -- bitが0の商品は加算
      CASE WHEN bit & (1 << id) = 0 
        THEN nimotu.value 
        ELSE 0 
      END
    ) AS value,
    SUM(
      -- bitが0の商品は加算
      CASE WHEN bit & (1 << id) = 0 
        THEN nimotu.weight 
        ELSE 0 
      END 
    ) AS weight
  -- 商品idと選び方をcross joinして1レコードがある選び方のときのある商品の状態を示すテーブルを作成
  FROM
    -- 商品idの列挙
    UNNEST(GENERATE_ARRAY(0, 19)) AS id
  CROSS JOIN
    -- bitで選び方を列挙
    UNNEST(GENERATE_ARRAY(0, 1<<19)) AS bit
  LEFT JOIN
    nimotu
  ON
    id = nimotu.id
  GROUP BY
    -- 選び方でグループ分けして1レコードがある選び方を示すテーブルに変換
    bit
)
SELECT
  MAX(value)
FROM
  solve
WHERE
  -- 重量は50以下の設定にする
  weight <= 50

GENERATE_ARRAYで商品idの連番テーブルと選び方のbit列の連番テーブル作ってCROSS JOINします。するとある商品がある選び方のときにの状態を示すテーブルができます。なのでbitでグループ分けして、bit & ( 1 << id )が0の商品を合計すると全ての選び方を全列挙することができました。