Hello, This is a (maybe) committer-ready patch of a Tomas
Vondra's project.
This patch applies on the current master and passes make check.
This is to exclude some base-estrict clauses that are implied by
index predicates on index scans on partial indexes.
First, this patch adds a new member indexrinfos to IndexOptInfo,
which usually has the same value with baserestrictinfo of the
parent RelOptInfo and cost_index() uses this instead of
RelOptInfo.baserestrictinfo.
For partial indexes, the clauses implied by the index predicates
are removed from the indexrinfos, so that the result plan for
scans on such indexes won't contain such restrictions. Such
restrictions commonly become filter quals that are nothing but a
useless work to do, so this will improve the performance of some
index scans on partial indexes.
The largest part of the extra cost of the additional work would
be the cost of predicate_implied_by() on all clauses of
baserectrictinfo and indpred of every IndexOptInfos. The extra
work is done in check_partial_indexes() for all index scans on
partial indexes.
regards,
--
Kyotaro Horiguchi
NTT Open Source Software Center
>From 97040f596e34d40f1e514c8385e0877f00d858ca Mon Sep 17 00:00:00 2001
From: Kyotaro Horiguchi <horiguchi.kyot...@lab.ntt.co.jp>
Date: Thu, 25 Feb 2016 18:49:36 +0900
Subject: [PATCH] Remove restrictinfo clauses that are implied by index
predicates.
Some clauses in baserestrictinfo are useless when they are implied by
index predicates of a paritial index currently focused. Removing such
clauses improves the performance of index scans.
---
src/backend/optimizer/path/costsize.c | 5 +-
src/backend/optimizer/path/indxpath.c | 90 ++++++++++++++++++++++++++------
src/backend/optimizer/util/pathnode.c | 1 +
src/include/nodes/relation.h | 7 +++
src/test/regress/expected/aggregates.out | 8 +--
5 files changed, 87 insertions(+), 24 deletions(-)
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index 5fc2f9c..36678e0 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -89,6 +89,7 @@
#include "optimizer/placeholder.h"
#include "optimizer/plancat.h"
#include "optimizer/planmain.h"
+#include "optimizer/predtest.h"
#include "optimizer/restrictinfo.h"
#include "parser/parsetree.h"
#include "utils/lsyscache.h"
@@ -433,7 +434,7 @@ cost_index(IndexPath *path, PlannerInfo *root, double loop_count)
path->path.rows = path->path.param_info->ppi_rows;
/* qpquals come from the rel's restriction clauses and ppi_clauses */
qpquals = list_concat(
- extract_nonindex_conditions(baserel->baserestrictinfo,
+ extract_nonindex_conditions(path->indexrinfos,
path->indexquals),
extract_nonindex_conditions(path->path.param_info->ppi_clauses,
path->indexquals));
@@ -442,7 +443,7 @@ cost_index(IndexPath *path, PlannerInfo *root, double loop_count)
{
path->path.rows = baserel->rows;
/* qpquals come from just the rel's restriction clauses */
- qpquals = extract_nonindex_conditions(baserel->baserestrictinfo,
+ qpquals = extract_nonindex_conditions(path->indexrinfos,
path->indexquals);
}
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index ddb4ca5..577e7a6 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -136,8 +136,7 @@ static double adjust_rowcount_for_semijoins(PlannerInfo *root,
Index outer_relid,
double rowcount);
static double approximate_joinrel_size(PlannerInfo *root, Relids relids);
-static void match_restriction_clauses_to_index(RelOptInfo *rel,
- IndexOptInfo *index,
+static void match_restriction_clauses_to_index(IndexOptInfo *index,
IndexClauseSet *clauseset);
static void match_join_clauses_to_index(PlannerInfo *root,
RelOptInfo *rel, IndexOptInfo *index,
@@ -266,7 +265,7 @@ create_index_paths(PlannerInfo *root, RelOptInfo *rel)
* Identify the restriction clauses that can match the index.
*/
MemSet(&rclauseset, 0, sizeof(rclauseset));
- match_restriction_clauses_to_index(rel, index, &rclauseset);
+ match_restriction_clauses_to_index(index, &rclauseset);
/*
* Build index paths from the restriction clauses. These will be
@@ -1801,13 +1800,13 @@ check_index_only(RelOptInfo *rel, IndexOptInfo *index)
* Check that all needed attributes of the relation are available from the
* index.
*
- * XXX this is overly conservative for partial indexes, since we will
- * consider attributes involved in the index predicate as required even
- * though the predicate won't need to be checked at runtime. (The same is
- * true for attributes used only in index quals, if we are certain that
- * the index is not lossy.) However, it would be quite expensive to
- * determine that accurately at this point, so for now we take the easy
- * way out.
+ * For partial indexes we won't consider attributes involved in clauses
+ * implied by the index predicate, as those won't be needed at runtime.
+ *
+ * XXX The same is true for attributes used only in index quals, if we
+ * are certain that the index is not lossy. However, it would be quite
+ * expensive to determine that accurately at this point, so for now we
+ * take the easy way out.
*/
/*
@@ -1817,8 +1816,8 @@ check_index_only(RelOptInfo *rel, IndexOptInfo *index)
*/
pull_varattnos((Node *) rel->reltarget.exprs, rel->relid, &attrs_used);
- /* Add all the attributes used by restriction clauses. */
- foreach(lc, rel->baserestrictinfo)
+ /* Add all the attributes used by index restriction clauses. */
+ foreach(lc, index->indrinfos)
{
RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
@@ -2020,10 +2019,10 @@ approximate_joinrel_size(PlannerInfo *root, Relids relids)
* Matching clauses are added to *clauseset.
*/
static void
-match_restriction_clauses_to_index(RelOptInfo *rel, IndexOptInfo *index,
+match_restriction_clauses_to_index(IndexOptInfo *index,
IndexClauseSet *clauseset)
{
- match_clauses_to_index(index, rel->baserestrictinfo, clauseset);
+ match_clauses_to_index(index, index->indrinfos, clauseset);
}
/*
@@ -2689,6 +2688,13 @@ check_partial_indexes(PlannerInfo *root, RelOptInfo *rel)
{
IndexOptInfo *index = (IndexOptInfo *) lfirst(lc);
+ /*
+ * Remember the restrictions for the index - we'll later modify
+ * them for partial indexes (exclude the restrictions that are
+ * implied by the index predicate).
+ */
+ index->indrinfos = rel->baserestrictinfo;
+
if (index->indpred == NIL)
continue; /* ignore non-partial indexes */
@@ -2696,7 +2702,6 @@ check_partial_indexes(PlannerInfo *root, RelOptInfo *rel)
continue; /* don't repeat work if already proven OK */
have_partial = true;
- break;
}
if (!have_partial)
return;
@@ -2743,10 +2748,14 @@ check_partial_indexes(PlannerInfo *root, RelOptInfo *rel)
otherrels,
rel));
- /* Now try to prove each index predicate true */
+ /*
+ * Now try to prove each index predicate true. We'll also tweak the
+ * index restrictions to exclude clauses implied by the predicate.
+ */
foreach(lc, rel->indexlist)
{
IndexOptInfo *index = (IndexOptInfo *) lfirst(lc);
+ ListCell *lcr;
if (index->indpred == NIL)
continue; /* ignore non-partial indexes */
@@ -2755,6 +2764,55 @@ check_partial_indexes(PlannerInfo *root, RelOptInfo *rel)
continue; /* don't repeat work if already proven OK */
index->predOK = predicate_implied_by(index->indpred, clauselist);
+
+ /*
+ * Update restrictinfo for this index by excluding clauses that are
+ * implied by the index predicates. We first quickly check if there
+ * are any implied clauses, and if we found at least one we do the
+ * actual work. This way we don't need to construct a copy of the list
+ * unless actually needed.
+ */
+
+ foreach (lcr, rel->baserestrictinfo)
+ {
+ RestrictInfo *rinfo = (RestrictInfo *) lfirst(lcr);
+
+ if (predicate_implied_by(list_make1(rinfo->clause),
+ index->indpred))
+ break;
+ }
+
+ /*
+ * If we found a clause implied by the index predicate, we walk
+ * the list of clauses again, but we skip the clauses before the
+ * one we found (to save re-evaluations of predicate_implied_by)
+ * and construct the list of non-implied clauses on the way.
+ */
+ if (lcr)
+ {
+ ListCell *lcr2;
+ bool needs_check = false;
+
+ index->indrinfos = NIL;
+
+ foreach (lcr2, rel->baserestrictinfo)
+ {
+ RestrictInfo *rinfo2 = (RestrictInfo *) lfirst(lcr2);
+
+ /* skip initial clauses already proven not to be implied */
+ if (lcr2 == lcr)
+ {
+ needs_check = true;
+ continue;
+ }
+
+ /* add to index clauses if initial or not implied */
+ if (!needs_check ||
+ !predicate_implied_by(list_make1(rinfo2->clause),
+ index->indpred))
+ index->indrinfos = lappend(index->indrinfos, rinfo2);
+ }
+ }
}
}
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index 9417587..b67e1e0 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -1027,6 +1027,7 @@ create_index_path(PlannerInfo *root,
pathnode->indexclauses = indexclauses;
pathnode->indexquals = indexquals;
pathnode->indexqualcols = indexqualcols;
+ pathnode->indexrinfos = index->indrinfos;
pathnode->indexorderbys = indexorderbys;
pathnode->indexorderbycols = indexorderbycols;
pathnode->indexscandir = indexscandir;
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index af8cb6b..405a97f 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -581,6 +581,8 @@ typedef struct IndexOptInfo
List *indexprs; /* expressions for non-simple index columns */
List *indpred; /* predicate if a partial index, else NIL */
+ List *indrinfos; /* baseristrict info which are not implied by
+ * indpred */
List *indextlist; /* targetlist representing index columns */
@@ -835,6 +837,10 @@ typedef struct Path
* index column, so 'indexqualcols' must form a nondecreasing sequence.
* (The order of multiple quals for the same index column is unspecified.)
*
+ * 'indexrinfos' is a list of RestrictInfo nodes from the query's WHERE
+ * or JOIN conditions, excluding those implied by the index predicate
+ * (if the index is not partial, the list includes all restriction clauses).
+ *
* 'indexorderbys', if not NIL, is a list of ORDER BY expressions that have
* been found to be usable as ordering operators for an amcanorderbyop index.
* The list must match the path's pathkeys, ie, one expression per pathkey
@@ -869,6 +875,7 @@ typedef struct IndexPath
List *indexclauses;
List *indexquals;
List *indexqualcols;
+ List *indexrinfos;
List *indexorderbys;
List *indexorderbycols;
ScanDirection indexscandir;
diff --git a/src/test/regress/expected/aggregates.out b/src/test/regress/expected/aggregates.out
index e434c5d..cec90bb 100644
--- a/src/test/regress/expected/aggregates.out
+++ b/src/test/regress/expected/aggregates.out
@@ -780,7 +780,6 @@ explain (costs off)
-> Index Only Scan Backward using minmaxtest2i on minmaxtest2
Index Cond: (f1 IS NOT NULL)
-> Index Only Scan using minmaxtest3i on minmaxtest3
- Index Cond: (f1 IS NOT NULL)
InitPlan 2 (returns $1)
-> Limit
-> Merge Append
@@ -792,8 +791,7 @@ explain (costs off)
-> Index Only Scan using minmaxtest2i on minmaxtest2 minmaxtest2_1
Index Cond: (f1 IS NOT NULL)
-> Index Only Scan Backward using minmaxtest3i on minmaxtest3 minmaxtest3_1
- Index Cond: (f1 IS NOT NULL)
-(25 rows)
+(23 rows)
select min(f1), max(f1) from minmaxtest;
min | max
@@ -819,7 +817,6 @@ explain (costs off)
-> Index Only Scan Backward using minmaxtest2i on minmaxtest2
Index Cond: (f1 IS NOT NULL)
-> Index Only Scan using minmaxtest3i on minmaxtest3
- Index Cond: (f1 IS NOT NULL)
InitPlan 2 (returns $1)
-> Limit
-> Merge Append
@@ -831,9 +828,8 @@ explain (costs off)
-> Index Only Scan using minmaxtest2i on minmaxtest2 minmaxtest2_1
Index Cond: (f1 IS NOT NULL)
-> Index Only Scan Backward using minmaxtest3i on minmaxtest3 minmaxtest3_1
- Index Cond: (f1 IS NOT NULL)
-> Result
-(27 rows)
+(25 rows)
select distinct min(f1), max(f1) from minmaxtest;
min | max
--
1.8.3.1
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
