如何在PostgreSQL中高效地设置减法联接表？

Question

我有以下数据表：

• work_units - 自解释
• workers - 自解释
• skills - 每个工作单元需要一些技能才能在上面工作。每个工人都精通一些技能。
• work_units_skills - 连接表
• workers_skills - 连接表

一个工人可以请求分配给她下一个适当的空闲最高优先级（无论这意味着什么）的工作单元。

---

目前我有：

SELECT work_units.*
FROM work_units
-- some joins
WHERE NOT EXISTS (
        SELECT skill_id
        FROM work_units_skills
        WHERE work_unit_id = work_units.id

        EXCEPT

        SELECT skill_id
        FROM workers_skills
        WHERE worker_id = 1 -- the worker id that made the request
      )
-- AND a bunch of other conditions
-- ORDER BY something complex
LIMIT 1
FOR UPDATE SKIP LOCKED;

这个条件会使查询变慢8-10倍。

有没有更好的方法来表达一个work_units的技能应该是workers的技能的子集或者改进当前的查询？

---

更多的背景信息：

• skills表比较小。
• work_units和workers都倾向于有非常少的相关技能。
• work_units_skills在work_unit_id上有索引。
• 我尝试将查询workers_skills移到了公共表达式中。这稍微提高了一点速度（10-15%），但仍然太慢了。
• 没有技能的工作单元可以被任何用户选择。也就是说，空集是每个集合的子集。

- ndnenkov

---

我认为魔鬼可能隐藏在注释中缺失的细节中（例如 ORDER BY something complex bunch of conditions 等）。因此，如果您能发布 EXPLAIN，那可能会有所帮助。 - Kaushik Nayak

@KaushikNayak，我尝试删除单个条件并使用更简单的排序方式。即使这样，查询仍然非常慢。因此，它不是这个条件和其他条件的组合。可能是这个条件和另外两个或更多条件，但这不太可能。不幸的是，由于项目是私有的，我无法发布“EXPLAIN”，但如果您有任何想法，我可以回答您的问题。 - ndnenkov

请**[编辑]您的问题，并添加使用explain (analyze, verbose, buffers)**生成的执行计划。请使用格式化文本，不要使用屏幕截图（http://meta.stackoverflow.com/questions/285551/why-may-i-not-upload-images-of-code-on-so- when-asking-a-question / 285557＃285557）。如果您不想（或无法）共享表名，请将其上传到http://explain.depesz.com并启用模糊化计划选项（尽管执行计划很少会显示任何机密信息）。 - user330315

2个问题？1. 我可以在您的数据库设计中提供一些更改吗？例如添加1或2个额外字段。2. 您使用哪种DBMS？ - Gholamali Irani

@g.Irani，对于前者-您可以。实际上，我考虑了两种带有额外列的解决方案-一种涉及位掩码，另一种涉及哈希。两者都显著提高了速度（在转储基准测试中提高了约60％），但仍然似乎不够快。对于后者-根据标签-使用Postgres。 - ndnenkov

Answer 1

一个简单的加速方法是使用EXCEPT ALL而不是EXCEPT。后者删除重复项，在这里是不必要且可能会很慢的。

另一个可能更快的选择是使用进一步的NOT EXISTS替代EXCEPT：

...
WHERE NOT EXISTS (
        SELECT skill_id
        FROM work_units_skills wus
        WHERE work_unit_id = work_units.id
        AND NOT EXISTS (
            SELECT skill_id
            FROM workers_skills ws
            WHERE worker_id = 1 -- the worker id that made the request
              AND ws.skill_id = wus.skill_id
        )
      )

演示

http://rextester.com/AGEIS52439 - 为了测试而删除了LIMIT

- Steve Chambers

---

不错。简单明了的更改导致了约50%的提升。尽管如此，我仍将尝试其他解决方案，因为这还不够快。可能我会与其他东西结合使用它。 - ndnenkov

Answer 2

(请见下面的更新)

该查询使用简单的 LEFT JOIN 查找缺少的技能以找到一个好的work_unit。当出现缺失技能时，连接将产生 NULL 值，这被转换为 1 ，并通过保留所有0值（即具有max为0）的选项来删除work_unit。

由于这是经典的 SQL 查询，因此它将成为引擎最重要的优化目标:

SELECT work_unit_id
FROM
  work_units_skills s
LEFT JOIN
  (SELECT skill_id FROM workers_skills WHERE worker_id = 1) t
