Thread: patch for geqo tweaks

I have two patches to make the geqo initialization and mutation
slightly better.

The first adjusts the mutation swaps to avoid having to re-pick
ties.  The second changes the initialization and shuffling algorithm
for the gene array to use an in-place Fisher-Yates shuffling
algorithm.

Diffs against commit 49124613f134b04594b1a5c46368eb0a5db16d4b
(i.e. tip of master as of when I re-made the diff).

On my system the patches pass a ./configure; make; make check

--
nw

Nathan Wagner <nw+pg@hydaspes.if.org> writes:
> I have two patches to make the geqo initialization and mutation
> slightly better.

> The first adjusts the mutation swaps to avoid having to re-pick
> ties.  The second changes the initialization and shuffling algorithm
> for the gene array to use an in-place Fisher-Yates shuffling
> algorithm.

I took a quick look at this.

I'm not very impressed with the first patch: it might save a few
geqo_randint() calls, but it seems to do so at the price of making the
swap choices less random --- for instance it sure looks to me like the
last array element is now less likely to participate in swaps than
other elements.  Unless you can prove that actually the swapping is
still unbiased, I'm inclined to reject this part.

As for the second part, I had to look up Fisher-Yates ;-) but after
having read Wikipedia's entry about it I think this is a good change.
The code's shorter and more efficient, and it should mathematically
provide an equally-unbiased initial shuffle.  It could do with a better
comment, and I'd be inclined to handle the first element outside the loop
rather than uselessly computing geqo_randint(0,0), but those are trivial
changes.

Having said that, though, I believe that it's also probably a
*different* initial shuffle, which may well mean that GEQO gives
different plans in some cases.  That doesn't bother me as long as
we only make the change in HEAD, but does anyone want to complain?
        regards, tom lane

Tom Lane wrote:

> Having said that, though, I believe that it's also probably a
> *different* initial shuffle, which may well mean that GEQO gives
> different plans in some cases.  That doesn't bother me as long as
> we only make the change in HEAD, but does anyone want to complain?

Uh, do we promise that plans found by geqo are stable?  That would seem
odd to me -- wouldn't they change shape on a whim, say because the stats
are different?  It seems odd to look for plan stability using a genetic
algorithm.

-- 
Álvaro Herrera                http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Alvaro Herrera <alvherre@2ndquadrant.com> writes:
> Tom Lane wrote:
>> Having said that, though, I believe that it's also probably a
>> *different* initial shuffle, which may well mean that GEQO gives
>> different plans in some cases.  That doesn't bother me as long as
>> we only make the change in HEAD, but does anyone want to complain?

> Uh, do we promise that plans found by geqo are stable?  That would seem
> odd to me -- wouldn't they change shape on a whim, say because the stats
> are different?  It seems odd to look for plan stability using a genetic
> algorithm.

Well, obviously any plan might change if the stats change.  But we do
promise repeatable plans given identical input data, cf commit f5bc74192.
        regards, tom lane

On Wed, Nov 04, 2015 at 12:51:52PM -0500, Tom Lane wrote:
> Nathan Wagner <nw+pg@hydaspes.if.org> writes:
> > I have two patches to make the geqo initialization and mutation
> > slightly better.
> 
> > The first adjusts the mutation swaps to avoid having to re-pick
> > ties.  The second changes the initialization and shuffling algorithm
> > for the gene array to use an in-place Fisher-Yates shuffling
> > algorithm.
> 
> I took a quick look at this.
> 
> I'm not very impressed with the first patch: it might save a few
> geqo_randint() calls, but it seems to do so at the price of making the
> swap choices less random --- for instance it sure looks to me like the
> last array element is now less likely to participate in swaps than
> other elements.  Unless you can prove that actually the swapping is
> still unbiased, I'm inclined to reject this part.

If I have understood the original code correctly, we need to select two
different random integers between 0 and num_gene-1, inclusive.  That
happens to be num_gene possible results.

Having chosen the first one, which I will call "swap1", we now only have
num_gene-1 possible results, which need to range from either 0 to
swap1-1 or from swap1+1 to num_gene-1, which is num_gene-1 possible
results.  I treat this as a single range from 0 to num_gene-2 and
generate a number within that range, which I will call "swap2".

If swap2 is between 0 and swap1-1, it is in the first range, and no
adjustment is necessary.  If it is greater than or equal to swap1, then
it is in the second range.  However the generated swap2 in the second
range will be between swap1 and num_gene-2, whereas we need it to be
between swap1+1 and num_gene-1, so I add one to swap2, adjusting the
range to the needed range.

It would be equivalent to set swap2 to num_gene-1 in that case,
effectively remapping the first value to the last, but an increment was
more intuitive to me.

> As for the second part, I had to look up Fisher-Yates ;-) but after
> having read Wikipedia's entry about it I think this is a good change.
> The code's shorter and more efficient, and it should mathematically
> provide an equally-unbiased initial shuffle.  It could do with a
> better comment, and I'd be inclined to handle the first element
> outside the loop rather than uselessly computing geqo_randint(0,0),

I could do that.  It will make the code slightly harder to read.  I
wonder if it would be worth having geqo_randint() handle the special
case instead.

> Having said that, though, I believe that it's also probably a
> *different* initial shuffle, which may well mean that GEQO gives
> different plans in some cases.

Yes, I would expect it to be different in the general case.  I think my
commit message noted that, but perhaps it could be more explicit.

> That doesn't bother me as long as we only make the change in HEAD, but
> does anyone want to complain?

I don't see any need to backport either of these patches.

-- 
nw

On Wed, Nov 04, 2015 at 12:51:52PM -0500, Tom Lane wrote:

> As for the second part, I had to look up Fisher-Yates ;-) but after
> having read Wikipedia's entry about it I think this is a good change.
> The code's shorter and more efficient, and it should mathematically
> provide an equally-unbiased initial shuffle.  It could do with a
> better comment, and I'd be inclined to handle the first element
> outside the loop rather than uselessly computing geqo_randint(0,0),
> but those are trivial changes.

I see you committed a modified version of my patch in commit
59464bd6f928ad0da30502cbe9b54baec9ca2c69.

You changed the tour[0] to be hardcoded to 1, but it should be any of
the possible gene numbers from 0 to remainder.  If you want to pull the
geqo_randint(0,0) out of the loop, it would be the last element, not the
first (i.e. where remainder == 0).

We might be able to just skip the last swap, and the loop could be

for (i=0; i < num_gene-1; i++) {

but I'd need to re-read the details of the Fisher-Yates algorithm to be
sure.  It may be that the last swap needs to happen for the shuffle to
be fully random.  In any case, tour[0] certainly shouldn't be hardcoded
to 1.

-- 
nw

Nathan Wagner <nw+pg@hydaspes.if.org> writes:
> I see you committed a modified version of my patch in commit
> 59464bd6f928ad0da30502cbe9b54baec9ca2c69.

> You changed the tour[0] to be hardcoded to 1, but it should be any of
> the possible gene numbers from 0 to remainder.

How so?  The intent is to replace the first iteration of the Fisher-Yates
loop, not the old loop.  That iteration will certainly end by assigning
1 to tour[0], because it must choose j = i = 0.
        regards, tom lane

Nathan Wagner <nw+pg@hydaspes.if.org> writes:
> On Wed, Nov 04, 2015 at 12:51:52PM -0500, Tom Lane wrote:
>> I'm not very impressed with the first patch: it might save a few
>> geqo_randint() calls, but it seems to do so at the price of making the
>> swap choices less random --- for instance it sure looks to me like the
>> last array element is now less likely to participate in swaps than
>> other elements.  Unless you can prove that actually the swapping is
>> still unbiased, I'm inclined to reject this part.

> If I have understood the original code correctly, we need to select two
> different random integers between 0 and num_gene-1, inclusive.  That
> happens to be num_gene possible results.

> Having chosen the first one, which I will call "swap1", we now only have
> num_gene-1 possible results, which need to range from either 0 to
> swap1-1 or from swap1+1 to num_gene-1, which is num_gene-1 possible
> results.  I treat this as a single range from 0 to num_gene-2 and
> generate a number within that range, which I will call "swap2".

> If swap2 is between 0 and swap1-1, it is in the first range, and no
> adjustment is necessary.  If it is greater than or equal to swap1, then
> it is in the second range.  However the generated swap2 in the second
> range will be between swap1 and num_gene-2, whereas we need it to be
> between swap1+1 and num_gene-1, so I add one to swap2, adjusting the
> range to the needed range.

Ah, after thinking some more, I see how that works.  I tend to think
that your other proposal of
    swap1 = geqo_randint(root, num_gene - 1, 0);    swap2 = geqo_randint(root, num_gene - 2, 0);    if (swap2 ===
swap1)       swap2 = num_gene - 1;
 

would be clearer, since only the forbidden case gets remapped.

However, really the whole argument is moot, because I notice that
geqo_mutation() is only called in the "#ifdef CX" code path, which
we don't use.  So there's little point in improving it.

(There's a fair amount of dead code in /geqo/, which I've never had
the energy to clean up, but maybe we should do that sometime.  It
seems unlikely that anyone will ever be interested in experimenting
with the ifdef'ed-out code paths.)
        regards, tom lane

On Fri, Nov 06, 2015 at 11:19:00AM -0500, Tom Lane wrote:
> Nathan Wagner <nw+pg@hydaspes.if.org> writes:
> > I see you committed a modified version of my patch in commit
> > 59464bd6f928ad0da30502cbe9b54baec9ca2c69.
> 
> > You changed the tour[0] to be hardcoded to 1, but it should be any
> > of the possible gene numbers from 0 to remainder.
> 
> How so?  The intent is to replace the first iteration of the
> Fisher-Yates loop, not the old loop.  That iteration will certainly
> end by assigning 1 to tour[0], because it must choose j = i = 0.

You are correct.  I got confused between reading the original code, my
patch, and your modified patch.

I wonder why the algorithm bothers with the first iteration at all, in
the case of an initialized array, it would just swap the first element
with itself.  I must be missing something.  I'll need to do some more
reading.

-- 
nw

On Fri, Nov 06, 2015 at 11:45:38AM -0500, Tom Lane wrote:

> However, really the whole argument is moot, because I notice that
> geqo_mutation() is only called in the "#ifdef CX" code path, which
> we don't use.

I suppose someone could turn it on via a compiler define.

> So there's little point in improving it.

No, probably not.

> (There's a fair amount of dead code in /geqo/, which I've never had
> the energy to clean up, but maybe we should do that sometime.  It
> seems unlikely that anyone will ever be interested in experimenting
> with the ifdef'ed-out code paths.)

I also note that in  src/backend/optimizer/path/allpaths.c there is a
join_search_hook variable apparently intended for plugins (extensions?)
to be able to control the search path optimizer.  And the geqo code is
AFAICT turned off by default anyway, so none of the code is used in
probably the vast majority of systems, with standard_join_search() being
called instead.

Would it be worth either of removing at least the non-ERX portions of
the geqo code, or removing the geqo code entirely (presumably with a
deprecation cycle) and moving it to an extension?  If there's any
interest, I can work up a patch for either or both.

There is only one test in the regression suite that turns on geqo that I
could find.  It's labeled "check for failure to generate a plan with
multiple degenerate IN clauses" in join.sql.

-- 
nw

Nathan Wagner <nw+pg@hydaspes.if.org> writes:
> On Fri, Nov 06, 2015 at 11:45:38AM -0500, Tom Lane wrote:
>> (There's a fair amount of dead code in /geqo/, which I've never had
>> the energy to clean up, but maybe we should do that sometime.  It
>> seems unlikely that anyone will ever be interested in experimenting
>> with the ifdef'ed-out code paths.)

> I also note that in  src/backend/optimizer/path/allpaths.c there is a
> join_search_hook variable apparently intended for plugins (extensions?)
> to be able to control the search path optimizer.  And the geqo code is
> AFAICT turned off by default anyway, so none of the code is used in
> probably the vast majority of systems, with standard_join_search() being
> called instead.

Uh, what?  It's not by any means turned off by default.

postgres=# select name,setting from pg_settings where name like '%geqo%';       name         | setting 
---------------------+---------geqo                | ongeqo_effort         | 5geqo_generations    | 0geqo_pool_size
| 0geqo_seed           | 0geqo_selection_bias | 2geqo_threshold      | 12
 
(7 rows)

You do need at least 12 tables in the FROM list to get it to be exercised
with the default settings, which among other things means that our
regression tests don't stress it much at all.  But it's definitely
reachable.

> Would it be worth either of removing at least the non-ERX portions of
> the geqo code, or removing the geqo code entirely (presumably with a
> deprecation cycle) and moving it to an extension?

Removing it is right out, as you'll soon find if you try to plan a query
with a couple dozen tables with geqo turned off.  The standard exhaustive
search just gets too slow.

I'm inclined to think that removing all the ifdefd-out-by-default logic
would be a fine thing to do, though.
        regards, tom lane

On Fri, Nov 06, 2015 at 02:16:41PM -0500, Tom Lane wrote:
> Uh, what?  It's not by any means turned off by default.
> 
> postgres=# select name,setting from pg_settings where name like '%geqo%';
>         name         | setting 
> ---------------------+---------
>  geqo                | on

[snip]

My day to make a fool of myself in public I guess.  You're right of
course.  I can only plead distraction by having too many projects in
mind at once and not focusing properly.  Sorry for taking up your time
on things I should have checked better.

> I'm inclined to think that removing all the ifdefd-out-by-default logic
> would be a fine thing to do, though.

I'll work up a patch.

-- 
nw

On 07/11/15 09:59, Nathan Wagner wrote:
[...]
> My day to make a fool of myself in public I guess. You're right of 
> course. I can only plead distraction by having too many projects in 
> mind at once and not focusing properly. Sorry for taking up your time 
> on things I should have checked better.
[...]

There are two types of people:    those that don't bother        and    those that try, & fail!


Cheers,
Gavin