by creating a reference-count mechanism, similar to what we did a long time
ago for catcache entries.  The back branches have an ugly solution involving
lots of extra copies, but this way is more efficient.  Reference counting is
only applied to tupdescs that are actually in caches --- there seems no need
to use it for tupdescs that are generated in the executor, since they'll go
away during plan shutdown by virtue of being in the per-query memory context.
Neil Conway and Tom Lane

choose_bitmap_and().  It was way too fuzzy --- per comment, it was meant to be
1% relative difference, but was actually coded as 0.01 absolute difference,
thus causing selectivities of say 0.001 and 0.000000000001 to be treated as
equal.  I believe this thinko explains Maxim Boguk's recent complaint.  While
we could change it to a relative test coded like compare_fuzzy_path_costs(),
there's a bigger problem here, which is that any fuzziness at all renders the
comparison function non-transitive, which could confuse qsort() to the point
of delivering completely wrong results.  So forget the whole thing and just
do an exact comparison.

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.

cost_nonsequential_access() is really totally inappropriate for its only
remaining use, namely estimating I/O costs in cost_sort().  The routine
was designed on the assumption that disk caching might eliminate the need
for some re-reads on a random basis, but there's nothing very random in
that sense about sort's access pattern --- it'll always be picking up the
oldest outputs.  If we had a good fix on the effective cache size we
might consider charging zero for I/O unless the sort temp file size
exceeds it, but that's probably putting much too much faith in the
parameter.  Instead just drop the logic in favor of a fixed compromise
between seq_page_cost and random_page_cost per page of sort I/O.

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.

deciding whether a potential additional indexscan is redundant or not.  As now
coded, any use of a partial index that was already used in a previous AND arm
will be rejected as redundant.  This might be overly restrictive, but not
considering the point at all is definitely bad, as per example in bug #2441
from Arjen van der Meijden.  In particular, a clauseless scan of a partial
index was *never* considered redundant by the previous coding, and that's
surely wrong.  Being more flexible would also require some consideration
of how not to double-count the index predicate's selectivity.

the partial index predicate in the scan's "recheck condition".  Otherwise,
if the scan becomes lossy for lack of bitmap memory, we would fail to enforce
that returned rows satisfy the predicate.  Noted while studying bug #2441
from Arjen van der Meijden.

condition: when there are multiple possible index paths involving
ScalarArrayOpExprs, they are logically to be ANDed together not ORed.
This thinko was a direct consequence of trying to put the processing
inside generate_bitmap_or_paths(), which I now see was a bit too cute.
So pull it out and make the callers do it separately (there are only two
that need it anyway).  Partially responds to bug #2441 from Arjen van der Meijden.
There are some additional infelicities exposed by his example, but they
are also in 8.1.x, while this mistake is not.

initPlan sets a parameter for another.  This could not (I think) happen before
8.1, but it's possible now because the initPlans generated by MIN/MAX
optimization might themselves use initPlans.  We attach those initPlans as
siblings of the MIN/MAX ones, not children, to avoid duplicate computation
when multiple MIN/MAX aggregates are present; so this leads to the case of an
initPlan needing the result of a sibling initPlan, which is not possible with
ordinary query nesting.  Hadn't been noticed because in most contexts having
too much stuff listed in extParam is fairly harmless.  Fixes "plan should not
reference subplan's variable" bug reported by Catalin Pitis.

the union of its child relations as well.  This might have been a good idea
when it was originally coded, but it's a fatally bad idea when inheritance is
being used for partitioning.  It's better to have no stats at all than
completely misleading stats.  Per report from Mark Liberman.

The bug arguably exists all the way back, but I've only patched HEAD and 8.1
because we weren't particularly trying to support partitioning before 8.1.

Eventually we ought to look at deriving union statistics instead of just
punting, but for now the drop kick looks good.

support both FOR UPDATE and FOR SHARE in one command, as well as both
NOWAIT and normal WAIT behavior.  The more general code is actually
simpler and cleaner.

MIN/MAX not be converted to use an index if the query WHERE clause contains
any volatile functions or subplans.

I had originally feared that the conversion might alter the behavior of such a
query with respect to a volatile function.  Well, so it might, but only in the
sense that the function would get evaluated at a subset of the table rows
rather than all of them --- and we have never made any such guarantee anyway.
(For instance, we don't refuse to use an index for an ordinary non-aggregate
query when one of the non-indexable filter conditions contains a volatile
function.)

The prohibition against subplans was because of worry that that case wasn't
adequately tested, which it wasn't, but it turns out to be possible to make
8.1 fail anyway:

regression=# select o.ten, (select max(unique2) from tenk1 i where ten = o.ten
or ten = (select f1 from int4_tbl limit 1)) from tenk1 o;
ERROR:  direct correlated subquery unsupported as initplan

