SQLでビット演算を使った検索が便利だったのでメモ

単なる備忘録ですいません。

SQLでビット演算を使った検索

お題

例えば、日本の山の名前を一覧で表示する画面があって、絞り込みをする際に都道府県を複数指定(OR)できるような仕組みを想定します。

山の情報

富士山は静岡県と山梨県にまたがってます。
御嶽山は岐阜県と長野県にまたがってます。
八ヶ岳は山梨県と長野県にまたがっています。

上記の情報をテーブルに保持するとします。

WEBの検索画面のUI

以下のような絞り込みたい都道府県をチェックボックスで複数選択(OR検索)できるようなものとします。

・都道府県を選択
□北海道
□青森県

□山梨県
□長野県
□岐阜県
□静岡県

□沖縄県

以下、最初に通常のやり方の例を出して、その後に改良型として示したいと思います。

通常のケース

通常は「山情報のテーブル」と「都道府県情報のテーブル」を用意し、「それらを関連付けたテーブル」を作ったりします。

テーブル構成の例
■mountainsテーブル
id,name
1,富士山
2,御嶽山
3,八ヶ岳

■prefecturesテーブル
id,name
1,北海道
2,青森県

19,山梨県
20,長野県
21,岐阜県
22,静岡県

47,沖縄県
※IDと都道府県名だけならテーブルでなくて、設定ファイル等で定義しても良い。

■mountain_prefecturesテーブル
id,mountain_id,prefecture_id
1,1,19
2,1,22
3,2,20
4,2,21
5,3,19
6,3,20

上記のようなテーブルを作り、SQLを組み立てる際はテーブルを結合して使います。

SQLと結果
例)山梨県(ID:19)、静岡県(ID:22)に位置する山を取得する
SELECT m.id, m.name FROM mountains m LEFT JOIN mountain_prefectures mp WHERE mp.prefecgure_id IN (19,22);
+—-+———–+
| id | name |
+—-+———–+
| 1 | 富士山 |
| 3 | 八ヶ岳 |
+—-+———–+
2 rows in set (0.01 sec)

みたいな。

改良型(SQLでビット演算を使った検索)

都道府県IDを47桁のフラグに見立てると、上の例の「mountain_prefecturesテーブル」を作らず、
mountainsテーブルにカラムを追加し、そちらに関連情報を格納する事で同じことができます。

具体的に説明します。

一般的な都道府県の北海道から沖縄までIDを47桁のフラグに見立てるとします。

ID:1 北海道 = (2の0乗)= 00000000000000000000000000000000000000000000001
ID:2 青森県 = (2の1乗)= 00000000000000000000000000000000000000000000010

ID:19 山梨県 =(2の18乗)= 00000000000000000000000000000100000000000000000
ID:20 長野県 =(2の19乗)= 00000000000000000000000000001000000000000000000
ID:21 岐阜県 =(2の20乗)= 00000000000000000000000000010000000000000000000
ID:22 静岡県 =(2の21乗)= 00000000000000000000000000100000000000000000000

ID:47 沖縄県 = (2の46乗)= 10000000000000000000000000000000000000000000000

のようにします。

富士山は山梨県と静岡県にまたがっているので、19桁目と22桁目に1を立てます。
御嶽山は長野県と岐阜県にまたがっているので、20,21桁目に1を立てます。
八ヶ岳は山梨県と長野県にまたがっているので、19,20桁目に1を立てます

その情報をmountainsテーブルに追加したカラムprefecture_idsに入力します。

(改造後)テーブル構成の例
■(改造後)mountainsテーブル(※イメージ)
id,name,prefecture_ids
1,富士山,00000000000000000000000001001000000000000000000
2,御嶽山,00000000000000000000000000110000000000000000000
3,八ヶ岳,00000000000000000000000000011000000000000000000

■prefecturesテーブル
以前と同じ

■mountain_prefecturesテーブル
廃止

mountainsテーブルのイメージは上記ですが、実際には10進数で入れるので、

(改造後)テーブル構成の例
■(改造後)mountainsテーブル
id,name,prefecture_ids
1,富士山,00000000000000000000000001001000000000000000000⇒(10進数に変換)⇒ 2359296
2,御嶽山,00000000000000000000000000110000000000000000000⇒(10進数に変換)⇒ 1572864
3,八ヶ岳,00000000000000000000000000011000000000000000000⇒(10進数に変換)⇒ 786432

となります。

例えば検索のUIで山梨県と静岡県それぞれにチェックを入れてリクエストし、
prefecture_id=19,22という値がリクエストパラメータとして送信されます。

サーバー側でSQLを組み立てます。

まずprefecture_idが19と22を選択した状態ということで、
19桁目、22桁目が1である2進数を作ります。
00000000000000000000000001001000000000000000000
これを10進数に変換すると、
2359296
になります。

というわけでSQLとその結果は以下となります。

SQLと結果

例)山梨県(ID:19)、静岡県(ID:22)に位置する山を取得する
SELECT id,name FROM mountains WHERE prefecture_ids & 2359296;

+—-+———–+
| id | name |
+—-+———–+
| 1 | 富士山 |
| 3 | 八ヶ岳 |
+—-+———–+
2 rows in set (0.01 sec)

ビットANDは演算子の左辺と右辺の同じ位置にあるビットを比較して、
両方のビットが共に1の場合だけ 1 にします。

これを2進数に変換すると理解しやすいかと思います。

SQLと結果
八ヶ岳 :00000000000000000000000000011000000000000000000
山梨静岡:00000000000000000000000001001000000000000000000
————————————————————
⇒⇒⇒⇒⇒00000000000000000000000000001000000000000000000←ヒット

 

富士山 :00000000000000000000000001001000000000000000000
山梨静岡:00000000000000000000000001001000000000000000000
————————————————————
⇒⇒⇒⇒⇒00000000000000000000000001001000000000000000000←ヒット

 

御嶽山はヒットしません。
御嶽山 :00000000000000000000000000110000000000000000000
山梨静岡:00000000000000000000000001001000000000000000000
————————————————————
⇒⇒⇒⇒⇒00000000000000000000000000000000000000000000000

以上です。

webエンジニアやってみてよかったか???キャリア12年の私が語ります

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です