Re: benchmarking the query planner

> Yeah, that would be fast.  To see a quadratic case you need MCV arrays
> that have little or no overlap of common values --- then each element of
> the first will be compared (in vain) to all or most of the elements in
> the second.

Ah, that makes sense.  Here's a test case based on Greg's.  This is
definitely more than linear once you get above about n = 80, but it's
not quadratic either.  n = 1000 is only 43x n = 80, and while that's
surely more than 1000/80 = 12.5, it's also a lot less than (1000/80)^2
= 156.25.

create table tk as select
random()::text||random()::text||random()::text||random()::text||random()::text||random()::text
as r from generate_series(1,1000);
insert into tk (select * from tk);
insert into tk (select * from tk);
insert into tk (select
random()::text||random()::text||random()::text||random()::text||random()::text||random()::text
as r from generate_series(1,2000));

create table tk2 as select
random()::text||random()::text||random()::text||random()::text||random()::text||random()::text
as r from generate_series(1,1000);
insert into tk2 (select * from tk2);
insert into tk2 (select * from tk2);
insert into tk2 (select
random()::text||random()::text||random()::text||random()::text||random()::text||random()::text
as r from generate_series(1,2000));

create table tk3 as select
random()::text||random()::text||random()::text||random()::text||random()::text||random()::text
as r from generate_series(1,1000);
insert into tk3 (select * from tk3);
insert into tk3 (select * from tk3);
insert into tk3 (select
random()::text||random()::text||random()::text||random()::text||random()::text||random()::text
as r from generate_series(1,2000));

create table tk4 as select
random()::text||random()::text||random()::text||random()::text||random()::text||random()::text
as r from generate_series(1,1000);
insert into tk4 (select * from tk4);
insert into tk4 (select * from tk4);
insert into tk4 (select
random()::text||random()::text||random()::text||random()::text||random()::text||random()::text
as r from generate_series(1,2000));

create table tk5 as select
random()::text||random()::text||random()::text||random()::text||random()::text||random()::text
as r from generate_series(1,1000);
insert into tk5 (select * from tk5);
insert into tk5 (select * from tk5);
insert into tk5 (select
random()::text||random()::text||random()::text||random()::text||random()::text||random()::text
as r from generate_series(1,2000));

create table tk6 as select
random()::text||random()::text||random()::text||random()::text||random()::text||random()::text
as r from generate_series(1,1000);
insert into tk6 (select * from tk6);
insert into tk6 (select * from tk6);
insert into tk6 (select
random()::text||random()::text||random()::text||random()::text||random()::text||random()::text
as r from generate_series(1,2000));

and then (after disabling autovacuum):

set default_statistics_target = XXX;
analyze;
repeat 100x: explain select count(*) from (select * from tk as k, tk2
as l,tk3 as m,tk4 as n,tk5 as o,tk6 as p where k.r=l.r and k.r=m.r and
k.r=n.r and k.r=o.r and k.r=p.r) as x;

Timings (for 100 iterations):

10    0.900309
20    1.189229
30    1.280892
40    1.447358
50    1.611779
60    1.795701
70    2.001245
80    2.286144
90    2.955732
100    3.925557
150    6.472436
200    9.010824
250    11.89753
300    15.109172
350    18.813514
400    22.901383
450    27.842019
500    32.02136
550    37.609196
600    42.894322
650    48.460327
700    55.169819
750    61.568125
800    68.222201
850    75.027591
900    82.918344
950    91.235267
1000    99.737802

...Robert