sql - 优化行排除查询

Question

我正在设计一个主要是只读的数据库，其中包含 300,000 个文档和大约 50,000 个不同的标签，每个文档平均有 15 个标签。目前，我关心的唯一查询是从给定的一组标签中选择所有没有标签的文档。我只对document_id感兴趣列(结果中没有其他列)。

我的架构本质上是:

CREATE TABLE documents (
    document_id  SERIAL  PRIMARY KEY,
    title        TEXT
);

CREATE TABLE tags (
    tag_id  SERIAL  PRIMARY KEY,
    name    TEXT    UNIQUE
);

CREATE TABLE documents_tags (
    document_id    INTEGER  REFERENCES documents,
    tag_id         INTEGER  REFERENCES tags,

    PRIMARY KEY (document_id, tag_id)
);

我可以通过预先计算给定标签的文档集来用 Python 编写这个查询，这将问题减少到几个快速的集合操作:

In [17]: %timeit all_docs - (tags_to_docs[12345] | tags_to_docs[7654])
100 loops, best of 3: 13.7 ms per loop

然而，将集合操作转换为 Postgres 并没有那么快:

stuff=# SELECT document_id AS id FROM documents WHERE document_id NOT IN (
stuff(#     SELECT documents_tags.document_id AS id FROM documents_tags
stuff(#     WHERE documents_tags.tag_id IN (12345, 7654)
stuff(# );
   document_id
---------------
    ...
Time: 201.476 ms

更换 NOT IN与 EXCEPT使它更慢。

我在 document_id 上有 btree 索引和 tag_id在所有三个表中，另一个位于 (document_id, tag_id) .

Postgres 进程的默认内存限制已显着增加，因此我不认为 Postgres 配置错误。

如何加快此查询？有没有办法像我用 Python 那样预先计算之间的映射，或者我是否以错误的方式思考这个问题？

这是 EXPLAIN ANALYZE 的结果:

EXPLAIN ANALYZE
SELECT document_id AS id FROM documents
WHERE document_id NOT IN (
    SELECT documents_tags.documents_id AS id FROM documents_tags
    WHERE documents_tags.tag_id IN (12345, 7654)
);
                                                                            QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Seq Scan on documents  (cost=20280.27..38267.57 rows=83212 width=4) (actual time=176.760..300.214 rows=20036 loops=1)
   Filter: (NOT (hashed SubPlan 1))
   Rows Removed by Filter: 146388
   SubPlan 1
     ->  Bitmap Heap Scan on documents_tags  (cost=5344.61..19661.00 rows=247711 width=4) (actual time=32.964..89.514 rows=235093 loops=1)
           Recheck Cond: (tag_id = ANY ('{12345,7654}'::integer[]))
           Heap Blocks: exact=3300
           ->  Bitmap Index Scan on documents_tags__tag_id_index  (cost=0.00..5282.68 rows=247711 width=0) (actual time=32.320..32.320 rows=243230 loops=1)
                 Index Cond: (tag_id = ANY ('{12345,7654}'::integer[]))
 Planning time: 0.117 ms
 Execution time: 303.289 ms
(11 rows)

Time: 303.790 ms

我从默认配置更改的唯一设置是:

shared_buffers = 5GB
temp_buffers = 128MB
work_mem = 512MB
effective_cache_size = 16GB

运行 Postgres 9.4.5 在具有 64GB RAM 的服务器上。

Answer 1

优化设置以提高读取性能

您的内存设置对于 64GB 服务器来说似乎合理 - 除了 work_mem = 512MB .那是高。您的查询不是特别复杂，您的表也不是那么大。

简单连接表中的 450 万行 (300k x 15) documents_tags应该占用 ~ 156 MB 和 PK 另一个 96 MB。对于您的查询，您通常不需要读取整个表，只需读取索引的一小部分。对于“ 大部分是只读的 ”，就像您一样，您应该看到 仅索引扫描 仅在 PK 的索引上。您几乎不需要那么多 work_mem - 这可能无关紧要 - 除非您有许多并发查询。 Quoting the manual :

... several running sessions could be doing such operations concurrently. Therefore, the total memory used could be many times the value of work_mem; it is necessary to keep this fact in mind when choosing the value.

设置 work_mem太高实际上可能会损害性能:

Increasing work_mem and shared_buffers on Postgres 9.2 significantly slows down queries

我建议减少 work_mem到 128 MB 或更少以避免可能的内存不足 - 除非您有其他需要更多的常见查询。对于特殊查询，您始终可以在本地将其设置得更高。

还有其他几个角度可以优化读取性能:

Configuring PostgreSQL for read performance

关键问题:前导索引列

所有这些可能会有所帮助。但关键问题是:

   
    PRIMARY KEY (document_id, 
    tag_id)
   

30 万个文档，要排除 2 个标签。理想情况下，您的索引为 tag_id如 领先 列和 document_id作为第二。只有 (tag_id) 上的索引您无法获得仅索引扫描。如果此查询是您唯一的用例，请按如下所示更改您的 PK。

或者甚至更好:您可以在 (tag_id, document_id) 上创建一个额外的普通索引如果您同时需要 - 并删除 documents_tags 上的其他两个索引就在 (tag_id)和 (document_id) .它们对两个多列索引没有任何提供。剩余 2 索引(与之前的 3 索引相反)在各方面都更小且更优越。理由:

Is a composite index also good for queries on the first field?

Working of indexes in PostgreSQL

同时，我建议也 CLUSTER使用新 PK 的表，全部在一个事务中，可能还有一些额外的 maintenance_work_mem本地:

BEGIN;
SET LOCAL maintenance_work_mem = '256MB';

ALTER TABLE documents_tags 
  DROP CONSTRAINT documents_tags_pkey
, ADD  PRIMARY KEY (tag_id, document_id);  -- tag_id first.

CLUSTER documents_tags USING documents_tags_pkey;

COMMIT;

不要忘记:

ANALYZE documents_tags;

查询

查询本身是普通的。以下是 4 种标准技术:

Select rows which are not present in other table

NOT IN是 - 引用我自己的话:

Only good for small sets without NULL values

您的用例正是:所有涉及的列 NOT NULL并且您的排除项目 list 很短。您的原始查询是一个热门竞争者。
NOT EXISTS和 LEFT JOIN / IS NULL总是热门的竞争者。两者都已在其他答案中提出。 LEFT JOIN必须是实际的 LEFT [OUTER] JOIN ， 尽管。
EXCEPT ALL将是最短的，但通常没有那么快。

1. 不在

SELECT document_id
FROM   documents d
WHERE  document_id NOT IN (
   SELECT document_id  -- no need for column alias, only value is relevant
   FROM   documents_tags
   WHERE  tag_id IN (12345, 7654)
   );

2. 不存在

SELECT document_id
FROM   documents d
WHERE  NOT EXISTS (
   SELECT 1
   FROM   documents_tags
   WHERE  document_id = d.document_id
   AND    tag_id IN (12345, 7654)
   );

3. 左连接/为空

SELECT d.document_id
FROM   documents d
LEFT JOIN documents_tags dt ON dt.document_id = d.document_id
                             AND dt.tag_id IN (12345, 7654)
WHERE  dt.document_id IS NULL;

4. 除了所有

SELECT document_id
FROM   documents
EXCEPT ALL               -- ALL, to keep duplicate rows and make it faster
SELECT document_id
FROM   documents_tags
WHERE  tag_id IN (12345, 7654);

基准

我在带有 4 GB RAM 和 Postgres 9.5.3 的旧笔记本电脑上运行了一个快速基准测试，以测试我的理论:

测试设置

SET random_page_cost = 1.1;
SET work_mem = '128MB';

CREATE SCHEMA temp;
SET search_path = temp, public;

CREATE TABLE documents (
    document_id serial PRIMARY KEY,
    title       text
);

-- CREATE TABLE tags ( ...  -- actually irrelevant for this query    

CREATE TABLE documents_tags (
    document_id    integer  REFERENCES documents,
    tag_id         integer  -- REFERENCES tags  -- irrelevant for test
    -- no PK yet, to test seq scan
    -- it's also faster to create the PK after filling the big table
);

INSERT INTO documents (title)
SELECT 'some dummy title ' || g
FROM   generate_series(1, 300000) g;

INSERT INTO documents_tags(document_id, tag_id)
SELECT i.*
FROM   documents d
CROSS  JOIN LATERAL (
   SELECT DISTINCT d.document_id, ceil(random() * 50000)::int
   FROM   generate_series (1,15)) i;

ALTER TABLE documents_tags ADD PRIMARY KEY (document_id, tag_id);  -- your current index

ANALYZE documents_tags;
ANALYZE documents;

请注意 documents_tags 中的行物理集群由 document_id由于我填表的方式 - 这也可能是你目前的情况。

测试

对 4 个查询中的每一个运行 3 个测试，每次最好 5 个以排除缓存影响。

测试 1:与 documents_tags_pkey就像你拥有它一样。行的索引和物理顺序对我们的查询不利。
测试 2:在 (tag_id, document_id) 上重新创建 PK喜欢建议。
测试 3: CLUSTER在新PK上。 EXPLAIN ANALYZE的执行时间毫秒:

时间以毫秒为单位 |测试 1 |测试 2 |测试 3
1. 不在 |第654话70 | 71——胜利者!
2. 不存在 |第684话103 | 97
3. 左加入 |第685话98 | 99
4. 除了所有 |第833话第255话250

结论

关键元素是对的指数领先 tag_id - 对于涉及少数 tag_id 的查询和许多 document_id .
准确的说是不是 重要的是有更多不同的document_id比tag_id .这也可能是相反的。 Btree 索引对于任何列顺序都基本相同。事实上，查询中最具选择性的谓词过滤了 tag_id .这在领先的索引列上更快。

少数中奖查询tag_id排除是您原来的 NOT IN .

NOT EXISTS和 LEFT JOIN / IS NULL导致相同的查询计划。对于几十个 ID，我希望它们能够更好地扩展...

在只读情况下，您会看到 仅索引扫描 排他性，因此表中行的物理顺序变得无关紧要。因此，测试 3 没有带来更多的改进。

如果写入表发生并且 autovacuum 跟不上，你会看到 (位图)索引扫描 .物理集群对那些很重要。