Optimiser une recherche dans un dictionnaire clés/valeurs

Version imprimable

:salut:

Prenons pour exemple ces deux tables

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
CREATE TABLE Main (
   pk1 integer,
   pk2 bigint,
   n varchar,
   CONSTRAINT main_pk PRIMARY KEY (pk1,pk2)
);
 
CREATE TABLE Arguments (
   pk1 integer,
   pk2 bigint,
   k varchar,
   v varchar,
   CONSTRAINT arguments_pk PRIMARY KEY (pk1,pk2,k),
   CONSTRAINT arguments_fk FOREIGN KEY (pk1,pk2) REFERENCES Main(pk1,pk2)
);

Je dois trouver toutes les lignes ayant différentes combinaisons clés/valeurs

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
SELECT pk1,pk2 FROM Main m WHERE
   n IN ('n1','n2')
   AND (
      (
            EXISTS (
               SELECT 1 FROM Arguments a WHERE
                  a.pk1=m.pk1 AND a.pk2=m.pk2 AND
                  k='k1' AND v ~* 'v1'
            )
            AND
            EXISTS (
               SELECT 1 FROM Arguments a WHERE
                  a.pk1=m.pk1 AND a.pk2=m.pk2 AND
                  k='k2' AND v ~* 'v2'
            )
      )
      OR
      (
            EXISTS (
               SELECT 1 FROM Arguments a WHERE
                  a.pk1=m.pk1 AND a.pk2=m.pk2 AND
                  k='k3' AND v ~* 'v3'
            )
      )
   )
;

Voyez-vous une méthode plus optimisée pour faire cela ?

:merci:

31/07/2014, 12h27
alassanediakite
Salut
Je vous rappelle que "Un dictionnaire sans exemple est un squelette".
Vous avez donné les schémas des tables sans préciser:
- le sens de leurs contenus
- des exemples de données
Par ailleurs, d'où viennent "n1", "n2", "k1", "v1"...?
@+

Qu'est ce que ça donne en pivotant les données pour récupérer des colonnes que l'on peut filtrer :

Code:

1
2
3
4
5
6
7
select pk1, pk2
     , max(case when k = 'k1' then v end) as k1
     , max(case when k = 'k2' then v end) as k2
     , max(case when k = 'k3' then v end) as k3
  from Arguments 
 where k in ('k1','k2','k3')
 group by pk1, pk2

Citation:

Envoyé par alassanediakite

Je vous rappelle que "Un dictionnaire sans exemple est un squelette".
Vous avez donné les schémas des tables sans préciser:

le sens de leurs contenus
des exemples de données

Par ailleurs, d'où viennent "n1", "n2", "k1", "v1"...?

Main : n est le "nom usuel" du composant concerné par le message
Arguments : k représente le nom d'une information concernant n tandis que v représente la valeur associée

les valeurs n1,n2 sont des valeurs exemples pour le champ n (idem k1,k2,k3 pour k v1,v2,v3 pour v)

un exemple de base
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Main 1;1;n1 1;2;n1 1;3;n2 1;4;n3 Arguments 1;1;k1;alpha_v1_bidule 1;1;k2;beta_v2_bidule 1;2;k1;alpha_v1_machin 1;2;k3b;gamma_v3_truc 1;3;k3;gamma_v3_machin 1;3;k4;delta_v4_chose 1;4;k5;epsilon_v5_truc
La requête doit me renvoyer :
Code:

1 2 3 1;1 1;3
Est-ce plus clair ?

01/08/2014, 10h57
aieeeuuuuu
Bonjour,

Non, ce n'est toujours pas très clair car :
1/ la requête du premier post ne renvoi pas le résultat voulu mais renvoi:
Code:

1 2 3 4 1;1 1;2 1;3
2/ je ne comprend pas bien comment obtenir le résultat voulu à partir du jeu d'essai !?!
01/08/2014, 14h06
alassanediakite

