pg.ddx.io  pgsql-performance@postgresql.org mailing list archive  
help / color / mirror / Atom feed
From: tarcizioab@c3sl.ufpr.br
To: pgsql-performance@postgresql.org
Subject: "Mysterious" - Dynamic Programming X GEQO
Date: Tue, 21 Oct 2008 12:40:19 -0300 (BRT)
Message-ID: <55663.200.17.202.126.1224603619.squirrel@webmail.inf.ufpr.br> (raw)

Hi!!!

I'm evaluating the performance of algorithms for optimization of queries.
I am comparing results between the algorithm of Dynamic Programming and
GEQO algorithm.

I use the base and queries provided by the benchmark OSDL DBT3 with scale
factor = 1. The queries were submitted randomly, I did the cleaning of
memory cache between tests (drop_caches) and restarting the database
postgres.

Stay surprise with the running time of the querie 11 of DBT3. These
results are an average of the "Total Runtime" after 20 executions:

Dynamic Programming Total runtime: 83.122,003 ms
Run-time optimizer algorithm  (Dynamic Programming): 0,453 ms

GEQO Total runtime: 18.266,819 ms
Run-time optimizer algorithm (GEQO): 0,440 ms

The GEQO optimizer Run-time is a little faster, not affecting the final
result. In theory the dynamic programming algorithm to choose the best
plan, resulting in less time to run the query.

Who knows what is happening?

In annex the Query Plans and Query 11 of DBT3.

Thank's for attention.

Tarcizio Bini.

Attachments:

Query11.txt (text/plain, 834B) download select ps_partkey, sum(ps_supplycost * ps_availqty) as value from partsupp, supplier, nation where ps_suppkey = s_suppkey and s_nationkey = n_nationkey and n_name = 'KENYA' group by ps_partkey having sum(ps_supplycost * ps_availqty) > ( select sum(ps_supplycost * ps_availqty) * 0.0001000000 from partsupp, supplier, nation where ps_suppkey = s_suppkey and s_nationkey = n_nationkey and n_name = 'KENYA' ) order by value desc;
QueryPlan11.txt (text/plain, 9.9K) download QUERY PLAN (GEQO -1-) --------------------------------------------------------------------------------------------------------------------------------------------------------------- Sort (cost=64653.75..64733.78 rows=32011 width=12) (actual time=2041.116..2041.370 rows=1217 loops=1) Sort Key: (sum((public.partsupp.ps_supplycost * (public.partsupp.ps_availqty)::double precision))) Sort Method: quicksort Memory: 106kB InitPlan -> Aggregate (cost=28821.75..28821.77 rows=1 width=8) (actual time=546.215..546.215 rows=1 loops=1) -> Hash Join (cost=249.74..28741.72 rows=32011 width=8) (actual time=0.844..530.934 rows=30080 loops=1) Hash Cond: (public.partsupp.ps_suppkey = public.supplier.s_suppkey) -> Seq Scan on partsupp (cost=0.00..25170.81 rows=800281 width=12) (actual time=0.022..280.595 rows=800000 loops=1) -> Hash (cost=244.74..244.74 rows=400 width=4) (actual time=0.797..0.797 rows=376 loops=1) -> Nested Loop (cost=11.35..244.74 rows=400 width=4) (actual time=0.129..0.641 rows=376 loops=1) -> Seq Scan on nation (cost=0.00..1.31 rows=1 width=4) (actual time=0.010..0.013 rows=1 loops=1) Filter: (n_name = 'KENYA'::bpchar) -> Bitmap Heap Scan on supplier (cost=11.35..238.43 rows=400 width=8) (actual time=0.110..0.436 rows=376 loops=1) Recheck Cond: (public.supplier.s_nationkey = public.nation.n_nationkey) -> Bitmap Index Scan on i_s_nationkey (cost=0.00..11.25 rows=400 width=0) (actual time=0.078..0.078 rows=376 loops=1) Index Cond: (public.supplier.s_nationkey = public.nation.n_nationkey) -> GroupAggregate (cost=31686.65..32887.06 rows=32011 width=12) (actual time=2009.620..2039.952 rows=1217 loops=1) Filter: (sum((public.partsupp.ps_supplycost * (public.partsupp.ps_availqty)::double precision)) > $0) -> Sort (cost=31686.65..31766.67 rows=32011 width=12) (actual time=1463.166..1472.588 rows=30080 loops=1) Sort Key: public.partsupp.ps_partkey Sort Method: external sort Disk: 824kB -> Hash Join (cost=249.74..28741.72 rows=32011 width=12) (actual time=62.849..1389.054 rows=30080 loops=1) Hash Cond: (public.partsupp.ps_suppkey = public.supplier.s_suppkey) -> Seq Scan on partsupp (cost=0.00..25170.81 rows=800281 width=16) (actual time=22.609..1096.402 rows=800000 loops=1) -> Hash (cost=244.74..244.74 rows=400 width=4) (actual time=40.199..40.199 rows=376 loops=1) -> Nested Loop (cost=11.35..244.74 rows=400 width=4) (actual time=24.393..39.969 rows=376 loops=1) -> Seq Scan on nation (cost=0.00..1.31 rows=1 width=4) (actual time=4.676..4.682 rows=1 loops=1) Filter: (n_name = 'KENYA'::bpchar) -> Bitmap Heap Scan on supplier (cost=11.35..238.43 rows=400 width=8) (actual time=19.707..35.047 rows=376 loops=1) Recheck Cond: (public.supplier.s_nationkey = public.nation.n_nationkey) -> Bitmap Index Scan on i_s_nationkey (cost=0.00..11.25 rows=400 width=0) (actual time=8.798..8.798 rows=376 loops=1) Index Cond: (public.supplier.s_nationkey = public.nation.n_nationkey) Total runtime: 2042.212 ms (33 rows) Time: 2198,067 ms ____________________________________________________________________________________________________________________________ Timing is on. QUERY PLAN (GEQO -2-) Sort (cost=62119.88..62199.91 rows=32011 width=12) (actual time=83783.236..83783.488 rows=1217 loops=1) Sort Key: (sum((public.partsupp.ps_supplycost * (public.partsupp.ps_availqty)::double precision))) Sort Method: quicksort Memory: 106kB InitPlan -> Aggregate (cost=28821.75..28821.77 rows=1 width=8) (actual time=1847.644..1847.644 rows=1 loops=1) -> Hash Join (cost=249.74..28741.72 rows=32011 width=8) (actual time=14.914..1830.144 rows=30080 loops=1) Hash Cond: (public.partsupp.ps_suppkey = public.supplier.s_suppkey) -> Seq Scan on partsupp (cost=0.00..25170.81 rows=800281 width=12) (actual time=0.012..1563.046 rows=800000 loops=1) -> Hash (cost=244.74..244.74 rows=400 width=4) (actual time=14.821..14.821 rows=376 loops=1) -> Nested Loop (cost=11.35..244.74 rows=400 width=4) (actual time=13.076..14.602 rows=376 loops=1) -> Seq Scan on nation (cost=0.00..1.31 rows=1 width=4) (actual time=0.008..0.015 rows=1 loops=1) Filter: (n_name = 'KENYA'::bpchar) -> Bitmap Heap Scan on supplier (cost=11.35..238.43 rows=400 width=8) (actual time=13.060..14.406 rows=376 loops=1) Recheck Cond: (public.supplier.s_nationkey = public.nation.n_nationkey) -> Bitmap Index Scan on i_s_nationkey (cost=0.00..11.25 rows=400 width=0) (actual time=13.011..13.011 rows=376 loops=1) Index Cond: (public.supplier.s_nationkey = public.nation.n_nationkey) -> GroupAggregate (cost=29152.77..30353.18 rows=32011 width=12) (actual time=83749.242..83782.097 rows=1217 loops=1) Filter: (sum((public.partsupp.ps_supplycost * (public.partsupp.ps_availqty)::double precision)) > $0) -> Sort (cost=29152.77..29232.80 rows=32011 width=12) (actual time=81901.333..81913.262 rows=30080 loops=1) Sort Key: public.partsupp.ps_partkey Sort Method: external merge Disk: 824kB -> Nested Loop (cost=0.00..26207.84 rows=32011 width=12) (actual time=51.765..81814.617 rows=30080 loops=1) -> Nested Loop (cost=0.00..445.31 rows=400 width=4) (actual time=5.648..14.493 rows=376 loops=1) Join Filter: (public.supplier.s_nationkey = public.nation.n_nationkey) -> Seq Scan on nation (cost=0.00..1.31 rows=1 width=4) (actual time=2.501..2.507 rows=1 loops=1) Filter: (n_name = 'KENYA'::bpchar) -> Seq Scan on supplier (cost=0.00..319.00 rows=10000 width=8) (actual time=3.132..8.416 rows=10000 loops=1) -> Index Scan using i_ps_suppkey on partsupp (cost=0.00..63.33 rows=86 width=16) (actual time=7.235..217.486 rows=80 loops=376) Index Cond: (public.partsupp.ps_suppkey = public.supplier.s_suppkey) Total runtime: 83784.321 ms (30 rows) Time: 83910,049 ms _________________________________________________________________________________________________________________________ QUERY PLAN (Dynamic Programming) ------------------------------------------------------------------------------------------------------------------------------------------------------- Sort (cost=59586.00..59666.03 rows=32011 width=12) (actual time=84312.869..84313.130 rows=1217 loops=1) Sort Key: (sum((public.partsupp.ps_supplycost * (public.partsupp.ps_availqty)::double precision))) Sort Method: quicksort Memory: 106kB InitPlan -> Aggregate (cost=26287.87..26287.89 rows=1 width=8) (actual time=240.783..240.784 rows=1 loops=1) -> Nested Loop (cost=0.00..26207.84 rows=32011 width=8) (actual time=0.063..224.969 rows=30080 loops=1) -> Nested Loop (cost=0.00..445.31 rows=400 width=4) (actual time=0.028..7.440 rows=376 loops=1) Join Filter: (public.supplier.s_nationkey = public.nation.n_nationkey) -> Seq Scan on nation (cost=0.00..1.31 rows=1 width=4) (actual time=0.009..0.014 rows=1 loops=1) Filter: (n_name = 'KENYA'::bpchar) -> Seq Scan on supplier (cost=0.00..319.00 rows=10000 width=8) (actual time=0.010..4.273 rows=10000 loops=1) -> Index Scan using i_ps_suppkey on partsupp (cost=0.00..63.33 rows=86 width=12) (actual time=0.020..0.534 rows=80 loops=376) Index Cond: (public.partsupp.ps_suppkey = public.supplier.s_suppkey) -> GroupAggregate (cost=29152.77..30353.18 rows=32011 width=12) (actual time=84278.513..84311.690 rows=1217 loops=1) Filter: (sum((public.partsupp.ps_supplycost * (public.partsupp.ps_availqty)::double precision)) > $0) -> Sort (cost=29152.77..29232.80 rows=32011 width=12) (actual time=84037.466..84049.094 rows=30080 loops=1) Sort Key: public.partsupp.ps_partkey Sort Method: external merge Disk: 824kB -> Nested Loop (cost=0.00..26207.84 rows=32011 width=12) (actual time=51.742..83954.992 rows=30080 loops=1) -> Nested Loop (cost=0.00..445.31 rows=400 width=4) (actual time=10.275..19.266 rows=376 loops=1) Join Filter: (public.supplier.s_nationkey = public.nation.n_nationkey) -> Seq Scan on nation (cost=0.00..1.31 rows=1 width=4) (actual time=7.133..7.139 rows=1 loops=1) Filter: (n_name = 'KENYA'::bpchar) -> Seq Scan on supplier (cost=0.00..319.00 rows=10000 width=8) (actual time=3.133..8.565 rows=10000 loops=1) -> Index Scan using i_ps_suppkey on partsupp (cost=0.00..63.33 rows=86 width=16) (actual time=7.411..223.160 rows=80 loops=376) Index Cond: (public.partsupp.ps_suppkey = public.supplier.s_suppkey) Total runtime: 84313.902 ms (27 rows) Time: 84438,998 ms Timing is on.

Message-ID: <55663.200.17.202.126.1224603619.squirrel@webmail.inf.ufpr.br>
Permalink:  ../55663.200.17.202.126.1224603619.squirrel@webmail.inf.ufpr.br/
Also on:    postgresql.org/message-id/55663.200.17.202.126.1224603619.squirrel@webmail.inf.ufpr.br

 · 

reply

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Reply to all the recipients from your mail client; the link fills in
  the headers below: reply via email
  Some clients, webmail especially, drop In-Reply-To and References from
  a link, and the reply then starts a new thread: use the mbox below.

  To: pgsql-performance@postgresql.org
  Cc: tarcizioab@c3sl.ufpr.br
  Subject: Re: "Mysterious" - Dynamic Programming X GEQO
  In-Reply-To: <55663.200.17.202.126.1224603619.squirrel@webmail.inf.ufpr.br>
  References: <55663.200.17.202.126.1224603619.squirrel@webmail.inf.ufpr.br>

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

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