Re: GSoC idea - Simulated annealing to search for query plans

Josh Berkus writes:

> On 02/26/2015 05:50 PM, Fabrízio de Royes Mello wrote:
>>
>> On Thu, Feb 26, 2015 at 10:27 PM, Andres Freund <andres(at)2ndquadrant(dot)com
>> <mailto:andres(at)2ndquadrant(dot)com>> wrote:
>>>
>>> On 2015-02-26 20:23:33 -0500, Tom Lane wrote:
>>> >
>>> > I seem to recall somebody demo'ing a simulated-annealing GEQO
>> replacement
>>> > at PGCon a couple years back. It never got to the point of being a
>>> > submitted patch though.
>>>
>>> Yea, it was Jan Urbański (CCed).
>>>
>>
>> And the project link: https://github.com/wulczer/saio
>
> So what w'ere saying, Grzegorz, is that we would love to see someone
> pick this up and get it to the point of making it a feature as a GSOC
> project. I think if you can start from where Jan left off, you could
> actually complete it.

Sorry, late to the party.

Yes, I wrote a GEQO replacement that used simulated annealing for my Master
thesis. It got to a point where it was generating plans similar to what GEQO
outputs for small queries and better plans for very large ones.

The thesis itself is here: https://wulczer.org/saio.pdf and the linked GitHub
repo contains source for the PGCon presentation, which gives a higher-level
overview.

The big problem turned out to be writing the step function that generates a new
join order from a previous one. Look for the "Simulated Annealing challenges"
and "Moves generator" chapters in my thesis, which are the only interesting
ones :)

If you'd like to pick up where I left, I'd be more than happy to help in any
ways I can.

Best,
Jan