Citation:

Envoyé par gorgonite

Je dois trouver toutes les lignes ayant différentes combinaisons clés/valeurs

S'agit-il du cas de division relationnelle?
Si tel est le cas, il y a une troisième table qui doit contenir les "différentes combinaisons clés/valeurs".
@+
01/08/2014, 14h43
gorgonite
Citation:
Envoyé par aieeeuuuuu

Non, ce n'est toujours pas très clair car :
1/ la requête du premier post ne renvoi pas le résultat voulu mais renvoi:

Code:

1 2 3 4 1;1 1;2 1;3

2/ je ne comprend pas bien comment obtenir le résultat voulu à partir du jeu d'essai !?!
Effectivement... :oops:
Petite erreur du jeu de test, j'ai modifié k3 en k3b sur (1,2,k3,***v3***)

Forcément, ça va mieux en testant l'exemple que l'on publie pour expliquer son concept :aie:

Citation:

Envoyé par alassanediakite

S'agit-il du cas de division relationnelle?

Non pas du tout... sachant qu'en plus, les couples (k1,v1) , etc. et que l'ensemble des valeurs prises par k n'est pas forcément connue à l'avance ne sont pas connues à l'avance (je dois générer une requête à partir de critères exigées dans une interface graphique)

Et donc qu'est ce que ça donne avec un pivot ? Au moins c'est plus facile à lire :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
  with pivot as (
SELECT pk1, pk2
     , max(case when k = 'k1' then v end) AS k1
     , max(case when k = 'k2' then v end) AS k2
     , max(case when k = 'k3' then v end) AS k3
  FROM Arguments 
 WHERE k IN ('k1','k2','k3')
 GROUP BY pk1, pk2
)
select m.pk1, m.pk2
  from main m
  join pivot p on p.pk1 = m.pk1
              and p.pk2 = m.pk2
 where m.n in ('n1','n2')
   and (  (p.k1 ~* 'v1' and p.k2 ~* 'v2')
        or p.k3 ~* 'v3'
       );

Après le modèle EAV n'est pas fait pour être requêté de façon transverse, donc c'est forcément peu performant...

Désolé, mais j'ai toujours pas compris !

Notamment, dans la requête postée, pour quoi ((v1 ET v2) OU v3)

Mais si on s'en tiens à une requete équivalent sans trop chercher la logique, on peut tenter ça :
Code:

1 2 3 4 5 6 7 8 9 10 11 SELECT pk1, pk2 FROM Arguments GROUP BY pk1, pk2 HAVING SUM( DISTINCT CASE WHEN k='k1' AND v ~* 'v1' THEN 1 WHEN k='k2' AND v ~* 'v2' THEN 2 WHEN k='k3' AND v ~* 'v3' THEN 4 END ) BETWEEN 3 AND 4;

01/08/2014, 16h01
gorgonite

Citation:

Envoyé par skuatamad

Et donc qu'est ce que ça donne avec un pivot ?
Après le modèle EAV n'est pas fait pour être requêté de façon transverse, donc c'est forcément peu performant...

En fait, similaire à ma requête :cry:

Citation:

Envoyé par aieeeuuuuu

Désolé, mais j'ai toujours pas compris !

Notamment, dans la requête postée, pour quoi ((v1 ET v2) OU v3)

Parce que l'interface d'interrogation leur permet d'avoir des contraintes de ce type uniquement (on pourrait discuter de la pertinence de l'interface, mais je me concentre d'abord sur cela ;) )

Citation:

Envoyé par aieeeuuuuu

Mais si on s'en tiens à une requete équivalent sans trop chercher la logique, on peut tenter ça :

Je perds un facteur 4 comparé à ma requête initiale

Je prépare des plans d'exécution sur ma base réelle pour illustrer tout cela :D

:merci: à vous

Comme promis... voici les plans d'exécution :D
Pour info, la base devrait à terme contenir 20 fois plus de données

