如何建模/快速测试 SQL 中的集合成员资格？

Question

表中的每一行都需要保护 一个应用程序特定角色的列表让我们说一些看起来像下面这个例子的东西

     Desired Table Structure

pkey | data | roles 
---------------------
 1   |  ... | {1,2,5}
 2   |  ... | {1,4,3}
 3   |  ... | {7,11,67,101}

在此示例中，具有主键 1 的行应该只对具有角色 1、2 或 5 的任何用户可见，第 2 行应该对具有角色 1、4 或 3 的任何用户可见......等等。

当用户登录应用程序时，应用程序会计算用户拥有的所有角色，例如我知道用户 1 具有角色 {1,11,7}，用户 2 具有角色 {1,3,5}

我当前的实现使用两个这样的表。

    Actual Table Structure

foo table
pkey | data 
------------
 1   | ... 
 2   | ...        
 3   | ...

 roles table
 foo_fk | role_id
 ------------------
   1     | 1
   1     | 2
   1     | 5
   2     | 1 
   2     | 4
   2     | 3
   3     | 7
   3     | 11 
   3     | 67
   3     | 101

对仅返回特定用户数据的数据进行查询需要连接。

有没有办法以某种方式表示角色，我可以在单个列中存储保护行的角色列表，以便我可以对该表执行选择语句，该语句仅返回用户可以看到的行。我希望这尽可能快。

我已经尝试过使用位串，但是因为 where 子句左侧的位串操作总是会导致全表扫描，因为(column & seach_bit_mask) == some_value需要评估表每一行上的位操作的表达式 返回结果，因此需要全表扫描。

有没有办法在不使用需要连接的两个表或需要全表扫描的位操作的情况下完成我上面想要的操作。我可以控制模式和角色的表示，如果有帮助，我愿意接受巧妙的编码方案。我正在使用 Postgres 9.2，如果为 PostgreSQL 编写 C 扩展可以帮助我愿意接受这个想法。

我无法为这个问题想出一个好的标题，任何可以改进标题的人都请这样做。

更新读取性能比 foo_roles 的更新性能重要得多

更新 PostgresSQL 的示例代码。

DROP TABLE IF EXISTS foo_roles;
DROP TABLE IF EXISTS foo;

CREATE TABLE foo (
  pkey INTEGER PRIMARY KEY,
  name TEXT
);

CREATE TABLE foo_roles(
  foo_fk INTEGER REFERENCES foo(pkey),
  role_id INTEGER,
  PRIMARY KEY (foo_fk,role_id)
);

INSERT INTO foo (pkey,name) VALUES 
(1,'A'), (2,'B'), (3,'C');

INSERT INTO foo_roles(foo_fk,role_id) VALUES 
(1,1), (1,2), (1,5), 
(2,1), (2,4), (2,3),
(3,7), (3,11), (3,67), (3,101);

SELECT DISTINCT foo.pkey
FROM   foo,
       foo_roles
WHERE  foo.pkey = foo_roles.foo_fk
       AND foo_roles.role_id IN ( 1, 2, 11, 14 ); 

解释当前实现查询，注意两个顺序表扫描。

HashAggregate  (cost=74.67..75.09 rows=42 width=4)
  ->  Hash Join  (cost=42.62..74.57 rows=42 width=4)
        Hash Cond: (foo.pkey = foo_roles.foo_fk)
        ->  Seq Scan on foo  (cost=0.00..22.30 rows=1230 width=4)
        ->  Hash  (cost=42.10..42.10 rows=42 width=4)
              ->  Seq Scan on foo_roles  (cost=0.00..42.10 rows=42 width=4)
                    Filter: (role_id = ANY ('{1,2,11,14}'::integer[]))

更新基于下面的 Chris Travers 回答。

DROP TABLE IF EXISTS foo_roles;
DROP TABLE IF EXISTS foo;

CREATE TABLE foo (
  pkey INTEGER PRIMARY KEY,
  name TEXT,
  roles INTEGER[]
);

CREATE INDEX ON foo USING gin(roles);

CREATE TABLE foo_roles(
  foo_fk INTEGER REFERENCES foo(pkey),
  role_id INTEGER,
  PRIMARY KEY (foo_fk,role_id)
);
CREATE OR REPLACE FUNCTION rebuild_foo_roles(in_foo_id int) RETURNS int[] 
LANGUAGE SQL AS $$

     UPDATE foo SET roles = (select array_agg(role_id) from foo_roles where foo_fk = $1)
      WHERE pkey = $1
     RETURNING roles;
$$;

INSERT INTO foo (pkey,name) VALUES (1,'A'), (2,'B'), (3,'C');
INSERT INTO foo_roles(foo_fk,role_id) VALUES 
(1,1),(1,2),(1,5),
(2,1),(2,4),(2,3),
(3,7),(3,11),(3,67),(3,101);

SELECT rebuild_foo_roles(1);
SELECT rebuild_foo_roles(2);
SELECT rebuild_foo_roles(3);

SELECT * from foo WHERE foo.roles && ARRAY[1,2,11,14];

查询结果

 pkey | name |     roles     
------+------+---------------
    1 | A    | {1,2,5}
    2 | B    | {1,4,3}
    3 | C    | {7,11,67,101}
(3 rows)

解释查询 EXPLAIN SELECT * from foo WHERE foo.roles && ARRAY[1,2,11,14];

                     QUERY PLAN                      
-----------------------------------------------------
 Seq Scan on foo  (cost=0.00..20.38 rows=4 width=68)
   Filter: (roles && '{1,2,11,14}'::integer[])
(2 rows)

它仍然会执行顺序扫描，但使用连接对查询计划进行了更好的改进。我不确定我是否正确创建了 GIN 索引，或者 postgres planner 是否正在执行 seq 扫描，因为没有足够的数据，所以我尝试了。

play=# set enable_seqscan=false;
SET
play=# explain SELECT * from foo WHERE foo.roles && ARRAY[1,2,11,14];
                                 QUERY PLAN                                  
-----------------------------------------------------------------------------
 Bitmap Heap Scan on foo  (cost=24.03..32.49 rows=4 width=68)
   Recheck Cond: (roles && '{1,2,11,14}'::integer[])
   ->  Bitmap Index Scan on foo_roles_idx  (cost=0.00..24.03 rows=4 width=0)
         Index Cond: (roles && '{1,2,11,14}'::integer[])
(4 rows)

这个查询计划对于 GIN 索引是否正确？

Answer 1

我在这里要说的第一件事是，您确实需要正确地封装它以使其工作。其次，这是一个很好的例子，打破 1NF 在性能方面可能是一件好事。

我会把它分成三部分，在这个过程中完全破坏 Codd 的规则，但我认为在某些情况下可以打破这些规则，在这里打破一个需要打破更多的部分以纠正损害。

第一部分是管理部分。在这部分，权限以您当前使用的形式存储。这用于以关系方式更新和管理权限。然后将使用存储过程为特定行编译这些。

第二块是存储块。正如您在第一个答案中所建议的，这里的行与角色一起存储在数组中。这里的数组使用 GIN 进行索引，这使得查找速度更快。

第三，您需要封装逻辑，例如仅检索用户有权访问的行的视图，或检查添加WHERE my_role_id = ANY(roles)到查询末尾的角色的存储过程接口。

要使此工作正常运行，您需要在更改权限时对其进行编译。但是，此结构允许您说“现在 Joe 可以访问 Bob 有权访问的所有行”。

 CREATE TABLE foo (
    id serial not null unique,
    ....
    roles int[]
 );
 CREATE TABLE foo_roles (
    foo_id int not null references foo(id),
    role_id int not null references roles(id)
 );

 CREATE OR REPLACE FUNCTION rebuild_foo_roles(in_foo_id int) RETURNS int[] 
 LANGUAGE SQL AS $$

     UPDATE foo SET roles = (select array_agg(role_id) from foo_roles 
                               where foo_id = $1)
      WHERE role_id = $1
     RETURNING roles;
  $$;

然后，您可以通过更改 foo_roles 中的数据来更新权限，然后rebuild_foo_roles使用要修改的行的 ID 进行调用。

现在关于这种结构的一件事是它使查找速度很快，但对权限的更新却很慢。

更新：关于 GIN 索引的说明（每个请求）。

传统的数据库索引是 B 树，这意味着您可以通过将期望值与索引的分支进行比较来进行搜索，然后遍历到叶子。如果搜索整个值（WHERE foo = 'my_fun_value'），这很有效，但不适用于更复杂的搜索。GIN 索引（通用索引方法）允许在更广泛的搜索中使用索引，但它们比 b 树索引稍慢。GIN 索引可用于提出以下问题：

• 值 x 在数组 y 中吗？（我们的用例在这里）

• 圆 A 与圆 B 重叠吗？

• 线段C是否与线段D交叉？

• 预约 A 是否与预约 B 在时间上重叠？

在较新版本的 PostgreSQL 中，您可以使用这些索引来强制执行约束，例如“任何给定房间中的约会都不会在时间上重叠”，但这里的主要用例是它使搜索数组更快。

一般来说，在连接上，GIN 索引会比 b 树或 GIST 索引提供更好的性能。在这种情况下，您的查询foo可以是针对不需要连接的关系的索引扫描。