Received: from localhost (unknown [200.46.204.183]) by postgresql.org (Postfix) with ESMTP id B410F64FDEB for ; Tue, 21 Oct 2008 12:40:26 -0300 (ADT) Received: from postgresql.org ([200.46.204.86]) by localhost (mx1.hub.org [200.46.204.183]) (amavisd-maia, port 10024) with ESMTP id 99011-06 for ; Tue, 21 Oct 2008 12:40:23 -0300 (ADT) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from urquell.c3sl.ufpr.br (mx.inf.ufpr.br [200.17.202.3]) by postgresql.org (Postfix) with ESMTP id D13C564FD77 for ; Tue, 21 Oct 2008 12:40:22 -0300 (ADT) Received: from webmail.inf.ufpr.br (calvados.c3sl.ufpr.br [200.17.202.2]) by urquell.c3sl.ufpr.br (Postfix) with ESMTP id 82804700003FB for ; Tue, 21 Oct 2008 13:40:19 -0200 (BRST) Received: from 200.17.202.126 (SquirrelMail authenticated user tarcizioab) by webmail.inf.ufpr.br with HTTP; Tue, 21 Oct 2008 12:40:19 -0300 (BRT) Message-ID: <55663.200.17.202.126.1224603619.squirrel@webmail.inf.ufpr.br> Date: Tue, 21 Oct 2008 12:40:19 -0300 (BRT) Subject: "Mysterious" - Dynamic Programming X GEQO From: tarcizioab@c3sl.ufpr.br To: pgsql-performance@postgresql.org User-Agent: SquirrelMail/1.4.9a MIME-Version: 1.0 Content-Type: multipart/mixed;boundary="----=_20081021124019_44480" X-Priority: 3 (Normal) Importance: Normal X-Virus-Scanned: Maia Mailguard 1.0.1 X-Spam-Status: No, hits=0 tagged_above=0 required=5 tests=none X-Spam-Level: X-Archive-Number: 200810/103 X-Sequence-Number: 31684 ------=_20081021124019_44480 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 8bit 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. ------=_20081021124019_44480 Content-Type: text/plain; name="Query11.txt" Content-Transfer-Encoding: 8bit Content-Disposition: attachment; filename="Query11.txt" 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; ------=_20081021124019_44480 Content-Type: text/plain; name="QueryPlan11.txt" Content-Transfer-Encoding: 8bit Content-Disposition: attachment; filename="QueryPlan11.txt" 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. ------=_20081021124019_44480--