From: Alexander Kuzmenkov <a.kuzmenkov@postgrespro.ru>
To: PostgreSQL-development <pgsql-hackers@postgresql.org>
Subject: Uninterruptible long planning of a query with too many WHERE clauses
Date: Fri, 9 Nov 2018 18:00:41 +0300
Message-ID: <90c5bdfa-d633-dabe-9889-3cf3e1acd443@postgrespro.ru> (raw)
Hi hackers,
Recently one of our customers encountered a situation when the planning
of a particular query takes too long (several minutes) and can't be
interrupted by pg_terminate_backend(). The query and schema are attached
(this is generated by Zabbix). The reason for the slowness is that the
run time of choose_bitmap_and() is quadratic in the number of WHERE
clauses. It assigns unique ids to the clauses by putting them in a list
and then doing a linear search with equal() to determine the position of
each new clause.
Our first attempt to fix this was putting these clauses into an rbtree
or dynahash. This improves the performance, but is not entirely correct.
We don't have a comparison or hash function for nodes, so we have to
hash or compare their string representation. But the equality of
nodeToString() is not equivalent to equal(), because the string has some
fields that are ignored by equal(), such as token location. So we can't
really compare the string value instead of using equal().
I settled on a simpler solution: limiting the number of clauses we try
to uniquely identify. If there are too many, skip the smarter logic that
requires comparing paths by clauses, and just return the cheapest input
path from choose_bitmap_and(). The patch is attached.
I'd like to hear your thoughts on this. This is a valid query that
freezes a backend with 100% CPU usage and no way to interrupt it, and I
think we should fail more gracefully.
--
Alexander Kuzmenkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
Attachments:
[application/sql] schema_dump.sql (3.1K, ../90c5bdfa-d633-dabe-9889-3cf3e1acd443@postgrespro.ru/2-schema_dump.sql)
download
[application/x-bzip] select.sql.bz2 (3.1M, ../90c5bdfa-d633-dabe-9889-3cf3e1acd443@postgrespro.ru/3-select.sql.bz2)
download
[text/x-patch] choose-bitmap-and.patch (3.6K, ../90c5bdfa-d633-dabe-9889-3cf3e1acd443@postgrespro.ru/4-choose-bitmap-and.patch)
download | inline diff:diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.cindex f295558..da5a98e 100644--- a/src/backend/optimizer/path/indxpath.c+++ b/src/backend/optimizer/path/indxpath.c@@ -1371,7 +1371,7 @@ choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel, List *paths)
{
int npaths = list_length(paths);
PathClauseUsage **pathinfoarray;
- PathClauseUsage *pathinfo;+ PathClauseUsage *pathinfo = NULL;
List *clauselist;
List *bestpaths = NIL;
Cost bestcost = 0;
@@ -1431,6 +1431,10 @@ choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel, List *paths)
* regular qual clauses too, to have a more intelligent, but much more
* expensive, check for redundancy --- but in most cases simple equality
* seems to suffice.)
+ *+ * It is too slow to compare paths by clause usage if there are too many+ * clauses, so in that case we skip the above algorithm and just return+ * the cheapest input path.
*/
/*
@@ -1447,6 +1451,14 @@ choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel, List *paths)
Path *ipath = (Path *) lfirst(l);
pathinfo = classify_index_clause_usage(ipath, &clauselist);
++ /*+ * There are too many clauses to classify efficiently, switch+ * to a simpler algorithm.+ */+ if (pathinfo == NULL)+ break;+
for (i = 0; i < npaths; i++)
{
if (bms_equal(pathinfo->clauseids, pathinfoarray[i]->clauseids))
@@ -1476,6 +1488,27 @@ choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel, List *paths)
if (npaths == 1)
return pathinfoarray[0]->path;
+ /*+ * If there are too many different clauses to classify efficiently,+ * just return the cheapest input path.+ */+ if (pathinfo == NULL)+ {+ Path *bestPath = NULL;+ Cost bestCost = 0.;+ foreach(l, paths)+ {+ Path *path = (Path *) lfirst(l);+ Cost cost = bitmap_and_cost_est(root, rel, list_make1(path));+ if (bestPath == NULL || cost < bestCost)+ {+ bestCost = cost;+ bestPath = path;+ }+ }+ return bestPath;+ }+
/* Sort the surviving paths by index access cost */
qsort(pathinfoarray, npaths, sizeof(PathClauseUsage *),
path_usage_comparator);
@@ -1695,6 +1728,17 @@ bitmap_and_cost_est(PlannerInfo *root, RelOptInfo *rel, List *paths)
* *clauselist is used and expanded as needed to identify all the distinct
* clauses seen across successive calls. Caller must initialize it to NIL
* before first call of a set.
+ *+ * We use linear search in list to find clauses in clauselist, so the time+ * to classify the clauses grows quadratically with their number. To control+ * the run time, this function returns NULL after clauselist length reaches+ * some threshold, so that the caller can switch to a simpler algorithm.+ *+ * It could be possible to use a tree or a hash table instead of list to+ * allows faster lookups, but we don't have comparison or hash function for+ * the nodes. The nodeToString() is not suitable because the equality of string+ * representation is not the same ad nodes being equal(). The string includes+ * some fields that are ignored by equal(), such as token location.
*/
static PathClauseUsage *
classify_index_clause_usage(Path *path, List **clauselist)
@@ -1711,6 +1755,13 @@ classify_index_clause_usage(Path *path, List **clauselist)
result->preds = NIL;
find_indexpath_quals(path, &result->quals, &result->preds);
+ /* Bail out if there are too many clauses to classify efficiently */+ if (list_length(result->quals) + list_length(result->preds)+ + list_length(*clauselist) > 1000)+ {+ return NULL;+ }+
/* Build up a bitmapset representing the quals and preds */
clauseids = NULL;
foreach(lc, result->quals)
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-hackers@postgresql.org
Cc: a.kuzmenkov@postgrespro.ru
Subject: Re: Uninterruptible long planning of a query with too many WHERE clauses
In-Reply-To: <90c5bdfa-d633-dabe-9889-3cf3e1acd443@postgrespro.ru>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox