1
votes

ACL comme la correspondance en SQL

J'essaie de stocker des données de type ACL dans une table et de vérifier si un chemin spécifique correspond à l'un des modèles stockés.

J'ai testé à la fois sur MySQL et PostgreSQL.

Il y a mon table et (BTREE) index:

root@:26257/defaultdb> explain select block from acl where pattern = substring('/public/blabla', 0, length(pattern)+1);
    tree    | field  |                          description
+-----------+--------+---------------------------------------------------------------+
  render    |        |
   â””â”€â”€ scan |        |
            | table  | acl@primary
            | spans  | ALL
            | filter | pattern = substring('/public/blabla', 0, length(pattern) + 1)

root@:26257/defaultdb> explain select block from acl where pattern = 'hello';
       tree       | field |         description
+-----------------+-------+-----------------------------+
  render          |       |
   â””â”€â”€ index-join |       |
        â”œâ”€â”€ scan  |       |
        â”‚         | table | acl@acl_pattern
        â”‚         | spans | /"hello"-/"hello"/PrefixEnd
        â””â”€â”€ scan  |       |
                  | table | acl@primary

J'ai d'abord essayé de stocker des caractères génériques comme celui-ci, cela fonctionne, mais je n'ai pas trouvé de moyen d'utiliser les index, je ne pense pas c'est possible:

insert into acl values (default, '/public/', false);
insert into acl values (default, '/admin/', true);

// PostgreSQL
test=# explain analyze select block from acl where pattern = substring('/public/blabla', 0, length(pattern)+1);
                                                   QUERY PLAN
-----------------------------------------------------------------------------------------------------------------
 Seq Scan on acl  (cost=10000000000.00..10000000001.04 rows=1 width=1) (actual time=0.058..0.059 rows=1 loops=1)
   Filter: (pattern = "substring"('/public/blabla'::text, 0, (length(pattern) + 1)))
   Rows Removed by Filter: 1
 Planning Time: 0.074 ms
 Execution Time: 0.085 ms
(5 rows)

test=# explain analyze select block from acl where pattern = 'test';
                                                   QUERY PLAN
-----------------------------------------------------------------------------------------------------------------
 Index Scan using acl_pattern on acl  (cost=0.13..8.14 rows=1 width=1) (actual time=0.039..0.039 rows=0 loops=1)
   Index Cond: (pattern = 'test'::text)
 Planning Time: 0.147 ms
 Execution Time: 1.063 ms
(4 rows)

// MySQL
mysql> explain select block from acl where pattern = left('/public/blabla', length(pattern));
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra       |
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------------+
|  1 | SIMPLE      | acl   | NULL       | ALL  | NULL          | NULL | NULL    | NULL |    2 |    50.00 | Using where |
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------------+
1 row in set, 1 warning (0.00 sec)

mysql> explain select block from acl where pattern = "hello";
+----+-------------+-------+------------+------+---------------+-------------+---------+-------+------+----------+-------+
| id | select_type | table | partitions | type | possible_keys | key         | key_len | ref   | rows | filtered | Extra |
+----+-------------+-------+------------+------+---------------+-------------+---------+-------+------+----------+-------+
|  1 | SIMPLE      | acl   | NULL       | ref  | acl_pattern   | acl_pattern | 1019    | const |    1 |   100.00 | NULL  |
+----+-------------+-------+------------+------+---------------+-------------+---------+-------+------+----------+-------+

Comme la plupart (sinon tous) les motifs seront uniquement des préfixes, j'ai essayé d'éviter le caractère générique en faisant quelque chose comme ça, mais je n'ai pas pu utiliser indexes soit:

insert into acl values (default, '/public/%', false);
insert into acl values (default, '/admin/%', true);
select * from acl where '/public/hello' like pattern;

Lorsque je remplace la bonne valeur de la comparaison par une valeur statique, les index sont utilisés correctement, cela ressemble à l'appel de la fonction ou à l'utilisation du champ de modèle sur le la bonne valeur invalide l'utilisation des index?

J'ai également essayé avec CockroachDB pour comparaison (avec exactement les mêmes requêtes que PostgreSQL) et j'obtiens exactement le même comportement:

create table acl (id serial, pattern text, block bool);
create index acl_pattern on acl(pattern);

postgresql sql mysql database indexing

4 commentaires

L'index ne sera pas utilisé pour une seule ligne. Remplissez le tableau avec plusieurs milliers de lignes et réexécutez expliquer.

Alors pourquoi sont-ils utilisés correctement lorsque j'utilise pattern = 'hello' ?

Vous ne pouvez pas tirer de conclusions des tests sur un tableau à une ligne.

J'ai refait le même test avec 100.000 lignes (et en cours d'analyse) dans la table PostgreSQL, même problème.

3 Réponses :

1
votes

Il semble que l'index ne puisse pas être utilisé car l'expression de droite dépend du pattern (nécessite donc une lecture de la table).

En supposant que vous puissiez déterminer la longueur minimale des motifs (disons 6 caractères), vous pouvez essayer quelque chose comme ceci:

create index acl_pattern on acl(left(pattern, 6));

select * 
from acl 
where left(pattern, 6) = left('/public/something', 6) and '/public/something' like pattern

0 commentaires

1
votes

Pour utiliser LIKE, il manque l'opérateur text_pattern_ops dans votre index. Postgres est un peu spécial en ce qui concerne les caractères et la façon dont il gère les btrees signifie que le comportement sera différent en fonction du paramètre, vous devrez peut-être lire à ce sujet. TLDR votre index doit ressembler à ceci pour utiliser LIKE:

créer un index acl_pattern sur acl (pattern text_pattern_ops);

https://www.postgresql.org/docs/11/indexes -opclass.html

L'autre problème est que Postgres a un planificateur de requêtes, donc si votre table ne contient que 2 lignes, il n'envisagerait pas de vérifier le coût initial de l'index car il y a de fortes chances que l'index lui dise simplement de se référer à la page sur la table sur laquelle se trouvent de toute façon ces deux lignes.

3 commentaires

J'ai mis 100 000 sur la table pour avoir plus de données, mais même après avoir remplacé mon index par le vôtre, j'obtiens le même comportement.

Le conseil est faux. L'index ne peut pas supporter une colonne utilisée sur le côté droit de comme .

Mes excuses, je n'ai pas vu la requête utiliser comme avec la valeur de la colonne - le pourcentage sera pris littéralement et non comme un caractère générique dans ce cas

0
votes

(D'un point de vue MySQL. Je ne parle pas postgres.)

SELECT ...
    FROM ( SELECT --- as above ) AS x
    WHERE pattern = LEFT('/public/blabla', CHAR_LENGTH(pattern))

SELECT ...
    FROM ...
    WHERE pattern <= '/public/blabla'
    ORDER BY pattern DESC
    LIMIT 1

Cela va vous obtenez la première ligne correspondante en temps O (1). Ou cela vous donnera quelque chose qui ne correspond pas. Maintenant, vérifions lequel:

pattern = left('/public/blabla', length(pattern))

Cela fournira soit la 1 ligne, soit le vide.

0 commentaires