优化行排除查询
Optimizing a row exclusion query
我正在设计一个主要只读的数据库，其中包含 300,000 个文档和大约 50,000 个不同的标签，每个文档平均有 15 个标签。目前，我唯一关心的查询是从一组给定的标签中选择所有带有 no 标签的文档。我只对 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 和 tag_id 上都有 btree 索引，另一个在 (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 的服务器上。
使用外部连接，在连接上使用标签条件，只保留未连接到 return 的连接，其中指定标签的 none 匹配：
select d.id
from documents d
join documents_tags t on t.document_id = d.id
and t.tag_id in (12345, 7654)
where t.document_id is null
优化读取性能设置
您的内存设置对于 64GB 服务器来说似乎是合理的 - 除了可能 work_mem = 512MB。那太高了。您的查询不是特别复杂，您的 table 也不是那么大。
简单连接中的 450 万行 (300k x 15) table documents_tags 应该占用 ~ 156 MB，PK 另外 96 MB。对于您的查询，您通常不需要阅读整个 table，只需阅读索引的一小部分。对于 " 大部分只读 "，您应该看到 仅索引扫描 索引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 过高实际上可能会影响性能：
我建议将 work_mem 减少到 128 MB 或更少以避免可能的内存不足 - 除非您有其他需要更多内存的常见查询。对于特殊查询，您始终可以在本地将其设置得更高。
还有其他几个角度可以优化读取性能：
关键问题：前导索引列
所有这些可能会有所帮助。但关键问题是：
<strike>PRIMARY KEY (document_id, <b>tag_id</b>)</strike>
300k 文档，要排除 2 个标签。理想情况下，您有一个索引，其中 tag_id 作为 leading 列，document_id 作为第二列。仅在 (tag_id) 上使用索引，您无法进行仅索引扫描。如果此查询是您唯一的用例，请按如下所示更改您的 PK。
或者可能更好：如果您同时需要，您可以在 (tag_id, document_id) 上创建一个额外的普通索引 - 并将 documents_tags 上的其他两个索引仅放在 (tag_id) 和 [= 上27=]。他们没有提供超过两个多列索引的任何东西。其余的 2 索引（与之前的 3 索引相反）在各个方面都更小但更优越。理由：
同时，我建议也 CLUSTER table 使用新的 PK，全部在一个 t运行 动作中，可能还有一些额外的 maintenance_work_mem本地：
BEGIN;
SET LOCAL maintenance_work_mem = '256MB';
ALTER TABLE documents_tags
DROP CONSTRAINT documents_tags_pkey
, ADD PRIMARY KEY (<b>tag_id</b>, document_id); -- tag_id first.
CLUSTER documents_tags USING documents_tags_pkey;
COMMIT;
别忘了：
ANALYZE documents_tags;
查询
查询本身是 运行-of-the-mill。以下是 4 种标准技术：
- Select rows which are not present in other table
NOT IN 是——引用我自己的话：
Only good for small sets without NULL values
正是您的用例：所有涉及的列 NOT NULL 并且您排除的项目列表非常短。您的原始查询是热门竞争者。
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
<b>LEFT JOIN</b> 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;
请注意，由于我填充 table 的方式，documents_tags 中的行在物理上由 document_id 聚类 - 这也可能是您当前的情况。
测试
3 次测试 运行s，每次 4 个查询，每次 5 个中最好，以排除缓存影响。
测试 1： 与 documents_tags_pkey 一样。索引 和 行的物理顺序对我们的查询来说 不好 。
测试 2： 按照建议在 (tag_id, document_id) 上重新创建 PK。
测试3： CLUSTER新PK。
EXPLAIN ANALYZE 的执行时间，以毫秒为单位：
time in ms | Test 1 | Test 2 | Test 3
1. NOT IN | 654 | 70 | 71 -- winner!
2. NOT EXISTS | 684 | 103 | 97
3. LEFT JOIN | 685 | 98 | 99
4. EXCEPT ALL | 833 | 255 | 250
结论
关键元素是正确的 索引，前导 tag_id - 对于涉及 few 的查询 tag_id 和 很多 document_id.
准确地说，不重要的是 document_id 比 tag_id 多。这也可能反过来。 Btree 索引基本上对任何顺序的列执行相同的操作。事实上，您查询中最具选择性的谓词筛选 tag_id。这在前导索引列上更快。
少数 tag_id 排除的获胜查询是您使用 NOT IN.
[=182 的原始查询=]
NOT EXISTS 和 LEFT JOIN / IS NULL 产生相同的查询计划。对于几十个 ID，我希望它们能够更好地扩展......
在只读情况下，您会看到 仅索引扫描，因此物理顺序table 中的行数变得无关紧要。因此，测试 3 没有带来任何改进。
如果写入 table 并且 autovacuum 无法跟上，您将看到 （位图）索引扫描。物理集群对这些很重要。
我正在设计一个主要只读的数据库，其中包含 300,000 个文档和大约 50,000 个不同的标签，每个文档平均有 15 个标签。目前，我唯一关心的查询是从一组给定的标签中选择所有带有 no 标签的文档。我只对 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和tag_id上都有 btree 索引，另一个在(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 的服务器上。
使用外部连接，在连接上使用标签条件，只保留未连接到 return 的连接，其中指定标签的 none 匹配：
select d.id
from documents d
join documents_tags t on t.document_id = d.id
and t.tag_id in (12345, 7654)
where t.document_id is null
优化读取性能设置
您的内存设置对于 64GB 服务器来说似乎是合理的 - 除了可能 work_mem = 512MB。那太高了。您的查询不是特别复杂，您的 table 也不是那么大。
简单连接中的 450 万行 (300k x 15) table documents_tags 应该占用 ~ 156 MB，PK 另外 96 MB。对于您的查询，您通常不需要阅读整个 table，只需阅读索引的一小部分。对于 " 大部分只读 "，您应该看到 仅索引扫描 索引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 过高实际上可能会影响性能：
我建议将 work_mem 减少到 128 MB 或更少以避免可能的内存不足 - 除非您有其他需要更多内存的常见查询。对于特殊查询，您始终可以在本地将其设置得更高。
还有其他几个角度可以优化读取性能：
关键问题：前导索引列
所有这些可能会有所帮助。但关键问题是：
<strike>PRIMARY KEY (document_id, <b>tag_id</b>)</strike>
300k 文档，要排除 2 个标签。理想情况下，您有一个索引，其中 tag_id 作为 leading 列，document_id 作为第二列。仅在 (tag_id) 上使用索引，您无法进行仅索引扫描。如果此查询是您唯一的用例，请按如下所示更改您的 PK。
或者可能更好：如果您同时需要，您可以在 (tag_id, document_id) 上创建一个额外的普通索引 - 并将 documents_tags 上的其他两个索引仅放在 (tag_id) 和 [= 上27=]。他们没有提供超过两个多列索引的任何东西。其余的 2 索引（与之前的 3 索引相反）在各个方面都更小但更优越。理由：
同时，我建议也 CLUSTER table 使用新的 PK，全部在一个 t运行 动作中，可能还有一些额外的 maintenance_work_mem本地：
BEGIN;
SET LOCAL maintenance_work_mem = '256MB';
ALTER TABLE documents_tags
DROP CONSTRAINT documents_tags_pkey
, ADD PRIMARY KEY (<b>tag_id</b>, document_id); -- tag_id first.
CLUSTER documents_tags USING documents_tags_pkey;
COMMIT;
别忘了：
ANALYZE documents_tags;
查询
查询本身是 运行-of-the-mill。以下是 4 种标准技术：
- Select rows which are not present in other table
NOT IN 是——引用我自己的话：
Only good for small sets without NULL values
正是您的用例：所有涉及的列 NOT NULL 并且您排除的项目列表非常短。您的原始查询是热门竞争者。
NOT EXISTS 和 LEFT JOIN / IS NULL 总是热门的竞争者。两者都已在其他答案中提出。不过，LEFT JOIN 必须是实际的 LEFT [OUTER] JOIN。
EXCEPT ALL 最短，但通常没有那么快。
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)
);
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)
);
SELECT d.document_id
FROM documents d
<b>LEFT JOIN</b> documents_tags dt ON dt.document_id = d.document_id
AND dt.tag_id IN (12345, 7654)
WHERE dt.document_id IS NULL;
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;
请注意，由于我填充 table 的方式，documents_tags 中的行在物理上由 document_id 聚类 - 这也可能是您当前的情况。
测试
3 次测试 运行s，每次 4 个查询，每次 5 个中最好，以排除缓存影响。
测试 1： 与 documents_tags_pkey 一样。索引 和 行的物理顺序对我们的查询来说 不好 。
测试 2： 按照建议在 (tag_id, document_id) 上重新创建 PK。
测试3： CLUSTER新PK。
EXPLAIN ANALYZE 的执行时间，以毫秒为单位：
time in ms | Test 1 | Test 2 | Test 3 1. NOT IN | 654 | 70 | 71 -- winner! 2. NOT EXISTS | 684 | 103 | 97 3. LEFT JOIN | 685 | 98 | 99 4. EXCEPT ALL | 833 | 255 | 250
结论
关键元素是正确的 索引，前导
tag_id- 对于涉及 few 的查询tag_id和 很多document_id.
准确地说，不重要的是document_id比tag_id多。这也可能反过来。 Btree 索引基本上对任何顺序的列执行相同的操作。事实上，您查询中最具选择性的谓词筛选tag_id。这在前导索引列上更快。少数
[=182 的原始查询=]tag_id排除的获胜查询是您使用NOT IN.NOT EXISTS和LEFT JOIN / IS NULL产生相同的查询计划。对于几十个 ID，我希望它们能够更好地扩展......在只读情况下，您会看到 仅索引扫描，因此物理顺序table 中的行数变得无关紧要。因此，测试 3 没有带来任何改进。
如果写入 table 并且 autovacuum 无法跟上，您将看到 （位图）索引扫描。物理集群对这些很重要。