PGCon2007 - Confirmed

PGCon 2007
The PostgreSQL Conference

Speakers
Tomas Kovarik
Julius Stroffek
Schedule
Day 3
Room SITE G0103
Start time 11:30
Duration 01:00
Info
ID 21
Event type Lecture
Track Hackers
Language English
Feedback

Execution plan optimization techniques

Execution plan optimization techniques and possible improvements in PostgreSQL implementation

We will shortly describe and explain the problem of cost based execution plan optimization. We will focus primarily on algorithms for searching the space of all possible alternatives for the large number of joins. We will briefly describe these algorithms and their possible variants, compare them together and we will try to pick up some of them as suitable for solving our problem. Some examples of execution of these algorithms on the traveling salesman problem will be shown. The traveling salesman problem was chosen for the presentation because it is a very similar problem and much easier to imagine and present than searching the space of execution plan alternatives.

We will shortly describe and explain the problem of cost based execution plan optimization. There are two main parts of this process:

1.) The execution plan cost evaluation based on estimates calculation. 2.) Searching the space of all possible execution plans and finding the one with the lowest cost.

We will focus primarily on algorithms for searching the space of all possible alternatives for the large number of joins. We will briefly describe these algorithms and their possible variants, compare them together and we will try to pick up some of them as suitable for solving our problem. Some examples of execution of these algorithms on the traveling salesman problem will be shown. The traveling salesman problem was chosen for the presentation because it is a very similar problem and much easier to imagine and present than searching the space of execution plan alternatives.

These are the algorithms that will be discussed: * current implementation of genetic algorithm * simulated annealing * Hopfield network * deterministic approximation algorithms * heuristic rules for picking up an alternatives for evaluation * possible combination of rule-based optimizer with a cost based optimizer