Version skuatamad

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
SELECT pk1, pk2
     , max(case when k = 'k1' then v end) AS k1
     , max(case when k = 'k2' then v end) AS k2
     , max(case when k = 'k3' then v end) AS k3
  FROM Arguments 
 WHERE k IN ('k1','k2','k3')
 GROUP BY pk1, pk2
 
Nested Loop  (cost=606983.28..606996.08 rows=1 width=265) (actual time=4800.009..4922.699 rows=227 loops=1)
   Join Filter: ((tbl.pk1 = main.pk1) AND (tbl.pk2 = main.pk2))
   CTE tbl
     ->  Nested Loop  (cost=606835.44..606983.28 rows=1 width=12) (actual time=4799.981..4917.891 rows=227 loops=1)
           CTE pivot
             ->  HashAggregate  (cost=606809.47..606835.44 rows=2597 width=42) (actual time=4799.773..4840.691 rows=70925 loops=1)
                   ->  Seq Scan on arguments  (cost=0.00..606420.05 rows=25961 width=42) (actual time=15.591..4735.148 rows=71156 loops=1)
                         Filter: ((cle)::text = ANY ('{"k1","k2"}'::text[]))
                         Rows Removed by Filter: 27346156
           ->  CTE Scan on pivot p  (cost=0.00..64.92 rows=8 width=12) (actual time=4799.928..4899.968 rows=227 loops=1)
                 Filter: ((k1 ~* 'v1'::text) AND (k2 ~* 'v2'::text))
                 Rows Removed by Filter: 70698
           ->  Index Scan using main_pkey on main m  (cost=0.00..10.35 rows=1 width=12) (actual time=0.076..0.077 rows=1 loops=227)
                 Index Cond: ((pk1 = p.pk1) AND (pk2 = p.pk2))
                 Filter: ((subsystem)::text = ANY ('{n1,n2}'::text[]))
   ->  Nested Loop  (cost=0.00..10.37 rows=1 width=268) (actual time=4799.996..4920.844 rows=227 loops=1)
         ->  CTE Scan on tbl  (cost=0.00..0.02 rows=1 width=12) (actual time=4799.984..4918.141 rows=227 loops=1)
         ->  Index Scan using main_text_pk on main_text  (cost=0.00..10.34 rows=1 width=256) (actual time=0.009..0.010 rows=1 loops=227)
               Index Cond: ((pk1 = tbl.pk1) AND (pk2 = tbl.pk2))
   ->  Index Scan using main_pkey on main  (cost=0.00..2.42 rows=1 width=25) (actual time=0.005..0.006 rows=1 loops=227)
         Index Cond: ((pk1 = main_text.pk1) AND (pk2 = main_text.pk2))
 Total runtime: 4923.862 ms

Version gorgonite

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
 
SELECT pk1,pk2 FROM Main m WHERE
   n IN ('n1','n2')
   AND (
      (
            EXISTS (
               SELECT 1 FROM Arguments a WHERE
                  a.pk1=m.pk1 AND a.pk2=m.pk2 AND
                  k='k1' AND v ~* 'v1'
            )
            AND
            EXISTS (
               SELECT 1 FROM Arguments a WHERE
                  a.pk1=m.pk1 AND a.pk2=m.pk2 AND
                  k='k2' AND v ~* 'v2'
            )
      )
      OR
      (
            EXISTS (
               SELECT 1 FROM Arguments a WHERE
                  a.pk1=m.pk1 AND a.pk2=m.pk2 AND
                  k='k3' AND v ~* 'v3'
            )
      )
   )
;
 
Nested Loop  (cost=603414.76..603427.57 rows=1 width=265) (actual time=226.368..4401.881 rows=227 loops=1)
   Join Filter: ((tbl.pk1 = main.pk1) AND (tbl.pk2 = main.pk2))
   CTE tbl
     ->  Nested Loop Semi Join  (cost=0.00..603414.76 rows=1 width=12) (actual time=226.318..4396.409 rows=227 loops=1)
           ->  Nested Loop Semi Join  (cost=0.00..603367.84 rows=1 width=24) (actual time=59.601..3993.950 rows=62552 loops=1)
                 ->  Seq Scan on main m  (cost=0.00..135001.30 rows=19964 width=12) (actual time=48.342..1734.049 rows=82263 loops=1)
                       Filter: ((subsystem)::text = ANY ('{n1,n2}'::text[]))
                       Rows Removed by Filter: 6647802
                 ->  Index Scan using arguments_pkey on arguments a  (cost=0.00..23.46 rows=1 width=12) (actual time=0.026..0.026 rows=1 loops=82263)
                       Index Cond: ((pk1 = m.pk1) AND (pk2 = m.pk2) AND ((cle)::text = 'k2'::text))
                       Filter: ((valeur)::text ~* 'v2'::text)
           ->  Index Scan using arguments_pkey on arguments a  (cost=0.00..23.46 rows=1 width=12) (actual time=0.006..0.006 rows=0 loops=62552)
                 Index Cond: ((pk1 = m.pk1) AND (pk2 = m.pk2) AND ((cle)::text = 'k1'::text))
                 Filter: ((valeur)::text ~* 'v1'::text)
   ->  Nested Loop  (cost=0.00..10.37 rows=1 width=268) (actual time=226.344..4399.461 rows=227 loops=1)
         ->  CTE Scan on tbl  (cost=0.00..0.02 rows=1 width=12) (actual time=226.324..4396.825 rows=227 loops=1)
         ->  Index Scan using main_text_pk on main_text  (cost=0.00..10.34 rows=1 width=256) (actual time=0.009..0.009 rows=1 loops=227)
               Index Cond: ((pk1 = tbl.pk1) AND (pk2 = tbl.pk2))
   ->  Index Scan using main_pkey on main  (cost=0.00..2.42 rows=1 width=25) (actual time=0.008..0.008 rows=1 loops=227)
         Index Cond: ((pk1 = main_text.pk1) AND (pk2 = main_text.pk2))
 Total runtime: 4402.071 ms

Version aieeeuuuuu

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
SELECT 	pk1, pk2
FROM 	Arguments
GROUP BY pk1, pk2
HAVING 	SUM( 	DISTINCT 
		CASE 
			WHEN k='k1' AND v ~* 'v1' THEN 1 
			WHEN k='k2' AND v ~* 'v2' THEN 2
			WHEN k='k3' AND v ~* 'v3'  THEN 4
		END
	)  BETWEEN 3 AND 4;
 
Nested Loop  (cost=3569215.63..4681505.46 rows=20404 width=265) (actual time=30341.751..33326.849 rows=227 loops=1)
   Join Filter: ((tbl.pk1 = main_text.pk1) AND (tbl.pk2 = main_text.pk2))
   CTE tbl
     ->  GroupAggregate  (cost=0.00..3079398.20 rows=2748369 width=42) (actual time=3486.792..29993.754 rows=227 loops=1)
           Filter: (sum(DISTINCT CASE WHEN (((arguments.cle)::text = 'k1'::text) AND ((arguments.valeur)::text ~* 'v1'::text)) THEN 1 WHEN (((arguments.cle)::text = 'k2'::text) AND ((arguments.valeur)::text ~* 'v2'::text)) THEN 2 ELSE NULL::integer END) = 3)
           Rows Removed by Filter: 6729838
           ->  Index Scan using arguments_pkey on arguments  (cost=0.00..2564079.12 rows=27483684 width=42) (actual time=0.033..10273.016 rows=27417312 loops=1)
   ->  Merge Join  (cost=489817.43..981930.38 rows=244704 width=37) (actual time=30341.708..33299.604 rows=227 loops=1)
         Merge Cond: ((main.pk1 = tbl.pk1) AND (main.pk2 = tbl.pk2))
         ->  Index Scan using main_pkey on main  (cost=0.00..428622.50 rows=6711944 width=25) (actual time=0.049..2484.847 rows=6510499 loops=1)
         ->  Materialize  (cost=489817.43..503559.27 rows=2748369 width=12) (actual time=29994.256..29994.447 rows=227 loops=1)
               ->  Sort  (cost=489817.43..496688.35 rows=2748369 width=12) (actual time=29994.253..29994.339 rows=227 loops=1)
                     Sort Key: tbl.pk1, tbl.pk2
                     Sort Method: quicksort  Memory: 35kB
                     ->  CTE Scan on tbl  (cost=0.00..54967.38 rows=2748369 width=12) (actual time=3486.795..29994.065 rows=227 loops=1)
   ->  Index Scan using main_text_pk on main_text  (cost=0.00..2.52 rows=1 width=256) (actual time=0.117..0.117 rows=1 loops=227)
         Index Cond: ((pk1 = main.pk1) AND (pk2 = main.pk2))
 Total runtime: 33327.007 ms

