pg.ddx.io pgsql-bugs@postgresql.org mailing list archive
help / color / mirror / Atom feedBUG #18365: Inconsistent cost function between materialized and non-materialized CTE
5+ messages / 3 participants
[nested] [flat]
* BUG #18365: Inconsistent cost function between materialized and non-materialized CTE
@ 2024-02-26 13:11 PG Bug reporting form <noreply@postgresql.org>
0 siblings, 2 replies; 5+ messages in thread
From: PG Bug reporting form @ 2024-02-26 13:11 UTC (permalink / raw)
To: pgsql-bugs@lists.postgresql.org; +Cc: postgresql@sjorsgielen.nl
The following bug has been logged on the website:
Bug reference: 18365
Logged by: Sjors Gielen
Email address: postgresql@sjorsgielen.nl
PostgreSQL version: 16.2
Operating system: Linux (native amd64 and Docker for Mac arm64)
Description:
Dear all,
I have run into an issue where a query with a CTE performs a sequential scan
on a large table (42M rows, ~1min on our prod), while explicitly
materializing the CTE simply performs an index only scan (~2s). When I set
`enable_seqscan=off` and compare the costs, it turns out the query planner
grossly overestimates the cost of a Nested Loop compared to the (as far as I
can tell) exact same Nested Loop when the CTE is materialized. I know that
the query planner acts on heuristics, so this might not be considered a bug,
but the cost values are so wildly different for what should be essentially
the same operation, that it might warrant further investigation.
I can reproduce the issue on PostgreSQL 15.2, 15.6, 16.2 and 17devel as of
20240223.1636.gd360e3c.
I have reported the issue, the schema, the query and the query plan outputs
at
<https://dba.stackexchange.com/questions/335570/why-is-postgresql-performing-a-sequential-scan-except...;.
Also, in order to facilitate reproduction, I have uploaded two reproduction
scripts and a 1 GB sample of my dataset which still reproduces the issue at
<https://sjorsgielen.nl/psql-bug-report.tar.gz;. `bring-up.sh` runs a given
version of the PostgreSQL Docker image listening on local port 15432.
`run-test.sh` creates the `testing` schema, creates the DDL, and imports the
data from data.sql.bz2. It should be easy to run `run-test.sh` against any
Postgres server by changing the DSN at the top of the script. The `testing`
schema is expected not to exist.
By running `./bring-up.sh 16.2 && ./run-test.sh`, some minutes later, you
should see the output of three `EXPLAIN (ANALYZE, BUFFERS, VERBOSE)`. I
would expect the cost of the Nested Loop in the first case (materialized
view), which is `2246..76657` (around 75k), to be more or less the same as
that of the Nested Loop in the third case (sequential scan disabled), which
is 230310..797581 (~570k). Because this cost is much higher, even surpassing
the Hash Join cost of ~290k, PostgreSQL decides to use a sequential scan in
the second case (non-materialized view) which ends up causing a slowdown of
~6.5 times.
Is this a bug?
Thank you,
Sjors Gielen
^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: BUG #18365: Inconsistent cost function between materialized and non-materialized CTE
@ 2024-05-31 20:29 Sjors Gielen <sjors@sjorsgielen.nl>
parent: PG Bug reporting form <noreply@postgresql.org>
1 sibling, 1 reply; 5+ messages in thread
From: Sjors Gielen @ 2024-05-31 20:29 UTC (permalink / raw)
To: pgsql-bugs@lists.postgresql.org
Dear all,
FYI - I have just tried the below on PostgreSQL 17-beta1 and the issue still occurs.
To be clear - this is not a regression. This appears to be a query planner bug (?) which reproduces in Postgres 15, 16 and now 17-beta1.
Best,
Sjors
> Op 26 feb 2024, om 14:11 heeft PG Bug reporting form <noreply@postgresql.org> het volgende geschreven:
>
> The following bug has been logged on the website:
>
> Bug reference: 18365
> Logged by: Sjors Gielen
> Email address:
> PostgreSQL version: 16.2
> Operating system: Linux (native amd64 and Docker for Mac arm64)
> Description:
>
> Dear all,
>
> I have run into an issue where a query with a CTE performs a sequential scan
> on a large table (42M rows, ~1min on our prod), while explicitly
> materializing the CTE simply performs an index only scan (~2s). When I set
> `enable_seqscan=off` and compare the costs, it turns out the query planner
> grossly overestimates the cost of a Nested Loop compared to the (as far as I
> can tell) exact same Nested Loop when the CTE is materialized. I know that
> the query planner acts on heuristics, so this might not be considered a bug,
> but the cost values are so wildly different for what should be essentially
> the same operation, that it might warrant further investigation.
>
> I can reproduce the issue on PostgreSQL 15.2, 15.6, 16.2 and 17devel as of
> 20240223.1636.gd360e3c.
>
> I have reported the issue, the schema, the query and the query plan outputs
> at
> <https://dba.stackexchange.com/questions/335570/why-is-postgresql-performing-a-sequential-scan-except...;.
> Also, in order to facilitate reproduction, I have uploaded two reproduction
> scripts and a 1 GB sample of my dataset which still reproduces the issue at
> <https://sjorsgielen.nl/psql-bug-report.tar.gz;. `bring-up.sh` runs a given
> version of the PostgreSQL Docker image listening on local port 15432.
> `run-test.sh` creates the `testing` schema, creates the DDL, and imports the
> data from data.sql.bz2. It should be easy to run `run-test.sh` against any
> Postgres server by changing the DSN at the top of the script. The `testing`
> schema is expected not to exist.
>
> By running `./bring-up.sh 16.2 && ./run-test.sh`, some minutes later, you
> should see the output of three `EXPLAIN (ANALYZE, BUFFERS, VERBOSE)`. I
> would expect the cost of the Nested Loop in the first case (materialized
> view), which is `2246..76657` (around 75k), to be more or less the same as
> that of the Nested Loop in the third case (sequential scan disabled), which
> is 230310..797581 (~570k). Because this cost is much higher, even surpassing
> the Hash Join cost of ~290k, PostgreSQL decides to use a sequential scan in
> the second case (non-materialized view) which ends up causing a slowdown of
> ~6.5 times.
>
> Is this a bug?
>
> Thank you,
> Sjors Gielen
>
^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: BUG #18365: Inconsistent cost function between materialized and non-materialized CTE
@ 2024-06-02 21:36 Sjors Gielen <sjors@sjorsgielen.nl>
parent: Sjors Gielen <sjors@sjorsgielen.nl>
0 siblings, 1 reply; 5+ messages in thread
From: Sjors Gielen @ 2024-06-02 21:36 UTC (permalink / raw)
To: pgsql-bugs@lists.postgresql.org
Dear all,
I am not sure I am using the correct list for this - please let me know if I
should move this to pgsql-hackers or pgsql-performance.
While investigating the below issue further, I found another potential issue
regarding CTE materialization, which is that uniqueness information does not
seem to be transported from the result of the CTE to the CTE Scan node. This is
not only causing unnecessary steps in the query plan, but also the cost for
such steps is dramatically under-estimated, so the incorrect query plan may be
used. I will illustrate with an example schema + query.
I am working with the following table, storing courses taken by a student and
their grade.
CREATE TABLE student_courses (
id BIGINT NOT NULL,
course_id BIGINT NOT NULL,
student_id BIGINT NOT NULL,
semester_id BIGINT NOT NULL,
grade BIGINT
);
ALTER TABLE student_courses
ADD CONSTRAINT pkey PRIMARY KEY (id),
ADD CONSTRAINT uq UNIQUE (semester_id, student_id, course_id);
CREATE INDEX idx on student_courses using btree (semester_id, student_id);
CREATE INDEX idx2 on student_courses using btree (student_id);
Now, the issue shows when we use a materialized query to make a selection of
values in the table, ensuring that this selection contains only unique rows;
then, using those rows to match back with the same table. In this example, we
want to have a list of all grades for all courses they took in their *last*
semester (assuming that semester IDs are in chronologic order). To speed up the
query a bit, we include a minimum semester ID.
EXPLAIN (ANALYZE, BUFFERS, VERBOSE)
WITH last_semester_per_student AS MATERIALIZED (
SELECT DISTINCT student_id, MAX(semester_id)
FROM student_courses
WHERE semester_id > 150
GROUP BY student_id
)
SELECT count(*)
FROM student_courses
WHERE (student_id, semester_id) IN (
SELECT student_id, semester_id
FROM last_semester_per_student
);
This is a shortened version of the query plan:
Aggregate (cost=3560.15..3560.16 rows=1 width=8) (actual time=42.937..42.943 rows=1 loops=1)
CTE last_semester_per_student
-> HashAggregate (cost=1921.54..2142.00 rows=22046 width=16) (actual time=9.945..11.067 rows=21826 loops=1)
Output: student_courses_1.student_id, (max(student_courses_1.semester_id))
Group Key: student_courses_1.student_id, max(student_courses_1.semester_id)
-> HashAggregate (cost=1590.85..1811.31 rows=22046 width=16) (actual time=6.165..7.504 rows=21826 loops=1)
Output: student_courses_1.student_id, max(student_courses_1.semester_id)
Group Key: student_courses_1.student_id
-> Index Only Scan using idx on public.student_courses student_courses_1 (cost=0.42..1393.87 rows=39397 width=16) (actual time=0.035..1.849 rows=39729 loops=1)
-> Nested Loop (cost=496.33..1218.96 rows=79678 width=0) (actual time=16.022..39.995 rows=121968 loops=1)
-> HashAggregate (cost=496.04..498.04 rows=200 width=8) (actual time=15.971..17.263 rows=21826 loops=1)
Output: last_semester_per_student.student_id
-> CTE Scan on last_semester_per_student (cost=0.00..440.92 rows=22046 width=8) (actual time=9.947..13.157 rows=21826 loops=1)
-> Index Only Scan using idx2 on public.student_courses (cost=0.29..3.54 rows=6 width=8) (actual time=0.001..0.001 rows=6 loops=21826)
As can be seen, the CTE is computed using an Index Only scan, then grouped with
a HashAggregate. After this, there could be duplicate rows (each having a
different course_id) so the outer HashAggregate ensures that the CTE output
contains only unique rows, to satisfy the DISTINCT.
Now the surprise is in the second half of the plan, within the Nested Loop. The
CTE is already known to return unique rows, and expected to return 22046 of
them. I believe that the HashAggregate around it is intended to make the rows
unique again. But, since the CTE rows were already known to be unique, I
believe this HashAggregate is unnecessary. In fact, you can see that the CTE
scan is expected to produce 22046 rows (quite close to the actual number of
21826), but the HashAggregate is actually expected to reduce this to 200 rows
(but in fact, it does not reduce it at all, and the query planner could know
this). This underestimation causes the cost of the Nested Loop to be much lower
than it should be, since most of the Nested Loop costs come from the number of
iterations in the outer loop. So this could cause the wrong plans to be chosen.
Should the correct plan not be simply this?
-> Nested Loop
-> CTE Scan on last_semester_per_student (cost=0.00..440.92 rows=22046 width=8) (actual time=9.947..13.157 rows=21826 loops=1)
-> Index Only Scan using idx2 on public.student_courses (cost=0.29..3.54 rows=6 width=8) (actual time=0.001..0.001 rows=6 loops=21826)
I am not certain, but it appears that the code generating this path might be in
pathnode.c create_unique_path, which already checks whether its child node
yields unique rows, but only supports relations or subqueries for this check,
not CTEs. Therefore, it falls back to a naive estimation which is off by a
factor of 100x.
Am I correct in thinking this code would be improved by supporting CTE
subqueries, as well, transporting the uniqueness information from the
CTE-producing node (in this case, the outer HashAggregate)?
Would a change of this nature be accepted upstream, if I were to put some time
and effort into it?
The exact schema, data and query are available at
https://sjorsgielen.nl/cte-uniqueness.tgz.
Thank you,
Sjors Gielen
> Op 31 mei 2024, om 22:29 heeft Sjors Gielen <sjors@sjorsgielen.nl> het volgende geschreven:
>
> Dear all,
>
> FYI - I have just tried the below on PostgreSQL 17-beta1 and the issue still occurs.
>
> To be clear - this is not a regression. This appears to be a query planner bug (?) which reproduces in Postgres 15, 16 and now 17-beta1.
>
> Best,
> Sjors
>
>> Op 26 feb 2024, om 14:11 heeft PG Bug reporting form <noreply@postgresql.org> het volgende geschreven:
>>
>> The following bug has been logged on the website:
>>
>> Bug reference: 18365
>> Logged by: Sjors Gielen
>> Email address:
>> PostgreSQL version: 16.2
>> Operating system: Linux (native amd64 and Docker for Mac arm64)
>> Description:
>>
>> Dear all,
>>
>> I have run into an issue where a query with a CTE performs a sequential scan
>> on a large table (42M rows, ~1min on our prod), while explicitly
>> materializing the CTE simply performs an index only scan (~2s). When I set
>> `enable_seqscan=off` and compare the costs, it turns out the query planner
>> grossly overestimates the cost of a Nested Loop compared to the (as far as I
>> can tell) exact same Nested Loop when the CTE is materialized. I know that
>> the query planner acts on heuristics, so this might not be considered a bug,
>> but the cost values are so wildly different for what should be essentially
>> the same operation, that it might warrant further investigation.
>>
>> I can reproduce the issue on PostgreSQL 15.2, 15.6, 16.2 and 17devel as of
>> 20240223.1636.gd360e3c.
>>
>> I have reported the issue, the schema, the query and the query plan outputs
>> at
>> <https://dba.stackexchange.com/questions/335570/why-is-postgresql-performing-a-sequential-scan-except...;.
>> Also, in order to facilitate reproduction, I have uploaded two reproduction
>> scripts and a 1 GB sample of my dataset which still reproduces the issue at
>> <https://sjorsgielen.nl/psql-bug-report.tar.gz;. `bring-up.sh` runs a given
>> version of the PostgreSQL Docker image listening on local port 15432.
>> `run-test.sh` creates the `testing` schema, creates the DDL, and imports the
>> data from data.sql.bz2. It should be easy to run `run-test.sh` against any
>> Postgres server by changing the DSN at the top of the script. The `testing`
>> schema is expected not to exist.
>>
>> By running `./bring-up.sh 16.2 && ./run-test.sh`, some minutes later, you
>> should see the output of three `EXPLAIN (ANALYZE, BUFFERS, VERBOSE)`. I
>> would expect the cost of the Nested Loop in the first case (materialized
>> view), which is `2246..76657` (around 75k), to be more or less the same as
>> that of the Nested Loop in the third case (sequential scan disabled), which
>> is 230310..797581 (~570k). Because this cost is much higher, even surpassing
>> the Hash Join cost of ~290k, PostgreSQL decides to use a sequential scan in
>> the second case (non-materialized view) which ends up causing a slowdown of
>> ~6.5 times.
>>
>> Is this a bug?
>>
>> Thank you,
>> Sjors Gielen
>>
>
^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: BUG #18365: Inconsistent cost function between materialized and non-materialized CTE
@ 2024-06-03 22:37 David Rowley <dgrowleyml@gmail.com>
parent: Sjors Gielen <sjors@sjorsgielen.nl>
0 siblings, 0 replies; 5+ messages in thread
From: David Rowley @ 2024-06-03 22:37 UTC (permalink / raw)
To: Sjors Gielen <sjors@sjorsgielen.nl>; +Cc: pgsql-bugs@lists.postgresql.org
On Tue, 4 Jun 2024 at 02:50, Sjors Gielen <sjors@sjorsgielen.nl> wrote:
> I am not sure I am using the correct list for this - please let me know if I
> should move this to pgsql-hackers or pgsql-performance.
This is the correct place to report bugs.
> Should the correct plan not be simply this?
>
> -> Nested Loop
> -> CTE Scan on last_semester_per_student (cost=0.00..440.92 rows=22046 width=8) (actual time=9.947..13.157 rows=21826 loops=1)
> -> Index Only Scan using idx2 on public.student_courses (cost=0.29..3.54 rows=6 width=8) (actual time=0.001..0.001 rows=6 loops=21826)
You're right that the query planner injected a uniquification step
into the plan unnecessarily. It did this to allow the semi-join to be
transformed into a join so it could swap the join order.
We won't class this issue as a bug as there is no code in PostgreSQL
that is malfunctioning. We simply don't have anything in place in the
current versions of PostgreSQL to detect which keys a Path is unique
on which the planner could use to skip performing the uniquification
step.
> I am not certain, but it appears that the code generating this path might be in
> pathnode.c create_unique_path, which already checks whether its child node
> yields unique rows, but only supports relations or subqueries for this check,
> not CTEs. Therefore, it falls back to a naive estimation which is off by a
> factor of 100x.
The row estimation part has been improved in the yet-to-be-released
PostgreSQL 17. The improvement won't be backpatched into earlier
versions.
> Am I correct in thinking this code would be improved by supporting CTE
> subqueries, as well, transporting the uniqueness information from the
> CTE-producing node (in this case, the outer HashAggregate)?
I'm unsure what you mean by the first part since CTEs already support
that. For the "transporting the uniqueness information" part, yes, if
the planner tracked that it could produce a plan that could be
executed more efficiently.
> Would a change of this nature be accepted upstream, if I were to put some time
> and effort into it?
There has been some effort in [1] to improve this. I've not had enough
spare time to look into how that's progressing. If you're keen to see
PostgreSQL produce better plans for this type of thing, you're very
welcome to catch up with what's been done so far and assess how you
can best assist with progressing this further. Showing interest on the
thread and testing the latest patch is likely a very good start.
David
[1] https://postgr.es/m/7mlamswjp81p.fsf@e18c07352.et15sqa
^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: BUG #18365: Inconsistent cost function between materialized and non-materialized CTE
@ 2024-06-03 23:07 David Rowley <dgrowleyml@gmail.com>
parent: PG Bug reporting form <noreply@postgresql.org>
1 sibling, 0 replies; 5+ messages in thread
From: David Rowley @ 2024-06-03 23:07 UTC (permalink / raw)
To: postgresql@sjorsgielen.nl; pgsql-bugs@lists.postgresql.org
On Tue, 27 Feb 2024 at 02:44, PG Bug reporting form
<noreply@postgresql.org> wrote:
> I have run into an issue where a query with a CTE performs a sequential scan
> on a large table (42M rows, ~1min on our prod), while explicitly
> materializing the CTE simply performs an index only scan (~2s). When I set
> `enable_seqscan=off` and compare the costs, it turns out the query planner
> grossly overestimates the cost of a Nested Loop compared to the (as far as I
> can tell) exact same Nested Loop when the CTE is materialized. I know that
> the query planner acts on heuristics, so this might not be considered a bug,
> but the cost values are so wildly different for what should be essentially
> the same operation, that it might warrant further investigation.
> Is this a bug?
I don't see any bugs. What seems to be going on is that the
materialized CTE underestimates the number of rows after making the
CTE distinct so the planner can use a join rather than a semi-join.
That's seen in:
-> HashAggregate (cost=2576.28..2679.33 rows=10305 width=16) (actual
time=765.793..893.761 rows=166060 loops=1)
Due to that row underestimation, the planner thinks a parameterized
nested loop is the best way to join the two relations as it thinks the
stock_history_date_product_id_idx index only needs to be looked up
10305 times rather than 166060 times. With the non-materialized
version, the planner estimates 103051. That causes it to think the
Nested Loop -> index scan on stock_history_date_product_id_idx is too
expensive and hash join with a seq scan is cheaper As it turns out,
looking up the index *is* faster, even when that's done 166060 times.
The two parameters that drive the planner's decision on this are
random_page_cost, (you might want to consider lowering that) and
effective_cache_size. A rough guideline for effective_cache_size is
75% of the machine's RAM. However, it much depends on your
shared_buffer setting and what type of other things run concurrently
on the machine. Some people have found lowering random_page_cost as
low as 1.1 helps. The default is 4.0, which has remained since the HDD
days. For SSDs, it's often too large.
I've attached the EXPLAINs I trimmed down and compared to reach this conclusion.
David
Attachments:
bug_18365_explain.txt (text/plain, 3.9K) download
EXPLAIN (ANALYZE, BUFFERS, VERBOSE)
WITH temp_stock_history AS (
SELECT MIN(date) AS date, product_id
FROM testing.stock_history SH_
WHERE SH_.date >= '2024-01-18 12:00+0100'
GROUP BY SH_.product_id
)
SELECT COUNT(id)
FROM testing.stock_history SH
WHERE (date, product_id) IN (
SELECT date, product_id
FROM temp_stock_history
);
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Finalize Aggregate (cost=624582.46..624582.47 rows=1 width=8) (actual time=55718.704..55718.867 rows=1 loops=1)
Output: count(sh.id)
Buffers: shared hit=4004 read=313651, temp read=138025 written=140224
-> Gather (cost=624582.24..624582.45 rows=2 width=8) (actual time=55718.678..55718.847 rows=3 loops=1)
-> Partial Aggregate (cost=623582.24..623582.25 rows=1 width=8) (actual time=55473.355..55473.366 rows=1 loops=3)
-> Hash Join (cost=38467.42..623580.84 rows=562 width=8) (actual time=40909.238..55464.326 rows=59341 loops=3)
-> Parallel Seq Scan on testing.stock_history sh (cost=0.00..491830.58 rows=17768158 width=24) (actual time=2.414..25400.057 rows=14215230 loops=3)
-> Hash (cost=36921.66..36921.66 rows=103051 width=16) (actual time=2972.388..2972.392 rows=166060 loops=3)
-> HashAggregate (cost=32040.93..35891.15 rows=103051 width=16) (actual time=2149.388..2720.948 rows=166060 loops=3)
-> Index Only Scan using stock_history_date_product_id_idx on testing.stock_history sh_ (cost=0.56..13543.65 rows=288738 width=16) (actual time=3.315..383.314 rows=315682 loops=3)
Execution Time: 55835.100 ms
(76 rows)
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Aggregate (cost=151878.19..151878.20 rows=1 width=8) (actual time=2257.709..2257.713 rows=1 loops=1)
Output: count(sh.id)
Buffers: shared hit=831576, temp read=770 written=2385
CTE temp_stock_history
-> HashAggregate (cost=32040.93..35891.15 rows=103051 width=16) (actual time=379.824..534.225 rows=166060 loops=1)
Group Key: sh_.product_id
-> Index Only Scan using stock_history_date_product_id_idx on testing.stock_history sh_ (cost=0.56..13543.65 rows=288738 width=16) (actual time=0.093..110.797 rows=315682 loops=1)
Index Cond: (sh_.date >= '2024-01-18 11:00:00+00'::timestamp with time zone)
-> Nested Loop (cost=2576.84..89334.80 rows=10660895 width=8) (actual time=765.940..2224.865 rows=178022 loops=1)
Buffers: shared hit=831576, temp read=770 written=2385
-> HashAggregate (cost=2576.28..2679.33 rows=10305 width=16) (actual time=765.793..893.761 rows=166060 loops=1)
Group Key: temp_stock_history.date, temp_stock_history.product_id
-> CTE Scan on temp_stock_history (cost=0.00..2061.02 rows=103051 width=16) (actual time=379.830..641.721 rows=166060 loops=1)
-> Index Scan using stock_history_date_product_id_idx on testing.stock_history sh (cost=0.56..8.40 rows=1 width=24) (actual time=0.007..0.007 rows=1 loops=166060)
Index Cond: ((sh.date = temp_stock_history.date) AND (sh.product_id = temp_stock_history.product_id))
Execution Time: 2269.782 ms
(38 rows)
end of thread, other threads:[~2024-06-03 23:07 UTC | newest]
Thread overview: 5+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2024-02-26 13:11 BUG #18365: Inconsistent cost function between materialized and non-materialized CTE PG Bug reporting form <noreply@postgresql.org>
2024-05-31 20:29 ` Sjors Gielen <sjors@sjorsgielen.nl>
2024-06-02 21:36 ` Sjors Gielen <sjors@sjorsgielen.nl>
2024-06-03 22:37 ` David Rowley <dgrowleyml@gmail.com>
2024-06-03 23:07 ` David Rowley <dgrowleyml@gmail.com>
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox