Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtp (Exim 4.84_2) (envelope-from ) id 1eLdNa-0003rX-AL for pgsql-hackers@arkaria.postgresql.org; Sun, 03 Dec 2017 23:08:58 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.84_2) (envelope-from ) id 1eLdNZ-0000p8-N3 for pgsql-hackers@arkaria.postgresql.org; Sun, 03 Dec 2017 23:08:57 +0000 Received: from makus.postgresql.org ([2001:4800:1501:1::229]) by malur.postgresql.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_CBC_SHA384:256) (Exim 4.84_2) (envelope-from ) id 1eLdNZ-0000oc-93; Sun, 03 Dec 2017 23:08:57 +0000 Received: from sss.pgh.pa.us ([66.207.139.130]) by makus.postgresql.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_CBC_SHA384:256) (Exim 4.89) (envelope-from ) id 1eLdNR-0002gB-Pg; Sun, 03 Dec 2017 23:08:55 +0000 Received: from sss1.sss.pgh.pa.us (localhost [127.0.0.1]) by sss.pgh.pa.us (8.14.4/8.14.4) with ESMTP id vB3N8kMb011631; Sun, 3 Dec 2017 18:08:47 -0500 From: Tom Lane To: Jeff Janes cc: Vitaliy Garnashevich , Justin Pryzby , pgsql-performance@lists.postgresql.org, pgsql-hackers@lists.postgresql.org Subject: Re: Bitmap scan is undercosted? In-reply-to: <18188.1512258290@sss.pgh.pa.us> References: <73a4936d-2814-dc08-ed0c-978f76f435b0@gmail.com> <20171201183427.GK18413@telsasoft.com> <20171201231104.GN18413@telsasoft.com> <18188.1512258290@sss.pgh.pa.us> Comments: In-reply-to Tom Lane message dated "Sat, 02 Dec 2017 18:44:50 -0500" MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----- =_aaaaaaaaaa0" Content-ID: <11418.1512342229.0@sss.pgh.pa.us> Date: Sun, 03 Dec 2017 18:08:46 -0500 Message-ID: <11630.1512342526@sss.pgh.pa.us> List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Precedence: bulk ------- =_aaaaaaaaaa0 Content-Type: text/plain; charset="us-ascii" Content-ID: <11418.1512342229.1@sss.pgh.pa.us> Content-Transfer-Encoding: quoted-printable I wrote: > I tried creating multiple-column statistics using the v10 facility for > that: > regression=3D# create statistics s1 on num, flag from aaa; > CREATE STATISTICS > regression=3D# analyze aaa; > ANALYZE > but that changed the estimate not at all, which surprised me because > dependency statistics are supposed to fix exactly this type of problem. > I suspect there may be something in the extended-stats code that causes = it > not to work right for boolean columns --- this wouldn't be excessively > surprising because of the way the planner messes around with converting > "flag =3D true" to just "flag" and sometimes back again. But I've not > looked closer yet. After looking, I found that indeed dependency_is_compatible_clause() rejects expressions like "flag" or "NOT flag", which it needn't since those are fully equivalent to "flag =3D true" or "flag =3D false" respectively. Moreover there's nothing else in dependencies_clauselist_selectivity that depends on the exact form of the clause under test, only on the semantics that it's an equality condition on some Var. Hence I propose the attached patch, which fixes the rowcount estimate for the example discussed in this thread: create table aaa as select (id%100)::int num, (id%10=3D1)::bool flag from = generate_series(1, 10000000) id; create index i1 on aaa (num); create index i2 on aaa (flag); create statistics s1 on num, flag from aaa; analyze aaa; explain analyze select count(*) from aaa where num =3D 1 and flag =3D true= ; Without patch: Aggregate (cost=3D43236.73..43236.74 rows=3D1 width=3D8) (actual time=3D= 349.365..349.3 65 rows=3D1 loops=3D1) -> Bitmap Heap Scan on aaa (cost=3D20086.40..43212.94 rows=3D9514 wid= th=3D0) (act ual time=3D101.308..337.985 rows=3D100000 loops=3D1) Recheck Cond: (num =3D 1) Filter: flag Heap Blocks: exact=3D44248 -> BitmapAnd (cost=3D20086.40..20086.40 rows=3D9514 width=3D0) = (actual time =3D92.214..92.214 rows=3D0 loops=3D1) -> Bitmap Index Scan on i1 (cost=3D0.00..1776.43 rows=3D9= 6000 width =3D0) (actual time=3D17.236..17.236 rows=3D100000 loops=3D1) Index Cond: (num =3D 1) -> Bitmap Index Scan on i2 (cost=3D0.00..18304.96 rows=3D= 991003 wid th=3D0) (actual time=3D72.168..72.168 rows=3D1000000 loops=3D1) Index Cond: (flag =3D true) Planning time: 0.254 ms Execution time: 350.796 ms With patch: Aggregate (cost=3D43496.19..43496.20 rows=3D1 width=3D8) (actual time=3D= 359.195..359.1 95 rows=3D1 loops=3D1) -> Bitmap Heap Scan on aaa (cost=3D20129.64..43256.19 rows=3D96000 wi= dth=3D0) (ac tual time=3D99.750..347.353 rows=3D100000 loops=3D1) Recheck Cond: (num =3D 1) Filter: flag Heap Blocks: exact=3D44248 -> BitmapAnd (cost=3D20129.64..20129.64 rows=3D9514 width=3D0) = (actual time =3D90.671..90.671 rows=3D0 loops=3D1) -> Bitmap Index Scan on i1 (cost=3D0.00..1776.43 rows=3D9= 6000 width =3D0) (actual time=3D16.946..16.946 rows=3D100000 loops=3D1) Index Cond: (num =3D 1) -> Bitmap Index Scan on i2 (cost=3D0.00..18304.96 rows=3D= 991003 wid th=3D0) (actual time=3D70.898..70.898 rows=3D1000000 loops=3D1) Index Cond: (flag =3D true) Planning time: 0.218 ms Execution time: 360.608 ms That's the right overall rowcount estimate for the scan, given the stats it's working from. There's apparently still something wrong with bitmap costing, since it's still estimating this as cheaper than the single-index case --- noting the bogus rowcount estimate for the BitmapAnd, I suspect that bitmap costing is taking shortcuts rather than using clauselist_selectivity to estimate the overall selectivity of the bitmap conditions. But whatever is causing that, it's independent of this deficiency. In addition to the bugfix proper, I improved some comments, got rid of a NumRelids() test that's redundant with the preceding bms_membership() test, and fixed dependencies_clauselist_selectivity so that estimatedclauses actually is a pure output argument as stated by its API contract. regards, tom lane ------- =_aaaaaaaaaa0 Content-Type: text/x-diff; name="fix-dependencies.c-for-boolean-quals.patch"; charset="us-ascii" Content-ID: <11418.1512342229.2@sss.pgh.pa.us> Content-Description: fix-dependencies.c-for-boolean-quals.patch Content-Transfer-Encoding: quoted-printable diff --git a/src/backend/statistics/dependencies.c b/src/backend/statistic= s/dependencies.c index 9756fb8..ae0f304 100644 *** a/src/backend/statistics/dependencies.c --- b/src/backend/statistics/dependencies.c *************** pg_dependencies_send(PG_FUNCTION_ARGS) *** 736,826 **** * dependency_is_compatible_clause * Determines if the clause is compatible with functional dependencies * ! * Only OpExprs with two arguments using an equality operator are suppor= ted. ! * When returning True attnum is set to the attribute number of the Var = within ! * the supported clause. ! * ! * Currently we only support Var =3D Const, or Const =3D Var. It may be = possible ! * to expand on this later. */ static bool dependency_is_compatible_clause(Node *clause, Index relid, AttrNumber *a= ttnum) { RestrictInfo *rinfo =3D (RestrictInfo *) clause; = if (!IsA(rinfo, RestrictInfo)) return false; = ! /* Pseudoconstants are not really interesting here. */ if (rinfo->pseudoconstant) return false; = ! /* clauses referencing multiple varnos are incompatible */ if (bms_membership(rinfo->clause_relids) !=3D BMS_SINGLETON) return false; = if (is_opclause(rinfo->clause)) { OpExpr *expr =3D (OpExpr *) rinfo->clause; - Var *var; - bool varonleft =3D true; - bool ok; = ! /* Only expressions with two arguments are considered compatible. */ if (list_length(expr->args) !=3D 2) return false; = ! /* see if it actually has the right */ ! ok =3D (NumRelids((Node *) expr) =3D=3D 1) && ! (is_pseudo_constant_clause(lsecond(expr->args)) || ! (varonleft =3D false, ! is_pseudo_constant_clause(linitial(expr->args)))); ! = ! /* unsupported structure (two variables or so) */ ! if (!ok) return false; = /* ! * If it's not "=3D" operator, just ignore the clause, as it's not * compatible with functional dependencies. * * This uses the function for estimating selectivity, not the operator * directly (a bit awkward, but well ...). */ if (get_oprrest(expr->opno) !=3D F_EQSEL) return false; = ! var =3D (varonleft) ? linitial(expr->args) : lsecond(expr->args); ! = /* ! * We may ignore any RelabelType node above the operand. (There won't ! * be more than one, since eval_const_expressions() has been applied ! * already.) */ ! if (IsA(var, RelabelType)) ! var =3D (Var *) ((RelabelType *) var)->arg; = ! /* We only support plain Vars for now */ ! if (!IsA(var, Var)) ! return false; = ! /* Ensure var is from the correct relation */ ! if (var->varno !=3D relid) ! return false; = ! /* we also better ensure the Var is from the current level */ ! if (var->varlevelsup > 0) ! return false; = ! /* Also skip system attributes (we don't allow stats on those). */ ! if (!AttrNumberIsForUserDefinedAttr(var->varattno)) ! return false; = ! *attnum =3D var->varattno; ! return true; ! } = ! return false; } = /* --- 736,839 ---- * dependency_is_compatible_clause * Determines if the clause is compatible with functional dependencies * ! * Only clauses that have the form of equality to a pseudoconstant, or c= an be ! * interpreted that way, are currently accepted. Furthermore the variab= le ! * part of the clause must be a simple Var belonging to the specified ! * relation, whose attribute number we return in *attnum on success. */ static bool dependency_is_compatible_clause(Node *clause, Index relid, AttrNumber *a= ttnum) { RestrictInfo *rinfo =3D (RestrictInfo *) clause; + Var *var; = if (!IsA(rinfo, RestrictInfo)) return false; = ! /* Pseudoconstants are not interesting (they couldn't contain a Var) */ if (rinfo->pseudoconstant) return false; = ! /* Clauses referencing multiple, or no, varnos are incompatible */ if (bms_membership(rinfo->clause_relids) !=3D BMS_SINGLETON) return false; = if (is_opclause(rinfo->clause)) { + /* If it's an opclause, check for Var =3D Const or Const =3D Var. */ OpExpr *expr =3D (OpExpr *) rinfo->clause; = ! /* Only expressions with two arguments are candidates. */ if (list_length(expr->args) !=3D 2) return false; = ! /* Make sure non-selected argument is a pseudoconstant. */ ! if (is_pseudo_constant_clause(lsecond(expr->args))) ! var =3D linitial(expr->args); ! else if (is_pseudo_constant_clause(linitial(expr->args))) ! var =3D lsecond(expr->args); ! else return false; = /* ! * If it's not an "=3D" operator, just ignore the clause, as it's not * compatible with functional dependencies. * * This uses the function for estimating selectivity, not the operator * directly (a bit awkward, but well ...). + * + * XXX this is pretty dubious; probably it'd be better to check btree + * or hash opclass membership, so as not to be fooled by custom + * selectivity functions, and to be more consistent with decisions + * elsewhere in the planner. */ if (get_oprrest(expr->opno) !=3D F_EQSEL) return false; = ! /* OK to proceed with checking "var" */ ! } ! else if (not_clause((Node *) rinfo->clause)) ! { /* ! * "NOT x" can be interpreted as "x =3D false", so get the argument an= d ! * proceed with seeing if it's a suitable Var. */ ! var =3D (Var *) get_notclausearg(rinfo->clause); ! } ! else ! { ! /* ! * A boolean expression "x" can be interpreted as "x =3D true", so ! * proceed with seeing if it's a suitable Var. ! */ ! var =3D (Var *) rinfo->clause; ! } = ! /* ! * We may ignore any RelabelType node above the operand. (There won't = be ! * more than one, since eval_const_expressions has been applied already= .) ! */ ! if (IsA(var, RelabelType)) ! var =3D (Var *) ((RelabelType *) var)->arg; = ! /* We only support plain Vars for now */ ! if (!IsA(var, Var)) ! return false; = ! /* Ensure Var is from the correct relation */ ! if (var->varno !=3D relid) ! return false; = ! /* We also better ensure the Var is from the current level */ ! if (var->varlevelsup !=3D 0) ! return false; = ! /* Also ignore system attributes (we don't allow stats on those) */ ! if (!AttrNumberIsForUserDefinedAttr(var->varattno)) ! return false; = ! *attnum =3D var->varattno; ! return true; } = /* *************** find_strongest_dependency(StatisticExtIn *** 891,902 **** = /* * dependencies_clauselist_selectivity ! * Return the estimated selectivity of the given clauses using ! * functional dependency statistics, or 1.0 if no useful functional * dependency statistic exists. * * 'estimatedclauses' is an output argument that gets a bit set correspo= nding ! * to the (zero-based) list index of clauses that are included in the * estimated selectivity. * * Given equality clauses on attributes (a,b) we find the strongest depe= ndency --- 904,915 ---- = /* * dependencies_clauselist_selectivity ! * Return the estimated selectivity of (a subset of) the given clauses ! * using functional dependency statistics, or 1.0 if no useful function= al * dependency statistic exists. * * 'estimatedclauses' is an output argument that gets a bit set correspo= nding ! * to the (zero-based) list index of each clause that is included in the * estimated selectivity. * * Given equality clauses on attributes (a,b) we find the strongest depe= ndency *************** dependencies_clauselist_selectivity(Plan *** 932,937 **** --- 945,953 ---- AttrNumber *list_attnums; int listidx; = + /* initialize output argument */ + *estimatedclauses =3D NULL; + = /* check if there's any stats that might be useful for us. */ if (!has_stats_of_kind(rel->statlist, STATS_EXT_DEPENDENCIES)) return 1.0; ------- =_aaaaaaaaaa0--