summaryrefslogtreecommitdiff
path: root/src/include/optimizer
Commit message (Collapse)AuthorAgeFilesLines
* Create hooks to let a loadable plugin monitor (or even replace) the plannerTom Lane2007-05-252-2/+18
| | | | | | | | | | | | | | | and/or create plans for hypothetical situations; in particular, investigate plans that would be generated using hypothetical indexes. This is a heavily-rewritten version of the hooks proposed by Gurjeet Singh for his Index Advisor project. In this formulation, the index advisor can be entirely a loadable module instead of requiring a significant part to be in the core backend, and plans can be generated for hypothetical indexes without requiring the creation and rolling-back of system catalog entries. The index advisor patch as-submitted is not compatible with these hooks, but it needs significant work anyway due to other 8.2-to-8.3 planner changes. With these hooks in the core backend, development of the advisor can proceed as a pgfoundry project.
* Fix best_inner_indexscan to return both the cheapest-total-cost andTom Lane2007-05-221-3/+4
| | | | | | | | | | | | cheapest-startup-cost innerjoin indexscans, and make joinpath.c consider both of these (when different) as the inside of a nestloop join. The original design was based on the assumption that indexscan paths always have negligible startup cost, and so total cost is the only important figure of merit; an assumption that's obviously broken by bitmap indexscans. This oversight could lead to choosing poor plans in cases where fast-start behavior is more important than total cost, such as LIMIT and IN queries. 8.1-vintage brain fade exposed by an example from Chuck D.
* Teach tuplestore.c to throw away data before the "mark" point when the callerTom Lane2007-05-211-1/+2
| | | | | | | | | | | | is using mark/restore but not rewind or backward-scan capability. Insert a materialize plan node between a mergejoin and its inner child if the inner child is a sort that is expected to spill to disk. The materialize shields the sort from the need to do mark/restore and thereby allows it to perform its final merge pass on-the-fly; while the materialize itself is normally cheap since it won't spill to disk unless the number of tuples with equal key values exceeds work_mem. Greg Stark, with some kibitzing from Tom Lane.
* Teach tuplesort.c about "top N" sorting, in which only the first N tuplesTom Lane2007-05-042-5/+6
| | | | | | | | | | need be returned. We keep a heap of the current best N tuples and sift-up new tuples into it as we scan the input. For M input tuples this means only about M*log(N) comparisons instead of M*log(M), not to mention a lot less workspace when N is small --- avoiding spill-to-disk for large M is actually the most attractive thing about it. Patch includes planner and executor support for invoking this facility in ORDER BY ... LIMIT queries. Greg Stark, with some editorialization by moi.
* Expose more cursor-related functionality in SPI: specifically, allowTom Lane2007-04-161-2/+2
| | | | | | | | | | | access to the planner's cursor-related planning options, and provide new FETCH/MOVE routines that allow access to the full power of those commands. Small refactoring of planner(), pg_plan_query(), and pg_plan_queries() APIs to make it convenient to pass the planning options down from SPI. This is the core-code portion of Pavel Stehule's patch for scrollable cursor support in plpgsql; I'll review and apply the plpgsql changes separately.
* Avoid running build_index_pathkeys() in situations where there cannotTom Lane2007-04-151-1/+2
| | | | | | | possibly be any useful pathkeys --- to wit, queries with neither any join clauses nor any ORDER BY request. It's nearly free to check for this case and it saves a useful fraction of the planning time for simple queries.
* Turn the rangetable used by the executor into a flat list, and avoid storingTom Lane2007-02-222-7/+10
| | | | | | | | | | | | | | | | | useless substructure for its RangeTblEntry nodes. (I chose to keep using the same struct node type and just zero out the link fields for unneeded info, rather than making a separate ExecRangeTblEntry type --- it seemed too fragile to have two different rangetable representations.) Along the way, put subplans into a list in the toplevel PlannedStmt node, and have SubPlan nodes refer to them by list index instead of direct pointers. Vadim wanted to do that years ago, but I never understood what he was on about until now. It makes things a *whole* lot more robust, because we can stop worrying about duplicate processing of subplans during expression tree traversals. That's been a constant source of bugs, and it's finally gone. There are some consequent simplifications yet to be made, like not using a separate EState for subplans in the executor, but I'll tackle that later.
* Remove the Query structure from the executor's API. This allows us to stopTom Lane2007-02-201-3/+3
| | | | | | | | | | | | | | | storing mostly-redundant Query trees in prepared statements, portals, etc. To replace Query, a new node type called PlannedStmt is inserted by the planner at the top of a completed plan tree; this carries just the fields of Query that are still needed at runtime. The statement lists kept in portals etc. now consist of intermixed PlannedStmt and bare utility-statement nodes --- no Query. This incidentally allows us to remove some fields from Query and Plan nodes that shouldn't have been there in the first place. Still to do: simplify the execution-time range table; at the moment the range table passed to the executor still contains Query trees for subqueries. initdb forced due to change of stored rules.
* Get rid of some old and crufty global variables in the planner. WhenTom Lane2007-02-193-19/+11
| | | | | | | | | this code was last gone over, there wasn't really any alternative to globals because we didn't have the PlannerInfo struct being passed all through the planner code. Now that we do, we can restructure things to avoid non-reentrancy. I'm fooling with this because otherwise I'd have had to add another global variable for the planned compact range table list.
* Restructure code that is responsible for ensuring that clauseless joins areTom Lane2007-02-161-1/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | considered when it is necessary to do so because of a join-order restriction (that is, an outer-join or IN-subselect construct). The former coding was a bit ad-hoc and inconsistent, and it missed some cases, as exposed by Mario Weilguni's recent bug report. His specific problem was that an IN could be turned into a "clauseless" join due to constant-propagation removing the IN's joinclause, and if the IN's subselect involved more than one relation and there was more than one such IN linking to the same upper relation, then the only valid join orders involve "bushy" plans but we would fail to consider the specific paths needed to get there. (See the example case added to the join regression test.) On examining the code I wonder if there weren't some other problem cases too; in particular it seems that GEQO was defending against a different set of corner cases than the main planner was. There was also an efficiency problem, in that when we did realize we needed a clauseless join because of an IN, we'd consider clauseless joins against every other relation whether this was sensible or not. It seems a better design is to use the outer-join and in-clause lists as a backup heuristic, just as the rule of joining only where there are joinclauses is a heuristic: we'll join two relations if they have a usable joinclause *or* this might be necessary to satisfy an outer-join or IN-clause join order restriction. I refactored the code to have just one place considering this instead of three, and made sure that it covered all the cases that any of them had been considering. Backpatch as far as 8.1 (which has only the IN-clause form of the disease). By rights 8.0 and 7.4 should have the bug too, but they accidentally fail to fail, because the joininfo structure used in those releases preserves some memory of there having once been a joinclause between the inner and outer sides of an IN, and so it leads the code in the right direction anyway. I'll be conservative and not touch them.
* Add COST and ROWS options to CREATE/ALTER FUNCTION, plus underlying pg_procTom Lane2007-01-223-3/+6
| | | | | | | | | | | | columns procost and prorows, to allow simple user adjustment of the estimated cost of a function call, as well as control of the estimated number of rows returned by a set-returning function. We might eventually wish to extend this to allow function-specific estimation routines, but there seems to be consensus that we should try a simple constant estimate first. In particular this provides a relatively simple way to control the order in which different WHERE clauses are applied in a plan node, which is a Good Thing in view of the fact that the recent EquivalenceClass planner rewrite made that much less predictable than before.
* Refactor planner's pathkeys data structure to create a separate, explicitTom Lane2007-01-205-30/+69
| | | | | | | | | | | | | | representation of equivalence classes of variables. This is an extensive rewrite, but it brings a number of benefits: * planner no longer fails in the presence of "incomplete" operator families that don't offer operators for every possible combination of datatypes. * avoid generating and then discarding redundant equality clauses. * remove bogus assumption that derived equalities always use operators named "=". * mergejoins can work with a variety of sort orders (e.g., descending) now, instead of tying each mergejoinable operator to exactly one sort order. * better recognition of redundant sort columns. * can make use of equalities appearing underneath an outer join.
* Change the planner-to-executor API so that the planner tells the executorTom Lane2007-01-102-6/+7
| | | | | | | | | | | | | | | | which comparison operators to use for plan nodes involving tuple comparison (Agg, Group, Unique, SetOp). Formerly the executor looked up the default equality operator for the datatype, which was really pretty shaky, since it's possible that the data being fed to the node is sorted according to some nondefault operator class that could have an incompatible idea of equality. The planner knows what it has sorted by and therefore can provide the right equality operator to use. Also, this change moves a couple of catalog lookups out of the executor and into the planner, which should help startup time for pre-planned queries by some small amount. Modify the planner to remove some other cavalier assumptions about always being able to use the default operators. Also add "nulls first/last" info to the Plan node for a mergejoin --- neither the executor nor the planner can cope yet, but at least the API is in place.
* Update CVS HEAD for 2007 copyright. Back branches are typically notBruce Momjian2007-01-0523-46/+46
| | | | back-stamped for this.
* Restructure operator classes to allow improved handling of cross-data-typeTom Lane2006-12-231-1/+3
| | | | | | | | | | | | | | | | cases. Operator classes now exist within "operator families". While most families are equivalent to a single class, related classes can be grouped into one family to represent the fact that they are semantically compatible. Cross-type operators are now naturally adjunct parts of a family, without having to wedge them into a particular opclass as we had done originally. This commit restructures the catalogs and cleans up enough of the fallout so that everything still works at least as well as before, but most of the work needed to actually improve the planner's behavior will come later. Also, there are not yet CREATE/DROP/ALTER OPERATOR FAMILY commands; the only way to create a new family right now is to allow CREATE OPERATOR CLASS to make one by default. I owe some more documentation work, too. But that can all be done in smaller pieces once this infrastructure is in place.
* Fix planner to do the right thing when a degenerate outer join (one whoseTom Lane2006-12-121-2/+3
| | | | | | | joinclause doesn't use any outer-side vars) requires a "bushy" plan to be created. The normal heuristic to avoid joins with no joinclause has to be overridden in that case. Problem is new in 8.2; before that we forced the outer join order anyway. Per example from Teodor.
* pgindent run for 8.2.Bruce Momjian2006-10-045-15/+15
|
* Increase default value of effective_cache_size to 128MB, per discussion.Tom Lane2006-09-251-2/+2
|
* Improve usage of effective_cache_size parameter by assuming that all theTom Lane2006-09-192-4/+5
| | | | | | | | | | | tables in the query compete for cache space, not just the one we are currently costing an indexscan for. This seems more realistic, and it definitely will help in examples recently exhibited by Stefan Kaltenbrunner. To get the total size of all the tables involved, we must tweak the handling of 'append relations' a bit --- formerly we looked up information about the child tables on-the-fly during set_append_rel_pathlist, but it needs to be done before we start doing any cost estimation, so push it into the add_base_rels_to_query scan.
* Add INSERT/UPDATE/DELETE RETURNING, with basic docs and regression tests.Tom Lane2006-08-121-1/+4
| | | | | | | | plpgsql support to come later. Along the way, convert execMain's SELECT INTO support into a DestReceiver, in order to eliminate some ugly special cases. Jonah Harris and Tom Lane
* Add support for multi-row VALUES clauses as part of INSERT statementsJoe Conway2006-08-022-2/+6
| | | | | | (e.g. "INSERT ... VALUES (...), (...), ...") and elsewhere as allowed by the spec. (e.g. similar to a FROM clause subselect). initdb required. Joe Conway and Tom Lane.
* Change the relation_open protocol so that we obtain lock on a relationTom Lane2006-07-311-2/+2
| | | | | | | | | | | | (table or index) before trying to open its relcache entry. This fixes race conditions in which someone else commits a change to the relation's catalog entries while we are in process of doing relcache load. Problems of that ilk have been reported sporadically for years, but it was not really practical to fix until recently --- for instance, the recent addition of WAL-log support for in-place updates helped. Along the way, remove pg_am.amconcurrent: all AMs are now expected to support concurrent update.
* Convert effective_cache_size to an integer, for better integration withPeter Eisentraut2006-07-261-3/+3
| | | | upcoming units feature.
* Change LIMIT/OFFSET to use int8Bruce Momjian2006-07-261-2/+2
| | | | Dhanaraj M
* In the recent changes to make the planner account better for cacheTom Lane2006-07-222-4/+4
| | | | | | | effects in a nestloop inner indexscan, I had only dealt with plain index scans and the index portion of bitmap scans. But there will be cache benefits for the heap accesses of bitmap scans too, so fix cost_bitmap_heap_scan() to account for that.
* Fix some missing inclusions identified with new pgcheckdefines tool.Tom Lane2006-07-151-1/+2
|
* Allow include files to compile own their own.Bruce Momjian2006-07-131-3/+1
| | | | | | | Strip unused include files out unused include files, and add needed includes to C files. The next step is to remove unused include files in C files.
* Revise the planner's handling of "pseudoconstant" WHERE clauses, that isTom Lane2006-07-014-10/+11
| | | | | | | | | | | | | | | | | | | clauses containing no variables and no volatile functions. Such a clause can be used as a one-time qual in a gating Result plan node, to suppress plan execution entirely when it is false. Even when the clause is true, putting it in a gating node wins by avoiding repeated evaluation of the clause. In previous PG releases, query_planner() would do this for pseudoconstant clauses appearing at the top level of the jointree, but there was no ability to generate a gating Result deeper in the plan tree. To fix it, get rid of the special case in query_planner(), and instead process pseudoconstant clauses through the normal RestrictInfo qual distribution mechanism. When a pseudoconstant clause is found attached to a path node in create_plan(), pull it out and generate a gating Result at that point. This requires special-casing pseudoconstants in selectivity estimation and cost_qual_eval, but on the whole it's pretty clean. It probably even makes the planner a bit faster than before for the normal case of no pseudoconstants, since removing pull_constant_clauses saves one useless traversal of the qual tree. Per gripe from Phil Frost.
* Make the planner estimate costs for nestloop inner indexscans on the basisTom Lane2006-06-063-10/+11
| | | | | | | | | | | | | | | | | | | | | that the Mackert-Lohmann formula applies across all the repetitions of the nestloop, not just each scan independently. We use the M-L formula to estimate the number of pages fetched from the index as well as from the table; that isn't what it was designed for, but it seems reasonably applicable anyway. This makes large numbers of repetitions look much cheaper than before, which accords with many reports we've received of overestimation of the cost of a nestloop. Also, change the index access cost model to charge random_page_cost per index leaf page touched, while explicitly not counting anything for access to metapage or upper tree pages. This may all need tweaking after we get some field experience, but in simple tests it seems to be giving saner results than before. The main thing is to get the infrastructure in place to let cost_index() and amcostestimate functions take repeated scans into account at all. Per my recent proposal. Note: this patch changes pg_proc.h, but I did not force initdb because the changes are basically cosmetic --- the system does not look into pg_proc to decide how to call an index amcostestimate function, and there's no way to call such a function from SQL at all.
* Increase the default value of cpu_index_tuple_cost from 0.001 to 0.005.Tom Lane2006-06-051-2/+2
| | | | | | This shouldn't affect simple indexscans much, while for bitmap scans that are touching a lot of index rows, this seems to bring the estimates more in line with reality. Per recent discussion.
* Add a GUC parameter seq_page_cost, and use that everywhere we formerlyTom Lane2006-06-051-6/+9
| | | | | | | | assumed that a sequential page fetch has cost 1.0. This patch doesn't in itself change the system's behavior at all, but it opens the door to people adopting other units of measurement for EXPLAIN costs. Also, if we ever decide it's worth inventing per-tablespace access cost settings, this change provides a workable intellectual framework for that.
* Update copyright for 2006. Update scripts.Bruce Momjian2006-03-0523-46/+46
|
* Improve my initial, rather hacky implementation of joins to appendTom Lane2006-02-051-8/+1
| | | | | | | | relations: fix the executor so that we can have an Append plan on the inside of a nestloop and still pass down outer index keys to index scans within the Append, then generate such plans as if they were regular inner indexscans. This avoids the need to evaluate the outer relation multiple times.
* Fix constraint exclusion to work in inherited UPDATE/DELETE queriesTom Lane2006-02-041-2/+3
| | | | | | | | | ... in fact, it will be applied now in any query whatsoever. I'm still a bit concerned about the cycles that might be expended in failed proof attempts, but given that CE is turned off by default, it's the user's choice whether to expend those cycles or not. (Possibly we should change the simple bool constraint_exclusion parameter to something more fine-grained?)
* Teach planner to convert simple UNION ALL subqueries into append relations,Tom Lane2006-02-033-9/+13
| | | | | | | | | thereby sharing code with the inheritance case. This puts the UNION-ALL-view approach to partitioned tables on par with inheritance, so far as constraint exclusion is concerned: it works either way. (Still need to update the docs to say so.) The definition of "simple UNION ALL" is a little simpler than I would like --- basically the union arms can only be SELECT * FROM foo --- but it's good enough for partitioned-table cases.
* Update random() usage so ranges are inclusive/exclusive as required.Bruce Momjian2006-02-031-2/+2
|
* Restructure planner's handling of inheritance. Rather than processingTom Lane2006-01-312-8/+16
| | | | | | | | | | | | | inheritance trees on-the-fly, which pretty well constrained us to considering only one way of planning inheritance, expand inheritance sets during the planner prep phase, and build a side data structure that can be consulted later to find which RTEs are members of which inheritance sets. As proof of concept, use the data structure to plan joins against inheritance sets more efficiently: we can now use indexes on the set members in inner-indexscan joins. (The generated plans could be improved further, but it'll take some executor changes.) This data structure will also support handling UNION ALL subqueries in the same way as inheritance sets, but that aspect of it isn't finished yet.
* Fix code that checks to see if an index can be considered to match the query'sTom Lane2006-01-291-2/+2
| | | | | | | | | requested sort order. It was assuming that build_index_pathkeys always generates a pathkey per index column, which was not true if implied equality deduction had determined that two index columns were effectively equated to each other. Simplest fix seems to be to install an option that causes build_index_pathkeys to support this behavior as well as the original one. Per report from Brian Hirt.
* Allow row comparisons to be used as indexscan qualifications.Tom Lane2006-01-251-2/+4
| | | | This completes the project to upgrade our handling of row comparisons.
* Teach planner how to rearrange join order for some classes of OUTER JOIN.Tom Lane2005-12-204-15/+11
| | | | | | Per my recent proposal. I ended up basing the implementation on the existing mechanism for enforcing valid join orders of IN joins --- the rules for valid outer-join orders are somewhat similar.
* Teach tid-scan code to make use of "ctid = ANY (array)" clauses, so thatTom Lane2005-11-262-4/+4
| | | | | | | "ctid IN (list)" will still work after we convert IN to ScalarArrayOpExpr. Make some minor efficiency improvements while at it, such as ensuring that multiple TIDs are fetched in physical heap order. And fix EXPLAIN so that it shows what's really going on for a TID scan.
* Teach planner and executor to handle ScalarArrayOpExpr as an indexableTom Lane2005-11-251-1/+10
| | | | | | | | | | | qualification when the underlying operator is indexable and useOr is true. That is, indexkey op ANY (ARRAY[...]) is effectively translated into an OR combination of one indexscan for each array element. This only works for bitmap index scans, of course, since regular indexscans no longer support OR'ing of scans. There are still some loose ends to clean up before changing 'x IN (list)' to translate as a ScalarArrayOpExpr; for instance predtest.c ought to be taught about it. But this gets the basic functionality in place.
* Restore the former RestrictInfo field valid_everywhere (but invert the flagTom Lane2005-11-141-1/+2
| | | | | | | | | | sense and rename to "outerjoin_delayed" to more clearly reflect what it means). I had decided that it was redundant in 8.1, but the folly of this is exposed by a bug report from Sebastian Böck. The place where it's needed is to prevent orindxpath.c from cherry-picking arms of an outer-join OR clause to form a relation restriction that isn't actually legal to push down to the relation scan level. There may be some legal cases that this forbids optimizing, but we'd need much closer analysis to determine it.
* Standard pgindent run for 8.1.Bruce Momjian2005-10-1511-49/+48
|
* Repair planning bug introduced in 7.4: outer-join ON clauses that referencedTom Lane2005-09-281-2/+3
| | | | | | only the inner-side relation would be considered as potential equijoin clauses, which is wrong because the condition doesn't necessarily hold above the point of the outer join. Per test case from Kevin Grittner (bug#1916).
* Change the division of labor between grouping_planner and query_plannerTom Lane2005-08-272-6/+4
| | | | | | | | | | | | | | so that the latter estimates the number of groups that grouping will produce. This is needed because it is primarily query_planner that makes the decision between fast-start and fast-finish plans, and in the original coding it was unable to make more than a crude rule-of-thumb choice when the query involved grouping. This revision helps us make saner choices for queries like SELECT ... GROUP BY ... LIMIT, as in a recent example from Mark Kirkwood. Also move the responsibility for canonicalizing sort_pathkeys and group_pathkeys into query_planner; this information has to be available anyway to support the first change, and doing it this way lets us get rid of compare_noncanonical_pathkeys entirely.
* enable_constraint_exclusion => constraint_exclusionBruce Momjian2005-08-221-2/+2
| | | | Also improve wording.
* Fix up LIMIT/OFFSET planning so that we cope with non-constant LIMITTom Lane2005-08-181-2/+3
| | | | | | | | | | or OFFSET clauses by using estimate_expression_value(). The main advantage of this is that if the expression is a Param and we have a value for the Param, we'll use that value rather than defaulting. Also, fix some thinkos in the logic for combining LIMIT/OFFSET with an externally supplied tuple fraction (this covers cases like EXISTS(...LIMIT...)). And make sure the results of all this are shown by EXPLAIN. Per a gripe from Merlin Moncure.
* Fix a bunch of bad interactions between partial indexes and the newTom Lane2005-07-282-4/+6
| | | | | | | | planning logic for bitmap indexscans. Partial indexes create corner cases in which a scan might be done with no explicit index qual conditions, and the code wasn't handling those cases nicely. Also be a little tenser about eliminating redundant clauses in the generated plan. Per report from Dmitry Karasik.
* Simple constraint exclusion. For now, only child tables of inheritanceTom Lane2005-07-233-3/+8
| | | | | scans are candidates for exclusion; this should be fixed eventually. Simon Riggs, with some help from Tom Lane.
View Lorry Controller Status