Re: Solving sudoku using SQL

Robert Haas <robertmhaas(at)gmail(dot)com> writes:
> On Wed, Dec 8, 2010 at 8:57 AM, Tatsuo Ishii <ishii(at)postgresql(dot)org> wrote:
>> In the page first one takes infinite time by PostgreSQL 9.0.1. Next
>> one can be executed very quickly because the join order is explicitely
>> specified by cross join syntax. This seems to be a limitation of
>> PostgreSQL optimizer and I would like it be removed. Comments?

> It's not easy to make the optimizer degrade gracefully when confronted
> with a very large number of tables, but I agree it would be worthwhile
> if we could figure out how to do it.

There is something funny going on there; it's not just that the planner
is slower with a large flat search space. It is slower, but only maybe
5x or so. What I'm seeing is that it actually finds a much worse plan
(very much larger estimated cost as well as actual runtime) when given
the flat problem. That seems like a bug: a constrained search ought
never find a better solution than an unconstrained search.

It may be that the search heuristics in joinrels.c are failing. If
so, it may be impractical to fix, ie making this better would slow down
more-typical planning problems enormously. But it'd be nice to
understand exactly where it's going off the rails.

regards, tom lane