Re: SDP query optimizer

Hi all,

I have developed a new query optimizer for PostgreSQL and I would like
to share it with the community. The optimizer's name is Sampling and
Dynamic Programming (SDP). I put it into a plugin developed some years
ago, named LJQO:

https://github.com/alange0001/ljqo.git

This plugin was configured to compile only against PostgreSQL 9.2.
However, I guess it may be easily adjusted for other versions of PostgreSQL.

I would be glad for any feedback about SDP or even about LJQO.

I have some numbers about the SDP in comparison with GEQO. If
interested, see a diff between the two ".out2" files attached. The
schema and query are from a previous email posted by Andres Freund in
this list.

Thanks for attention.
Adriano Lange

Adriano,

> I have developed a new query optimizer for PostgreSQL and I would like
> to share it with the community. The optimizer's name is Sampling and
> Dynamic Programming (SDP). I put it into a plugin developed some years
> ago, named LJQO:

Woah! Way cool.

As a warning, we're in the closing throes of version 9.3 right now, so
if you code/ideas doesn't get the attention it deserves, that's why.

There is an incomplete project from a few years back to make the
non-exhaustive query planner pluggable so that we could use different
algorithms. Unfortunately, it was never finished and merged with the
core code. Your planner is yet another reason it would be great to
complete this.

Keep up the good work!

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

On Sat, Mar 23, 2013 at 1:35 AM, Adriano Lange <alange0001(at)gmail(dot)com> wrote:
> I have developed a new query optimizer for PostgreSQL and I would like to
> share it with the community. The optimizer's name is Sampling and Dynamic
> Programming (SDP). I put it into a plugin developed some years ago, named
> LJQO:
>
> https://github.com/alange0001/ljqo.git

Looks great. Do you happen to have any papers or insight into why SDP
works as well as it does? It isn't immediately clear to me why the
cheapest left-deep tree is a good heuristic start point for the
dynamic programming phase.

Regards,
Ants Aasma
--
Cybertec Schönig & Schönig GmbH
Gröhrmühlgasse 26
A-2700 Wiener Neustadt
Web: http://www.postgresql-support.de

Hi,

On 22-03-2013 21:22, Josh Berkus wrote:
> Woah! Way cool.
>
> As a warning, we're in the closing throes of version 9.3 right now, so
> if you code/ideas doesn't get the attention it deserves, that's why.

Ok. No problem. :-)

> There is an incomplete project from a few years back to make the
> non-exhaustive query planner pluggable so that we could use different
> algorithms. Unfortunately, it was never finished and merged with the
> core code. Your planner is yet another reason it would be great to
> complete this.

Yes. I looked at the Julius and Tomas' project in pgFoundry [1] some
years ago, but it was inactive. Therefore, I decided to start a new one.

[1] - http://pgfoundry.org/projects/optimizer/

Anyway, good work for all of you.

--
Adriano Lange

On 22-03-2013 21:46, Ants Aasma wrote:
> On Sat, Mar 23, 2013 at 1:35 AM, Adriano Lange <alange0001(at)gmail(dot)com> wrote:
>> I have developed a new query optimizer for PostgreSQL and I would like to
>> share it with the community. The optimizer's name is Sampling and Dynamic
>> Programming (SDP). I put it into a plugin developed some years ago, named
>> LJQO:
>>
>> https://github.com/alange0001/ljqo.git
>
> Looks great. Do you happen to have any papers or insight into why SDP
> works as well as it does? It isn't immediately clear to me why the
> cheapest left-deep tree is a good heuristic start point for the
> dynamic programming phase.

Hi Ants Aasma,

I think it is difficult to say that SDP is completely better than GEQO.
There is a huge variety of situations where these kinds of optimizers
can be used.

I have made a series of experiments on SDP in a separate environment.
The main objective was to parallelize the optimizer. Thus, I called it
PSDP. I developed this environment from scratch in c++ and I used a
simplified version of the cost model used by PostgreSQL. Therefore, the
SDP is a sequential version of an experimental parallel optimizer.

For PSDP in its experimental environment, I have a comparison between
the costs obtained by the sampling phase and the costs obtained by the
complete PSDP. See the figure grafico-scaled_costs-dp_psdp attached. I
think that the dynamic programming phase can bring some robustness to
the optimizer. However, I still need to perform these same experiments
on PostgreSQL.

Considering the heuristic used in sampling phase, I have made another
series of experiments on PostgreSQL 9.0 comparing this sampling
(Sampling-L) with both a sampling on bushy trees (Sampling-B) and the
sampling used by GEQO. See as example the file "sampling...eps" also
attached. By these experiments I observed that Sampling-L was
statistically more efficient to get good join orders in a short time.

Regards,
Adriano Lange

On 2013-03-22 20:35:43 -0300, Adriano Lange wrote:
> Hi all,
>
> I have developed a new query optimizer for PostgreSQL and I would like to
> share it with the community. The optimizer's name is Sampling and Dynamic
> Programming (SDP). I put it into a plugin developed some years ago, named
> LJQO:
>
> https://github.com/alange0001/ljqo.git
>
> This plugin was configured to compile only against PostgreSQL 9.2. However,
> I guess it may be easily adjusted for other versions of PostgreSQL.
>
> I would be glad for any feedback about SDP or even about LJQO.
>
> I have some numbers about the SDP in comparison with GEQO. If interested,
> see a diff between the two ".out2" files attached. The schema and query are
> from a previous email posted by Andres Freund in this list.

I just want to mention that unless you skew the statistics for the individual
tables from their empty/default state this mostly measures a pretty degenerate
case where optima are very rare and not very differentiated. Thats a useful
thing to test, but not to have as the target to optimize for.
So it might be interesting to run that thing with some table
stats/contents stats set up.

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

On 23-03-2013 10:15, Andres Freund wrote:
> I just want to mention that unless you skew the statistics for the individual
> tables from their empty/default state this mostly measures a pretty degenerate
> case where optima are very rare and not very differentiated. Thats a useful
> thing to test, but not to have as the target to optimize for.
> So it might be interesting to run that thing with some table
> stats/contents stats set up.

Yes, the search space obtained from this experiment may be very simpler
than a real case. Beyond this experiment, I can construct classical
queries used to evaluate this kind of algorithm, as stars, cliques,
chains and cycles. Beyond these queries I have no idea how can I further
test it.

Regards,

Adriano Lange