Thread: Sort operation displays more tuples than it contains its subnode
Hi!
I faced the issue, when the sorting node in the actual information shows a larger number of tuples than it actually is. And I can not understand why?
I attached the dump file with my database and run this query that consists underestimation and it works fine.
Unfortunately, I could not find the approach how I can improve statistic information here, so I did it in the code.
I needed to better cardinality in IndexScan and MergeJoin nodes. I highlighted them in bold.
postgres=# set enable_hashjoin =off;
SET
postgres=# set enable_nestloop =off;
SET
explain analyze select cname, avg(degree) from course, student,score join broke_down_course on
(score.cno=broke_down_course.cno and score.sno=broke_down_course.sno) where score.sno = student.sno group by (cname);
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------------------------------
GroupAggregate (cost=10000001523.70..10000001588.95 rows=10 width=250) (actual time=262.903..322.973 rows=10 loops=1)
Group Key: course.cname
-> Sort (cost=10000001523.70..10000001545.41 rows=8684 width=222) (actual time=256.221..283.710 rows=77540 loops=1)
Sort Key: course.cname
Sort Method: external merge Disk: 4656kB
-> Nested Loop (cost=10000000614.18..10000000955.58 rows=8684 width=222) (actual time=7.518..160.518 rows=77540 loops=1)
-> Merge Join (cost=614.18..845.96 rows=868 width=4) (actual time=7.497..126.632 rows=7754 loops=1)
Merge Cond: ((score.sno = broke_down_course.sno) AND (score.cno = broke_down_course.cno))
-> Merge Join (cost=0.70..1297.78 rows=29155 width=16) (actual time=0.099..99.329 rows=29998 loops=1)
Merge Cond: (score.sno = student.sno)
-> Index Scan using score_idx1 on score (cost=0.42..10125.41 rows=29998 width=12) (actual time=0.045..74.427 rows=29998 loops=1)
-> Index Only Scan using student_pkey on student (cost=0.28..89.28 rows=3000 width=4) (actual time=0.045..2.170 rows=3000 loops=1)
Heap Fetches: 0
-> Sort (cost=613.48..632.86 rows=7754 width=8) (actual time=7.378..9.626 rows=7754 loops=1)
Sort Key: broke_down_course.sno, broke_down_course.cno
Sort Method: quicksort Memory: 374kB
-> Seq Scan on broke_down_course (cost=0.00..112.54 rows=7754 width=8) (actual time=0.028..1.428 rows=7754 loops=1)
-> Materialize (cost=0.00..1.15 rows=10 width=218) (actual time=0.000..0.001 rows=10 loops=7754)
-> Seq Scan on course (cost=0.00..1.10 rows=10 width=218) (actual time=0.012..0.017 rows=10 loops=1)
Planning Time: 124.591 ms
Execution Time: 326.547 ms
When I run this query again I see that the Sort node shows more actual data than it was in SeqScan (I highlighted it).
postgres=# explain analyze select cname, avg(degree) from course, student,score join broke_down_course on
(score.cno=broke_down_course.cno and score.sno=broke_down_course.sno) where score.sno = student.sno group by (cname);
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------------------------------------
GroupAggregate (cost=10000001746.28..10000001811.53 rows=10 width=250) (actual time=553.428..615.028 rows=10 loops=1)
Group Key: course.cname
-> Sort (cost=10000001746.28..10000001767.99 rows=8684 width=222) (actual time=546.531..574.223 rows=77540 loops=1)
Sort Key: course.cname
Sort Method: external merge Disk: 4656kB
-> Merge Join (cost=10000000614.18..10000001178.16 rows=8684 width=222) (actual time=7.892..448.889 rows=77540 loops=1)
Merge Cond: ((score.sno = broke_down_course.sno) AND (score.cno = broke_down_course.cno))
-> Merge Join (cost=10000000000.70..10000002146.57 rows=291550 width=234) (actual time=0.137..318.345 rows=299971 loops=1)
Merge Cond: (score.sno = student.sno)
-> Index Scan using score_idx1 on score (cost=0.42..10125.41 rows=29998 width=12) (actual time=0.046..76.505 rows=29998 loops=1)
-> Materialize (cost=10000000000.28..10000000540.41 rows=30000 width=222) (actual time=0.082..76.345 rows=299964 loops=1)
-> Nested Loop (cost=10000000000.28..10000000465.41 rows=30000 width=222) (actual time=0.077..16.543 rows=30000 loops=1)
-> Index Only Scan using student_pkey on student (cost=0.28..89.28 rows=3000 width=4) (actual time=0.045..2.774 rows=3000 loops=1)
Heap Fetches: 0
-> Materialize (cost=0.00..1.15 rows=10 width=218) (actual time=0.000..0.002 rows=10 loops=3000)
-> Seq Scan on course (cost=0.00..1.10 rows=10 width=218) (actual time=0.023..0.038 rows=10 loops=1)
-> Sort (cost=613.48..632.86 rows=7754 width=8) (actual time=7.612..21.214 rows=77531 loops=1)
Sort Key: broke_down_course.sno, broke_down_course.cno
Sort Method: quicksort Memory: 374kB
-> Seq Scan on broke_down_course (cost=0.00..112.54 rows=7754 width=8) (actual time=0.016..1.366 rows=7754 loops=1)
Planning Time: 96.685 ms
Execution Time: 618.538 ms
(22 rows)
Maybe, my reproduction looks questionable, sorry for that, but I seriously don't understand why we have so many tuples here in Sort node.
Attachment
On Thu, 23 May 2024 at 08:48, a.rybakina <a.rybakina@postgrespro.ru> wrote:
> -> Sort (cost=613.48..632.86 rows=7754 width=8) (actual time=7.612..21.214 rows=77531 loops=1)
> Sort Key: broke_down_course.sno, broke_down_course.cno
> Sort Method: quicksort Memory: 374kB
> -> Seq Scan on broke_down_course (cost=0.00..112.54 rows=7754 width=8) (actual
time=0.016..1.366rows=7754 loops=1)
> Maybe, my reproduction looks questionable, sorry for that, but I seriously don't understand why we have so many
tupleshere in Sort node.
This is because of the "mark and restore" that occurs because of the
Merge Join. This must happen for joins because every tuple matching
the join condition must join to every other tuple that matches the
join condition. That means, if you have 3 tuples with the same key on
either side, you get 9 rows, not 3 rows.
Here's a simple example of the behaviour you describe shrunk down so
that it's more easily understandable:
create table t(a int);
insert into t values(1),(1),(1);
set enable_hashjoin=0;
set enable_nestloop=0;
explain (analyze, costs off) select * from t inner join t t1 on t.a=t1.a;
QUERY PLAN
------------------------------------------------------------------------
Merge Join (actual time=0.036..0.038 rows=9 loops=1)
Merge Cond: (t.a = t1.a)
-> Sort (actual time=0.025..0.025 rows=3 loops=1)
Sort Key: t.a
Sort Method: quicksort Memory: 25kB
-> Seq Scan on t (actual time=0.017..0.018 rows=3 loops=1)
-> Sort (actual time=0.007..0.007 rows=7 loops=1)
Sort Key: t1.a
Sort Method: quicksort Memory: 25kB
-> Seq Scan on t t1 (actual time=0.003..0.003 rows=3 loops=1)
Note the sort has rows=7 and the Seq Scan on t1 rows=3 and an output of 9 rows.
If you look at the code in [1], you can see the restoreMark() calls to
achieve this.
David
[1] https://en.wikipedia.org/wiki/Sort-merge_join
"a.rybakina" <a.rybakina@postgrespro.ru> writes:
> I faced the issue, when the sorting node in the actual information
> shows a larger number of tuples than it actually is. And I can not
> understand why?
If I'm reading this correctly, the sort node you're worrying about
feeds the inner side of a merge join. Merge join will rewind its
inner side to the start of the current group of equal-keyed tuples
whenever it sees that the next outer tuple must also be joined to
that group. Since what EXPLAIN is counting is the number of tuples
returned from the node, that causes it to double-count those tuples.
The more duplicate-keyed tuples on the outer side, the bigger the
effect.
You can see the same thing happening at the Materialize a little
further up, which is feeding the inside of the other merge join.
regards, tom lane
Yes, I got it. Thank you very much for the explanation. On 23.05.2024 00:17, Tom Lane wrote: > "a.rybakina" <a.rybakina@postgrespro.ru> writes: >> I faced the issue, when the sorting node in the actual information >> shows a larger number of tuples than it actually is. And I can not >> understand why? > If I'm reading this correctly, the sort node you're worrying about > feeds the inner side of a merge join. Merge join will rewind its > inner side to the start of the current group of equal-keyed tuples > whenever it sees that the next outer tuple must also be joined to > that group. Since what EXPLAIN is counting is the number of tuples > returned from the node, that causes it to double-count those tuples. > The more duplicate-keyed tuples on the outer side, the bigger the > effect. > > You can see the same thing happening at the Materialize a little > further up, which is feeding the inside of the other merge join. -- Regards, Alena Rybakina Postgres Professional: http://www.postgrespro.com The Russian Postgres Company