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.


Julius Stroffek

Proposal for Pluggable Optimizer Interface


We have presented at PGCon 2007 in Ottawa couple of other
approaches and algorithms that can be used for query optimization,
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

postgres=# select * from pg_optimizer;
 optname |      optproc
 geqo    | geqo_optimizer
 dynamic | dynamic_optimizer
 greedy  | greedy_optimizer
(4 rows)

postgres=# set optimizer=greedy;

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'
> ;

Once, the optimizer function is created user may create
an optimizer using the function with the statement

>     function = greedyoptimizer
>     comment = 'Greedy Nearest Neighbor Optimizer'
> );

If the user decides not to use the optimizer anymore
he can invoke


User have to also drop the optimizer function with

> DROP FUNCTION greedyoptimizer;

Project TODO List
1.Create a pg_optimizer catalog to hold available
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
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

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
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

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.

---------------------------(end of broadcast)---------------------------
TIP 2: Don't 'kill -9' the postmaster

Reply via email to