Избегайте огромных промежуточных результатов объединения запросов (1.33615E + 35 строк)

Question

Мне нужен запрос для предотвращения объединения, которое дает 1.34218E + 35 результатов!

У меня есть стол item (примерно 8 000 предметов; например, Щит Фу, Оружие Бар), и каждый предмет - один из 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 представьте лучшие 10 установок по урону, где 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 имеется около 8 тыс. Элементов, это означает, что величина результатов, которые СУБД должна отсортировать, близка к 8000 ^ 9 = 1,34218E + 35 различных установок! Есть ли лучший способ?

Answer 1

Я думаю, что ваша проблема может быть решена с помощью целочисленного линейного программирования .Я бы предложил вытащить ваши данные из базы данных и передать их одному из высоко оптимизированных решателей, написанных людьми, которые долгое время работали над своими алгоритмами, вместо того, чтобы пытаться написать свой собственный решатель на SQL.

Answer 2

Первое, что я хотел бы сделать, это изолировать ваши предметы.Вместо того, чтобы смотреть на установку в целом, посмотрите на сумму отдельных элементов.Если ваши предметы не взаимодействуют друг с другом (устанавливают бонусы), вы проделаете долгий путь, просто максимизируя стат А и минимизируя стат Б только для одного слота, и повторяя этот процесс для каждого слота предметов в вашей настройке.Это значительно снизит сложность запроса, даже если это будет означать больше запросов.В долгосрочной перспективе это должно ускорить процесс.

Еще один вопрос, который вы себе задаете: сколько стоит получить стат B (тот, который вы хотите потерять), чтобы получить стат А?Если бы вы могли получить 1000 А, и вам нужно всего лишь 1 Б, это может стоить того.Но как насчет получения 10 А, но вам нужно было бы получить 9 В, чтобы сделать это?Теперь все немного меняется.

Если вы придерживаетесь отношения A: B, вы, вероятно, можете сделать каждый слот отдельно и объединить каждый из этих отдельных результатов в один запрос.

Answer 3

Разве вы не можете присоединиться только к # самым мощным предметам? Следует резко уменьшить размер коллекции. Логически сумма самых высоких предметов должна давать самые высокие комбинации.