CVS log for pgsql/src/backend/optimizer/util/joininfo.c

Up to [PostgreSQL CVS Repository] / pgsql / src / backend / optimizer / util

Request diff between arbitrary revisions - Display revisions graphically

Keyword substitution: kv
Default branch: MAIN

Fix join-removal logic for pseudoconstant and outerjoin-delayed quals.

In these cases a qual can get marked with the removable rel in its
required_relids, but this is just to schedule its evaluation correctly, not
because it really depends on the rel.  We were assuming that, in effect,
we could throw away *all* quals so marked, which is nonsense.  Tighten up
the logic to be a little more paranoid about which quals belong to the
outer join being considered for removal, and arrange for all quals that
don't belong to be updated so they will still get evaluated correctly.

Also fix another problem that happened to be exposed by this test case,
which was that make_join_rel() was failing to notice some cases where
a constant-false qual could be used to prove a join relation empty.  If it's
a pushed-down constant false, then the relation is empty even if it's an
outer join, because the qual applies after the outer join expansion.

Per report from Nathan Grange.  Back-patch into 9.0.

Fix join-removal logic for pseudoconstant and outerjoin-delayed quals.

In these cases a qual can get marked with the removable rel in its
required_relids, but this is just to schedule its evaluation correctly, not
because it really depends on the rel.  We were assuming that, in effect,
we could throw away *all* quals so marked, which is nonsense.  Tighten up
the logic to be a little more paranoid about which quals belong to the
outer join being considered for removal, and arrange for all quals that
don't belong to be updated so they will still get evaluated correctly.

Also fix another problem that happened to be exposed by this test case,
which was that make_join_rel() was failing to notice some cases where
a constant-false qual could be used to prove a join relation empty.  If it's
a pushed-down constant false, then the relation is empty even if it's an
outer join, because the qual applies after the outer join expansion.

Per report from Nathan Grange.  Back-patch into 9.0.

Update copyright for the year 2010.

Update copyright for 2009.

Update copyrights in source tree to 2008.

pgindent run for 8.3.

Restructure code that is responsible for ensuring that clauseless joins are
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.

Restructure code that is responsible for ensuring that clauseless joins are
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.

Refactor planner's pathkeys data structure to create a separate, explicit
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.

Update CVS HEAD for 2007 copyright.  Back branches are typically not
back-stamped for this.

