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

Commitc186c93

Browse files
committed
Change the planner to allow indexscan qualification clauses to use
nonconsecutive columns of a multicolumn index, as per discussion aroundmid-May (pghackers thread "Best way to scan on-disk bitmaps"). Thisturns out to require only minimal changes in btree, and so far as I cansee none at all in GiST. btcostestimate did need some work, but itsoriginal assumption that index selectivity == heap selectivity wasquite bogus even before this.
1 parent0778116 commitc186c93

File tree

12 files changed

+208
-114
lines changed

12 files changed

+208
-114
lines changed

‎doc/src/sgml/catalogs.sgml

Lines changed: 9 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
<!--
22
Documentation of the system catalogs, directed toward PostgreSQL developers
3-
$PostgreSQL: pgsql/doc/src/sgml/catalogs.sgml,v 2.102 2005/05/17 21:46:09 tgl Exp $
3+
$PostgreSQL: pgsql/doc/src/sgml/catalogs.sgml,v 2.103 2005/06/13 23:14:47 tgl Exp $
44
-->
55

66
<chapter id="catalogs">
@@ -358,6 +358,14 @@
358358
<entry>Does the access method support multicolumn indexes?</entry>
359359
</row>
360360

361+
<row>
362+
<entry><structfield>amoptionalkey</structfield></entry>
363+
<entry><type>bool</type></entry>
364+
<entry></entry>
365+
<entry>Does the access method support a scan without any constraint
366+
for the first index column?</entry>
367+
</row>
368+
361369
<row>
362370
<entry><structfield>amindexnulls</structfield></entry>
363371
<entry><type>bool</type></entry>

‎doc/src/sgml/indexam.sgml

Lines changed: 18 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
11
<!--
2-
$PostgreSQL: pgsql/doc/src/sgml/indexam.sgml,v 2.5 2005/06/05 22:32:53 tgl Exp $
2+
$PostgreSQL: pgsql/doc/src/sgml/indexam.sgml,v 2.6 2005/06/13 23:14:47 tgl Exp $
33
-->
44

55
<chapter id="indexam">
@@ -100,21 +100,30 @@ $PostgreSQL: pgsql/doc/src/sgml/indexam.sgml,v 2.5 2005/06/05 22:32:53 tgl Exp $
100100
<structfield>amconcurrent</structfield> in <xref linkend="index-locking">.
101101
The <structfield>amcanmulticol</structfield> flag asserts that the
102102
access method supports multi-column indexes, while
103+
<structfield>amoptionalkey</structfield> asserts that it allows scans
104+
where no indexable restriction clause is given for the first index column.
105+
When <structfield>amcanmulticol</structfield> is false,
106+
<structfield>amoptionalkey</structfield> essentially says whether the
107+
access method allows full-index scans without any restriction clause.
108+
Access methods that support multiple index columns <emphasis>must</>
109+
support scans that omit restrictions on any or all of the columns after
110+
the first; however they are permitted to require some restriction to
111+
appear for the first index column, and this is signaled by setting
112+
<structfield>amoptionalkey</structfield> false.
103113
<structfield>amindexnulls</structfield> asserts that index entries are
104114
created for NULL key values. Since most indexable operators are
105115
strict and hence cannot return TRUE for NULL inputs,
106116
it is at first sight attractive to not store index entries for NULLs:
107117
they could never be returned by an index scan anyway. However, this
108-
argument fails for a full-table index scan (one with no scan keys);
109-
such a scan should include null rows. In practice this means that
110-
indexes that support ordered scans (have <structfield>amorderstrategy</>
111-
nonzero) must index nulls, since the planner might decide to use such a
112-
scan as a substitute for sorting. Such indexes must also be willing to
113-
run a scan with no scan keys at all. Another restriction is that an index
118+
argument fails when an index scan has no restriction clause for a given
119+
index column. In practice this means that
120+
indexes that have <structfield>amoptionalkey</structfield> true must
121+
index nulls, since the planner might decide to use such an index
122+
with no scan keys at all. A related restriction is that an index
114123
access method that supports multiple index columns <emphasis>must</>
115124
support indexing null values in columns after the first, because the planner
116-
will assume the index can be used for querieson just the first
117-
column(s). For example, consider an index on (a,b) and a query with
125+
will assume the index can be used for queriesthat do not restrict
126+
these columns. For example, consider an index on (a,b) and a query with
118127
<literal>WHERE a = 4</literal>. The system will assume the index can be
119128
used to scan for rows with <literal>a = 4</literal>, which is wrong if the
120129
index omits rows where <literal>b</> is null.

‎src/backend/access/index/indexam.c

Lines changed: 1 addition & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $PostgreSQL: pgsql/src/backend/access/index/indexam.c,v 1.82 2005/05/27 23:31:20 tgl Exp $
11+
* $PostgreSQL: pgsql/src/backend/access/index/indexam.c,v 1.83 2005/06/13 23:14:48 tgl Exp $
1212
*
1313
* INTERFACE ROUTINES
1414
*index_open- open an index relation by relation OID
@@ -25,7 +25,6 @@
2525
*index_getmulti- get multiple tuples from a scan
2626
*index_bulk_delete- bulk deletion of index tuples
2727
*index_vacuum_cleanup- post-deletion cleanup of an index
28-
*index_cost_estimator- fetch amcostestimate procedure OID
2928
*index_getprocid - get a support procedure OID
3029
*index_getprocinfo - get a support procedure's lookup info
3130
*
@@ -718,27 +717,6 @@ index_vacuum_cleanup(Relation indexRelation,
718717
returnresult;
719718
}
720719

721-
/* ----------------
722-
*index_cost_estimator
723-
*
724-
*Fetch the amcostestimate procedure OID for an index.
725-
*
726-
*We could combine fetching and calling the procedure,
727-
*as index_insert does for example; but that would require
728-
*importing a bunch of planner/optimizer stuff into this file.
729-
* ----------------
730-
*/
731-
RegProcedure
732-
index_cost_estimator(RelationindexRelation)
733-
{
734-
FmgrInfo*procedure;
735-
736-
RELATION_CHECKS;
737-
GET_REL_PROCEDURE(amcostestimate);
738-
739-
returnprocedure->fn_oid;
740-
}
741-
742720
/* ----------------
743721
*index_getprocid
744722
*

‎src/backend/access/nbtree/nbtsearch.c

Lines changed: 7 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
* Portions Copyright (c) 1994, Regents of the University of California
99
*
1010
* IDENTIFICATION
11-
* $PostgreSQL: pgsql/src/backend/access/nbtree/nbtsearch.c,v 1.91 2005/03/29 00:16:52 tgl Exp $
11+
* $PostgreSQL: pgsql/src/backend/access/nbtree/nbtsearch.c,v 1.92 2005/06/13 23:14:48 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -594,15 +594,17 @@ _bt_first(IndexScanDesc scan, ScanDirection dir)
594594
}
595595

596596
/*
597-
* Done if that was the last attribute.
597+
* Done if that was the last attribute, or if next key
598+
* is not in sequence (implying no boundary key is available
599+
* for the next attribute).
598600
*/
599-
if (i >=so->numberOfKeys)
601+
if (i >=so->numberOfKeys||
602+
cur->sk_attno!=curattr+1)
600603
break;
601604

602605
/*
603-
* Reset for next attr, which should be in sequence.
606+
* Reset for next attr.
604607
*/
605-
Assert(cur->sk_attno==curattr+1);
606608
curattr=cur->sk_attno;
607609
chosen=NULL;
608610
}

‎src/backend/access/nbtree/nbtutils.c

Lines changed: 10 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $PostgreSQL: pgsql/src/backend/access/nbtree/nbtutils.c,v 1.62 2004/12/31 21:59:22 pgsql Exp $
11+
* $PostgreSQL: pgsql/src/backend/access/nbtree/nbtutils.c,v 1.63 2005/06/13 23:14:48 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -190,7 +190,9 @@ _bt_formitem(IndexTuple itup)
190190
* matched to continue the scan. In general, numberOfRequiredKeys is equal
191191
* to the number of keys for leading attributes with "=" keys, plus the
192192
* key(s) for the first non "=" attribute, which can be seen to be correct
193-
* by considering the above example.
193+
* by considering the above example. Note in particular that if there are no
194+
* keys for a given attribute, the keys for subsequent attributes can never
195+
* be required; for instance "WHERE y = 4" requires a full-index scan.
194196
*
195197
* If possible, redundant keys are eliminated: we keep only the tightest
196198
* >/>= bound and the tightest </<= bound, and if there's an = key then
@@ -248,8 +250,8 @@ _bt_preprocess_keys(IndexScanDesc scan)
248250
outkeys=so->keyData;
249251
cur=&inkeys[0];
250252
/* we check that input keys are correctly ordered */
251-
if (cur->sk_attno!=1)
252-
elog(ERROR,"key(s) for attribute 1 missed");
253+
if (cur->sk_attno<1)
254+
elog(ERROR,"btree index keys must be ordered by attribute");
253255

254256
/* We can short-circuit most of the work if there's just one key */
255257
if (numberOfKeys==1)
@@ -270,7 +272,8 @@ _bt_preprocess_keys(IndexScanDesc scan)
270272
}
271273
memcpy(outkeys,inkeys,sizeof(ScanKeyData));
272274
so->numberOfKeys=1;
273-
so->numberOfRequiredKeys=1;
275+
if (cur->sk_attno==1)
276+
so->numberOfRequiredKeys=1;
274277
return;
275278
}
276279

@@ -324,8 +327,8 @@ _bt_preprocess_keys(IndexScanDesc scan)
324327
intpriorNumberOfEqualCols=numberOfEqualCols;
325328

326329
/* check input keys are correctly ordered */
327-
if (i<numberOfKeys&&cur->sk_attno!=attno+1)
328-
elog(ERROR,"key(s) for attribute %d missed",attno+1);
330+
if (i<numberOfKeys&&cur->sk_attno<attno)
331+
elog(ERROR,"btree index keys must be ordered by attribute");
329332

330333
/*
331334
* If = has been specified, no other key will be used. In case

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

Lines changed: 26 additions & 27 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.183 2005/06/10 22:25:36 tgl Exp $
12+
* $PostgreSQL: pgsql/src/backend/optimizer/path/indxpath.c,v 1.184 2005/06/13 23:14:48 tgl Exp $
1313
*
1414
*-------------------------------------------------------------------------
1515
*/
@@ -87,7 +87,8 @@ static Const *string_to_const(const char *str, Oid datatype);
8787
*
8888
* To be considered for an index scan, an index must match one or more
8989
* restriction clauses or join clauses from the query's qual condition,
90-
* or match the query's ORDER BY condition.
90+
* or match the query's ORDER BY condition, or have a predicate that
91+
* matches the query's qual condition.
9192
*
9293
* There are two basic kinds of index scans. A "plain" index scan uses
9394
* only restriction clauses (possibly none at all) in its indexqual,
@@ -210,6 +211,7 @@ create_index_paths(PlannerInfo *root, RelOptInfo *rel)
210211
* 'clauses' is the current list of clauses (RestrictInfo nodes)
211212
* 'outer_clauses' is the list of additional upper-level clauses
212213
* 'istoplevel' is true if clauses are the rel's top-level restriction list
214+
*(outer_clauses must be NIL when this is true)
213215
* 'isjoininner' is true if forming an inner indexscan (so some of the
214216
*given clauses are join clauses)
215217
* 'outer_relids' identifies the outer side of the join (pass NULL
@@ -295,13 +297,12 @@ find_usable_indexes(PlannerInfo *root, RelOptInfo *rel,
295297
* selectivity of the predicate might alone make the index useful.
296298
*
297299
* Note: not all index AMs support scans with no restriction clauses.
298-
* We assume here that the AM does so if and only if it supports
299-
* ordered scans. (It would probably be better if there were a
300-
* specific flag for this in pg_am, but there's not.)
300+
* We can't generate a scan over an index with amoptionalkey = false
301+
* unless there's at least one restriction clause.
301302
*/
302303
if (restrictclauses!=NIL||
303-
useful_pathkeys!=NIL||
304-
(index->indpred!=NIL&&index_is_ordered))
304+
(index->amoptionalkey&&
305+
(useful_pathkeys!=NIL||index->indpred!=NIL)))
305306
{
306307
ipath=create_index_path(root,index,
307308
restrictclauses,
@@ -608,6 +609,11 @@ bitmap_and_cost_est(PlannerInfo *root, RelOptInfo *rel, List *paths)
608609
* group_clauses_by_indexkey
609610
* Find restriction clauses that can be used with an index.
610611
*
612+
* Returns a list of sublists of RestrictInfo nodes for clauses that can be
613+
* used with this index. Each sublist contains clauses that can be used
614+
* with one index key (in no particular order); the top list is ordered by
615+
* index key. (This is depended on by expand_indexqual_conditions().)
616+
*
611617
* As explained in the comments for find_usable_indexes(), we can use
612618
* clauses from either of the given lists, but the result is required to
613619
* use at least one clause from the "current clauses" list. We return
@@ -616,18 +622,14 @@ bitmap_and_cost_est(PlannerInfo *root, RelOptInfo *rel, List *paths)
616622
* outer_relids determines what Vars will be allowed on the other side
617623
* of a possible index qual; see match_clause_to_indexcol().
618624
*
619-
*Returns a list of sublists of RestrictInfo nodes for clauses that can be
620-
*used with this index. Each sublist contains clauses that can be used
621-
*with one index key (innoparticular order); the top list is ordered by
622-
*index key. (This is depended on by expand_indexqual_conditions().)
625+
*If the index has amoptionalkey = false, we give up and return NIL when
626+
*there are no restriction clauses matching the first index key. Otherwise,
627+
*we return NIL if there arenorestriction clauses matching any index key.
628+
*A non-NIL result will have one (possibly empty) sublist for each index key.
623629
*
624-
* Note that in a multi-key index, we stop if we find a key that cannot be
625-
* used with any clause. For example, given an index on (A,B,C), we might
626-
* return ((C1 C2) (C3 C4)) if we find that clauses C1 and C2 use column A,
627-
* clauses C3 and C4 use column B, and no clauses use column C. But if
628-
* no clauses match B we will return ((C1 C2)), whether or not there are
629-
* clauses matching column C, because the executor couldn't use them anyway.
630-
* Therefore, there are no empty sublists in the result.
630+
* Example: given an index on (A,B,C), we would return ((C1 C2) () (C3 C4))
631+
* if we find that clauses C1 and C2 use column A, clauses C3 and C4 use
632+
* column C, and no clauses use column B.
631633
*/
632634
List*
633635
group_clauses_by_indexkey(IndexOptInfo*index,
@@ -680,11 +682,10 @@ group_clauses_by_indexkey(IndexOptInfo *index,
680682
}
681683

682684
/*
683-
* If no clauses match this key, we're done; we don't want to look
684-
* at keys to its right.
685+
* If no clauses match this key, check for amoptionalkey restriction.
685686
*/
686-
if (clausegroup==NIL)
687-
break;
687+
if (clausegroup==NIL&& !index->amoptionalkey&&indexcol==0)
688+
returnNIL;
688689

689690
clausegroup_list=lappend(clausegroup_list,clausegroup);
690691

@@ -1581,11 +1582,9 @@ match_special_index_operator(Expr *clause, Oid opclass,
15811582
* will know what to do with.
15821583
*
15831584
* The input list is ordered by index key, and so the output list is too.
1584-
* (The latter is not depended on by any part of the planner, so far as I can
1585-
* tell; but some parts of the executor do assume that the indexqual list
1586-
* ultimately delivered to the executor is so ordered.One such place is
1587-
* _bt_preprocess_keys() in the btree support.Perhaps that ought to be fixed
1588-
* someday --- tgl 7/00)
1585+
* (The latter is not depended on by any part of the core planner, I believe,
1586+
* but parts of the executor require it, and so do the amcostestimate
1587+
* functions.)
15891588
*/
15901589
List*
15911590
expand_indexqual_conditions(IndexOptInfo*index,List*clausegroups)

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

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,7 @@
99
*
1010
*
1111
* IDENTIFICATION
12-
* $PostgreSQL: pgsql/src/backend/optimizer/util/plancat.c,v 1.111 2005/06/05 22:32:56 tgl Exp $
12+
* $PostgreSQL: pgsql/src/backend/optimizer/util/plancat.c,v 1.112 2005/06/13 23:14:48 tgl Exp $
1313
*
1414
*-------------------------------------------------------------------------
1515
*/
@@ -161,7 +161,8 @@ get_relation_info(Oid relationObjectId, RelOptInfo *rel)
161161
}
162162

163163
info->relam=indexRelation->rd_rel->relam;
164-
info->amcostestimate=index_cost_estimator(indexRelation);
164+
info->amcostestimate=indexRelation->rd_am->amcostestimate;
165+
info->amoptionalkey=indexRelation->rd_am->amoptionalkey;
165166

166167
/*
167168
* Fetch the ordering operators associated with the index, if

0 commit comments

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