> 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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