Fix planner to do the right thing when a degenerate outer join (one whose
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.

Fix planner to do the right thing when a degenerate outer join (one whose
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.

Update copyright for 2006.  Update scripts.

Simplify the planner's join clause management by storing join clauses
of a relation in a flat 'joininfo' list.  The former arrangement grouped
the join clauses according to the set of unjoined relids used in each;
however, profiling on test cases involving lots of joins proves that
that data structure is a net loss.  It takes more time to group the
join clauses together than is saved by avoiding duplicate tests later.
It doesn't help any that there are usually not more than one or two
clauses per group ...

Remove planner's private fields from Query struct, and put them into
a new PlannerInfo struct, which is passed around instead of the bare
Query in all the planning code.  This commit is essentially just a
code-beautification exercise, but it does open the door to making
larger changes to the planner data structures without having to muck
with the widely-known Query struct.

Tag appropriate files for rc3

Also performed an initial run through of upgrading our Copyright date to
extend to 2005 ... first run here was very simple ... change everything
where: grep 1996-2004 && the word 'Copyright' ... scanned through the
generated list with 'less' first, and after, to make sure that I only
picked up the right entries ...

Update copyright to 2004.

Use the new List API function names throughout the backend, and disable the
list compatibility API by default. While doing this, I decided to keep
the llast() macro around and introduce llast_int() and llast_oid() variants.

Reimplement the linked list data structure used throughout the backend.

In the past, we used a 'Lispy' linked list implementation: a "list" was
merely a pointer to the head node of the list. The problem with that
design is that it makes lappend() and length() linear time. This patch
fixes that problem (and others) by maintaining a count of the list
length and a pointer to the tail node along with each head node pointer.
A "list" is now a pointer to a structure containing some meta-data
about the list; the head and tail pointers in that structure refer
to ListCell structures that maintain the actual linked list of nodes.

The function names of the list API have also been changed to, I hope,
be more logically consistent. By default, the old function names are
still available; they will be disabled-by-default once the rest of
the tree has been updated to use the new API names.

$Header: -> $PostgreSQL Changes ...

Update copyrights to 2003.

pgindent run.

Replace planner's representation of relation sets, per pghackers discussion.
Instead of Lists of integers, we now store variable-length bitmap sets.
This should be faster as well as less error-prone.

Modify planner's implied-equality-deduction code so that when a set
of known-equal expressions includes any constant expressions (including
Params from outer queries), we actively suppress any 'var = var'
clauses that are or could be deduced from the set, generating only the
deducible 'var = const' clauses instead.  The idea here is to push down
the restrictions implied by the equality set to base relations whenever
possible.  Once we have applied the 'var = const' clauses, the 'var = var'
clauses are redundant, and should be suppressed both to save work at
execution and to avoid double-counting restrictivity.

IN clauses appearing at top level of WHERE can now be handled as joins.
There are two implementation techniques: the executor understands a new
JOIN_IN jointype, which emits at most one matching row per left-hand row,
or the result of the IN's sub-select can be fed through a DISTINCT filter
and then joined as an ordinary relation.
Along the way, some minor code cleanup in the optimizer; notably, break
out most of the jointree-rearrangement preprocessing in planner.c and
put it in a new file prep/prepjointree.c.

Update copyright to 2002.

pgindent run on all C files.  Java run to follow.  initdb/regression
tests pass.

pgindent run.  Make it all clean.

Change Copyright from PostgreSQL, Inc to PostgreSQL Global Development Group.

Mark functions as static and ifdef NOT_USED as appropriate.

Rename same() to sameseti() to have a slightly less generic name.  Move
nonoverlap_sets() and is_subset() to list.c, where they should have lived
to begin with, and rename to nonoverlap_setsi and is_subseti since they
only work on integer lists.

Add:

  * Portions Copyright (c) 1996-2000, PostgreSQL, Inc

to all files copyright Regents of Berkeley.  Man, that's a lot of files.

Major planner/optimizer revision: get rid of PathOrder node type,
store all ordering information in pathkeys lists (which are now lists of
lists of PathKeyItem nodes, not just lists of lists of vars).  This was
a big win --- the code is smaller and IMHO more understandable than it
was, even though it handles more cases.  I believe the node changes will
not force an initdb for anyone; planner nodes don't show up in stored
rules.

Final round before bed...more tomorrow...

Final cleanup.

Remove unused #includes in *.c files.

Another pgindent run.  Sorry folks.

pgindent run over code.

Final optimizer cleanups.

Fix bushy plans.  Cleanup.

otherrels is now unjoined_rels

Remove duplicate geqo functions, and more optimizer cleanup

Change my-function-name-- to my_function_name, and optimizer renames.

Optmizer cleanup

Optimizer rename ClauseInfo -> RestrictInfo.  Update optimizer README.

OK, folks, here is the pgindent output.

Renaming cleanup, no pgindent yet.

Cleanup optimizer function names and clarify code.

MergeSort was sometimes called mergejoin and was confusing.  Now
it is now only mergejoin.

Rename Rel to RelOptInfo.

Remove un-needed braces around single statements.

pgindent run before 6.3 release, with Thomas' requested changes.

Used modified version of indent that understands over 100 typedefs.

Another PGINDENT run that changes variable indenting and case label indenting.  Also static variable indenting.

Massive commit to run PGINDENT on all *.c and *.h files.

All external function definitions now have prototypes that are checked.

Postgres95 1.01 Distribution - Virgin Sources

Initial revision