Skip to content

Commit c0b5fac

Browse files
tglsfdctglsfdc
committed
Simplify and speed up mapping of index opfamilies to pathkeys.
Formerly we looked up the operators associated with each index (caching them in relcache) and then the planner looked up the btree opfamily containing such operators in order to build the btree-centric pathkey representation that describes the index's sort order. This is quite pointless for btree indexes: we might as well just use the index's opfamily information directly. That saves syscache lookup cycles during planning, and furthermore allows us to eliminate the relcache's caching of operators altogether, which may help in reducing backend startup time. I added code to plancat.c to perform the same type of double lookup on-the-fly if it's ever faced with a non-btree amcanorder index AM. If such a thing actually becomes interesting for production, we should replace that logic with some more-direct method for identifying the corresponding btree opfamily; but it's not worth spending effort on now. There is considerably more to do pursuant to my recent proposal to get rid of sort-operator-based representations of sort orderings, but this patch grabs some of the low-hanging fruit. I'll look at the remainder of that work after the current commitfest.
1 parent 3c42efc commit c0b5fac

File tree

7 files changed

+217
-258
lines changed

7 files changed

+217
-258
lines changed

‎src/backend/optimizer/path/indxpath.c

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -380,7 +380,7 @@ find_usable_indexes(PlannerInfo *root, RelOptInfo *rel,
380380
* how many of them are actually useful for this query. This is not
381381
* relevant unless we are at top level.
382382
*/
383-
index_is_ordered = OidIsValid(index->fwdsortop[0]);
383+
index_is_ordered = (index->sortopfamily != NULL);
384384
if (index_is_ordered && possibly_useful_pathkeys &&
385385
istoplevel && outer_rel == NULL)
386386
{

‎src/backend/optimizer/path/pathkeys.c

Lines changed: 81 additions & 56 deletions
Original file line numberDiff line numberDiff line change
@@ -36,12 +36,6 @@ static PathKey *make_canonical_pathkey(PlannerInfo *root,
3636
EquivalenceClass *eclass, Oid opfamily,
3737
int strategy, bool nulls_first);
3838
static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys);
39-
static PathKey *make_pathkey_from_sortinfo(PlannerInfo *root,
40-
Expr *expr, Oid ordering_op,
41-
bool nulls_first,
42-
Index sortref,
43-
bool create_it,
44-
bool canonicalize);
4539
static Var *find_indexkey_var(PlannerInfo *root, RelOptInfo *rel,
4640
AttrNumber varattno);
4741
static bool right_merge_direction(PlannerInfo *root, PathKey *pathkey);
@@ -224,9 +218,9 @@ canonicalize_pathkeys(PlannerInfo *root, List *pathkeys)
224218

225219
/*
226220
* make_pathkey_from_sortinfo
227-
* Given an expression, a sortop, and a nulls-first flag, create
228-
* a PathKey. If canonicalize = true, the result is a "canonical"
229-
* PathKey, otherwise not. (But note it might be redundant anyway.)
221+
* Given an expression and sort-order information, create a PathKey.
222+
* If canonicalize = true, the result is a "canonical" PathKey,
223+
* otherwise not. (But note it might be redundant anyway.)
230224
*
231225
* If the PathKey is being generated from a SortGroupClause, sortref should be
232226
* the SortGroupClause's SortGroupRef; otherwise zero.
@@ -240,46 +234,39 @@ canonicalize_pathkeys(PlannerInfo *root, List *pathkeys)
240234
*/
241235
static PathKey *
242236
make_pathkey_from_sortinfo(PlannerInfo *root,
243-
Expr *expr, Oid ordering_op,
237+
Expr *expr,
238+
Oid opfamily,
239+
Oid opcintype,
240+
bool reverse_sort,
244241
bool nulls_first,
245242
Index sortref,
246243
bool create_it,
247244
bool canonicalize)
248245
{
249-
Oid opfamily,
250-
opcintype;
251246
int16 strategy;
252247
Oid equality_op;
253248
List *opfamilies;
254249
EquivalenceClass *eclass;
255250

251+
strategy = reverse_sort ? BTGreaterStrategyNumber : BTLessStrategyNumber;
252+
256253
/*
257-
* An ordering operator fully determines the behavior of its opfamily, so
258-
* could only meaningfully appear in one family --- or perhaps two if one
259-
* builds a reverse-sort opfamily, but there's not much point in that
260-
* anymore. But EquivalenceClasses need to contain opfamily lists based
261-
* on the family membership of equality operators, which could easily be
262-
* bigger. So, look up the equality operator that goes with the ordering
263-
* operator (this should be unique) and get its membership.
254+
* EquivalenceClasses need to contain opfamily lists based on the family
255+
* membership of mergejoinable equality operators, which could belong to
256+
* more than one opfamily. So we have to look up the opfamily's equality
257+
* operator and get its membership.
264258
*/
265-
266-
/* Find the operator in pg_amop --- failure shouldn't happen */
267-
if (!get_ordering_op_properties(ordering_op,
268-
&opfamily, &opcintype, &strategy))
269-
elog(ERROR, "operator %u is not a valid ordering operator",
270-
ordering_op);
271-
/* Get matching equality operator */
272259
equality_op = get_opfamily_member(opfamily,
273260
opcintype,
274261
opcintype,
275262
BTEqualStrategyNumber);
276263
if (!OidIsValid(equality_op)) /* shouldn't happen */
277-
elog(ERROR, "could not find equality operator for ordering operator %u",
278-
ordering_op);
264+
elog(ERROR, "could not find equality operator for opfamily %u",
265+
opfamily);
279266
opfamilies = get_mergejoin_opfamilies(equality_op);
280267
if (!opfamilies) /* certainly should find some */
281-
elog(ERROR, "could not find opfamilies for ordering operator %u",
282-
ordering_op);
268+
elog(ERROR, "could not find opfamilies for equality operator %u",
269+
equality_op);
283270

284271
/*
285272
* When dealing with binary-compatible opclasses, we have to ensure that
@@ -322,6 +309,42 @@ make_pathkey_from_sortinfo(PlannerInfo *root,
322309
return makePathKey(eclass, opfamily, strategy, nulls_first);
323310
}
324311

312+
/*
313+
* make_pathkey_from_sortop
314+
* Like make_pathkey_from_sortinfo, but work from a sort operator.
315+
*
316+
* This should eventually go away, but we need to restructure SortGroupClause
317+
* first.
318+
*/
319+
static PathKey *
320+
make_pathkey_from_sortop(PlannerInfo *root,
321+
Expr *expr,
322+
Oid ordering_op,
323+
bool nulls_first,
324+
Index sortref,
325+
bool create_it,
326+
bool canonicalize)
327+
{
328+
Oid opfamily,
329+
opcintype;
330+
int16 strategy;
331+
332+
/* Find the operator in pg_amop --- failure shouldn't happen */
333+
if (!get_ordering_op_properties(ordering_op,
334+
&opfamily, &opcintype, &strategy))
335+
elog(ERROR, "operator %u is not a valid ordering operator",
336+
ordering_op);
337+
return make_pathkey_from_sortinfo(root,
338+
expr,
339+
opfamily,
340+
opcintype,
341+
(strategy == BTGreaterStrategyNumber),
342+
nulls_first,
343+
sortref,
344+
create_it,
345+
canonicalize);
346+
}
347+
325348

326349
/****************************************************************************
327350
* PATHKEY COMPARISONS
@@ -479,11 +502,10 @@ get_cheapest_fractional_path_for_pathkeys(List *paths,
479502
* build_index_pathkeys
480503
* Build a pathkeys list that describes the ordering induced by an index
481504
* scan using the given index. (Note that an unordered index doesn't
482-
* induce any ordering; such an index will have no sortop OIDS in
483-
* its sortops arrays, and we will return NIL.)
505+
* induce any ordering, so we return NIL.)
484506
*
485-
* If 'scandir' is BackwardScanDirection, attempt to build pathkeys
486-
* representing a backwards scan of the index. Return NIL if can't do it.
507+
* If 'scandir' is BackwardScanDirection, build pathkeys representing a
508+
* backwards scan of the index.
487509
*
488510
* The result is canonical, meaning that redundant pathkeys are removed;
489511
* it may therefore have fewer entries than there are index columns.
@@ -500,31 +522,32 @@ build_index_pathkeys(PlannerInfo *root,
500522
ScanDirection scandir)
501523
{
502524
List *retval = NIL;
503-
ListCell *indexprs_item = list_head(index->indexprs);
525+
ListCell *indexprs_item;
504526
int i;
505527

528+
if (index->sortopfamily == NULL)
529+
return NIL; /* non-orderable index */
530+
531+
indexprs_item = list_head(index->indexprs);
506532
for (i = 0; i < index->ncolumns; i++)
507533
{
508-
Oid sortop;
534+
bool reverse_sort;
509535
bool nulls_first;
510536
int ikey;
511537
Expr *indexkey;
512538
PathKey *cpathkey;
513539

514540
if (ScanDirectionIsBackward(scandir))
515541
{
516-
sortop = index->revsortop[i];
542+
reverse_sort = !index->reverse_sort[i];
517543
nulls_first = !index->nulls_first[i];
518544
}
519545
else
520546
{
521-
sortop = index->fwdsortop[i];
547+
reverse_sort = index->reverse_sort[i];
522548
nulls_first = index->nulls_first[i];
523549
}
524550

525-
if (!OidIsValid(sortop))
526-
break; /* no more orderable columns */
527-
528551
ikey = index->indexkeys[i];
529552
if (ikey != 0)
530553
{
@@ -543,7 +566,9 @@ build_index_pathkeys(PlannerInfo *root,
543566
/* OK, try to make a canonical pathkey for this sort key */
544567
cpathkey = make_pathkey_from_sortinfo(root,
545568
indexkey,
546-
sortop,
569+
index->sortopfamily[i],
570+
index->opcintype[i],
571+
reverse_sort,
547572
nulls_first,
548573
0,
549574
false,
@@ -892,13 +917,13 @@ make_pathkeys_for_sortclauses(PlannerInfo *root,
892917

893918
sortkey = (Expr *) get_sortgroupclause_expr(sortcl, tlist);
894919
Assert(OidIsValid(sortcl->sortop));
895-
pathkey = make_pathkey_from_sortinfo(root,
896-
sortkey,
897-
sortcl->sortop,
898-
sortcl->nulls_first,
899-
sortcl->tleSortGroupRef,
900-
true,
901-
canonicalize);
920+
pathkey = make_pathkey_from_sortop(root,
921+
sortkey,
922+
sortcl->sortop,
923+
sortcl->nulls_first,
924+
sortcl->tleSortGroupRef,
925+
true,
926+
canonicalize);
902927

903928
/* Canonical form eliminates redundant ordering keys */
904929
if (canonicalize)
@@ -935,13 +960,13 @@ make_pathkeys_for_aggregate(PlannerInfo *root,
935960
* We arbitrarily set nulls_first to false. Actually, a MIN/MAX agg can
936961
* use either nulls ordering option, but that is dealt with elsewhere.
937962
*/
938-
pathkey = make_pathkey_from_sortinfo(root,
939-
aggtarget,
940-
aggsortop,
941-
false, /* nulls_first */
942-
0,
943-
true,
944-
false);
963+
pathkey = make_pathkey_from_sortop(root,
964+
aggtarget,
965+
aggsortop,
966+
false, /* nulls_first */
967+
0,
968+
true,
969+
false);
945970
return list_make1(pathkey);
946971
}
947972

‎src/backend/optimizer/util/plancat.c

Lines changed: 72 additions & 41 deletions
Original file line numberDiff line numberDiff line change
@@ -189,19 +189,9 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
189189
RelationGetForm(indexRelation)->reltablespace;
190190
info->rel = rel;
191191
info->ncolumns = ncolumns = index->indnatts;
192-
193-
/*
194-
* Allocate per-column info arrays. To save a few palloc cycles
195-
* we allocate all the Oid-type arrays in one request. We must
196-
* pre-zero the sortop and nulls_first arrays in case the index is
197-
* unordered.
198-
*/
199192
info->indexkeys = (int *) palloc(sizeof(int) * ncolumns);
200-
info->opfamily = (Oid *) palloc0(sizeof(Oid) * (4 * ncolumns));
201-
info->opcintype = info->opfamily + ncolumns;
202-
info->fwdsortop = info->opcintype + ncolumns;
203-
info->revsortop = info->fwdsortop + ncolumns;
204-
info->nulls_first = (bool *) palloc0(sizeof(bool) * ncolumns);
193+
info->opfamily = (Oid *) palloc(sizeof(Oid) * ncolumns);
194+
info->opcintype = (Oid *) palloc(sizeof(Oid) * ncolumns);
205195

206196
for (i = 0; i < ncolumns; i++)
207197
{
@@ -219,49 +209,90 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
219209
info->amhasgetbitmap = OidIsValid(indexRelation->rd_am->amgetbitmap);
220210

221211
/*
222-
* Fetch the ordering operators associated with the index, if any.
223-
* We expect that all ordering-capable indexes use btree's
224-
* strategy numbers for the ordering operators.
212+
* Fetch the ordering information for the index, if any.
225213
*/
226-
if (indexRelation->rd_am->amcanorder)
214+
if (info->relam == BTREE_AM_OID)
227215
{
228-
int nstrat = indexRelation->rd_am->amstrategies;
216+
/*
217+
* If it's a btree index, we can use its opfamily OIDs
218+
* directly as the sort ordering opfamily OIDs.
219+
*/
220+
Assert(indexRelation->rd_am->amcanorder);
221+
222+
info->sortopfamily = info->opfamily;
223+
info->reverse_sort = (bool *) palloc(sizeof(bool) * ncolumns);
224+
info->nulls_first = (bool *) palloc(sizeof(bool) * ncolumns);
229225

230226
for (i = 0; i < ncolumns; i++)
231227
{
232228
int16 opt = indexRelation->rd_indoption[i];
233-
int fwdstrat;
234-
int revstrat;
235229

236-
if (opt & INDOPTION_DESC)
237-
{
238-
fwdstrat = BTGreaterStrategyNumber;
239-
revstrat = BTLessStrategyNumber;
240-
}
241-
else
242-
{
243-
fwdstrat = BTLessStrategyNumber;
244-
revstrat = BTGreaterStrategyNumber;
245-
}
230+
info->reverse_sort[i] = (opt & INDOPTION_DESC) != 0;
231+
info->nulls_first[i] = (opt & INDOPTION_NULLS_FIRST) != 0;
232+
}
233+
}
234+
else if (indexRelation->rd_am->amcanorder)
235+
{
236+
/*
237+
* Otherwise, identify the corresponding btree opfamilies by
238+
* trying to map this index's "<" operators into btree. Since
239+
* "<" uniquely defines the behavior of a sort order, this is
240+
* a sufficient test.
241+
*
242+
* XXX This method is rather slow and also requires the
243+
* undesirable assumption that the other index AM numbers its
244+
* strategies the same as btree. It'd be better to have a way
245+
* to explicitly declare the corresponding btree opfamily for
246+
* each opfamily of the other index type. But given the lack
247+
* of current or foreseeable amcanorder index types, it's not
248+
* worth expending more effort on now.
249+
*/
250+
info->sortopfamily = (Oid *) palloc(sizeof(Oid) * ncolumns);
251+
info->reverse_sort = (bool *) palloc(sizeof(bool) * ncolumns);
252+
info->nulls_first = (bool *) palloc(sizeof(bool) * ncolumns);
253+
254+
for (i = 0; i < ncolumns; i++)
255+
{
256+
int16 opt = indexRelation->rd_indoption[i];
257+
Oid ltopr;
258+
Oid btopfamily;
259+
Oid btopcintype;
260+
int16 btstrategy;
246261

247-
/*
248-
* Index AM must have a fixed set of strategies for it to
249-
* make sense to specify amcanorder, so we need not allow
250-
* the case amstrategies == 0.
251-
*/
252-
if (fwdstrat > 0)
262+
info->reverse_sort[i] = (opt & INDOPTION_DESC) != 0;
263+
info->nulls_first[i] = (opt & INDOPTION_NULLS_FIRST) != 0;
264+
265+
ltopr = get_opfamily_member(info->opfamily[i],
266+
info->opcintype[i],
267+
info->opcintype[i],
268+
BTLessStrategyNumber);
269+
if (OidIsValid(ltopr) &&
270+
get_ordering_op_properties(ltopr,
271+
&btopfamily,
272+
&btopcintype,
273+
&btstrategy) &&
274+
btopcintype == info->opcintype[i] &&
275+
btstrategy == BTLessStrategyNumber)
253276
{
254-
Assert(fwdstrat <= nstrat);
255-
info->fwdsortop[i] = indexRelation->rd_operator[i * nstrat + fwdstrat - 1];
277+
/* Successful mapping */
278+
info->sortopfamily[i] = btopfamily;
256279
}
257-
if (revstrat > 0)
280+
else
258281
{
259-
Assert(revstrat <= nstrat);
260-
info->revsortop[i] = indexRelation->rd_operator[i * nstrat + revstrat - 1];
282+
/* Fail ... quietly treat index as unordered */
283+
info->sortopfamily = NULL;
284+
info->reverse_sort = NULL;
285+
info->nulls_first = NULL;
286+
break;
261287
}
262-
info->nulls_first[i] = (opt & INDOPTION_NULLS_FIRST) != 0;
263288
}
264289
}
290+
else
291+
{
292+
info->sortopfamily = NULL;
293+
info->reverse_sort = NULL;
294+
info->nulls_first = NULL;
295+
}
265296

266297
/*
267298
* Fetch the index expressions and predicate, if any. We must

0 commit comments

Comments
 (0)