Marc Cousin <cousinmarc@xxxxxxxxx> writes: > The Monday 28 February 2011 16:35:37, Tom Lane wrote : >> Could we see a concrete example demonstrating that? I agree with Heikki >> that it's not obvious what you are testing that would have such behavior. >> I can think of places that would have O(N^2) behavior in the length of >> the targetlist, but it seems unlikely that they'd come to dominate >> runtime at a mere 1000 columns. > I feel a little silly not having provided a test case from the startâ?¦ > A script doing a complete test is attached to this email. I did some oprofile analysis of this test case. It's spending essentially all its time in SearchCatCache, on failed searches of pg_statistic. The cache accumulates negative entries for each probed column, and then the searches take time proportional to the number of entries, so indeed there is an O(N^2) behavior --- but N is the number of columns times number of tables in your test case, not just the number of columns. The cache is a hash table, so ideally the search time would be more or less constant as the table grows, but to make that happen we'd need to reallocate with more buckets as the table grows, and catcache.c doesn't do that yet. We've seen a few cases that make that look worth doing, but they tend to be pretty extreme, like this one. It's worth pointing out that the only reason this effect is dominating the runtime is that you don't have any statistics for these toy test tables. If you did, the cycles spent using those entries would dwarf the lookup costs, I think. So it's hard to get excited about doing anything based on this test case --- it's likely the bottleneck would be somewhere else entirely if you'd bothered to load up some data. regards, tom lane -- Sent via pgsql-performance mailing list (pgsql-performance@xxxxxxxxxxxxxx) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance
