SQL comment déterminer le nombre et la séquence de Autojointures donné les critères de sélection

Question

J'ai une table valeur clé nommée ATTR, où les données relatives à un enregistrement logique (identifié par un S #) sont stockées sous forme de paires clé-valeur .

table ATTR: 
S# KEY VALUE 

Ainsi, les critères indiqués dans le code: psuedo-

Select S# Where k1 > 5 

devient

Select t1.S# 
from ATTR t1 
where t1.KEY = 'k1' AND t1.VALUE > 5 

et ainsi de suite. Pratiquement tous mes cas d'utilisation impliquent une ou plusieurs auto-adhésions.

Ma question est - étant donné un critère, est il y a une approche scientifique à déduire le nombre d'auto-jointures nécessaires, et comment faire. Est-ce qu'il faut un réarrangement des critères (je voudrais éviter que l'optimiseur de requêtes dbms ne se charge de cela).

Pour donner quelques exemples

crit: where k1 > 5 OR k2 > 10 
=> no extra join needed 
Select t1.S# 
from ATTR t1 
where (t1.KEY = 'k1' AND t1.VALUE > 5) OR (t1.KEY = 'k2' AND t1.VALUE > 10) 

crit: where k1 > 5 AND k2 > 10 
=> 1 self-join needed 
Select t1.S# 
from ATTR t1 
inner join ATTR t2 on t1.S# = t2.S# 
where (t1.KEY = 'k1' AND t1.VALUE > 5) 
     AND 
     (t2.KEY = 'k2' AND t2.VALUE > 10) 

crit: where k1 > 5 AND k2 > 10 AND k3 > 20 
=> 2 self-joins needed 
Select t1.S# 
from ATTR t1 
inner join ATTR t2 on t1.S# = t2.S# 
inner join ATTR t3 on t1.S# = t3.S# 
where (t1.KEY = 'k1' AND t1.VALUE > 5) 
     AND 
     (t2.KEY = 'k2' AND t2.VALUE > 10) 
     AND 
     (t3.KEY = 'k3' AND t3.VALUE > 20) 

crit: where (k1 > 5 OR k2 > 10) AND (k1 > 10 OR K3 > 20) 
=> 1 self-join needed 
Select t1.S# 
from ATTR t1 
inner join ATTR t2 on t1.S# = t2.S# 
where ((t1.KEY = 'k1' AND t1.VALUE > 5) OR (t1.KEY = 'k2' AND t1.VALUE > 10)) 
     AND 
     ((t1.KEY = 'k1' AND t1.VALUE > 10) OR (t2.KEY = 'k3' AND t2.VALUE > 20)) 

crit: where (k1 > 5 AND k2 > 10) or (k1 > 10 OR K3 > k4) 
and so on 
=> ?? 

Je n'ai pas les limites définies sur le nombre d'expressions atomiques (à savoir le plus petit d'expression booléenne), à ​​l'exception qu'ils soient combinés en utilisant seulement ET OU NON. Mais je peux heureusement fixer une limite (disons 10-20 atomes) si cela permet de faire de l'algo. Je suis sûr que tous les SGBDR ont aussi des limites de base. Je pense aussi que le cas XOR pourrait être plié en ET, et NON n'est pas important pour le problème.

J'utilise une base de données columnr.

Merci beaucoup

EDIT # 2 - ajouté quelques exemples de données

S# KEY VALUE 
1 k1 1 
1 k2 5 
1 k3 10 
1 k4 20 
2 k1 10 
2 k2 20 
2 k3 30 
2 k4 40 
2 k5 50 
3 k2 11 
3 k4 22 
3 k6 33 
3 k8 44 
3 k10 55 
and so on 

Dans environ 500 millions de lignes, il y a environ 900 clés distinctes au total. La plupart des "enregistrements" utilisent environ 50 à 60 clés différentes. La table actuelle contient environ 20 colonnes, y compris les informations sur les pistes de vérification. Je les ai réduits ici pour garder le problème concentré.

Answer 1

En général, chaque critère de valeur-clé (par exemple Key = 'k1' AND Value > 5) avec un opérande AND nécessite une recherche de table séparée. Une fois que vous aurez déterminé comment analyser vos critères (par exemple, où k1> 5 ET k2> 10), vous pourrez générer le code SQL requis.

Vous n'avez pas besoin d'utiliser explicitement le mot clé JOIN. Vous pouvez utiliser à la place EXISTS, ce qui peut être un peu plus simple à lire. Voici un exemple en fonction de critères que vous avez fournis à titre d'exemple:

where (k1 > 5 OR k2 > 10) AND (k1 > 10 OR K3 > 20) 

SELECT t.s# 
FROM ATTR t 
WHERE 1=1 
-- KVP on left side of the AND 
AND EXISTS (
    SELECT 1 
    FROM ATTR t1 
    WHERE t.S# = t1.S# -- Join sub-query to parent query 
    AND (
     (t1.Key = 'k1' AND t1.Value > 5) 
     OR 
     (t1.Key = 'k2' AND t1.Value > 10) 
     ) 
) 
-- KVP on right side of the AND 
AND EXISTS (
    SELECT 1 
    FROM ATTR t1 
    WHERE t.S# = t1.S# -- Join sub-query to parent query 
    AND (
     (t1.Key = 'k1' AND t1.Value > 10) 
     OR 
     (t1.Key = 'k3' AND t1.Value > 20) 
     ) 
)