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.
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;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.
--
Sent via pgsql-performance mailing list (pgsql-performance@xxxxxxxxxxxxxx)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
