ACL как сопоставление в SQL

Question

Я пытаюсь сохранить ACL-подобные данные в таблице и проверить, соответствует ли конкретный путь какому-либо из сохраненных шаблонов.

Я тестировал как на MySQL, так и на PostgreSQL.

Таммоя таблица и индекс (BTREE):

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

Сначала я попытался сохранить подстановочный знак, как это работает, но я не смог найти способ использовать индексы, я не думаю, что это возможно:

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

Поскольку большинство (если не все) шаблонов будут только префиксами, я пытался избежать подстановочного знака, делая что-то подобное, но я также не мог использовать индексы:

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  |
+----+-------------+-------+------------+------+---------------+-------------+---------+-------+------+----------+-------+

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

Я такжепопробовал с CockroachDB для сравнения (с теми же запросами, что и PostgreSQL), и я получаю точно такое же поведение:

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

Answer 1

Для использования LIKE в вашем индексе отсутствует оператор text_pattern_ops.Postgres немного особенный, когда дело доходит до символов, и то, как он обрабатывает btrees, означает, что поведение будет различным в зависимости от настроек, поэтому вам, возможно, придется ознакомиться с этим.TLDR ваш индекс должен выглядеть так, чтобы использовать LIKE:

create index acl_pattern on acl(pattern text_pattern_ops);

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

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

Answer 2

(С точки зрения MySQL. Я не говорю на postgres.)

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

->

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

Это даст вам первую подходящую строку в O(1 раз.Или это даст вам то, что не соответствует.Теперь давайте проверим, какие из них:

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

Это приведет либо к 1 строке, либо к пустому набору.

Answer 3

Кажется, что индекс нельзя использовать, потому что правое выражение зависит от pattern (поэтому требуется чтение из таблицы).

Предполагая, что вы можете определить минимальную длину паттернов (скажем, 6 символов), вы можете попробовать что-то вроде этого:

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