避免庞大的中间查询连接结果（1.33615E + 35行）

Question

我需要一个查询来阻止产生1.34218E + 35结果的连接！我有一个表item（约8K项目;例如Foo的盾牌，武器的酒吧），每个项目是9个不同的item_type（护甲，武器等）之一。每个物品在item_attribute（例如伤害，防御）中有多个条目。下面是一个伪代码表示：

Table item (
item_id autoincrement, 
... 
item_type_id char, --- e.g. Armor, Weapon, etc 
level int    --- Must be at least this level to wear this item 
); 

Table item_attribute (
item_id int references item(item_id), 
... 
attribute char  --- e.g. Damage, Defense, etc 
amount int   --- e.g. 100 
) 

现在，一个字符一次穿9个总项目（每个装甲，武器，盾牌之一，等等），我称之为设置。我想建立一个设置列表，最大化属性，但具有另一个属性的最小。举个例子来说：对于一个角色等级100，出现前十个受损伤的装备，其中sum(defense of all items) >= 100。

天真的方法是：

select top 10 
q1.item_id,q2.item_id,q3.item_id,..., q1.damage+q2.damage+q3.damage... as damage 
from 
(select item_id from item where item_type = 'Armor' 
    and level <= 100) as q1 
inner join (select item_id from item where item_type = 'Shield' 
    and level <= 100) as q2 on 1 = 1 
inner join (select item_id from item where item_type = 'Weapon' 
    and level <= 100) as q3 on 1 = 1 
... 
where 
q1.defense+q2.defense+q3.defense+... >= 100 
order by 
q1.damage+q2.damage+q3.damage,... descending 

但是，因为有在item大约8K项，这意味着结果为DBMS需要整理的幅度接近8000^9 = 1.34218E + 35不同的设置！有没有更好的办法？

Answer 1

我认为你的问题可以使用integer linear programming来解决。我建议将数据从数据库中提取出来，并将其提供给高度优化的求解器之一，这些求解器是由花费很长时间研究算法的人编写的，而不是试图用SQL编写自己的求解器。

Answer 2

难道你不能只加入＃个最强大的物品吗？应该大幅度缩小收集尺寸。从逻辑上讲，最高项目的总和应该提供最高的组合。

Answer 3

我会做的第一件事就是隔离你的物品。不要将整个设置看在一起，而要看各个项目的总和。除非你的物品与海誓山盟互动（设置奖励），否则只需要最大化统计数据A并将统计数据B最小化为一个时间段，并对设置中的每个物品槽位重复该过程即可。这将大大降低查询的复杂性，即使这意味着更多的查询。从长远来看，它应该让事情变得更快。

另一个要问自己的问题是，获得数据A有多少值得到数据B（你想失去的数据）？如果你可以获得1000 A，并且只需要获得1 B，那可能是值得的。但是，获得10分，但你必须获得9分才能做到这一点？现在情况有所改变。

如果你坚持A：B比例，你可以单独做每个插槽，并将每个单独的结果连接到一个查询中。