Robert Haas <robertmh...@gmail.com> writes: > On Mon, Nov 9, 2009 at 1:10 PM, Tom Lane <t...@sss.pgh.pa.us> wrote: >> Yowza. 18000 distinct paths for one relation? Could we see the test >> case?
> Hey, wait a minute. Unless I'm missing something, the items being > accumulated here are not paths (as Tom said upthread and I naively > believed), but RelOptInfos. Yeah, I failed to think carefully about that. > It looks like we create a RelOptInfo for > every legal join order, so this is going to happen on any large-ish > query where the joins can be reordered relatively freely. Actually, it's more like a RelOptInfo for every combination of base rels that could be formed along any legal join path (where "legal" includes the heuristics that avoid clauseless joins when possible). So the worst case is 2^n for n base rels, but usually considerably fewer. Nonetheless, even a small fraction of 2^37 is Too Many. > I don't think there's any easy fix for this. Nope :-(. I was able to get rid of the specific O(N^2) behavior that you were running into, but that just pushes the problem out a bit. FWIW, a profile of CVS HEAD running on this query looks like samples % symbol name 208189 15.9398 compare_fuzzy_path_costs 116260 8.9014 add_path 97509 7.4657 AllocSetAlloc 78354 5.9991 make_canonical_pathkey 69027 5.2850 generate_join_implied_equalities 65153 4.9884 cost_nestloop 59689 4.5700 bms_is_subset 49176 3.7651 add_paths_to_joinrel 39720 3.0411 bms_overlap 32562 2.4931 cost_mergejoin 30101 2.3047 pathkeys_useful_for_merging 26409 2.0220 AllocSetFree 24459 1.8727 MemoryContextAllocZeroAligned 23247 1.7799 hash_search_with_hash_value 16018 1.2264 check_list_invariants which is at least unsurprising. However, it eats memory fast enough to start swapping after level 7 or so, so there is no way that the exhaustive planner is ever going to finish this problem. > Playing around with this a bit, I was easily able to get 2-second > planing times on 15 table join, 6-second planning times on a 16 table > join and 30-second planning times on a 17 table join. This makes it > hard to support raising the GEQO threshold, as most recently suggested > by Greg Sabino Mullane here (and previously by me on an earlier > thread): Yeah. I think GEQO or other approximate methods are the only hope for very large join problems. We could however hope to get to the point of being able to raise the collapse limits, rather than keeping them below the geqo_threshold by default. In principle that should result in better plans ... regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers