Обсуждение: Rethinking representation of sort/hash semantics in queries and plans
In recent discussions of the plan-tree representation for KNNGIST index
scans, there seemed to be agreement that it'd be a good idea to explicitly
represent the expected sort ordering of the output. While thinking about
how best to do that, it struck me that there's some pretty horrendous
impedance mismatches in the way we do things now. Different parts of the
system use two different representations of sort ordering:
* A sort operator (which can have < or > semantics) plus nulls-first flag
* A btree opfamily plus direction and nulls-first flags
Getting from one of these representations to the other is not exactly
cheap, as it requires one or more syscache lookups. But consider what
happens when we process a simple SELECT ... ORDER BY query to produce
a Sort plan:
1. The parser generates a SortGroupClause, which contains the
sort-operator representation. This involves looking up the default btree
opclass for the ORDER BY column's datatype, then finding the < or > member
of the opclass. (These lookups are buffered by the typcache, but we'll
still have to do them at least once per session.) If you use ORDER BY
USING then you might think it's cheaper ... but we still do a lookup to
verify that the operator is in some btree family.
2. The planner generates a PathKey, which is based on the opfamily
representation, so we have to do get_ordering_op_properties to go back the
other way.
3. If a sort plan is chosen, createplan.c uses get_opfamily_member to go
from the PathKey representation back to sort-operator representation,
because the Sort plan node type stores sort operators.
4. At runtime, tuplesort_begin_heap needs the comparison function for the
sort operator, so it calls get_ordering_op_properties *again* to re-derive
the opfamily, from which it can extract the right support function using
get_opfamily_proc.
Things are only marginally less comical if an indexscan plan is chosen,
and that's only because the IndexScan plan node doesn't contain any
explicit representation of the output sort order. If we were to solve the
KNNGIST issue by installing sort operator lists in IndexScan, it'd be
about as ugly as this. (For some extra amusement, trace through where
build_index_pathkeys' data comes from...)
I have not traced through the behavior for hash-based plans as carefully,
but I believe that there are a similar number of conversions between
operator OID and hash opfamily OID representations.
We got into this mess by revising the planner to use opfamily OIDs to
define sort/hash semantics without changing the structures that are its
input and output APIs. I think it's probably time to fix this. I don't
have any evidence at the moment about what fraction of SearchSysCache load
is coming from these repeated conversions, but it can't be trivial. And
quite aside from any performance benefits, it would be conceptually
cleaner to have only one representation of sort semantics not two.
If you look closely at what we're doing with sort operators
(get_ordering_op_properties pretty much encapsulates this), it turns out
that a sort operator is shorthand for three pieces of information:
1. btree opfamily OID
2. specific input datatype for the opfamily
3. ascending or descending direction
So to fix these problems we'd need to replace sort operator OIDs in
SortGroupClause and plan nodes with those three items. Obviously, this
would be slightly bulkier, but the extra cost added to copying parse and
plan trees should be tiny compared to the avoided syscache lookups.
A possible compromise is to avoid storing the specific input datatype.
In most cases it's the same as the column datatype or expression datatype
that we're feeding to the sort operation, which I believe we can always
get from somewhere else in the plan. However, it can be different in
binary-compatibility cases (such as feeding a specific array type to
anyarray_ops, or varchar to text_ops). If we don't store it then we'd
need to add extra complexity in get_opfamily_proc and similar places
to search for a binary-compatible member function or operator. This
extra cost would be paid only when actually using binary-compatible
cases, but it still seems like it'd be better to pay a little extra
storage to avoid it.
In a similar fashion, I think that the eqop member of SortGroupClause
should be replaced by a hash opfamily OID and specific input datatype
(no direction needed here, of course), and likewise for hash operator
OIDs in hash-based plan node types.
A possible objection to this idea is that instead of having stored rules
and views depending on specific operators, they'd now be shown as
depending on specific opfamilies. If you were to drop the relevant
operators then you'd get failures at runtime because no suitable member
operator or function could be found. However, with the current scheme
it's possible to drop the opfamily that makes use of a particular operator
valid in a given query context; so you can still get a failure, though it
would happen a bit upstream in the planner when it fails to locate the
opfamily. On balance I don't think this is any better or worse, just
different. We don't support dynamic modification of opclasses terribly
well anyhow, given all the caching that is done for them.
Thoughts, objections?
regards, tom lane
Re: Rethinking representation of sort/hash semantics in queries and plans
От
Martijn van Oosterhout
Дата:
On Sat, Nov 27, 2010 at 10:02:33PM -0500, Tom Lane wrote: > In recent discussions of the plan-tree representation for KNNGIST index > scans, there seemed to be agreement that it'd be a good idea to explicitly > represent the expected sort ordering of the output. While thinking about > how best to do that, it struck me that there's some pretty horrendous > impedance mismatches in the way we do things now. Different parts of the > system use two different representations of sort ordering: > > * A sort operator (which can have < or > semantics) plus nulls-first flag > > * A btree opfamily plus direction and nulls-first flags Sounds like a good idea to me. Quite aside from the performance issues, having one way to represent things will make it clearer what's going on and easier to extend in the future. Have a nice day, -- Martijn van Oosterhout <kleptog@svana.org> http://svana.org/kleptog/ > Patriotism is when love of your own people comes first; nationalism, > when hate for people other than your own comes first. > - Charles de Gaulle
Tom Lane <tgl@sss.pgh.pa.us> writes: > If you look closely at what we're doing with sort operators > (get_ordering_op_properties pretty much encapsulates this), it turns out > that a sort operator is shorthand for three pieces of information: > > 1. btree opfamily OID > 2. specific input datatype for the opfamily > 3. ascending or descending direction > > So to fix these problems we'd need to replace sort operator OIDs in > SortGroupClause and plan nodes with those three items. Obviously, this > would be slightly bulkier, but the extra cost added to copying parse and > plan trees should be tiny compared to the avoided syscache lookups. > > A possible compromise is to avoid storing the specific input datatype. My understanding is that opfamily+datatype gives an opclass. What about storing the opclass OID there? Other than that, cleaning up the current situation by having as good an view of the bigger picture as what you have now sounds great. Regards, -- Dimitri Fontaine http://2ndQuadrant.fr PostgreSQL : Expertise, Formation et Support
Dimitri Fontaine <dimitri@2ndQuadrant.fr> writes:
> Tom Lane <tgl@sss.pgh.pa.us> writes:
>> So to fix these problems we'd need to replace sort operator OIDs in
>> SortGroupClause and plan nodes with those three items. Obviously, this
>> would be slightly bulkier, but the extra cost added to copying parse and
>> plan trees should be tiny compared to the avoided syscache lookups.
> My understanding is that opfamily+datatype gives an opclass. What about
> storing the opclass OID there?
Then you'd just need to look up the opfamily again. Opclasses are too
small a division to be useful.
regards, tom lane
I wrote:
> (For some extra amusement, trace through where
> build_index_pathkeys' data comes from...)
While I don't propose to implement right away the whole SortGroupClause
and plan tree modification sketched above, I did look into fixing
build_index_pathkeys so that it doesn't uselessly convert from
opfamilies to sort operators and back again. The main reason this is
relevant at the moment is that we could get rid of relcache.c's caching
of operators related to indexes, which seems possibly useful in
connection with the current discussion of backend startup time.
What becomes apparent when you look closely at what that code is doing
is that it's catering to the possibility of an amcanorder index access
method that isn't btree. As things stand in HEAD, an add-on index
access method would be recognized as supporting ordering so long as it
registers the regular comparison operators (<, >, etc) with the same
index strategy numbers as btree. The reason that it would work is that
those operators would be found as the fwdsortop/revsortop entries for
the index, and then looking up those operator OIDs in btree opfamilies
would locate the corresponding btree opfamily OIDs, which is what you
have to have to match to a pathkey's opfamily.
In the attached draft patch that would no longer work, because the new
access method would have to have the exact same opfamily OIDs as btree
in order to match to btree-derived pathkeys --- and of course it can't
have that, since access method is a property of an opfamily.
Now, this loss of flexibility doesn't particularly bother me, because
I know of no existing or contemplated btree-substitute access methods.
If one did appear on the horizon, there are a couple of ways we could
fix the problem, the cleanest being to let a non-btree opfamily declare
that it sorts the same as btree opfamily so-and-so. Or we could fix
it locally in plancat.c by performing the lookup-the-operators-and-
then-the-btree-opfamilies dance on the fly when setting up IndexOptInfo
for a non-btree amcanorder index. But I'm disinclined to write such
code when there's no way to test it and no foreseeable possibility
that it'll ever be used. Maybe we should just make plancat.c throw
a not-implemented error if amcanorder is true but it's not btree.
Thoughts? Anyone particularly opposed to pursuing an optimization
of this kind at all?
regards, tom lane
PS: the attached patch doesn't yet include removal of relcache
rd_operator arrays, since that would just make the patch bigger
without exposing any new issues.
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index d8fc12068fb6113c0baf8aa4e5941e0150ce3521..f73e0e6dc6007ce768828480f74621752aaf57d2 100644
*** a/src/backend/optimizer/path/indxpath.c
--- b/src/backend/optimizer/path/indxpath.c
*************** find_usable_indexes(PlannerInfo *root, R
*** 380,386 ****
* how many of them are actually useful for this query. This is not
* relevant unless we are at top level.
*/
! index_is_ordered = OidIsValid(index->fwdsortop[0]);
if (index_is_ordered && possibly_useful_pathkeys &&
istoplevel && outer_rel == NULL)
{
--- 380,386 ----
* how many of them are actually useful for this query. This is not
* relevant unless we are at top level.
*/
! index_is_ordered = (index->sortopfamily != NULL);
if (index_is_ordered && possibly_useful_pathkeys &&
istoplevel && outer_rel == NULL)
{
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 8af0c6dc482372244b15a8a5f5a4a562e34ac91b..6325655eed84759168a51aed3f712582ec9c1f00 100644
*** a/src/backend/optimizer/path/pathkeys.c
--- b/src/backend/optimizer/path/pathkeys.c
*************** static PathKey *make_canonical_pathkey(P
*** 36,47 ****
EquivalenceClass *eclass, Oid opfamily,
int strategy, bool nulls_first);
static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys);
- static PathKey *make_pathkey_from_sortinfo(PlannerInfo *root,
- Expr *expr, Oid ordering_op,
- bool nulls_first,
- Index sortref,
- bool create_it,
- bool canonicalize);
static Var *find_indexkey_var(PlannerInfo *root, RelOptInfo *rel,
AttrNumber varattno);
static bool right_merge_direction(PlannerInfo *root, PathKey *pathkey);
--- 36,41 ----
*************** canonicalize_pathkeys(PlannerInfo *root,
*** 224,232 ****
/*
* make_pathkey_from_sortinfo
! * Given an expression, a sortop, and a nulls-first flag, create
! * a PathKey. If canonicalize = true, the result is a "canonical"
! * PathKey, otherwise not. (But note it might be redundant anyway.)
*
* If the PathKey is being generated from a SortGroupClause, sortref should be
* the SortGroupClause's SortGroupRef; otherwise zero.
--- 218,226 ----
/*
* make_pathkey_from_sortinfo
! * Given an expression and sort-order information, create a PathKey.
! * If canonicalize = true, the result is a "canonical" PathKey,
! * otherwise not. (But note it might be redundant anyway.)
*
* If the PathKey is being generated from a SortGroupClause, sortref should be
* the SortGroupClause's SortGroupRef; otherwise zero.
*************** canonicalize_pathkeys(PlannerInfo *root,
*** 240,285 ****
*/
static PathKey *
make_pathkey_from_sortinfo(PlannerInfo *root,
! Expr *expr, Oid ordering_op,
bool nulls_first,
Index sortref,
bool create_it,
bool canonicalize)
{
- Oid opfamily,
- opcintype;
int16 strategy;
Oid equality_op;
List *opfamilies;
EquivalenceClass *eclass;
/*
! * An ordering operator fully determines the behavior of its opfamily, so
! * could only meaningfully appear in one family --- or perhaps two if one
! * builds a reverse-sort opfamily, but there's not much point in that
! * anymore. But EquivalenceClasses need to contain opfamily lists based
! * on the family membership of equality operators, which could easily be
! * bigger. So, look up the equality operator that goes with the ordering
! * operator (this should be unique) and get its membership.
*/
-
- /* Find the operator in pg_amop --- failure shouldn't happen */
- if (!get_ordering_op_properties(ordering_op,
- &opfamily, &opcintype, &strategy))
- elog(ERROR, "operator %u is not a valid ordering operator",
- ordering_op);
- /* Get matching equality operator */
equality_op = get_opfamily_member(opfamily,
opcintype,
opcintype,
BTEqualStrategyNumber);
if (!OidIsValid(equality_op)) /* shouldn't happen */
! elog(ERROR, "could not find equality operator for ordering operator %u",
! ordering_op);
opfamilies = get_mergejoin_opfamilies(equality_op);
if (!opfamilies) /* certainly should find some */
! elog(ERROR, "could not find opfamilies for ordering operator %u",
! ordering_op);
/*
* When dealing with binary-compatible opclasses, we have to ensure that
--- 234,272 ----
*/
static PathKey *
make_pathkey_from_sortinfo(PlannerInfo *root,
! Expr *expr,
! Oid opfamily,
! Oid opcintype,
! bool reverse_sort,
bool nulls_first,
Index sortref,
bool create_it,
bool canonicalize)
{
int16 strategy;
Oid equality_op;
List *opfamilies;
EquivalenceClass *eclass;
+ strategy = reverse_sort ? BTGreaterStrategyNumber : BTLessStrategyNumber;
+
/*
! * EquivalenceClasses need to contain opfamily lists based on the family
! * membership of mergejoinable equality operators, which could belong to
! * more than one opfamily. So we have to look up the opfamily's equality
! * operator and get its membership.
*/
equality_op = get_opfamily_member(opfamily,
opcintype,
opcintype,
BTEqualStrategyNumber);
if (!OidIsValid(equality_op)) /* shouldn't happen */
! elog(ERROR, "could not find equality operator for opfamily %u",
! opfamily);
opfamilies = get_mergejoin_opfamilies(equality_op);
if (!opfamilies) /* certainly should find some */
! elog(ERROR, "could not find opfamilies for equality operator %u",
! equality_op);
/*
* When dealing with binary-compatible opclasses, we have to ensure that
*************** make_pathkey_from_sortinfo(PlannerInfo *
*** 322,327 ****
--- 309,350 ----
return makePathKey(eclass, opfamily, strategy, nulls_first);
}
+ /*
+ * make_pathkey_from_sortop
+ * Like make_pathkey_from_sortinfo, but work from a sort operator.
+ *
+ * This should eventually go away, but we need to restructure SortGroupClause
+ * first.
+ */
+ static PathKey *
+ make_pathkey_from_sortop(PlannerInfo *root,
+ Expr *expr,
+ Oid ordering_op,
+ bool nulls_first,
+ Index sortref,
+ bool create_it,
+ bool canonicalize)
+ {
+ Oid opfamily,
+ opcintype;
+ int16 strategy;
+
+ /* Find the operator in pg_amop --- failure shouldn't happen */
+ if (!get_ordering_op_properties(ordering_op,
+ &opfamily, &opcintype, &strategy))
+ elog(ERROR, "operator %u is not a valid ordering operator",
+ ordering_op);
+ return make_pathkey_from_sortinfo(root,
+ expr,
+ opfamily,
+ opcintype,
+ (strategy == BTGreaterStrategyNumber),
+ nulls_first,
+ sortref,
+ create_it,
+ canonicalize);
+ }
+
/****************************************************************************
* PATHKEY COMPARISONS
*************** get_cheapest_fractional_path_for_pathkey
*** 479,489 ****
* build_index_pathkeys
* Build a pathkeys list that describes the ordering induced by an index
* scan using the given index. (Note that an unordered index doesn't
! * induce any ordering; such an index will have no sortop OIDS in
! * its sortops arrays, and we will return NIL.)
*
! * If 'scandir' is BackwardScanDirection, attempt to build pathkeys
! * representing a backwards scan of the index. Return NIL if can't do it.
*
* The result is canonical, meaning that redundant pathkeys are removed;
* it may therefore have fewer entries than there are index columns.
--- 502,511 ----
* build_index_pathkeys
* Build a pathkeys list that describes the ordering induced by an index
* scan using the given index. (Note that an unordered index doesn't
! * induce any ordering, so we return NIL.)
*
! * If 'scandir' is BackwardScanDirection, build pathkeys representing a
! * backwards scan of the index.
*
* The result is canonical, meaning that redundant pathkeys are removed;
* it may therefore have fewer entries than there are index columns.
*************** build_index_pathkeys(PlannerInfo *root,
*** 500,511 ****
ScanDirection scandir)
{
List *retval = NIL;
! ListCell *indexprs_item = list_head(index->indexprs);
int i;
for (i = 0; i < index->ncolumns; i++)
{
! Oid sortop;
bool nulls_first;
int ikey;
Expr *indexkey;
--- 522,537 ----
ScanDirection scandir)
{
List *retval = NIL;
! ListCell *indexprs_item;
int i;
+ if (index->sortopfamily == NULL)
+ return NIL; /* non-orderable index */
+
+ indexprs_item = list_head(index->indexprs);
for (i = 0; i < index->ncolumns; i++)
{
! bool reverse_sort;
bool nulls_first;
int ikey;
Expr *indexkey;
*************** build_index_pathkeys(PlannerInfo *root,
*** 513,530 ****
if (ScanDirectionIsBackward(scandir))
{
! sortop = index->revsortop[i];
nulls_first = !index->nulls_first[i];
}
else
{
! sortop = index->fwdsortop[i];
nulls_first = index->nulls_first[i];
}
- if (!OidIsValid(sortop))
- break; /* no more orderable columns */
-
ikey = index->indexkeys[i];
if (ikey != 0)
{
--- 539,553 ----
if (ScanDirectionIsBackward(scandir))
{
! reverse_sort = !index->reverse_sort[i];
nulls_first = !index->nulls_first[i];
}
else
{
! reverse_sort = index->reverse_sort[i];
nulls_first = index->nulls_first[i];
}
ikey = index->indexkeys[i];
if (ikey != 0)
{
*************** build_index_pathkeys(PlannerInfo *root,
*** 543,549 ****
/* OK, try to make a canonical pathkey for this sort key */
cpathkey = make_pathkey_from_sortinfo(root,
indexkey,
! sortop,
nulls_first,
0,
false,
--- 566,574 ----
/* OK, try to make a canonical pathkey for this sort key */
cpathkey = make_pathkey_from_sortinfo(root,
indexkey,
! index->sortopfamily[i],
! index->opcintype[i],
! reverse_sort,
nulls_first,
0,
false,
*************** make_pathkeys_for_sortclauses(PlannerInf
*** 892,904 ****
sortkey = (Expr *) get_sortgroupclause_expr(sortcl, tlist);
Assert(OidIsValid(sortcl->sortop));
! pathkey = make_pathkey_from_sortinfo(root,
! sortkey,
! sortcl->sortop,
! sortcl->nulls_first,
! sortcl->tleSortGroupRef,
! true,
! canonicalize);
/* Canonical form eliminates redundant ordering keys */
if (canonicalize)
--- 917,929 ----
sortkey = (Expr *) get_sortgroupclause_expr(sortcl, tlist);
Assert(OidIsValid(sortcl->sortop));
! pathkey = make_pathkey_from_sortop(root,
! sortkey,
! sortcl->sortop,
! sortcl->nulls_first,
! sortcl->tleSortGroupRef,
! true,
! canonicalize);
/* Canonical form eliminates redundant ordering keys */
if (canonicalize)
*************** make_pathkeys_for_aggregate(PlannerInfo
*** 935,947 ****
* We arbitrarily set nulls_first to false. Actually, a MIN/MAX agg can
* use either nulls ordering option, but that is dealt with elsewhere.
*/
! pathkey = make_pathkey_from_sortinfo(root,
! aggtarget,
! aggsortop,
! false, /* nulls_first */
! 0,
! true,
! false);
return list_make1(pathkey);
}
--- 960,972 ----
* We arbitrarily set nulls_first to false. Actually, a MIN/MAX agg can
* use either nulls ordering option, but that is dealt with elsewhere.
*/
! pathkey = make_pathkey_from_sortop(root,
! aggtarget,
! aggsortop,
! false, /* nulls_first */
! 0,
! true,
! false);
return list_make1(pathkey);
}
diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c
index 908b4f7205d86f0888007d3a05e65b13132520b9..a29401ba48c7776f91fdb38bbc1100801661327b 100644
*** a/src/backend/optimizer/util/plancat.c
--- b/src/backend/optimizer/util/plancat.c
*************** get_relation_info(PlannerInfo *root, Oid
*** 189,207 ****
RelationGetForm(indexRelation)->reltablespace;
info->rel = rel;
info->ncolumns = ncolumns = index->indnatts;
-
- /*
- * Allocate per-column info arrays. To save a few palloc cycles
- * we allocate all the Oid-type arrays in one request. We must
- * pre-zero the sortop and nulls_first arrays in case the index is
- * unordered.
- */
info->indexkeys = (int *) palloc(sizeof(int) * ncolumns);
! info->opfamily = (Oid *) palloc0(sizeof(Oid) * (4 * ncolumns));
! info->opcintype = info->opfamily + ncolumns;
! info->fwdsortop = info->opcintype + ncolumns;
! info->revsortop = info->fwdsortop + ncolumns;
! info->nulls_first = (bool *) palloc0(sizeof(bool) * ncolumns);
for (i = 0; i < ncolumns; i++)
{
--- 189,197 ----
RelationGetForm(indexRelation)->reltablespace;
info->rel = rel;
info->ncolumns = ncolumns = index->indnatts;
info->indexkeys = (int *) palloc(sizeof(int) * ncolumns);
! info->opfamily = (Oid *) palloc(sizeof(Oid) * ncolumns);
! info->opcintype = (Oid *) palloc(sizeof(Oid) * ncolumns);
for (i = 0; i < ncolumns; i++)
{
*************** get_relation_info(PlannerInfo *root, Oid
*** 219,267 ****
info->amhasgetbitmap = OidIsValid(indexRelation->rd_am->amgetbitmap);
/*
! * Fetch the ordering operators associated with the index, if any.
! * We expect that all ordering-capable indexes use btree's
! * strategy numbers for the ordering operators.
*/
if (indexRelation->rd_am->amcanorder)
{
! int nstrat = indexRelation->rd_am->amstrategies;
for (i = 0; i < ncolumns; i++)
{
int16 opt = indexRelation->rd_indoption[i];
- int fwdstrat;
- int revstrat;
! if (opt & INDOPTION_DESC)
! {
! fwdstrat = BTGreaterStrategyNumber;
! revstrat = BTLessStrategyNumber;
! }
! else
! {
! fwdstrat = BTLessStrategyNumber;
! revstrat = BTGreaterStrategyNumber;
! }
!
! /*
! * Index AM must have a fixed set of strategies for it to
! * make sense to specify amcanorder, so we need not allow
! * the case amstrategies == 0.
! */
! if (fwdstrat > 0)
! {
! Assert(fwdstrat <= nstrat);
! info->fwdsortop[i] = indexRelation->rd_operator[i * nstrat + fwdstrat - 1];
! }
! if (revstrat > 0)
! {
! Assert(revstrat <= nstrat);
! info->revsortop[i] = indexRelation->rd_operator[i * nstrat + revstrat - 1];
! }
info->nulls_first[i] = (opt & INDOPTION_NULLS_FIRST) != 0;
}
}
/*
* Fetch the index expressions and predicate, if any. We must
--- 209,244 ----
info->amhasgetbitmap = OidIsValid(indexRelation->rd_am->amgetbitmap);
/*
! * Fetch the ordering information for the index, if any.
! *
! * Currently, we assume that any orderable index uses btree's
! * opfamily numbers, which really is equivalent to supposing that
! * btree is the only amcanorder index type. To support other
! * orderable index types, we'd need a way to map from their
! * opfamilies to btree opfamilies. (This could reasonably be
! * done as an additional property in pg_opfamily, but for the
! * foreseeable future there's no need to bother.)
*/
if (indexRelation->rd_am->amcanorder)
{
! info->sortopfamily = info->opfamily;
! info->reverse_sort = (bool *) palloc(sizeof(bool) * ncolumns);
! info->nulls_first = (bool *) palloc(sizeof(bool) * ncolumns);
for (i = 0; i < ncolumns; i++)
{
int16 opt = indexRelation->rd_indoption[i];
! info->reverse_sort[i] = (opt & INDOPTION_DESC) != 0;
info->nulls_first[i] = (opt & INDOPTION_NULLS_FIRST) != 0;
}
}
+ else
+ {
+ info->sortopfamily = NULL;
+ info->reverse_sort = NULL;
+ info->nulls_first = NULL;
+ }
/*
* Fetch the index expressions and predicate, if any. We must
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index c7442218a84a12972658ef320c20c7aa783b80a7..95397aa7cee3132db72138443bd7181ff5c32889 100644
*** a/src/backend/utils/adt/selfuncs.c
--- b/src/backend/utils/adt/selfuncs.c
*************** get_actual_variable_range(PlannerInfo *r
*** 4567,4580 ****
* The first index column must match the desired variable and sort
* operator --- but we can use a descending-order index.
*/
- if (sortop == index->fwdsortop[0])
- indexscandir = ForwardScanDirection;
- else if (sortop == index->revsortop[0])
- indexscandir = BackwardScanDirection;
- else
- continue;
if (!match_index_to_operand(vardata->var, 0, index))
continue;
/*
* Found a suitable index to extract data from. We'll need an EState
--- 4567,4592 ----
* The first index column must match the desired variable and sort
* operator --- but we can use a descending-order index.
*/
if (!match_index_to_operand(vardata->var, 0, index))
continue;
+ switch (get_op_opfamily_strategy(sortop, index->sortopfamily[0]))
+ {
+ case BTLessStrategyNumber:
+ if (index->reverse_sort[0])
+ indexscandir = BackwardScanDirection;
+ else
+ indexscandir = ForwardScanDirection;
+ break;
+ case BTGreaterStrategyNumber:
+ if (index->reverse_sort[0])
+ indexscandir = ForwardScanDirection;
+ else
+ indexscandir = BackwardScanDirection;
+ break;
+ default:
+ /* index doesn't match the sortop */
+ continue;
+ }
/*
* Found a suitable index to extract data from. We'll need an EState
*************** btcostestimate(PG_FUNCTION_ARGS)
*** 6150,6161 ****
if (HeapTupleIsValid(vardata.statsTuple))
{
float4 *numbers;
int nnumbers;
! if (get_attstatsslot(vardata.statsTuple, InvalidOid, 0,
STATISTIC_KIND_CORRELATION,
! index->fwdsortop[0],
NULL,
NULL, NULL,
&numbers, &nnumbers))
--- 6162,6179 ----
if (HeapTupleIsValid(vardata.statsTuple))
{
+ Oid sortop;
float4 *numbers;
int nnumbers;
! sortop = get_opfamily_member(index->opfamily[0],
! index->opcintype[0],
! index->opcintype[0],
! BTLessStrategyNumber);
! if (OidIsValid(sortop) &&
! get_attstatsslot(vardata.statsTuple, InvalidOid, 0,
STATISTIC_KIND_CORRELATION,
! sortop,
NULL,
NULL, NULL,
&numbers, &nnumbers))
*************** btcostestimate(PG_FUNCTION_ARGS)
*** 6165,6170 ****
--- 6183,6191 ----
Assert(nnumbers == 1);
varCorrelation = numbers[0];
+ if (index->reverse_sort[0])
+ varCorrelation = -varCorrelation;
+
if (index->ncolumns > 1)
*indexCorrelation = varCorrelation * 0.75;
else
*************** btcostestimate(PG_FUNCTION_ARGS)
*** 6172,6196 ****
free_attstatsslot(InvalidOid, NULL, 0, numbers, nnumbers);
}
- else if (get_attstatsslot(vardata.statsTuple, InvalidOid, 0,
- STATISTIC_KIND_CORRELATION,
- index->revsortop[0],
- NULL,
- NULL, NULL,
- &numbers, &nnumbers))
- {
- double varCorrelation;
-
- Assert(nnumbers == 1);
- varCorrelation = numbers[0];
-
- if (index->ncolumns > 1)
- *indexCorrelation = -varCorrelation * 0.75;
- else
- *indexCorrelation = -varCorrelation;
-
- free_attstatsslot(InvalidOid, NULL, 0, numbers, nnumbers);
- }
}
ReleaseVariableStats(vardata);
--- 6193,6198 ----
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index 785acc955ad652254c547d015715ec6ac1841925..d084338f356206c354a0a85179ea358862eab5bb 100644
*** a/src/include/nodes/relation.h
--- b/src/include/nodes/relation.h
*************** typedef struct RelOptInfo
*** 421,440 ****
* IndexOptInfo
* Per-index information for planning/optimization
*
! * Prior to Postgres 7.0, RelOptInfo was used to describe both relations
! * and indexes, but that created confusion without actually doing anything
! * useful. So now we have a separate IndexOptInfo struct for indexes.
! *
! * opfamily[], indexkeys[], opcintype[], fwdsortop[], revsortop[],
! * and nulls_first[] each have ncolumns entries.
*
* Zeroes in the indexkeys[] array indicate index columns that are
* expressions; there is one element in indexprs for each such column.
*
! * For an unordered index, the sortop arrays contains zeroes. Note that
! * fwdsortop[] and nulls_first[] describe the sort ordering of a forward
! * indexscan; we can also consider a backward indexscan, which will
! * generate sort order described by revsortop/!nulls_first.
*
* The indexprs and indpred expressions have been run through
* prepqual.c and eval_const_expressions() for ease of matching to
--- 421,437 ----
* IndexOptInfo
* Per-index information for planning/optimization
*
! * opfamily[], indexkeys[], and opcintype[] each have ncolumns entries.
! * sortopfamily[], reverse_sort[], and nulls_first[] likewise have
! * ncolumns entries, if the index is ordered; but if it is unordered,
! * those pointers are NULL.
*
* Zeroes in the indexkeys[] array indicate index columns that are
* expressions; there is one element in indexprs for each such column.
*
! * For an ordered index, reverse_sort[] and nulls_first[] describe the
! * sort ordering of a forward indexscan; we can also consider a backward
! * indexscan, which will generate the reverse ordering.
*
* The indexprs and indpred expressions have been run through
* prepqual.c and eval_const_expressions() for ease of matching to
*************** typedef struct IndexOptInfo
*** 457,464 ****
Oid *opfamily; /* OIDs of operator families for columns */
int *indexkeys; /* column numbers of index's keys, or 0 */
Oid *opcintype; /* OIDs of opclass declared input data types */
! Oid *fwdsortop; /* OIDs of sort operators for each column */
! Oid *revsortop; /* OIDs of sort operators for backward scan */
bool *nulls_first; /* do NULLs come first in the sort order? */
Oid relam; /* OID of the access method (in pg_am) */
--- 454,461 ----
Oid *opfamily; /* OIDs of operator families for columns */
int *indexkeys; /* column numbers of index's keys, or 0 */
Oid *opcintype; /* OIDs of opclass declared input data types */
! Oid *sortopfamily; /* OIDs of btree opfamilies, if orderable */
! bool *reverse_sort; /* is sort order descending? */
bool *nulls_first; /* do NULLs come first in the sort order? */
Oid relam; /* OID of the access method (in pg_am) */
I wrote:
> Now, this loss of flexibility doesn't particularly bother me, because
> I know of no existing or contemplated btree-substitute access methods.
> If one did appear on the horizon, there are a couple of ways we could
> fix the problem, the cleanest being to let a non-btree opfamily declare
> that it sorts the same as btree opfamily so-and-so. Or we could fix
> it locally in plancat.c by performing the lookup-the-operators-and-
> then-the-btree-opfamilies dance on the fly when setting up IndexOptInfo
> for a non-btree amcanorder index. But I'm disinclined to write such
> code when there's no way to test it and no foreseeable possibility
> that it'll ever be used. Maybe we should just make plancat.c throw
> a not-implemented error if amcanorder is true but it's not btree.
On further reflection the last seems like clearly the thing to do.
> PS: the attached patch doesn't yet include removal of relcache
> rd_operator arrays, since that would just make the patch bigger
> without exposing any new issues.
And here's the complete patch.
regards, tom lane
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index d8fc12068fb6113c0baf8aa4e5941e0150ce3521..f73e0e6dc6007ce768828480f74621752aaf57d2 100644
*** a/src/backend/optimizer/path/indxpath.c
--- b/src/backend/optimizer/path/indxpath.c
*************** find_usable_indexes(PlannerInfo *root, R
*** 380,386 ****
* how many of them are actually useful for this query. This is not
* relevant unless we are at top level.
*/
! index_is_ordered = OidIsValid(index->fwdsortop[0]);
if (index_is_ordered && possibly_useful_pathkeys &&
istoplevel && outer_rel == NULL)
{
--- 380,386 ----
* how many of them are actually useful for this query. This is not
* relevant unless we are at top level.
*/
! index_is_ordered = (index->sortopfamily != NULL);
if (index_is_ordered && possibly_useful_pathkeys &&
istoplevel && outer_rel == NULL)
{
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 8af0c6dc482372244b15a8a5f5a4a562e34ac91b..6325655eed84759168a51aed3f712582ec9c1f00 100644
*** a/src/backend/optimizer/path/pathkeys.c
--- b/src/backend/optimizer/path/pathkeys.c
*************** static PathKey *make_canonical_pathkey(P
*** 36,47 ****
EquivalenceClass *eclass, Oid opfamily,
int strategy, bool nulls_first);
static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys);
- static PathKey *make_pathkey_from_sortinfo(PlannerInfo *root,
- Expr *expr, Oid ordering_op,
- bool nulls_first,
- Index sortref,
- bool create_it,
- bool canonicalize);
static Var *find_indexkey_var(PlannerInfo *root, RelOptInfo *rel,
AttrNumber varattno);
static bool right_merge_direction(PlannerInfo *root, PathKey *pathkey);
--- 36,41 ----
*************** canonicalize_pathkeys(PlannerInfo *root,
*** 224,232 ****
/*
* make_pathkey_from_sortinfo
! * Given an expression, a sortop, and a nulls-first flag, create
! * a PathKey. If canonicalize = true, the result is a "canonical"
! * PathKey, otherwise not. (But note it might be redundant anyway.)
*
* If the PathKey is being generated from a SortGroupClause, sortref should be
* the SortGroupClause's SortGroupRef; otherwise zero.
--- 218,226 ----
/*
* make_pathkey_from_sortinfo
! * Given an expression and sort-order information, create a PathKey.
! * If canonicalize = true, the result is a "canonical" PathKey,
! * otherwise not. (But note it might be redundant anyway.)
*
* If the PathKey is being generated from a SortGroupClause, sortref should be
* the SortGroupClause's SortGroupRef; otherwise zero.
*************** canonicalize_pathkeys(PlannerInfo *root,
*** 240,285 ****
*/
static PathKey *
make_pathkey_from_sortinfo(PlannerInfo *root,
! Expr *expr, Oid ordering_op,
bool nulls_first,
Index sortref,
bool create_it,
bool canonicalize)
{
- Oid opfamily,
- opcintype;
int16 strategy;
Oid equality_op;
List *opfamilies;
EquivalenceClass *eclass;
/*
! * An ordering operator fully determines the behavior of its opfamily, so
! * could only meaningfully appear in one family --- or perhaps two if one
! * builds a reverse-sort opfamily, but there's not much point in that
! * anymore. But EquivalenceClasses need to contain opfamily lists based
! * on the family membership of equality operators, which could easily be
! * bigger. So, look up the equality operator that goes with the ordering
! * operator (this should be unique) and get its membership.
*/
-
- /* Find the operator in pg_amop --- failure shouldn't happen */
- if (!get_ordering_op_properties(ordering_op,
- &opfamily, &opcintype, &strategy))
- elog(ERROR, "operator %u is not a valid ordering operator",
- ordering_op);
- /* Get matching equality operator */
equality_op = get_opfamily_member(opfamily,
opcintype,
opcintype,
BTEqualStrategyNumber);
if (!OidIsValid(equality_op)) /* shouldn't happen */
! elog(ERROR, "could not find equality operator for ordering operator %u",
! ordering_op);
opfamilies = get_mergejoin_opfamilies(equality_op);
if (!opfamilies) /* certainly should find some */
! elog(ERROR, "could not find opfamilies for ordering operator %u",
! ordering_op);
/*
* When dealing with binary-compatible opclasses, we have to ensure that
--- 234,272 ----
*/
static PathKey *
make_pathkey_from_sortinfo(PlannerInfo *root,
! Expr *expr,
! Oid opfamily,
! Oid opcintype,
! bool reverse_sort,
bool nulls_first,
Index sortref,
bool create_it,
bool canonicalize)
{
int16 strategy;
Oid equality_op;
List *opfamilies;
EquivalenceClass *eclass;
+ strategy = reverse_sort ? BTGreaterStrategyNumber : BTLessStrategyNumber;
+
/*
! * EquivalenceClasses need to contain opfamily lists based on the family
! * membership of mergejoinable equality operators, which could belong to
! * more than one opfamily. So we have to look up the opfamily's equality
! * operator and get its membership.
*/
equality_op = get_opfamily_member(opfamily,
opcintype,
opcintype,
BTEqualStrategyNumber);
if (!OidIsValid(equality_op)) /* shouldn't happen */
! elog(ERROR, "could not find equality operator for opfamily %u",
! opfamily);
opfamilies = get_mergejoin_opfamilies(equality_op);
if (!opfamilies) /* certainly should find some */
! elog(ERROR, "could not find opfamilies for equality operator %u",
! equality_op);
/*
* When dealing with binary-compatible opclasses, we have to ensure that
*************** make_pathkey_from_sortinfo(PlannerInfo *
*** 322,327 ****
--- 309,350 ----
return makePathKey(eclass, opfamily, strategy, nulls_first);
}
+ /*
+ * make_pathkey_from_sortop
+ * Like make_pathkey_from_sortinfo, but work from a sort operator.
+ *
+ * This should eventually go away, but we need to restructure SortGroupClause
+ * first.
+ */
+ static PathKey *
+ make_pathkey_from_sortop(PlannerInfo *root,
+ Expr *expr,
+ Oid ordering_op,
+ bool nulls_first,
+ Index sortref,
+ bool create_it,
+ bool canonicalize)
+ {
+ Oid opfamily,
+ opcintype;
+ int16 strategy;
+
+ /* Find the operator in pg_amop --- failure shouldn't happen */
+ if (!get_ordering_op_properties(ordering_op,
+ &opfamily, &opcintype, &strategy))
+ elog(ERROR, "operator %u is not a valid ordering operator",
+ ordering_op);
+ return make_pathkey_from_sortinfo(root,
+ expr,
+ opfamily,
+ opcintype,
+ (strategy == BTGreaterStrategyNumber),
+ nulls_first,
+ sortref,
+ create_it,
+ canonicalize);
+ }
+
/****************************************************************************
* PATHKEY COMPARISONS
*************** get_cheapest_fractional_path_for_pathkey
*** 479,489 ****
* build_index_pathkeys
* Build a pathkeys list that describes the ordering induced by an index
* scan using the given index. (Note that an unordered index doesn't
! * induce any ordering; such an index will have no sortop OIDS in
! * its sortops arrays, and we will return NIL.)
*
! * If 'scandir' is BackwardScanDirection, attempt to build pathkeys
! * representing a backwards scan of the index. Return NIL if can't do it.
*
* The result is canonical, meaning that redundant pathkeys are removed;
* it may therefore have fewer entries than there are index columns.
--- 502,511 ----
* build_index_pathkeys
* Build a pathkeys list that describes the ordering induced by an index
* scan using the given index. (Note that an unordered index doesn't
! * induce any ordering, so we return NIL.)
*
! * If 'scandir' is BackwardScanDirection, build pathkeys representing a
! * backwards scan of the index.
*
* The result is canonical, meaning that redundant pathkeys are removed;
* it may therefore have fewer entries than there are index columns.
*************** build_index_pathkeys(PlannerInfo *root,
*** 500,511 ****
ScanDirection scandir)
{
List *retval = NIL;
! ListCell *indexprs_item = list_head(index->indexprs);
int i;
for (i = 0; i < index->ncolumns; i++)
{
! Oid sortop;
bool nulls_first;
int ikey;
Expr *indexkey;
--- 522,537 ----
ScanDirection scandir)
{
List *retval = NIL;
! ListCell *indexprs_item;
int i;
+ if (index->sortopfamily == NULL)
+ return NIL; /* non-orderable index */
+
+ indexprs_item = list_head(index->indexprs);
for (i = 0; i < index->ncolumns; i++)
{
! bool reverse_sort;
bool nulls_first;
int ikey;
Expr *indexkey;
*************** build_index_pathkeys(PlannerInfo *root,
*** 513,530 ****
if (ScanDirectionIsBackward(scandir))
{
! sortop = index->revsortop[i];
nulls_first = !index->nulls_first[i];
}
else
{
! sortop = index->fwdsortop[i];
nulls_first = index->nulls_first[i];
}
- if (!OidIsValid(sortop))
- break; /* no more orderable columns */
-
ikey = index->indexkeys[i];
if (ikey != 0)
{
--- 539,553 ----
if (ScanDirectionIsBackward(scandir))
{
! reverse_sort = !index->reverse_sort[i];
nulls_first = !index->nulls_first[i];
}
else
{
! reverse_sort = index->reverse_sort[i];
nulls_first = index->nulls_first[i];
}
ikey = index->indexkeys[i];
if (ikey != 0)
{
*************** build_index_pathkeys(PlannerInfo *root,
*** 543,549 ****
/* OK, try to make a canonical pathkey for this sort key */
cpathkey = make_pathkey_from_sortinfo(root,
indexkey,
! sortop,
nulls_first,
0,
false,
--- 566,574 ----
/* OK, try to make a canonical pathkey for this sort key */
cpathkey = make_pathkey_from_sortinfo(root,
indexkey,
! index->sortopfamily[i],
! index->opcintype[i],
! reverse_sort,
nulls_first,
0,
false,
*************** make_pathkeys_for_sortclauses(PlannerInf
*** 892,904 ****
sortkey = (Expr *) get_sortgroupclause_expr(sortcl, tlist);
Assert(OidIsValid(sortcl->sortop));
! pathkey = make_pathkey_from_sortinfo(root,
! sortkey,
! sortcl->sortop,
! sortcl->nulls_first,
! sortcl->tleSortGroupRef,
! true,
! canonicalize);
/* Canonical form eliminates redundant ordering keys */
if (canonicalize)
--- 917,929 ----
sortkey = (Expr *) get_sortgroupclause_expr(sortcl, tlist);
Assert(OidIsValid(sortcl->sortop));
! pathkey = make_pathkey_from_sortop(root,
! sortkey,
! sortcl->sortop,
! sortcl->nulls_first,
! sortcl->tleSortGroupRef,
! true,
! canonicalize);
/* Canonical form eliminates redundant ordering keys */
if (canonicalize)
*************** make_pathkeys_for_aggregate(PlannerInfo
*** 935,947 ****
* We arbitrarily set nulls_first to false. Actually, a MIN/MAX agg can
* use either nulls ordering option, but that is dealt with elsewhere.
*/
! pathkey = make_pathkey_from_sortinfo(root,
! aggtarget,
! aggsortop,
! false, /* nulls_first */
! 0,
! true,
! false);
return list_make1(pathkey);
}
--- 960,972 ----
* We arbitrarily set nulls_first to false. Actually, a MIN/MAX agg can
* use either nulls ordering option, but that is dealt with elsewhere.
*/
! pathkey = make_pathkey_from_sortop(root,
! aggtarget,
! aggsortop,
! false, /* nulls_first */
! 0,
! true,
! false);
return list_make1(pathkey);
}
diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c
index 908b4f7205d86f0888007d3a05e65b13132520b9..cd26e906187167728042945f9e8ba29046500e2e 100644
*** a/src/backend/optimizer/util/plancat.c
--- b/src/backend/optimizer/util/plancat.c
*************** get_relation_info(PlannerInfo *root, Oid
*** 189,207 ****
RelationGetForm(indexRelation)->reltablespace;
info->rel = rel;
info->ncolumns = ncolumns = index->indnatts;
-
- /*
- * Allocate per-column info arrays. To save a few palloc cycles
- * we allocate all the Oid-type arrays in one request. We must
- * pre-zero the sortop and nulls_first arrays in case the index is
- * unordered.
- */
info->indexkeys = (int *) palloc(sizeof(int) * ncolumns);
! info->opfamily = (Oid *) palloc0(sizeof(Oid) * (4 * ncolumns));
! info->opcintype = info->opfamily + ncolumns;
! info->fwdsortop = info->opcintype + ncolumns;
! info->revsortop = info->fwdsortop + ncolumns;
! info->nulls_first = (bool *) palloc0(sizeof(bool) * ncolumns);
for (i = 0; i < ncolumns; i++)
{
--- 189,197 ----
RelationGetForm(indexRelation)->reltablespace;
info->rel = rel;
info->ncolumns = ncolumns = index->indnatts;
info->indexkeys = (int *) palloc(sizeof(int) * ncolumns);
! info->opfamily = (Oid *) palloc(sizeof(Oid) * ncolumns);
! info->opcintype = (Oid *) palloc(sizeof(Oid) * ncolumns);
for (i = 0; i < ncolumns; i++)
{
*************** get_relation_info(PlannerInfo *root, Oid
*** 219,267 ****
info->amhasgetbitmap = OidIsValid(indexRelation->rd_am->amgetbitmap);
/*
! * Fetch the ordering operators associated with the index, if any.
! * We expect that all ordering-capable indexes use btree's
! * strategy numbers for the ordering operators.
*/
! if (indexRelation->rd_am->amcanorder)
{
! int nstrat = indexRelation->rd_am->amstrategies;
for (i = 0; i < ncolumns; i++)
{
int16 opt = indexRelation->rd_indoption[i];
- int fwdstrat;
- int revstrat;
! if (opt & INDOPTION_DESC)
! {
! fwdstrat = BTGreaterStrategyNumber;
! revstrat = BTLessStrategyNumber;
! }
! else
! {
! fwdstrat = BTLessStrategyNumber;
! revstrat = BTGreaterStrategyNumber;
! }
!
! /*
! * Index AM must have a fixed set of strategies for it to
! * make sense to specify amcanorder, so we need not allow
! * the case amstrategies == 0.
! */
! if (fwdstrat > 0)
! {
! Assert(fwdstrat <= nstrat);
! info->fwdsortop[i] = indexRelation->rd_operator[i * nstrat + fwdstrat - 1];
! }
! if (revstrat > 0)
! {
! Assert(revstrat <= nstrat);
! info->revsortop[i] = indexRelation->rd_operator[i * nstrat + revstrat - 1];
! }
info->nulls_first[i] = (opt & INDOPTION_NULLS_FIRST) != 0;
}
}
/*
* Fetch the index expressions and predicate, if any. We must
--- 209,250 ----
info->amhasgetbitmap = OidIsValid(indexRelation->rd_am->amgetbitmap);
/*
! * Fetch the ordering information for the index, if any.
! *
! * If it's a btree index, we can use its opfamily OIDs directly
! * as the sort ordering opfamily OIDs.
*/
! if (info->relam == BTREE_AM_OID)
{
! info->sortopfamily = info->opfamily;
! info->reverse_sort = (bool *) palloc(sizeof(bool) * ncolumns);
! info->nulls_first = (bool *) palloc(sizeof(bool) * ncolumns);
for (i = 0; i < ncolumns; i++)
{
int16 opt = indexRelation->rd_indoption[i];
! info->reverse_sort[i] = (opt & INDOPTION_DESC) != 0;
info->nulls_first[i] = (opt & INDOPTION_NULLS_FIRST) != 0;
}
}
+ else if (indexRelation->rd_am->amcanorder)
+ {
+ /*
+ * To support other orderable index types, we'd need a way to
+ * map from their opfamilies to btree opfamilies. This could
+ * reasonably be done as an additional property in
+ * pg_opfamily, but for the foreseeable future there's no need
+ * to bother implementing that.
+ */
+ elog(ERROR, "only btree is currently allowed to set amcanorder");
+ }
+ else
+ {
+ info->sortopfamily = NULL;
+ info->reverse_sort = NULL;
+ info->nulls_first = NULL;
+ }
/*
* Fetch the index expressions and predicate, if any. We must
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index c7442218a84a12972658ef320c20c7aa783b80a7..95397aa7cee3132db72138443bd7181ff5c32889 100644
*** a/src/backend/utils/adt/selfuncs.c
--- b/src/backend/utils/adt/selfuncs.c
*************** get_actual_variable_range(PlannerInfo *r
*** 4567,4580 ****
* The first index column must match the desired variable and sort
* operator --- but we can use a descending-order index.
*/
- if (sortop == index->fwdsortop[0])
- indexscandir = ForwardScanDirection;
- else if (sortop == index->revsortop[0])
- indexscandir = BackwardScanDirection;
- else
- continue;
if (!match_index_to_operand(vardata->var, 0, index))
continue;
/*
* Found a suitable index to extract data from. We'll need an EState
--- 4567,4592 ----
* The first index column must match the desired variable and sort
* operator --- but we can use a descending-order index.
*/
if (!match_index_to_operand(vardata->var, 0, index))
continue;
+ switch (get_op_opfamily_strategy(sortop, index->sortopfamily[0]))
+ {
+ case BTLessStrategyNumber:
+ if (index->reverse_sort[0])
+ indexscandir = BackwardScanDirection;
+ else
+ indexscandir = ForwardScanDirection;
+ break;
+ case BTGreaterStrategyNumber:
+ if (index->reverse_sort[0])
+ indexscandir = ForwardScanDirection;
+ else
+ indexscandir = BackwardScanDirection;
+ break;
+ default:
+ /* index doesn't match the sortop */
+ continue;
+ }
/*
* Found a suitable index to extract data from. We'll need an EState
*************** btcostestimate(PG_FUNCTION_ARGS)
*** 6150,6161 ****
if (HeapTupleIsValid(vardata.statsTuple))
{
float4 *numbers;
int nnumbers;
! if (get_attstatsslot(vardata.statsTuple, InvalidOid, 0,
STATISTIC_KIND_CORRELATION,
! index->fwdsortop[0],
NULL,
NULL, NULL,
&numbers, &nnumbers))
--- 6162,6179 ----
if (HeapTupleIsValid(vardata.statsTuple))
{
+ Oid sortop;
float4 *numbers;
int nnumbers;
! sortop = get_opfamily_member(index->opfamily[0],
! index->opcintype[0],
! index->opcintype[0],
! BTLessStrategyNumber);
! if (OidIsValid(sortop) &&
! get_attstatsslot(vardata.statsTuple, InvalidOid, 0,
STATISTIC_KIND_CORRELATION,
! sortop,
NULL,
NULL, NULL,
&numbers, &nnumbers))
*************** btcostestimate(PG_FUNCTION_ARGS)
*** 6165,6170 ****
--- 6183,6191 ----
Assert(nnumbers == 1);
varCorrelation = numbers[0];
+ if (index->reverse_sort[0])
+ varCorrelation = -varCorrelation;
+
if (index->ncolumns > 1)
*indexCorrelation = varCorrelation * 0.75;
else
*************** btcostestimate(PG_FUNCTION_ARGS)
*** 6172,6196 ****
free_attstatsslot(InvalidOid, NULL, 0, numbers, nnumbers);
}
- else if (get_attstatsslot(vardata.statsTuple, InvalidOid, 0,
- STATISTIC_KIND_CORRELATION,
- index->revsortop[0],
- NULL,
- NULL, NULL,
- &numbers, &nnumbers))
- {
- double varCorrelation;
-
- Assert(nnumbers == 1);
- varCorrelation = numbers[0];
-
- if (index->ncolumns > 1)
- *indexCorrelation = -varCorrelation * 0.75;
- else
- *indexCorrelation = -varCorrelation;
-
- free_attstatsslot(InvalidOid, NULL, 0, numbers, nnumbers);
- }
}
ReleaseVariableStats(vardata);
--- 6193,6198 ----
diff --git a/src/backend/utils/cache/relcache.c b/src/backend/utils/cache/relcache.c
index 9353a347bcb3692a4c82bc4ea3c275610e42fd82..8df12a1424322501c2a55a59723a4b21880dfb35 100644
*** a/src/backend/utils/cache/relcache.c
--- b/src/backend/utils/cache/relcache.c
***************
*** 39,45 ****
#include "catalog/index.h"
#include "catalog/indexing.h"
#include "catalog/namespace.h"
- #include "catalog/pg_amop.h"
#include "catalog/pg_amproc.h"
#include "catalog/pg_attrdef.h"
#include "catalog/pg_authid.h"
--- 39,44 ----
***************
*** 48,54 ****
#include "catalog/pg_database.h"
#include "catalog/pg_namespace.h"
#include "catalog/pg_opclass.h"
- #include "catalog/pg_operator.h"
#include "catalog/pg_proc.h"
#include "catalog/pg_rewrite.h"
#include "catalog/pg_tablespace.h"
--- 47,52 ----
***************
*** 84,93 ****
*/
#define RELCACHE_INIT_FILENAME "pg_internal.init"
! #define RELCACHE_INIT_FILEMAGIC 0x573265 /* version ID value */
/*
! * hardcoded tuple descriptors, generated by genbki.pl
*/
static const FormData_pg_attribute Desc_pg_class[Natts_pg_class] = {Schema_pg_class};
static const FormData_pg_attribute Desc_pg_attribute[Natts_pg_attribute] = {Schema_pg_attribute};
--- 82,91 ----
*/
#define RELCACHE_INIT_FILENAME "pg_internal.init"
! #define RELCACHE_INIT_FILEMAGIC 0x573266 /* version ID value */
/*
! * hardcoded tuple descriptors, contents generated by genbki.pl
*/
static const FormData_pg_attribute Desc_pg_class[Natts_pg_class] = {Schema_pg_class};
static const FormData_pg_attribute Desc_pg_attribute[Natts_pg_attribute] = {Schema_pg_attribute};
*************** do { \
*** 185,203 ****
/*
* Special cache for opclass-related information
*
! * Note: only default operators and support procs get cached, ie, those with
* lefttype = righttype = opcintype.
*/
typedef struct opclasscacheent
{
Oid opclassoid; /* lookup key: OID of opclass */
bool valid; /* set TRUE after successful fill-in */
- StrategyNumber numStrats; /* max # of strategies (from pg_am) */
StrategyNumber numSupport; /* max # of support procs (from pg_am) */
Oid opcfamily; /* OID of opclass's family */
Oid opcintype; /* OID of opclass's declared input type */
! Oid *operatorOids; /* strategy operators' OIDs */
! RegProcedure *supportProcs; /* support procs */
} OpClassCacheEnt;
static HTAB *OpClassCache = NULL;
--- 183,199 ----
/*
* Special cache for opclass-related information
*
! * Note: only default support procs get cached, ie, those with
* lefttype = righttype = opcintype.
*/
typedef struct opclasscacheent
{
Oid opclassoid; /* lookup key: OID of opclass */
bool valid; /* set TRUE after successful fill-in */
StrategyNumber numSupport; /* max # of support procs (from pg_am) */
Oid opcfamily; /* OID of opclass's family */
Oid opcintype; /* OID of opclass's declared input type */
! RegProcedure *supportProcs; /* OIDs of support procedures */
} OpClassCacheEnt;
static HTAB *OpClassCache = NULL;
*************** static void AttrDefaultFetch(Relation re
*** 231,245 ****
static void CheckConstraintFetch(Relation relation);
static List *insert_ordered_oid(List *list, Oid datum);
static void IndexSupportInitialize(oidvector *indclass,
- Oid *indexOperator,
RegProcedure *indexSupport,
Oid *opFamily,
Oid *opcInType,
- StrategyNumber maxStrategyNumber,
StrategyNumber maxSupportNumber,
AttrNumber maxAttributeNumber);
static OpClassCacheEnt *LookupOpclassInfo(Oid operatorClassOid,
- StrategyNumber numStrats,
StrategyNumber numSupport);
static void RelationCacheInitFileRemoveInDir(const char *tblspcpath);
static void unlink_initfile(const char *initfilename);
--- 227,238 ----
*************** RelationInitIndexAccessInfo(Relation rel
*** 980,986 ****
MemoryContext indexcxt;
MemoryContext oldcontext;
int natts;
- uint16 amstrategies;
uint16 amsupport;
/*
--- 973,978 ----
*************** RelationInitIndexAccessInfo(Relation rel
*** 1015,1021 ****
if (natts != relation->rd_index->indnatts)
elog(ERROR, "relnatts disagrees with indnatts for index %u",
RelationGetRelid(relation));
- amstrategies = aform->amstrategies;
amsupport = aform->amsupport;
/*
--- 1007,1012 ----
*************** RelationInitIndexAccessInfo(Relation rel
*** 1044,1056 ****
relation->rd_opcintype = (Oid *)
MemoryContextAllocZero(indexcxt, natts * sizeof(Oid));
- if (amstrategies > 0)
- relation->rd_operator = (Oid *)
- MemoryContextAllocZero(indexcxt,
- natts * amstrategies * sizeof(Oid));
- else
- relation->rd_operator = NULL;
-
if (amsupport > 0)
{
int nsupport = natts * amsupport;
--- 1035,1040 ----
*************** RelationInitIndexAccessInfo(Relation rel
*** 1082,1095 ****
indclass = (oidvector *) DatumGetPointer(indclassDatum);
/*
! * Fill the operator and support procedure OID arrays, as well as the info
! * about opfamilies and opclass input types. (aminfo and supportinfo are
! * left as zeroes, and are filled on-the-fly when used)
*/
! IndexSupportInitialize(indclass,
! relation->rd_operator, relation->rd_support,
relation->rd_opfamily, relation->rd_opcintype,
! amstrategies, amsupport, natts);
/*
* Similarly extract indoption and copy it to the cache entry
--- 1066,1078 ----
indclass = (oidvector *) DatumGetPointer(indclassDatum);
/*
! * Fill the support procedure OID array, as well as the info about
! * opfamilies and opclass input types. (aminfo and supportinfo are left
! * as zeroes, and are filled on-the-fly when used)
*/
! IndexSupportInitialize(indclass, relation->rd_support,
relation->rd_opfamily, relation->rd_opcintype,
! amsupport, natts);
/*
* Similarly extract indoption and copy it to the cache entry
*************** RelationInitIndexAccessInfo(Relation rel
*** 1118,1139 ****
* Initializes an index's cached opclass information,
* given the index's pg_index.indclass entry.
*
! * Data is returned into *indexOperator, *indexSupport, *opFamily, and
! * *opcInType, which are arrays allocated by the caller.
*
! * The caller also passes maxStrategyNumber, maxSupportNumber, and
! * maxAttributeNumber, since these indicate the size of the arrays
! * it has allocated --- but in practice these numbers must always match
! * those obtainable from the system catalog entries for the index and
! * access method.
*/
static void
IndexSupportInitialize(oidvector *indclass,
- Oid *indexOperator,
RegProcedure *indexSupport,
Oid *opFamily,
Oid *opcInType,
- StrategyNumber maxStrategyNumber,
StrategyNumber maxSupportNumber,
AttrNumber maxAttributeNumber)
{
--- 1101,1119 ----
* Initializes an index's cached opclass information,
* given the index's pg_index.indclass entry.
*
! * Data is returned into *indexSupport, *opFamily, and *opcInType,
! * which are arrays allocated by the caller.
*
! * The caller also passes maxSupportNumber and maxAttributeNumber, since these
! * indicate the size of the arrays it has allocated --- but in practice these
! * numbers must always match those obtainable from the system catalog entries
! * for the index and access method.
*/
static void
IndexSupportInitialize(oidvector *indclass,
RegProcedure *indexSupport,
Oid *opFamily,
Oid *opcInType,
StrategyNumber maxSupportNumber,
AttrNumber maxAttributeNumber)
{
*************** IndexSupportInitialize(oidvector *indcla
*** 1148,1163 ****
/* look up the info for this opclass, using a cache */
opcentry = LookupOpclassInfo(indclass->values[attIndex],
- maxStrategyNumber,
maxSupportNumber);
/* copy cached data into relcache entry */
opFamily[attIndex] = opcentry->opcfamily;
opcInType[attIndex] = opcentry->opcintype;
- if (maxStrategyNumber > 0)
- memcpy(&indexOperator[attIndex * maxStrategyNumber],
- opcentry->operatorOids,
- maxStrategyNumber * sizeof(Oid));
if (maxSupportNumber > 0)
memcpy(&indexSupport[attIndex * maxSupportNumber],
opcentry->supportProcs,
--- 1128,1138 ----
*************** IndexSupportInitialize(oidvector *indcla
*** 1171,1179 ****
* This routine maintains a per-opclass cache of the information needed
* by IndexSupportInitialize(). This is more efficient than relying on
* the catalog cache, because we can load all the info about a particular
! * opclass in a single indexscan of pg_amproc or pg_amop.
*
! * The information from pg_am about expected range of strategy and support
* numbers is passed in, rather than being looked up, mainly because the
* caller will have it already.
*
--- 1146,1154 ----
* This routine maintains a per-opclass cache of the information needed
* by IndexSupportInitialize(). This is more efficient than relying on
* the catalog cache, because we can load all the info about a particular
! * opclass in a single indexscan of pg_amproc.
*
! * The information from pg_am about expected range of support function
* numbers is passed in, rather than being looked up, mainly because the
* caller will have it already.
*
*************** IndexSupportInitialize(oidvector *indcla
*** 1187,1193 ****
*/
static OpClassCacheEnt *
LookupOpclassInfo(Oid operatorClassOid,
- StrategyNumber numStrats,
StrategyNumber numSupport)
{
OpClassCacheEnt *opcentry;
--- 1162,1167 ----
*************** LookupOpclassInfo(Oid operatorClassOid,
*** 1223,1238 ****
{
/* Need to allocate memory for new entry */
opcentry->valid = false; /* until known OK */
- opcentry->numStrats = numStrats;
opcentry->numSupport = numSupport;
- if (numStrats > 0)
- opcentry->operatorOids = (Oid *)
- MemoryContextAllocZero(CacheMemoryContext,
- numStrats * sizeof(Oid));
- else
- opcentry->operatorOids = NULL;
-
if (numSupport > 0)
opcentry->supportProcs = (RegProcedure *)
MemoryContextAllocZero(CacheMemoryContext,
--- 1197,1204 ----
*************** LookupOpclassInfo(Oid operatorClassOid,
*** 1242,1248 ****
}
else
{
- Assert(numStrats == opcentry->numStrats);
Assert(numSupport == opcentry->numSupport);
}
--- 1208,1213 ----
*************** LookupOpclassInfo(Oid operatorClassOid,
*** 1273,1279 ****
/*
* We have to fetch the pg_opclass row to determine its opfamily and
! * opcintype, which are needed to look up the operators and functions.
* It'd be convenient to use the syscache here, but that probably doesn't
* work while bootstrapping.
*/
--- 1238,1244 ----
/*
* We have to fetch the pg_opclass row to determine its opfamily and
! * opcintype, which are needed to look up related operators and functions.
* It'd be convenient to use the syscache here, but that probably doesn't
* work while bootstrapping.
*/
*************** LookupOpclassInfo(Oid operatorClassOid,
*** 1298,1342 ****
systable_endscan(scan);
heap_close(rel, AccessShareLock);
-
- /*
- * Scan pg_amop to obtain operators for the opclass. We only fetch the
- * default ones (those with lefttype = righttype = opcintype).
- */
- if (numStrats > 0)
- {
- ScanKeyInit(&skey[0],
- Anum_pg_amop_amopfamily,
- BTEqualStrategyNumber, F_OIDEQ,
- ObjectIdGetDatum(opcentry->opcfamily));
- ScanKeyInit(&skey[1],
- Anum_pg_amop_amoplefttype,
- BTEqualStrategyNumber, F_OIDEQ,
- ObjectIdGetDatum(opcentry->opcintype));
- ScanKeyInit(&skey[2],
- Anum_pg_amop_amoprighttype,
- BTEqualStrategyNumber, F_OIDEQ,
- ObjectIdGetDatum(opcentry->opcintype));
- rel = heap_open(AccessMethodOperatorRelationId, AccessShareLock);
- scan = systable_beginscan(rel, AccessMethodStrategyIndexId, indexOK,
- SnapshotNow, 3, skey);
-
- while (HeapTupleIsValid(htup = systable_getnext(scan)))
- {
- Form_pg_amop amopform = (Form_pg_amop) GETSTRUCT(htup);
-
- if (amopform->amopstrategy <= 0 ||
- (StrategyNumber) amopform->amopstrategy > numStrats)
- elog(ERROR, "invalid amopstrategy number %d for opclass %u",
- amopform->amopstrategy, operatorClassOid);
- opcentry->operatorOids[amopform->amopstrategy - 1] =
- amopform->amopopr;
- }
-
- systable_endscan(scan);
- heap_close(rel, AccessShareLock);
- }
-
/*
* Scan pg_amproc to obtain support procs for the opclass. We only fetch
* the default ones (those with lefttype = righttype = opcintype).
--- 1263,1268 ----
*************** RelationCacheInitializePhase3(void)
*** 2907,2924 ****
IndexRelationId);
load_critical_index(OpclassOidIndexId,
OperatorClassRelationId);
- load_critical_index(AccessMethodStrategyIndexId,
- AccessMethodOperatorRelationId);
load_critical_index(AccessMethodProcedureIndexId,
AccessMethodProcedureRelationId);
- load_critical_index(OperatorOidIndexId,
- OperatorRelationId);
load_critical_index(RewriteRelRulenameIndexId,
RewriteRelationId);
load_critical_index(TriggerRelidNameIndexId,
TriggerRelationId);
! #define NUM_CRITICAL_LOCAL_INDEXES 9 /* fix if you change list above */
criticalRelcachesBuilt = true;
}
--- 2833,2846 ----
IndexRelationId);
load_critical_index(OpclassOidIndexId,
OperatorClassRelationId);
load_critical_index(AccessMethodProcedureIndexId,
AccessMethodProcedureRelationId);
load_critical_index(RewriteRelRulenameIndexId,
RewriteRelationId);
load_critical_index(TriggerRelidNameIndexId,
TriggerRelationId);
! #define NUM_CRITICAL_LOCAL_INDEXES 7 /* fix if you change list above */
criticalRelcachesBuilt = true;
}
*************** load_relcache_init_file(bool shared)
*** 4044,4050 ****
MemoryContext indexcxt;
Oid *opfamily;
Oid *opcintype;
- Oid *operator;
RegProcedure *support;
int nsupport;
int16 *indoption;
--- 3966,3971 ----
*************** load_relcache_init_file(bool shared)
*** 4105,4121 ****
rel->rd_opcintype = opcintype;
! /* next, read the vector of operator OIDs */
! if (fread(&len, 1, sizeof(len), fp) != sizeof(len))
! goto read_failed;
!
! operator = (Oid *) MemoryContextAlloc(indexcxt, len);
! if (fread(operator, 1, len, fp) != len)
! goto read_failed;
!
! rel->rd_operator = operator;
!
! /* next, read the vector of support procedures */
if (fread(&len, 1, sizeof(len), fp) != sizeof(len))
goto read_failed;
support = (RegProcedure *) MemoryContextAlloc(indexcxt, len);
--- 4026,4032 ----
rel->rd_opcintype = opcintype;
! /* next, read the vector of support procedure OIDs */
if (fread(&len, 1, sizeof(len), fp) != sizeof(len))
goto read_failed;
support = (RegProcedure *) MemoryContextAlloc(indexcxt, len);
*************** load_relcache_init_file(bool shared)
*** 4154,4160 ****
Assert(rel->rd_aminfo == NULL);
Assert(rel->rd_opfamily == NULL);
Assert(rel->rd_opcintype == NULL);
- Assert(rel->rd_operator == NULL);
Assert(rel->rd_support == NULL);
Assert(rel->rd_supportinfo == NULL);
Assert(rel->rd_indoption == NULL);
--- 4065,4070 ----
*************** write_relcache_init_file(bool shared)
*** 4371,4382 ****
relform->relnatts * sizeof(Oid),
fp);
! /* next, write the vector of operator OIDs */
! write_item(rel->rd_operator,
! relform->relnatts * (am->amstrategies * sizeof(Oid)),
! fp);
!
! /* next, write the vector of support procedures */
write_item(rel->rd_support,
relform->relnatts * (am->amsupport * sizeof(RegProcedure)),
fp);
--- 4281,4287 ----
relform->relnatts * sizeof(Oid),
fp);
! /* next, write the vector of support procedure OIDs */
write_item(rel->rd_support,
relform->relnatts * (am->amsupport * sizeof(RegProcedure)),
fp);
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index 785acc955ad652254c547d015715ec6ac1841925..d084338f356206c354a0a85179ea358862eab5bb 100644
*** a/src/include/nodes/relation.h
--- b/src/include/nodes/relation.h
*************** typedef struct RelOptInfo
*** 421,440 ****
* IndexOptInfo
* Per-index information for planning/optimization
*
! * Prior to Postgres 7.0, RelOptInfo was used to describe both relations
! * and indexes, but that created confusion without actually doing anything
! * useful. So now we have a separate IndexOptInfo struct for indexes.
! *
! * opfamily[], indexkeys[], opcintype[], fwdsortop[], revsortop[],
! * and nulls_first[] each have ncolumns entries.
*
* Zeroes in the indexkeys[] array indicate index columns that are
* expressions; there is one element in indexprs for each such column.
*
! * For an unordered index, the sortop arrays contains zeroes. Note that
! * fwdsortop[] and nulls_first[] describe the sort ordering of a forward
! * indexscan; we can also consider a backward indexscan, which will
! * generate sort order described by revsortop/!nulls_first.
*
* The indexprs and indpred expressions have been run through
* prepqual.c and eval_const_expressions() for ease of matching to
--- 421,437 ----
* IndexOptInfo
* Per-index information for planning/optimization
*
! * opfamily[], indexkeys[], and opcintype[] each have ncolumns entries.
! * sortopfamily[], reverse_sort[], and nulls_first[] likewise have
! * ncolumns entries, if the index is ordered; but if it is unordered,
! * those pointers are NULL.
*
* Zeroes in the indexkeys[] array indicate index columns that are
* expressions; there is one element in indexprs for each such column.
*
! * For an ordered index, reverse_sort[] and nulls_first[] describe the
! * sort ordering of a forward indexscan; we can also consider a backward
! * indexscan, which will generate the reverse ordering.
*
* The indexprs and indpred expressions have been run through
* prepqual.c and eval_const_expressions() for ease of matching to
*************** typedef struct IndexOptInfo
*** 457,464 ****
Oid *opfamily; /* OIDs of operator families for columns */
int *indexkeys; /* column numbers of index's keys, or 0 */
Oid *opcintype; /* OIDs of opclass declared input data types */
! Oid *fwdsortop; /* OIDs of sort operators for each column */
! Oid *revsortop; /* OIDs of sort operators for backward scan */
bool *nulls_first; /* do NULLs come first in the sort order? */
Oid relam; /* OID of the access method (in pg_am) */
--- 454,461 ----
Oid *opfamily; /* OIDs of operator families for columns */
int *indexkeys; /* column numbers of index's keys, or 0 */
Oid *opcintype; /* OIDs of opclass declared input data types */
! Oid *sortopfamily; /* OIDs of btree opfamilies, if orderable */
! bool *reverse_sort; /* is sort order descending? */
bool *nulls_first; /* do NULLs come first in the sort order? */
Oid relam; /* OID of the access method (in pg_am) */
diff --git a/src/include/utils/rel.h b/src/include/utils/rel.h
index 9ad92c299e8355ce9874478c76d71330b940e382..39e0365c0b124022f2ec487d8be6a4fa2668760d 100644
*** a/src/include/utils/rel.h
--- b/src/include/utils/rel.h
*************** typedef struct RelationData
*** 178,187 ****
/*
* index access support info (used only for an index relation)
*
! * Note: only default operators and support procs for each opclass are
! * cached, namely those with lefttype and righttype equal to the opclass's
! * opcintype. The arrays are indexed by strategy or support number, which
! * is a sufficient identifier given that restriction.
*
* Note: rd_amcache is available for index AMs to cache private data about
* an index. This must be just a cache since it may get reset at any time
--- 178,187 ----
/*
* index access support info (used only for an index relation)
*
! * Note: only default support procs for each opclass are cached, namely
! * those with lefttype and righttype equal to the opclass's opcintype.
! * The arrays are indexed by support function number, which is a
! * sufficient identifier given that restriction.
*
* Note: rd_amcache is available for index AMs to cache private data about
* an index. This must be just a cache since it may get reset at any time
*************** typedef struct RelationData
*** 194,200 ****
RelationAmInfo *rd_aminfo; /* lookup info for funcs found in pg_am */
Oid *rd_opfamily; /* OIDs of op families for each index col */
Oid *rd_opcintype; /* OIDs of opclass declared input data types */
- Oid *rd_operator; /* OIDs of index operators */
RegProcedure *rd_support; /* OIDs of support procedures */
FmgrInfo *rd_supportinfo; /* lookup info for support procedures */
int16 *rd_indoption; /* per-column AM-specific flags */
--- 194,199 ----