Évitez les résultats de jointure de requête intermédiaire énorme (1.33615E + 35 lignes)

Question

J'ai besoin d'une requête pour empêcher une jointure qui produit 1.34218E + 35 résultats!

J'ai un tableau item (environ 8k articles, par exemple bouclier de Foo, arme de barre), et chaque article est l'un des 9 item_type différents (armure, arme, etc.). Chaque élément a plusieurs entrées dans item_attribute (par exemple Damage, Defense). Voici une représentation pseudo-code:

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 
) 

Maintenant, un personnage porte 9 articles au total à la fois (un chacun armure, arme, bouclier, etc) que j'appelle une configuration . Je veux construire une liste de configurations qui maximise un attribut, mais a un minimum d'un autre attribut. En termes d'exemple: pour un niveau de personnage 100, présente les 10 meilleurs réglages par dégâts où sum(defense of all items) >= 100.

L'approche naïve est:

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 

Mais, parce qu'il ya environ 8k articles dans item, cela signifie que l'importance des résultats pour le SGBD pour trier par près de 8000^9 = 1.34218E + 35 différentes configurations! Y a-t-il un meilleur moyen? Vous ne pouvez pas vous joindre uniquement aux # éléments les plus puissants?

Answer 1

Je pense que votre problème peut être résolu en utilisant integer linear programming. Je suggère de retirer vos données de la base de données et de les donner à l'un des solveurs hautement optimisés qui ont été écrits par des personnes qui ont travaillé longtemps sur leurs algorithmes, plutôt que d'essayer d'écrire votre propre solveur en SQL.

Answer 2

Devrait réduire la taille de la collection de manière drastique. Logiquement, la somme des éléments les plus élevés devrait fournir les combinaisons les plus élevées.

Answer 3

La première chose que je ferais est d'isoler vos articles. Au lieu de regarder la configuration dans son ensemble, regardez la somme des éléments individuels. À moins que vos objets n'interagissent l'un avec l'autre (bonus d'ensemble) vous allez faire un long chemin en maximisant stat A et en minimisant la stat B pour un seul slot, et en répétant ce processus pour chaque slot d'élément dans votre configuration. Cela réduira drastiquement la complexité de la requête, même si cela impliquera plus de requêtes. Cela devrait accélérer les choses à long terme. Une autre chose à se demander est combien vaut-il la peine de gagner la stat B (celle que vous voulez perdre) pour gagner stat A? Si vous pouviez gagner 1000 A, et ne gagner que 1 B, cela pourrait en valoir la peine. Mais, qu'en est-il de gagner 10 A, mais il faudrait gagner 9 B pour le faire? Maintenant les choses changent un peu.

Si vous respectez un ratio A: B, vous pouvez probablement faire chaque slot séparément, et joindre chacun de ces résultats séparés en une seule requête.