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