From: Julius Stroffek <Julius.Stroffek@Sun.COM>
To: pgsql-performance@postgresql.org
To: pgsql-hackers@postgresql.org
Subject: Proposal: Pluggable Optimizer Interface
Date: Mon, 13 Aug 2007 21:49:56 +0200
Message-ID: <46C0B5E4.4020305@sun.com> (raw)
Hi All,
Tomas Kovarik and I have presented at PGCon 2007 in Ottawa
the ideas about other possible optimizer algorithms to be used
in PostgreSQL.
We are quite new to PostgreSQL project so it took us some
time to go through the sources end explore the possibilities
how things could be implemented.
There is a proposal attached to this mail about the interface
we would like to implement for switching between different
optimizers. Please review it and provide a feedback to us.
Thank You.
Regards
Julius Stroffek
Attachments:Optimizer - Proposal.txt (text/plain, 5.4K) download
Proposal for Pluggable Optimizer Interface
==========================================
Overview
========
We have presented at PGCon 2007 in Ottawa couple of other
approaches and algorithms that can be used for query optimization,
see http://www.pgcon.org/2008/papers/Execution_Plan_Optimization_Techniques_Julius_Stroffek.pdf
We have focused on algorithms for searching the space of
all possible orders of joins including bushy trees.
The possible algorithms include
* Dynamic Programming (already implemented
in PostgreSQL)
* Genetic Algorithm (already implemented
in PostgreSQL)
* Dijkstra's Algorithm
* A* Search Algorithm
* Greedy “Nearest Neighbor” Algorithm
* Hill-Climbing
* Simulated Annealing
* Iterative Improvement
* Two Phase Optimization
* Toured Simulated Annealing
Choosing the best algorithm from the above list is
difficult. We have to consider the length of the optimizer
computation vs. the quality of the solution which we would
like to achieve. We may want to do some hybrid optimization
– run couple of the algorithms from the above and choose
the best solution found. We might run some very fast
algorithm at the beginning and depending on the solution
cost we may decide whether it is worthwhile to try
to optimize the plan even more (using other algorithm
with longer running time but producing better solutions).
Therefore we would like to propose an interface which
can be used to switch between different optimizer algorithms
and/or allow a user to write and use his own implementation.
It would allow the community to ship more optimizer
algorithms as contrib modules and users may then decide
which of those algorithms should be used for their queries.
Creating an optimizer
=====================
We would propose to create a catalog holding the available
optimizers in the system called pg_optimizer. Users could
than use a SET command to switch between different
optimizers.
postgres=# select * from pg_optimizer;
optname | optproc
---------+-------------------
geqo | geqo_optimizer
dynamic | dynamic_optimizer
greedy | greedy_optimizer
(4 rows)
postgres=# set optimizer=greedy;
SET
Optimizer Invocation Point
==========================
There is a code in function make_rel_from_joinlist which
decides whether to invoke dynamic programming or genetic
algorithm for query optimization. We would propose to place
the invocation of the plugged optimizer to the same place
and with the same parameters as function geqo and
make_one_rel_by_joins are currently invoked.
Creating and dropping an optimizer
==================================
The optimizer function have to be implemented as a C-Language
Function using “Version 1 Calling Conventions”. The return
type of the function is RelOptInfo * and the arguments
passed to the function are
1.PlannerInfo *root
2.int levels_needed
3.List * initial_rels
The proper “CREATE FUNCTION” statement have to be used
to create the optimizer function.
> CREATE FUNCTION greedyoptimizer(internal, int, internal)
> RETURNS internal
> AS 'mylib', 'greedy_optimizer'
> LANGUAGE C
> ;
Once, the optimizer function is created user may create
an optimizer using the function with the statement
> CREATE OPTIMIZER greedy (
> function = greedyoptimizer
> comment = 'Greedy Nearest Neighbor Optimizer'
> );
If the user decides not to use the optimizer anymore
he can invoke
> DROP OPTIMIZER greedy;
User have to also drop the optimizer function with
> DROP FUNCTION greedyoptimizer;
Project TODO List
=================
1.Create a pg_optimizer catalog to hold available
optimizers.
2.Create wrappers above the current dynamic
programming and genetic algorithm optimizers
to be used to call those implementations.
3.Modify the parser and add the functions to handle
and execute the CREATE/DROP OPTIMIZER statements.
4.Modify GUC that it would be possible to switch
between optimizers.
5.Change the code at the optimizer invocation
point that the appropriate optimizer function
would be called.
6.Handle object dependencies – make an entry
in pg_depend that optimizer depends on its
function.
7.Implement '\dO' command that will list the
available optimizers.
8.Create a contrib module and ship some other
optimizer algorithms.
9.Any other suggestion, comments and changes
that will come out from the review of this
proposal.
Things to Decide
================
1.Rights. Who can create/drop optimizers?
Who can use the optimizer? Are the rights
for optimizer function enough? Probably,
creating and dropping optimizer could be
allowed just for DB administrators and
rights for optimizer functions are enough
to restrict the usage. No need to introduce
“GRANT ON OPTIMIZER”.
2.How to behave when dropping an optimizer
which is currently running or is set up
in other sessions.
3.Any other suggestion, comments and changes
that will come out from the review of this
proposal.
Future Possible Improvements
============================
* Implement more algorithms and implement also
more complex combinations of the algorithms.
* Create even more optimizer invocation points.
Different implementations might be invoked in
different places of the current code. If this
would make sense and it will come up as
a requirement for some optimizer algorithm.
* Do some work on “benchmarking” the algorithms
depending on the cost of the plan found,
running time, etc.
* Consider some heuristic for choosing the different
optimizers for different queries.
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 using the --to and --cc options:
reply via email
To: pgsql-performance@postgresql.org
Cc: Julius.Stroffek@Sun.COM, pgsql-hackers@postgresql.org
Subject: Re: Proposal: Pluggable Optimizer Interface
In-Reply-To: <46C0B5E4.4020305@sun.com>
* 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