「サイゼリヤで1000円あれば最大何kcal摂れるのか」をSQLで解いてみた。 


#はじめに
サイゼリヤ1000円カロリー問題が流行っているのを見て、SQLならもっとシンプルに記述できるんじゃないかなぁ（遅いだろうけど）と思い立ち作ってみました。

* [サイゼリヤ1000円ガチャをつくってみた(Heroku + Flask + LINEbot](https://qiita.com/marusho_summers/items/a2d3681fac863734ec8a)
* [「サイゼリヤで1000円あれば最大何kcal摂れるのか」を量子アニーリング計算(Wildqat)で解いてみた。](https://qiita.com/hodaka0714/items/cf44b4ece992a39b5be4)
* [「サイゼリヤで1000円あれば最大何kcal摂れるのか」をSMTソルバー(Z3)で解いてみた。](https://qiita.com/tanakh/items/a1fb13f78e0576415de3)
* [「サイゼリヤで1000円あれば最大何kcal摂れるのか」を整数計画法ソルバー(PuLP)で解いてみた。](https://qiita.com/YSRKEN/items/dfc8604eb8598e5e9076)
* [「サイゼリヤで1000円あれば最大何kcal摂れるのか」をマルコフ連鎖モンテカルロで解いてみた。](https://qiita.com/kaityo256/items/b9a146d806dcb4f6edf9)
* [「サイゼリヤで1000円あれば最大何kcal摂れるのか」をExcel のソルバーでで解いてみた。](https://qiita.com/miki_iwa/items/5e0434da8b1150c21741)
* [【Excel】サイゼリヤ1000円で摂れるカロリーの最大値をVLOOKUP関数だけで求める方法](https://www.waenavi.com/entry/20190519/1558269886)
* [「サイゼリヤで1000円あれば最大何kcal摂れるのか」をTeX言語で計算する ～TeX言語で動的計画法(DP)～](https://doratex.hatenablog.jp/entry/20190520/1558323856)
* [「サイゼリヤで1000円あれば最大何kcal摂れるのか」をなでしこでDPで解いてみた。](https://qiita.com/n_chiba_/items/694035ad880126230309)

#環境
windows subsystem for windowsのUbuntu18.04で実行しました。PCのスペックは下記。

* CPU:Core i7-6700HQ
* Memory:8GB


#セットアップ
postgresをインストールして起動。

```
$ sudo apt install postgresql postgresql-contrib
$ sudo /etc/init.d/postgresql start
```

テーブル作ってCSVをインポート。CSVは@hodaka0714さんの[git](https://github.com/hodaka0714/saize_calory_maxmization)から拝借して「C:\temp」に配置

```
$ sudo su postgres -c 'psql'
CREATE TABLE menu (
    id       INTEGER
  , name     TEXT
  , category TEXT
  , type     TEXT
  , price    INTEGER
  , calorie  INTEGER
  , salt     NUMERIC
  , PRIMARY KEY (id) 
);
\COPY menu FROM '/mnt/c/temp/menu.csv' CSV HEADER
```

#SQL検討
直積で全パターンの組み合わせ作って不要なレコードをフィルターすれば良いんじゃないか？と思いまず書いたのがコレ。

```
SELECT a.name
     , b.name
     , a.price + b.price AS total_price
     , a.calorie + b.calorie AS total_calorie
  FROM menu AS a
 CROSS JOIN menu AS b
 WHERE a.price + b.price <= 1000
 ORDER BY total_calorie desc 
 FETCH FIRST 10 ROWS ONLY; 
```

結果はこちら。そうだよね、、、そりゃ重複するよね、、、

```
                 name                 |                 name                 | total_price | total_calorie
--------------------------------------+--------------------------------------+-------------+---------------
 ラージライス                         | パルマ風スパゲッティ(Wサイズ)        |         989 |          1854
 パルマ風スパゲッティ(Wサイズ)        | ラージライス                         |         989 |          1854
 ラージライス                         | キャベツのペペロンチーノ(Wサイズ)    |         989 |          1826
 キャベツのペペロンチーノ(Wサイズ)    | ラージライス                         |         989 |          1826
 アーリオ・オーリオ(Wサイズ)          | パルマ風スパゲッティ                 |         973 |          1820
 パルマ風スパゲッティ                 | アーリオ・オーリオ(Wサイズ)          |         973 |          1820
 キャベツのペペロンチーノ             | アーリオ・オーリオ(Wサイズ)          |         973 |          1806
 アーリオ・オーリオ(Wサイズ)          | キャベツのペペロンチーノ             |         973 |          1806
 アーリオ・オーリオ(Wサイズ)          | セットプチフォッカ付きミラノ風ドリア |         952 |          1769
 セットプチフォッカ付きミラノ風ドリア | アーリオ・オーリオ(Wサイズ)          |         952 |          1769
```

重複を排除するなら「a.name!=b.name」を追加すれば良いけど、これだと順番違いが含まれちゃいます。順番違いも含め重複を排除するイディオム的な書き方はこちら。CROSS JOINでWHEREに結合条件を書いても一緒。

```
SELECT a.name
     , b.name
     , a.price + b.price AS total_price
     , a.calorie + b.calorie AS total_calorie
  FROM menu AS a
 INNER JOIN menu AS b
    ON a.price < b.price
 WHERE a.price + b.price <= 1000
 ORDER BY total_calorie desc 
 FETCH FIRST 10 ROWS ONLY; 
```

結合条件「a.price<b.price」の所の意味が一見しただけだと分かり辛いけど、絵にかくと良くわかる（気がする）
![組み合わせの絵.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/14831/495e9810-2418-29bc-060a-05bbd3a261eb.png)

結果はそれっぽくなってきました。

```
                 name                 |               name                | total_price | total_calorie
--------------------------------------+-----------------------------------+-------------+---------------
 ラージライス                         | パルマ風スパゲッティ(Wサイズ)     |         989 |          1854
 ラージライス                         | キャベツのペペロンチーノ(Wサイズ) |         989 |          1826
 パルマ風スパゲッティ                 | アーリオ・オーリオ(Wサイズ)       |         973 |          1820
 キャベツのペペロンチーノ             | アーリオ・オーリオ(Wサイズ)       |         973 |          1806
 セットプチフォッカ付きミラノ風ドリア | アーリオ・オーリオ(Wサイズ)       |         952 |          1769
 ポテトのグリル                       | パルマ風スパゲッティ(Wサイズ)     |         969 |          1766
 パンチェッタのピザ                   | アーリオ・オーリオ(Wサイズ)       |         973 |          1766
 半熟卵のミラノ風ドリア               | アーリオ・オーリオ(Wサイズ)       |         942 |          1752
 ポテトのグリル                       | キャベツのペペロンチーノ(Wサイズ) |         969 |          1738
 野菜ときのこのピザ                   | アーリオ・オーリオ(Wサイズ)       |         973 |          1730
```

ただ上記だと2品の組み合わせだけなので、1000円以下を満たす複数の品の組み合わせを作る必要があります。
これは簡単で、3品以上も同様の考え方でINNER JOINを増やして行けば良いだけ。

```
SELECT a.name
     , b.name
     , a.price + b.price + c.price AS total_price
     , a.calorie + b.calorie + c.calorie AS total_calorie
  FROM menu AS a
 INNER JOIN menu AS b
    ON a.price < b.price
 INNER JOIN menu AS c
    ON b.price < c.price
 WHERE a.price + b.price + c.price  <= 1000
 ORDER BY total_calorie desc 
 FETCH FIRST 10 ROWS ONLY; 
```

一番安いトッピング半熟卵が69円なので、1000円以下とすると最大でも14品の組み合わせとなるため、上記のSQLを14品のパターンまで作ってunion allで纏めるだけ、、、ってさすがにやってられんわ！

でもそんな時は再帰を使えばOKです。postgresで良かった。

#まとめ

最終的にこんな感じになりました。シンプル！とは言い難い、、、

```
WITH RECURSIVE cource(name_list, pre_id, total_price, total_calorie) AS ( 
    SELECT a.name    AS name_list 
         , a.id      AS pre_id 
         , a.price   AS total_price  
         , a.calorie AS total_calorie 
      FROM menu a 
     WHERE a.price <= 1000
    UNION ALL 
    SELECT a.name_list ||','|| b.name AS name_list --カンマ区切りで商品名を保持
         , b.id AS pre_id --次回の結合用に前回のidを保存
         , a.total_price + b.price AS total_price  
         , a.total_calorie + b.calorie AS total_calorie 
      FROM cource a  
     INNER JOIN menu AS b  
        ON a.pre_id < b.id 
     WHERE (a.total_price + b.price) <= 1000 
) 
SELECT name_list , total_price, total_calorie 
  FROM cource 
 ORDER BY total_calorie desc 
 FETCH FIRST 10 ROWS ONLY; 

```

結果は下記で先人達と同様と思われます。

```
                                 name_list                                  | total_price | total_calorie
----------------------------------------------------------------------------+-------------+---------------
 ポテトのグリル,アーリオ・オーリオ(Wサイズ),ラージライス                         |         992 |          1940
 フォッカチオ,セットプチフォッカ,アーリオ・オーリオ(Wサイズ),ラージライス         |         991 |          1895
 フォッカチオ,アーリオ・オーリオ,アーリオ・オーリオ(Wサイズ)                     |         992 |          1894
 フォッカチオ,アーリオ・オーリオ(Wサイズ),トッピング半熟卵,ラージライス           |         981 |          1878
 アーリオ・オーリオ(Wサイズ),ライス,ラージライス                                |         962 |          1877
 フォッカチオ,アーリオ・オーリオ(Wサイズ),ミラノ風ドリア                         |         992 |          1876
 アーリオ・オーリオ,ミラノ風ドリア,ライス,ラージライス                           |         986 |          1859
 パルマ風スパゲッティ(Wサイズ),ラージライス                                     |         989 |          1854
 セットプチフォッカ,アーリオ・オーリオ(Wサイズ),ラージライス,スモールライス        |         991 |          1832
 アーリオ・オーリオ,アーリオ・オーリオ(Wサイズ),スモールライス                    |         992 |          1831
```

実行計画はこんな感じ。約100万件の組み合わせをnestloopで作ってフィルターで抽出するという力業。約2分もかかっていて先人達のアルゴリズムの偉大さが良く分かる。

```
----------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=22445.22..22445.25 rows=10 width=40) (actual time=11209.001..11209.018 rows=10 loops=1)
   CTE cource
     ->  Recursive Union  (cost=0.00..16698.60 rows=138108 width=47) (actual time=0.018..8656.302 rows=1042164 loops=1)
           ->  Seq Scan on menu a  (cost=0.00..3.44 rows=108 width=47) (actual time=0.015..0.077 rows=108 loops=1)
                 Filter: (price <= 1000)
                 Rows Removed by Filter: 7
           ->  Nested Loop  (cost=0.14..1393.30 rows=13800 width=44) (actual time=1.371..908.944 rows=130257 loops=8)
                 ->  WorkTable Scan on cource a_1  (cost=0.00..21.60 rows=1080 width=44) (actual time=0.031..95.031 rows=130270 loops=8)
                 ->  Index Scan using menu_pkey on menu b  (cost=0.14..1.01 rows=13 width=47) (actual time=0.003..0.004 rows=1 loops=1042164)
                       Index Cond: (a_1.pre_id < id)
                       Filter: ((a_1.total_price + price) <= 1000)
                       Rows Removed by Filter: 18
   ->  Sort  (cost=5746.62..6091.89 rows=138108 width=40) (actual time=11208.999..11209.003 rows=10 loops=1)
         Sort Key: cource.total_calorie DESC
         Sort Method: top-N heapsort  Memory: 27kB
         ->  CTE Scan on cource  (cost=0.00..2762.16 rows=138108 width=40) (actual time=0.019..10605.978 rows=1042164 loops=1)
 Planning time: 0.212 ms
 Execution time: 11232.940 ms
(18 rows)
```

ちなみにこの記事は閉店間際のサイゼリヤで飲みながら書きました。
![飲みながら.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/14831/d95569ee-7441-cb07-6dbb-0a07101be82c.png)