01/08/2014, 17h16
alassanediakite

Salut
gorgonite, est-il possible d'injecter dans une table temporaire, les valeurs reçues de l'interface?
Je rejoins aieeeuuuuu, la logique de la chose est encore floue!
@+
01/08/2014, 20h26
gorgonite

Citation:

Envoyé par alassanediakite

gorgonite, est-il possible d'injecter dans une table temporaire, les valeurs reçues de l'interface?

oui, je comptais justement faire des stats sur les requêtes exécutées :)

Citation:

Envoyé par alassanediakite

Je rejoins aieeeuuuuu, la logique de la chose est encore floue!

"recherche floue" dans un système de monitoring architecturé EAV... justement :ccool:

Citation:

Filter: ((subsystem)::text = ANY ('{n1,n2}'::text[]))
Rows Removed BY Filter: 6647802

Bien sûr, dans la requete que j'avais proposée, il faut remettre le filtre sur n IN ('n1','n2')soit :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 SELECT m.pk1, m.pk2 FROM Main m INNER JOIN Arguments A ON m.pk1 = A.pk1 AND m.pk2 = A.pk2 WHERE n IN ('n1','n2') GROUP BY m.pk1, m.pk2 HAVING SUM( DISTINCT CASE WHEN k='k1' AND v LIKE '%v1%' THEN 1 WHEN k='k2' AND v LIKE '%v2%' THEN 2 WHEN k='k3' AND v LIKE '%v3%' THEN 4 END ) BETWEEN 3 AND 4;

04/08/2014, 14h13
gorgonite

erreur de ma part... :oops:

cela passe de 32s à 26s

réflexion faite, on peut ajouter un filtre supplémentaire AND k IN ('k1', 'k2', 'k3')

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
 
SELECT 	m.pk1, m.pk2
FROM 	Main m
INNER JOIN Arguments A
	ON m.pk1 = A.pk1
	AND m.pk2 = A.pk2
WHERE n IN ('n1','n2')
AND k IN ('k1', 'k2', 'k3')
GROUP BY m.pk1, m.pk2
HAVING 	SUM( 	DISTINCT 
		CASE 
			WHEN k='k1' AND v LIKE '%v1%' THEN 1 
			WHEN k='k2' AND v LIKE '%v2%' THEN 2
			WHEN k='k3' AND v LIKE '%v3%'  THEN 4
		END
	)  BETWEEN 3 AND 4;

Quels sont les index sur ces tables ?

04/08/2014, 16h34
gorgonite

Citation:

Envoyé par aieeeuuuuu

réflexion faite, on peut ajouter un filtre supplémentaire AND k IN ('k1', 'k2', 'k3')

effectivement, ça passe à 8s

Citation:

Envoyé par aieeeuuuuu

Quels sont les index sur ces tables ?

Rien de notable