Re: Solving sudoku using SQL

On 08/12/10 21:18, Tom Lane wrote:
> =?UTF-8?B?SmFuIFVyYmHFhHNraQ==?= <wulczer(at)wulczer(dot)org> writes:
>> I'm pleasantly surprised that the SA code as it stands today, setting
>> the equlibrium factor to 8 and temperature reduction factor to 0.4, the
>> query takes 1799.662 ms in total.
>
> Cool.
>
>> With the default values it runs
>> forever, but I long discovered that defaults taken from the original
>> paper are not well suited for my PG implementation (I could plug my MSc
>> thesis here, but I'm way too shy for that). 8/0.4 are values where I got
>> better results than GEQO for Andres' monster-query.
>
> Hmmm ... "runs forever" is a bit scary. One of the few good things I
> can say about GEQO is that it will terminate in a reasonable amount of
> time for even quite large problems. I would like to think that SA will
> also have that property. I thought that the annealing approach was sure
> to terminate in a fixed number of steps? Or did you mean that the
> planner terminated, but produced a horrid plan?

It finishes after a bound number of steps, but with high values of
temperature reduction it takes a lot of time for the temperature to fall
low enough to consider the system "frozen", so that number of steps is big.

With SA you start with a temperature that's linearily dependant on the
size of the query, and back off exponentially. Each step means work tha
also depends on the size of the query, so big queries can mean expensive
steps. With q=0.9 and initial temperature=<very-big> it takes too much
time to plan.

The good thing is that it's trivial to implement a hard cut-off value,
which will stop annealing after a fixed number of steps (regardless of
the current temperature) that would serve as a safety valve.

Jan