ON (s.skill_id=t.skill_id)
GROUP BY work_unit_id
HAVING max(CASE WHEN t.skill_id IS NULL THEN 1 ELSE 0 END)=0
-- AND a bunch of other conditions
-- ORDER BY something complex
LIMIT 1
FOR UPDATE SKIP LOCKED;

更新

为了捕捉没有技能的work_units，我们将work_units表加入到JOIN中：

SELECT r.id AS work_unit_id
FROM
  work_units r
LEFT JOIN
  work_units_skills s ON (r.id=s.work_unit_id)
LEFT JOIN
  (SELECT skill_id FROM workers_skills WHERE worker_id = 1) t
ON (s.skill_id=t.skill_id)
GROUP BY r.id
HAVING bool_or(s.skill_id IS NULL) OR bool_and(t.skill_id IS NOT NULL)
-- AND a bunch of other conditions
-- ORDER BY something complex
LIMIT 1
FOR UPDATE SKIP LOCKED;

- Dan Getz

---

COUNT(t.skill_id) = COUNT(s.skil_id) 的结果也是相同的逻辑。正如 @RadimBača 所注意到的，这需要稍微修改以允许将没有技能的工作单元视为有效（基于空集是每个其他集合的子集的前提）。 - MatBailie

不错。这个查询比我的原始查询快6-8倍，速度在可接受范围内。但是，它排除了没有任何技能的工作单元。我想不出一种方法来包括它们，而不需要使用“OR”，否则速度会变得更慢（只比原始查询快2倍）。如果您能想到一种方法来包括没有技能的文档，并保持接近当前性能，那就可以了。 - ndnenkov

除了HAVING子句外，这与我下面答案中的子查询相同（功能上它们是相同的，只是计算缺失技能的不同代数）。通过首先加入工作单元表，可以使其适用于没有技能的工作单元；请参见我的答案中的第三个查询。 - MatBailie

尝试将子查询连接到文档表，而不是使用IN()，这样可以提高性能。 （另外，文档表从何而来？这是你第一次提到它;)） - MatBailie

@ndn *[我已经用一个查询更新了答案，它可以捕获未经过技能培训的工作单元]*。查询错过没有技能的工作单位的原因可能是这些单位在work_units_skills表中没有出现。要解决这个问题，在创建work_units_skills表时要使用LEFT JOIN。这将为每个工作单元留下一行，如果没有技能，则该行将在skill_id中具有NULL值。另外一个解决方法是将work_units表添加到JOIN查询中，而不是使用OR或UNION。但是扩展work_units_skills表似乎是更好的选择。 - Dan Getz

Answer 3

您可以使用以下查询：

SELECT wu.*
FROM work_units wu
LEFT JOIN work_units_skills wus ON wus.work_unit_id = wu.id and wus.skill_id IN (
    SELECT id
    FROM skills
    EXCEPT
    SELECT skill_id
    FROM workers_skills
    WHERE worker_id = 1 -- the worker id that made the request
)
WHERE wus.work_unit_id IS NULL;  

演示版（感谢Steve Chambers提供大部分数据）

您一定要在work_units_skills(skill_id)、workers_skills(worker_id)和work_units(id)上建立索引。 如果您想进一步加快速度，请创建索引work_units_skills(skill_id, work_unit_id)和workers_skills(worker_id, skill_id)，以避免访问这些表。

子查询是独立的，如果结果不大，则外连接应该相对较快。

- Radim Bača

Answer 4

位运算解决方案
在不改变之前的数据库设计的情况下，只需添加2个字段。
第一个：长整型或大整数（与您的DBMS相关）到Workers中
第二个：另一个长整型或大整数到Work_Units中

这些字段显示了工作单元的技能和工人的技能。例如，假设您在Skills表中有8条记录。 （注意，技能记录很小）
1-一些技能1
2-一些技能2
...
8-一些技能8

那么，如果我们想要将技能1、3、6、7设置为一个work_unit，则只需使用数字01100101。
（我建议使用反转的二进制0、1布局版本以支持将来的其他技能。）

在实际操作中，您可以使用10进制数字添加到数据库中（101代替01100101）

类似的数字也可以生成给工人。任何工人都会选择一些技能。因此，我们可以将所选项目转换为数字，并将其保存在Worker表中的附加字段中。

最后，为了找到任何工人的适当的工作单元子集，只需从work_units中选择并像下面这样使用位运算AND。
A：正在查找与他/她相关的工作单元的特定工人的new_field_of_specific_worker（显示每个工人的技能）。
B：显示每个work_unit技能的new_field_of_work_units

select * from work_units
where A & B  = B

