Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitbd6bf50

Browse files
committed
Teach planner to optionally ignore index columns that have an equality
constraint while determining whether the index sort order matches thequery's ORDER BY. This for example allows an index on (x,y) to match... WHERE x = 42 ORDER BY y;It only works for btree indexes, but since those are the only ones wecurrently have that are ordered at all, that's good enough for now.Per popular demand.
1 parent189f89c commitbd6bf50

File tree

1 file changed

+276
-13
lines changed

1 file changed

+276
-13
lines changed

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

Lines changed: 276 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,7 @@
99
*
1010
*
1111
* IDENTIFICATION
12-
* $PostgreSQL: pgsql/src/backend/optimizer/path/indxpath.c,v 1.184 2005/06/13 23:14:48 tgl Exp $
12+
* $PostgreSQL: pgsql/src/backend/optimizer/path/indxpath.c,v 1.185 2005/06/14 04:04:30 tgl Exp $
1313
*
1414
*-------------------------------------------------------------------------
1515
*/
@@ -65,6 +65,17 @@ static bool matches_any_index(RestrictInfo *rinfo, RelOptInfo *rel,
6565
Relidsouter_relids);
6666
staticList*find_clauses_for_join(PlannerInfo*root,RelOptInfo*rel,
6767
Relidsouter_relids,boolisouterjoin);
68+
staticboolmatch_variant_ordering(PlannerInfo*root,
69+
IndexOptInfo*index,
70+
List*restrictclauses,
71+
ScanDirection*indexscandir);
72+
staticList*identify_ignorable_ordering_cols(PlannerInfo*root,
73+
IndexOptInfo*index,
74+
List*restrictclauses);
75+
staticboolmatch_index_to_query_keys(PlannerInfo*root,
76+
IndexOptInfo*index,
77+
ScanDirectionindexscandir,
78+
List*ignorables);
6879
staticboolmatch_boolean_index_clause(Node*clause,intindexcol,
6980
IndexOptInfo*index);
7081
staticboolmatch_special_index_operator(Expr*clause,Oidopclass,
@@ -315,22 +326,24 @@ find_usable_indexes(PlannerInfo *root, RelOptInfo *rel,
315326
}
316327

317328
/*
318-
* 4. If the index is ordered, a backwards scan might be
319-
* interesting. Currently this is only possible for a DESC query
320-
* result ordering.
329+
* 4. If the index is ordered, and there is a requested query
330+
* ordering that we failed to match, consider variant ways of
331+
* achieving the ordering. Again, this is only interesting
332+
* at top level.
321333
*/
322-
if (istoplevel&&index_is_ordered&& !isjoininner)
334+
if (istoplevel&&index_is_ordered&& !isjoininner&&
335+
root->query_pathkeys!=NIL&&
336+
pathkeys_useful_for_ordering(root,useful_pathkeys)==0)
323337
{
324-
index_pathkeys=build_index_pathkeys(root,index,
325-
BackwardScanDirection);
326-
useful_pathkeys=truncate_useless_pathkeys(root,rel,
327-
index_pathkeys);
328-
if (useful_pathkeys!=NIL)
338+
ScanDirectionindexscandir;
339+
340+
if (match_variant_ordering(root,index,restrictclauses,
341+
&indexscandir))
329342
{
330343
ipath=create_index_path(root,index,
331344
restrictclauses,
332-
useful_pathkeys,
333-
BackwardScanDirection,
345+
root->query_pathkeys,
346+
indexscandir,
334347
false);
335348
result=lappend(result,ipath);
336349
}
@@ -1220,6 +1233,255 @@ find_clauses_for_join(PlannerInfo *root, RelOptInfo *rel,
12201233
returnclause_list;
12211234
}
12221235

1236+
/****************************************************************************
1237+
*---- ROUTINES TO HANDLE PATHKEYS ----
1238+
****************************************************************************/
1239+
1240+
/*
1241+
* match_variant_ordering
1242+
*Try to match an index's ordering to the query's requested ordering
1243+
*
1244+
* This is used when the index is ordered but a naive comparison fails to
1245+
* match its ordering (pathkeys) to root->query_pathkeys. It may be that
1246+
* we need to scan the index backwards. Also, a less naive comparison can
1247+
* help for both forward and backward indexscans. Columns of the index
1248+
* that have an equality restriction clause can be ignored in the match;
1249+
* that is, an index on (x,y) can be considered to match the ordering of
1250+
*... WHERE x = 42 ORDER BY y;
1251+
*
1252+
* Note: it would be possible to similarly ignore useless ORDER BY items;
1253+
* that is, an index on just y could be considered to match the ordering of
1254+
*... WHERE x = 42 ORDER BY x, y;
1255+
* But proving that this is safe would require finding a btree opclass
1256+
* containing both the = operator and the < or > operator in the ORDER BY
1257+
* item. That's significantly more expensive than what we do here, since
1258+
* we'd have to look at restriction clauses unrelated to the current index
1259+
* and search for opclasses without any hint from the index. The practical
1260+
* use-cases seem to be mostly covered by ignoring index columns, so that's
1261+
* all we do for now.
1262+
*
1263+
* Inputs:
1264+
* 'index' is the index of interest.
1265+
* 'restrictclauses' is the list of sublists of restriction clauses
1266+
*matching the columns of the index (NIL if none)
1267+
*
1268+
* Returns TRUE if able to match the requested query pathkeys, FALSE if not.
1269+
* In the TRUE case, sets '*indexscandir' to either ForwardScanDirection or
1270+
* BackwardScanDirection to indicate the proper scan direction.
1271+
*/
1272+
staticbool
1273+
match_variant_ordering(PlannerInfo*root,
1274+
IndexOptInfo*index,
1275+
List*restrictclauses,
1276+
ScanDirection*indexscandir)
1277+
{
1278+
List*ignorables;
1279+
1280+
/*
1281+
* Forget the whole thing if not a btree index; our check for ignorable
1282+
* columns assumes we are dealing with btree opclasses. (It'd be possible
1283+
* to factor out just the try for backwards indexscan, but considering
1284+
* that we presently have no orderable indexes except btrees anyway,
1285+
* it's hardly worth contorting this code for that case.)
1286+
*
1287+
* Note: if you remove this, you probably need to put in a check on
1288+
* amoptionalkey to prevent possible clauseless scan on an index that
1289+
* won't cope.
1290+
*/
1291+
if (index->relam!=BTREE_AM_OID)
1292+
return false;
1293+
/*
1294+
* Figure out which index columns can be optionally ignored because
1295+
* they have an equality constraint. This is the same set for either
1296+
* forward or backward scan, so we do it just once.
1297+
*/
1298+
ignorables=identify_ignorable_ordering_cols(root,index,
1299+
restrictclauses);
1300+
/*
1301+
* Try to match to forward scan, then backward scan. However, we can
1302+
* skip the forward-scan case if there are no ignorable columns,
1303+
* because find_usable_indexes() would have found the match already.
1304+
*/
1305+
if (ignorables&&
1306+
match_index_to_query_keys(root,index,ForwardScanDirection,
1307+
ignorables))
1308+
{
1309+
*indexscandir=ForwardScanDirection;
1310+
return true;
1311+
}
1312+
if (match_index_to_query_keys(root,index,BackwardScanDirection,
1313+
ignorables))
1314+
{
1315+
*indexscandir=BackwardScanDirection;
1316+
return true;
1317+
}
1318+
return false;
1319+
}
1320+
1321+
/*
1322+
* identify_ignorable_ordering_cols
1323+
*Determine which index columns can be ignored for ordering purposes
1324+
*
1325+
* Returns an integer List of column numbers (1-based) of ignorable
1326+
* columns. The ignorable columns are those that have equality constraints
1327+
* against pseudoconstants.
1328+
*/
1329+
staticList*
1330+
identify_ignorable_ordering_cols(PlannerInfo*root,
1331+
IndexOptInfo*index,
1332+
List*restrictclauses)
1333+
{
1334+
List*result=NIL;
1335+
intindexcol=0;/* note this is 0-based */
1336+
ListCell*l;
1337+
1338+
/* restrictclauses is either NIL or has a sublist per column */
1339+
foreach(l,restrictclauses)
1340+
{
1341+
List*sublist= (List*)lfirst(l);
1342+
Oidopclass=index->classlist[indexcol];
1343+
ListCell*l2;
1344+
1345+
foreach(l2,sublist)
1346+
{
1347+
RestrictInfo*rinfo= (RestrictInfo*)lfirst(l2);
1348+
OpExpr*clause= (OpExpr*)rinfo->clause;
1349+
Oidclause_op;
1350+
intop_strategy;
1351+
boolvaronleft;
1352+
boolispc;
1353+
1354+
/* We know this clause passed match_clause_to_indexcol */
1355+
1356+
/* First check for boolean-index cases. */
1357+
if (IsBooleanOpclass(opclass))
1358+
{
1359+
if (match_boolean_index_clause((Node*)clause,indexcol,
1360+
index))
1361+
{
1362+
/*
1363+
* The clause means either col = TRUE or col = FALSE;
1364+
* we do not care which, it's an equality constraint
1365+
* either way.
1366+
*/
1367+
result=lappend_int(result,indexcol+1);
1368+
break;
1369+
}
1370+
}
1371+
1372+
/* Else clause must be a binary opclause. */
1373+
Assert(IsA(clause,OpExpr));
1374+
1375+
/* Determine left/right sides and check the operator */
1376+
clause_op=clause->opno;
1377+
if (match_index_to_operand(linitial(clause->args),indexcol,
1378+
index))
1379+
{
1380+
/* clause_op is correct */
1381+
varonleft= true;
1382+
}
1383+
else
1384+
{
1385+
Assert(match_index_to_operand(lsecond(clause->args),indexcol,
1386+
index));
1387+
/* Must flip operator to get the opclass member */
1388+
clause_op=get_commutator(clause_op);
1389+
varonleft= false;
1390+
}
1391+
if (!OidIsValid(clause_op))
1392+
continue;/* ignore non match, per next comment */
1393+
op_strategy=get_op_opclass_strategy(clause_op,opclass);
1394+
1395+
/*
1396+
* You might expect to see Assert(op_strategy != 0) here,
1397+
* but you won't: the clause might contain a special indexable
1398+
* operator rather than an ordinary opclass member. Currently
1399+
* none of the special operators are very likely to expand to
1400+
* an equality operator; we do not bother to check, but just
1401+
* assume no match.
1402+
*/
1403+
if (op_strategy!=BTEqualStrategyNumber)
1404+
continue;
1405+
1406+
/* Now check that other side is pseudoconstant */
1407+
if (varonleft)
1408+
ispc=is_pseudo_constant_clause_relids(lsecond(clause->args),
1409+
rinfo->right_relids);
1410+
else
1411+
ispc=is_pseudo_constant_clause_relids(linitial(clause->args),
1412+
rinfo->left_relids);
1413+
if (ispc)
1414+
{
1415+
result=lappend_int(result,indexcol+1);
1416+
break;
1417+
}
1418+
}
1419+
indexcol++;
1420+
}
1421+
returnresult;
1422+
}
1423+
1424+
/*
1425+
* match_index_to_query_keys
1426+
*Check a single scan direction for "intelligent" match to query keys
1427+
*
1428+
* 'index' is the index of interest.
1429+
* 'indexscandir' is the scan direction to consider
1430+
* 'ignorables' is an integer list of indexes of ignorable index columns
1431+
*
1432+
* Returns TRUE on successful match (ie, the query_pathkeys can be considered
1433+
* to match this index).
1434+
*/
1435+
staticbool
1436+
match_index_to_query_keys(PlannerInfo*root,
1437+
IndexOptInfo*index,
1438+
ScanDirectionindexscandir,
1439+
List*ignorables)
1440+
{
1441+
List*index_pathkeys;
1442+
ListCell*index_cell;
1443+
intindex_col;
1444+
ListCell*r;
1445+
1446+
/* Get the pathkeys that exactly describe the index */
1447+
index_pathkeys=build_index_pathkeys(root,index,indexscandir);
1448+
1449+
/*
1450+
* Can we match to the query's requested pathkeys? The inner loop
1451+
* skips over ignorable index columns while trying to match.
1452+
*/
1453+
index_cell=list_head(index_pathkeys);
1454+
index_col=0;
1455+
1456+
foreach(r,root->query_pathkeys)
1457+
{
1458+
List*rsubkey= (List*)lfirst(r);
1459+
1460+
for (;;)
1461+
{
1462+
List*isubkey;
1463+
1464+
if (index_cell==NULL)
1465+
return false;
1466+
isubkey= (List*)lfirst(index_cell);
1467+
index_cell=lnext(index_cell);
1468+
index_col++;/* index_col is now 1-based */
1469+
/*
1470+
* Since we are dealing with canonicalized pathkeys, pointer
1471+
* comparison is sufficient to determine a match.
1472+
*/
1473+
if (rsubkey==isubkey)
1474+
break;/* matched current query pathkey */
1475+
1476+
if (!list_member_int(ignorables,index_col))
1477+
return false;/* definite failure to match */
1478+
/* otherwise loop around and try to match to next index col */
1479+
}
1480+
}
1481+
1482+
return true;
1483+
}
1484+
12231485
/****************************************************************************
12241486
*---- PATH CREATION UTILITIES ----
12251487
****************************************************************************/
@@ -1230,7 +1492,8 @@ find_clauses_for_join(PlannerInfo *root, RelOptInfo *rel,
12301492
* of RestrictInfos.
12311493
*
12321494
* This is used to flatten out the result of group_clauses_by_indexkey()
1233-
* to produce an indexclauses list.
1495+
* to produce an indexclauses list. The original list structure mustn't
1496+
* be altered, but it's OK to share copies of the underlying RestrictInfos.
12341497
*/
12351498
List*
12361499
flatten_clausegroups_list(List*clausegroups)

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp