Proof of concept initial patch for enabling index only scans for
partial indices even when an attribute is not in the target list, as
long as it is only used in restriction clauses that can be proved by
the index predicate. This also works for index quals, though they
still can't be used in the target list. However, this patch may be
inefficient since it duplicates effort that is currently delayed until
after the best plan is chosen.
The patch works by basically repeating the logic from
create_indexscan_plan in createplan.c that determines which clauses
can't be discarded, instead of the current approach, which just
assumes that any attributes referenced anywhere in a restriction
clause has to be a column in the relevant index. It should build
against master and passes make check for me. It also includes a minor
fix in the same code in createplan.c to make sure we're explicitly
comparing an empty list to NIL, but I can take that out if that's not
considered in scope. If this were the final patch I'd probably
coalesce the code used in both places into a single function, but
since I'm not certain that the implementation in check_index_only
won't change substantially I held off on that.
Since the original comment suggested that this was not done due to
planner performance concerns, I assume the performance of this
approach is unacceptable (though I did a few benchmarks and wasn't
able to detect a consistent difference--what would be a good test for
this?). As such, this is intended as more of a first pass that I can
build on, but I wanted to get feedback at this stage on where we can
improve (particularly if there were already ideas on how this might be
done, as the comment hints). Index only scans cost less than regular
index scans so I don't think we can get away with waiting until we've
chosen the best plan before we do the work described above. That
said, as I see it performance could improve in any combination of five
ways:
* Improve the performance of determining which clauses can't be
discarded (e.g. precompute some information about equivalence classes
for index predicates, mess around with the order in which we check the
clauses to make it fail faster, switch to real union-find data
structures for equivalence classes).
* Find a cleverer way of figuring out whether a partial index can be
used than just checking which clauses can't be discarded.
* Use a simpler heuristic (that doesn't match what use to determine
which clauses can be discarded, but still matches more than we do
now).
* Take advantage of work we do here to speed things up elsewhere (e.g.
if this does get chosen as the best plan we don't need to recompute
the same information in create_indexscan_plan).
* Delay determining whether to use an index scan or index only scan
until after cost analysis somehow. I'm not sure exactly what this
would entail.
Since this is my first real work with the codebase, I'd really
appreciate it if people could help me figure out the best approach
here (and, more importantly, if one is necessary based on benchmarks).
And while this should go without saying, if this patch doesn't
actually work then please let me know, since all the above is based on
the assumption that what's there is enough :)
Thanks,
Joshua Yanovski
diff --git a/src/backend/optimizer/path/indxpath.c
b/src/backend/optimizer/path/indxpath.c
new file mode 100644
index a912174..ed87261
*** a/src/backend/optimizer/path/indxpath.c
--- b/src/backend/optimizer/path/indxpath.c
***************
*** 32,37 ****
--- 32,38 ----
#include "optimizer/predtest.h"
#include "optimizer/restrictinfo.h"
#include "optimizer/var.h"
+ #include "parser/parsetree.h"
#include "utils/builtins.h"
#include "utils/bytea.h"
#include "utils/lsyscache.h"
*************** static PathClauseUsage *classify_index_c
*** 135,141 ****
static Relids get_bitmap_tree_required_outer(Path *bitmapqual);
static void find_indexpath_quals(Path *bitmapqual, List **quals, List
**preds);
static int find_list_position(Node *node, List **nodelist);
! static bool check_index_only(RelOptInfo *rel, IndexOptInfo *index);
static double get_loop_count(PlannerInfo *root, Relids outer_relids);
static void match_restriction_clauses_to_index(RelOptInfo *rel,
IndexOptInfo
*index,
--- 136,143 ----
static Relids get_bitmap_tree_required_outer(Path *bitmapqual);
static void find_indexpath_quals(Path *bitmapqual, List **quals, List
**preds);
static int find_list_position(Node *node, List **nodelist);
! static bool check_index_only(PlannerInfo *root, RelOptInfo *rel,
! IndexOptInfo *index, List *index_clauses);
static double get_loop_count(PlannerInfo *root, Relids outer_relids);
static void match_restriction_clauses_to_index(RelOptInfo *rel,
IndexOptInfo
*index,
*************** build_index_paths(PlannerInfo *root, Rel
*** 980,986 ****
* index data retrieval anyway.
*/
index_only_scan = (scantype != ST_BITMAPSCAN &&
! check_index_only(rel, index));
/*
* 4. Generate an indexscan path if there are relevant restriction
clauses
--- 982,988 ----
* index data retrieval anyway.
*/
index_only_scan = (scantype != ST_BITMAPSCAN &&
! check_index_only(root, rel, index,
index_clauses));
/*
* 4. Generate an indexscan path if there are relevant restriction
clauses
*************** find_list_position(Node *node, List **no
*** 1741,1747 ****
* Determine whether an index-only scan is possible for this index.
*/
static bool
! check_index_only(RelOptInfo *rel, IndexOptInfo *index)
{
bool result;
Bitmapset *attrs_used = NULL;
--- 1743,1750 ----
* Determine whether an index-only scan is possible for this index.
*/
static bool
! check_index_only(PlannerInfo *root, RelOptInfo *rel, IndexOptInfo *index,
! List *index_clauses)
{
bool result;
Bitmapset *attrs_used = NULL;
*************** check_index_only(RelOptInfo *rel, IndexO
*** 1758,1771 ****
/*
* 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.
*/
/*
--- 1761,1766 ----
*************** check_index_only(RelOptInfo *rel, IndexO
*** 1775,1785 ****
*/
pull_varattnos((Node *) rel->reltargetlist, rel->relid, &attrs_used);
! /* Add all the attributes used by restriction clauses. */
foreach(lc, rel->baserestrictinfo)
{
RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
pull_varattnos((Node *) rinfo->clause, rel->relid, &attrs_used);
}
--- 1770,1805 ----
*/
pull_varattnos((Node *) rel->reltargetlist, rel->relid, &attrs_used);
! /*
! * Add all the attributes required by restriction clauses. This is
! * essentially the same thing we do in create_indexscan_plan.
! */
foreach(lc, rel->baserestrictinfo)
{
RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
+ Assert(IsA(rinfo, RestrictInfo));
+ if (rinfo->pseudoconstant)
+ continue; /* we may drop
pseudoconstants here */
+ if (list_member_ptr(index_clauses, rinfo))
+ continue; /* simple duplicate */
+ if (is_redundant_derived_clause(rinfo, index_clauses))
+ continue; /* derived from same
EquivalenceClass */
+ if (!contain_mutable_functions((Node *) rinfo->clause))
+ {
+ List *clausel = list_make1(rinfo->clause);
+
+ if (predicate_implied_by(clausel, index_clauses))
+ continue; /* provably implied by
index_clauses */
+ if (index->indpred != NIL)
+ {
+ if (rel->relid != root->parse->resultRelation &&
+ get_parse_rowmark(root->parse,
rel->relid) == NULL)
+ if (predicate_implied_by(clausel,
index->indpred))
+ continue; /*
implied by index predicate */
+ }
+ }
+
pull_varattnos((Node *) rinfo->clause, rel->relid, &attrs_used);
}
diff --git a/src/backend/optimizer/plan/createplan.c
b/src/backend/optimizer/plan/createplan.c
new file mode 100644
index 184d37a..d1b656f
*** a/src/backend/optimizer/plan/createplan.c
--- b/src/backend/optimizer/plan/createplan.c
*************** create_indexscan_plan(PlannerInfo *root,
*** 1215,1221 ****
if (predicate_implied_by(clausel, indexquals))
continue; /* provably implied by
indexquals */
! if (best_path->indexinfo->indpred)
{
if (baserelid != root->parse->resultRelation &&
get_parse_rowmark(root->parse,
baserelid) == NULL)
--- 1215,1221 ----
if (predicate_implied_by(clausel, indexquals))
continue; /* provably implied by
indexquals */
! if (best_path->indexinfo->indpred != NIL)
{
if (baserelid != root->parse->resultRelation &&
get_parse_rowmark(root->parse,
baserelid) == NULL)
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
