Prev: [HACKERS] Review of Synchronous Replication patches
Next: [HACKERS] psql \timing output supressed in quiet mode
From: Adriano Lange on 24 Jul 2010 09:20
Hi,

I'd like to release the last version of my experimental join order
algorithm (TwoPO - Two Phase Optimization [1]):

http://git.c3sl.ufpr.br/gitweb?p=lbd/ljqo.git;a=summary

This algorithm is not production-ready, but an experimental set of
ideas, which need to be refined and evaluated. As the join order
optimization is a hard problem, the evaluation of a search strategy is
also a hard task. Therefore, I think the most important TODO item
related to replacement of GEQO algorithm is to define a set of
evaluation criteria considered as relevant.

TwoPO is encapsulated in a plug-in called LJQO (Large Join Query
Optimization [2]). This plug-in has two main GUC variables:

ljqo_threshold = N (like geqo_threshold)
ljqo_algorithm = {twopo|geqo}

As its name means, TwoPO has internally two search strategies that
constitute its two phases of optimization:

* Iterative Improvement (II) � Biased Sampling + Local Search
* Simulated Annealing (SA)

This algorithm also works in two search spaces:

* deep-trees (subset of bushy-trees)
- list of baserels
- initial states: biased sampling using
Prim algorithm over join graph (new, very efficient)
- moves: swap, 3cycle [2]
* bushy-trees
- binary join tree representation
- initial states: biased sampling using
Kruskal's algorithm over join graph [3,4].
- moves: associative

You can modify the functionality of TwoPO through the following parameters:

twopo_bushy_space = {true|false}
- set it to false if you want only deep-trees
default=true
twopo_heuristic_states = {true|false}
- enables heuristic to initial states
default=true
twopo_ii_stop = Int
- number of initial states
default=10
twopo_ii_improve_states = {true|false}
- find local-minimum of each initial state
default=true
twopo_sa_phase = {true|false}
- enables Simulated Annealing (SA) phase
default=true
twopo_sa_initial_temperature = Float
- initial temperature for SA phase
default=0.1
twopo_sa_temperature_reduction = Float
- temperature reduction
default=0.95
twopo_sa_equilibrium = Int
- number of states generated for each temperature
(Int * State Size)
default=16


References:

[1] Yannis E. Ioannidis e Younkyung Kang. Randomized algorithms for
optimizing large join queries. SIGMOD Rec., 19(2):312-321, 1990.

[2] Arun Swami e Anoop Gupta. Optimization of large join queries. SIGMOD
'88: Proceedings of the 1988 ACM SIGMOD international conference on
Management of data, pages 8-17, New York, NY, USA, 1988. ACM.

[3] P.B. Guttoski, M. S. Sunye, e F. Silva. Kruskal's algorithm for
query tree optimization. IDEAS '07: Proceedings of the 11th
International Database Engineering and Applications Symposium, pages
296-302, Washington, DC, USA, 2007. IEEE Computer Society.

[4] Florian Waas e Arjan Pellenkoft. Join order selection - good enough
is easy. BNCOD, pages 51-67, 2000.


Att,
Adriano Lange


--
Sent via pgsql-hackers mailing list (pgsql-hackers(a)postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

 | 
Pages: 1
Prev: [HACKERS] Review of Synchronous Replication patches
Next: [HACKERS] psql \timing output supressed in quiet mode