Spent some time analyzing a severe performance regression on 9.1->9.3
upgrade for a user on IRC. Narrowed it down to this:
commit 807a40c5 fixed a bug in handling of (new in 9.2) functionality
of ScalarArrayOpExpr in btree index quals, forcing the results of
scans including such a qual to be treated as unordered (because the
order can in fact be wrong).
However, this kills any chance of using the same index _without_ the
SAOP to get the benefit of its ordering.
For example:
regression=# create index on tenk1 (ten,unique1,thousand);
CREATE INDEX
regression=# set enable_sort = false;
SET
regression=# explain analyze select * from tenk1 where thousand in
(19,29,39,49,57,66,77,8,90,12,22,32) and (ten >= 5) and (ten > 5 or unique1 >
5000) order by ten,unique1 limit 1;
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=10000000294.71..10000000294.71 rows=1 width=244) (actual
time=0.889..0.891 rows=1 loops=1)
-> Sort (cost=10000000294.71..10000000294.81 rows=42 width=244) (actual
time=0.884..0.884 rows=1 loops=1)
Sort Key: ten, unique1
Sort Method: top-N heapsort Memory: 25kB
-> Bitmap Heap Scan on tenk1 (cost=44.34..294.50 rows=42 width=244)
(actual time=0.194..0.687 rows=80 loops=1)
Recheck Cond: (thousand = ANY
('{19,29,39,49,57,66,77,8,90,12,22,32}'::integer[]))
Filter: ((ten >= 5) AND ((ten > 5) OR (unique1 > 5000)))
Rows Removed by Filter: 40
Heap Blocks: exact=100
-> Bitmap Index Scan on tenk1_thous_tenthous (cost=0.00..44.33
rows=120 width=0) (actual time=0.148..0.148 rows=120 loops=1)
Index Cond: (thousand = ANY
('{19,29,39,49,57,66,77,8,90,12,22,32}'::integer[]))
Planning time: 0.491 ms
Execution time: 1.023 ms
(13 rows)
(real case had larger rowcounts of course, but showed the same effect
of using a Sort plan even when enable_sort=false.)
Obviously one can create a (ten,unique1) index (which would otherwise
be almost completely redundant with the 3-column one), but that wastes
space and eliminates some index-only-scan opportunities. Similarly one
can hack the query, e.g. using WHERE (thousand+0) IN (...) but that is
as ugly as all sin.
I've experimented with the attached patch, which detects when this
situation might have occurred and does another pass to try and build
ordered scans without the SAOP condition. However, the results may not
be quite ideal, because at least in some test queries (not all) the
scan with the SAOP included in the indexquals is being costed higher
than the same scan with the SAOP moved to a Filter, which seems
unreasonable. (One of the affected queries is the regression test for
the original bug, which this patch does not yet try and fix and
therefore currently fails regression on.)
Thoughts?
--
Andrew (irc:RhodiumToad)
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 42dcb11..6ae8e33 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -50,7 +50,8 @@ typedef enum
{
SAOP_PER_AM, /* Use ScalarArrayOpExpr if amsearcharray */
SAOP_ALLOW, /* Use ScalarArrayOpExpr for all indexes */
- SAOP_REQUIRE /* Require ScalarArrayOpExpr to be used */
+ SAOP_REQUIRE, /* Require ScalarArrayOpExpr to be used */
+ SAOP_SKIP_LOWER /* Require lower ScalarArrayOpExpr to be eliminated */
} SaOpControl;
/* Whether we are looking for plain indexscan, bitmap scan, or either */
@@ -118,7 +119,8 @@ static void get_index_paths(PlannerInfo *root, RelOptInfo *rel,
static List *build_index_paths(PlannerInfo *root, RelOptInfo *rel,
IndexOptInfo *index, IndexClauseSet *clauses,
bool useful_predicate,
- SaOpControl saop_control, ScanTypeControl scantype);
+ SaOpControl saop_control, ScanTypeControl scantype,
+ bool *saop_retry);
static List *build_paths_for_OR(PlannerInfo *root, RelOptInfo *rel,
List *clauses, List *other_clauses);
static List *generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel,
@@ -734,6 +736,7 @@ get_index_paths(PlannerInfo *root, RelOptInfo *rel,
{
List *indexpaths;
ListCell *lc;
+ bool saop_retry = false;
/*
* Build simple index paths using the clauses. Allow ScalarArrayOpExpr
@@ -742,7 +745,23 @@ get_index_paths(PlannerInfo *root, RelOptInfo *rel,
indexpaths = build_index_paths(root, rel,
index, clauses,
index->predOK,
- SAOP_PER_AM, ST_ANYSCAN);
+ SAOP_PER_AM, ST_ANYSCAN, &saop_retry);
+
+ /*
+ * If we allowed any ScalarArrayOpExprs on an index with a useful sort
+ * ordering, then try again without them, since otherwise we miss important
+ * paths where the index ordering is relevant.
+ */
+ if (saop_retry)
+ {
+ indexpaths = list_concat(indexpaths,
+ build_index_paths(root, rel,
+ index, clauses,
+ index->predOK,
+ SAOP_SKIP_LOWER,
+ ST_ANYSCAN,
+ NULL));
+ }
/*
* Submit all the ones that can form plain IndexScan plans to add_path. (A
@@ -779,7 +798,7 @@ get_index_paths(PlannerInfo *root, RelOptInfo *rel,
indexpaths = build_index_paths(root, rel,
index, clauses,
false,
- SAOP_REQUIRE, ST_BITMAPSCAN);
+ SAOP_REQUIRE, ST_BITMAPSCAN, NULL);
*bitindexpaths = list_concat(*bitindexpaths, indexpaths);
}
}
@@ -816,12 +835,14 @@ get_index_paths(PlannerInfo *root, RelOptInfo *rel,
* 'useful_predicate' indicates whether the index has a useful predicate
* 'saop_control' indicates whether ScalarArrayOpExpr clauses can be used
* 'scantype' indicates whether we need plain or bitmap scan support
+ * 'saop_retry' indicates whether a SAOP_SKIP_LOWER retry is worthwhile
*/
static List *
build_index_paths(PlannerInfo *root, RelOptInfo *rel,
IndexOptInfo *index, IndexClauseSet *clauses,
bool useful_predicate,
- SaOpControl saop_control, ScanTypeControl scantype)
+ SaOpControl saop_control, ScanTypeControl scantype,
+ bool *saop_retry)
{
List *result = NIL;
IndexPath *ipath;
@@ -877,7 +898,9 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
* assuming that the scan result is ordered. (Actually, the result is
* still ordered if there are equality constraints for all earlier
* columns, but it seems too expensive and non-modular for this code to be
- * aware of that refinement.)
+ * aware of that refinement.) But if saop_control is SAOP_SKIP_LOWER, we
+ * skip exactly these clauses that break sorting, and don't bother
+ * building any paths otherwise.
*
* We also build a Relids set showing which outer rels are required by the
* selected clauses. Any lateral_relids are included in that, but not
@@ -901,9 +924,13 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
/* Ignore if not supported by index */
if (saop_control == SAOP_PER_AM && !index->amsearcharray)
continue;
- found_clause = true;
if (indexcol > 0)
+ {
found_lower_saop_clause = true;
+ if (saop_control == SAOP_SKIP_LOWER)
+ continue;
+ }
+ found_clause = true;
}
else
{
@@ -928,6 +955,13 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
return NIL;
}
+ if (saop_control == SAOP_SKIP_LOWER)
+ {
+ if (!found_lower_saop_clause)
+ return NIL;
+ found_lower_saop_clause = false;
+ }
+
/* We do not want the index's rel itself listed in outer_relids */
outer_relids = bms_del_member(outer_relids, rel->relid);
/* Enforce convention that outer_relids is exactly NULL if empty */
@@ -944,9 +978,19 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
* assume the scan is unordered.
*/
pathkeys_possibly_useful = (scantype != ST_BITMAPSCAN &&
- !found_lower_saop_clause &&
has_useful_pathkeys(root, rel));
index_is_ordered = (index->sortopfamily != NULL);
+ if (pathkeys_possibly_useful && found_lower_saop_clause)
+ {
+ /*
+ * We can't use an ordering with a lower SAOP clause, but we might be
+ * able to use this same index better without the SAOP. Set a retry
+ * flag so we can do another pass to catch that.
+ */
+ pathkeys_possibly_useful = false;
+ if (saop_retry)
+ *saop_retry = true;
+ }
if (index_is_ordered && pathkeys_possibly_useful)
{
index_pathkeys = build_index_pathkeys(root, index,
@@ -1137,7 +1181,7 @@ build_paths_for_OR(PlannerInfo *root, RelOptInfo *rel,
indexpaths = build_index_paths(root, rel,
index, &clauseset,
useful_predicate,
- SAOP_ALLOW, ST_BITMAPSCAN);
+ SAOP_ALLOW, ST_BITMAPSCAN, NULL);
result = list_concat(result, indexpaths);
}
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