This is due to bogus code in SS_make_initplan_from_plan (it's an initplan,
ergo it can't have any parParams).  Having fixed that, we might as well allow
subplans as well as initplans.

implied by the predicate of a partial index being used to scan a table.
However, this optimization is unsafe in an UPDATE, DELETE, or SELECT FOR
UPDATE query, because the quals need to be rechecked by EvalPlanQual if
there's an update conflict.  Per example from Jean-Samuel Reynaud.

not named ones, and replace linear searches of the list with array indexing.
The named-parameter support has been dead code for many years anyway,
and recent profiling suggests that the searching was costing a noticeable
amount of performance for complex queries.

had a bad side-effect: it stopped finding plans that involved BitmapAnd
combinations of indexscans using both join and non-join conditions.  Instead,
make choose_bitmap_and more aggressive about detecting redundancies between
BitmapOr subplans.

at least one join condition as an indexqual.  Before bitmap indexscans, this
oversight didn't really cost much except for redundantly considering the
same join paths twice; but as of 8.1 it could result in silly bitmap scans
that would do the same BitmapOr twice and then BitmapAnd these together :-(

output, ie, no OR immediately below an OR.  Otherwise we get Asserts or
wrong answers for cases such as
	select * from tenk1 a, tenk1 b
	where (a.ten = b.ten and (a.unique1 = 100 or a.unique1 = 101))
	   or (a.hundred = b.hundred and a.unique1 = 42);
Per report from Rafael Martinez Guerrero.

that apply the necessary domain constraint checks immediately.  This fixes
cases where domain constraints went unchecked for statement parameters,
PL function local variables and results, etc.  We can also eliminate existing
special cases for domains in places that had gotten it right, eg COPY.

Also, allow domains over domains (base of a domain is another domain type).
This almost worked before, but was disallowed because the original patch
hadn't gotten it quite right.

during parse analysis, not only errors detected in the flex/bison stages.
This is per my earlier proposal.  This commit includes all the basic
infrastructure, but locations are only tracked and reported for errors
involving column references, function calls, and operators.  More could
be done later but this seems like a good set to start with.  I've also
moved the ReportSyntaxErrorPosition logic out of psql and into libpq,
which should make it available to more people --- even within psql this
is an improvement because warnings weren't handled by ReportSyntaxErrorPosition.

not likely ever to be implemented seeing it's been removed from SQL2003.
This allows getting rid of the 'filter' version of yylex() that we had in
parser.c, which should save at least a few microseconds in parsing.

with fixed merge order (fixed number of "tapes") was based on obsolete
assumptions, namely that tape drives are expensive.  Since our "tapes"
are really just a couple of buffers, we can have a lot of them given
adequate workspace.  This allows reduction of the number of merge passes
with consequent savings of I/O during large sorts.

Simon Riggs with some rework by Tom Lane

Var referencing the subselect output.  While this case could possibly be made
to work, it seems not worth expending effort on.  Per report from Magnus
Naeslund(f).

would basically punt in all cases for 'foo <> ALL (array)', which resulted
in a performance regression for NOT IN compared to what we were doing in
8.1 and before.  Per report from Pavel Stehule.

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.

... 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?)

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.

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.

to avoid sharing substructure with the lower-level indexquals.  This is
currently only an issue if there are SubPlans in the indexquals, which is
uncommon but not impossible --- see bug #2218 reported by Nicholas Vinen.
We use the same kluge for indexqual vs indexqualorig in the index scans
themselves ... would be nice to clean this up someday.

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.

and rely exclusively on the SQL type system to tell the difference between
the types.  Prevent creation of invalid CIDR values via casting from INET
or set_masklen() --- both of these operations now silently zero any bits
to the right of the netmask.  Remove duplicate CIDR comparison operators,
letting the type rely on the INET operators instead.

This completes the project to upgrade our handling of row comparisons.

but a lot better than nothing at all ...

http://archives.postgresql.org/pgsql-hackers/2006-01/msg00151.php for the
complete plan.

(previously we only did = and <> correctly).  Also, allow row comparisons
with any operators that are in btree opclasses, not only those with these
specific names.  This gets rid of a whole lot of indefensible assumptions
about the behavior of particular operators based on their names ... though
it's still true that IN and NOT IN expand to "= ANY".  The patch adds a
RowCompareExpr expression node type, and makes some changes in the
representation of ANY/ALL/ROWCOMPARE SubLinks so that they can share code
with RowCompareExpr.

I have not yet done anything about making RowCompareExpr an indexable
operator, but will look at that soon.

initdb forced due to changes in stored rules.

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.

clauses even if it's an outer join.  This is a corner case since such
clauses could only arise from weird OUTER JOIN ON conditions, but worth
fixing.  Per example from Ron at cheapcomplexdevices.com.

#2075: consider an index redundant if any of its index conditions were already
used, rather than if all of them were.  Also, make the selectivity comparison
a bit fuzzy, so that very small differences in estimated selectivities don't
skew the results.