提示：
1：绝对地说，这是最快的方法，但它也有一些困难。
2：当添加或删除新技能时，我们会遇到一些额外的困难。但这是一个权衡。添加或删除新技能的情况较少。
3：我们应该使用skills、work_unit_skills和workers_skills。但在搜索时，我们只使用新的字段。

此外，这种方法也可以用于像Stack Overflow TAGs这样的标签管理系统。

- Gholamali Irani

Answer 5

使用Postgres，关系除法通常可以使用数组更有效地表达。

在您的情况下，我认为以下内容可以满足您的要求：

select *
from work_units
where id in (select work_unit_id
             from work_units_skills
             group by work_unit_id
             having array_agg(skill_id) <@ array(select skill_id 
                                                 from workers_skills 
                                                 where worker_id = 6))
and ... other conditions here ...
order by ...

array_agg(skill_id)收集每个工作单位的所有技能ID，并使用<@运算符（“包含于”）与特定工人的技能进行比较。该条件返回所有技能列表包含在单个工人技能中的工作单位ID。

根据我的经验，这种方法通常比等效的exists或intersect解决方案更快。

在线示例：http://rextester.com/WUPA82849

- user330315

Answer 6

相关子查询对你来说很麻烦，特别是在使用EXCEPT时。

换句话说，你只对指定的工人拥有所有工作单元技能的work_unit_id感兴趣吗？ （如果一个工作单元有一个与之关联的技能，但指定的用户没有这个技能，则排除该工作单元？）

这可以通过JOIN和GROUP BY实现，完全不需要相关性。

SELECT
    work_units.*
FROM
    work_units
--
-- some joins
--
INNER JOIN
(
    SELECT
        wus.work_unit_id
    FROM
        work_unit_skills   wus
    LEFT JOIN
        workers_skills     ws
            ON  ws.skill_id  = wus.skill_id
            AND ws.worker_id = 1
    GROUP BY
        wus.work_unit_id
    HAVING
        COUNT(wus.skill_id) = COUNT(ws.skill_id)
)
     applicable_work_units
         ON  applicable_work_units.work_unit_id = work_units.id
-- AND a bunch of other conditions
-- ORDER BY something complex
LIMIT 1

子查询比较工人的技能集与每个工作单元的技能集。如果工作单元具有而工人没有的任何技能，则该行的ws.skill_id将为NULL，由于NULL被COUNT()忽略，这意味着COUNT(ws.skill_id)将小于COUNT(wus.skill_id)，因此该work_unit将从子查询的结果中排除。

假设workers_skills表在(work_id, skill_id)上是唯一的，而work_unit_skills表在(work_unit_id, skill_id)上是唯一的。如果不是这种情况，则可能需要调整HAVING子句（例如：COUNT(DISTINT wus.skill_id)等）。

编辑：以上查询假定只有相对较少数量的工作单元与某个特定工人匹配。如果假设相对较大数量的工作单元符合条件，则相反的逻辑更快。（本质上，尝试使子查询返回的行数尽可能少。）

SELECT
    work_units.*
FROM
    work_units
--
-- some joins
--
LEFT JOIN
(
    SELECT
        wus.work_unit_id
    FROM
        work_unit_skills   wus
    LEFT JOIN
        workers_skills     ws
            ON  ws.skill_id  = wus.skill_id
            AND ws.worker_id = 1
    WHERE
        ws.skill_id IS NULL
    GROUP BY
        wus.work_unit_id
)
     excluded_work_units
         ON  excluded_work_units.work_unit_id = work_units.id
WHERE
    excluded_work_units.work_unit_id IS NULL
-- AND a bunch of other conditions
-- ORDER BY something complex
LIMIT 1

这个查询会将所有工作单位所具有的技能与员工的技能进行比较，只保留工作单位拥有但员工没有的技能所在的行。

接着，使用GROUP BY关键字按照工作单位分组，得到需要被排除的工作单位列表。

通过左连接这个列表到现有的结果中，可以指定仅在子查询中未出现该工作单位时才包含它，即通过指定excluded_work_units.work_unit_id IS NULL来实现。

有用的在线指南将提到anti-join和anti-semi-join。

编辑：

一般而言，我不建议使用位掩码。

不是因为它慢，而是因为它违背了规范化。单个字段表示多个数据项是一种常见的SQL代码异味/反模式，因为数据不再是原子性的。（这会导致未来出现问题，特别是当您拥有的技能过多时，它们无法全部适应位掩码所选择的数据类型，或者在管理技能集合的频繁或复杂更改时。）

话虽如此，如果性能仍然是个问题，去规范化往往是一个非常有用的选项。我建议将位掩码存储在单独的表中，以便清楚地表示它们是去规范化/缓存计算结果。然而，一般来说，这样的选择应该是最后的手段，而不是首选反应。

编辑：示例修订，始终包括没有技能的工作单位...

SELECT
    work_units.*
FROM
    work_units
--
-- some joins
--
INNER JOIN
(
    SELECT
        w.id   AS work_unit_id
    FROM
        work_units          w
    LEFT JOIN
        work_units_skills   wus
            ON wus.work_unit_id = w.id
    LEFT JOIN
        workers_skills      ws
            ON  ws.skill_id  = wus.skill_id
            AND ws.worker_id = 1
    GROUP BY
        w.id
    HAVING
        COUNT(wus.skill_id) = COUNT(ws.skill_id)
)
     applicable_work_units
         ON  applicable_work_units.work_unit_id = work_units.id

excluded_work_units版本的代码（上面第二个示例查询）应该可以在不需要修改的情况下处理这种特殊情况（并且是我最初用于实时性能指标试验的版本）。

- MatBailie

---

我认为你错过了没有分配技能的work_units：http://dbfiddle.uk/?rdbms=postgres_10&fiddle=b3a1efb1368b2fcaf2aea3bf1567e394 - Radim Bača

已经进行了修改，但在哪里能看到“他”的查询返回了这些结果呢？ - MatBailie

位掩码违反了规范化，导致 SQL 代码味道难闻/SQL 反模式。这是事实。但当我们的数据很大时，我们可以使用一些非常规策略来达到所需的性能。所有大数据技术都违反了规范化。我们应该通过编程来控制这种非规范化，而不仅仅是通过数据库概念和特性。 - Gholamali Irani

我很想知道是谁投了反对票以及为什么。但是在我多年的 Stack Overflow 经历中，我担心看到恶意投票变得越来越普遍。 - MatBailie

@g.irani 要小心类别性语句，比如“所有大数据技术都无法标准化”。这种说法简直不符合事实。例如，QlikView 使用高度规范化的数据湖模型以最小化内存占用。 - MatBailie

Answer 7

你可以获取一个工人所掌握的工作单元，如前所示，这是一个聚合操作。然后你通常会在这个工作单元集合上使用IN。

SELECT wu.*
FROM work_units wu
-- some joins
WHERE wu.id IN
(
  SELECT wus.work_unit_id
  FROM work_units_skills wus
  LEFT JOIN workers_skills ws ON ws.skill_id = wus.skill_id AND ws.worker_id = 1
  GROUP BY wus.work_unit_id
  HAVING COUNT(*) = COUNT(ws.skill_id)
)
-- AND a bunch of other conditions
-- ORDER BY something complex
LIMIT 1
FOR UPDATE SKIP LOCKED;

当涉及加速查询时，通常最重要的部分是提供适当的索引。（使用完美的优化器，重新编写查询以获得相同结果将没有任何效果，因为优化器将获得相同的执行计划。）

您需要以下索引（列的顺序很重要）：

create index idx_ws on workers_skills (worker_id, skill_id);
create index idx_wus on work_units_skills (skill_id, work_unit_id);

我们需要提供worker_id，然后获取该工人所需的skill_ids，根据这些skill_ids连接工作单位并获取work_unit_ids。

- Thorsten Kettner

---

根据其他类似的答案，这需要进行一些微调以适应没有与之关联技能的工作单元。基本上，这与我在第一个建议中使用的前提相同，@DanGetz也是如此。 - MatBailie

我还建议将第二个索引反转。目前，技能可以被最优地连接，但需要进行排序以进行聚合。当反转为 work_unit_id, skill_id 时，数据已经在聚合之前排序，并且右侧的表已经被缩减为一个工人，因此非常小，易于保留在内存中。 - MatBailie

Answer 8

也许不适用于你，但我曾遇到类似问题，并通过将主列和子列合并为同一列，使用数字表示主列，使用字母表示子列解决了该问题。

顺便问一下，连接所涉及的所有列都有索引吗？ 如果我忘记索引，我的服务器从对500k+表的2-3秒查询崩溃到对10k表的崩溃

- Batman

Answer 9

根据目前的信息，我只能凭直觉回答。尝试删除EXCEPT语句并查看是否会显著加快速度。如果确实如此，您可以再次添加该部分，但使用WHERE条件。 在我的经验中，集合运算符(MINUS/EXCEPT、UNION、INTERSECT)会极大地影响性能。

- Thomas