Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_CBC_SHA1:256) (Exim 4.89) (envelope-from ) id 1gx5yd-0006kN-Kx for pgsql-hackers@arkaria.postgresql.org; Fri, 22 Feb 2019 08:14:35 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.89) (envelope-from ) id 1gx5yc-00075l-CN for pgsql-hackers@arkaria.postgresql.org; Fri, 22 Feb 2019 08:14:34 +0000 Received: from makus.postgresql.org ([2001:4800:3e1:1::229]) by malur.postgresql.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_CBC_SHA1:256) (Exim 4.89) (envelope-from ) id 1gx5yb-00073i-TC for pgsql-hackers@lists.postgresql.org; Fri, 22 Feb 2019 08:14:34 +0000 Received: from tama500.ecl.ntt.co.jp ([129.60.39.148]) by makus.postgresql.org with esmtp (Exim 4.89) (envelope-from ) id 1gx5yY-00054P-6a for pgsql-hackers@lists.postgresql.org; Fri, 22 Feb 2019 08:14:32 +0000 Received: from vc2.ecl.ntt.co.jp (vc2.ecl.ntt.co.jp [129.60.86.154]) by tama500.ecl.ntt.co.jp (8.13.8/8.13.8) with ESMTP id x1M8ESP3006681 for ; Fri, 22 Feb 2019 17:14:28 +0900 Received: from vc2.ecl.ntt.co.jp (localhost [127.0.0.1]) by vc2.ecl.ntt.co.jp (Postfix) with ESMTP id 31F53638E9D; Fri, 22 Feb 2019 17:14:28 +0900 (JST) Received: from jcms-pop11.ecl.ntt.co.jp (jcms-pop11.ecl.ntt.co.jp [129.60.87.132]) by vc2.ecl.ntt.co.jp (Postfix) with ESMTP id 1F43D638D5B; Fri, 22 Feb 2019 17:14:28 +0900 (JST) Received: from hosoyahp (unknown [129.60.241.74]) by jcms-pop11.ecl.ntt.co.jp (Postfix) with ESMTPSA id 126B470C099B; Fri, 22 Feb 2019 17:14:28 +0900 (JST) From: "Yuzuko Hosoya" Subject: Problem with default partition pruning Date: Fri, 22 Feb 2019 17:14:04 +0900 Message-ID: <00e601d4ca86$932b8bc0$b982a340$@lab.ntt.co.jp> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_NextPart_000_00E7_01D4CAD2.031333C0" X-Mailer: Microsoft Outlook 15.0 Content-language: ja Thread-Index: AdTKhcDwfZD2VzYgTkmIr5ynUs9Fkg== X-CC-Mail-RelayStamp: 1 To: "'PostgreSQL Hackers'" Cc: "'Amit Langote'" X-TM-AS-MML: disable List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Precedence: bulk This is a multipart message in MIME format. ------=_NextPart_000_00E7_01D4CAD2.031333C0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Hi, I found the bug of default partition pruning when executing a range query. ----- postgres=# create table test1(id int, val text) partition by range (id); postgres=# create table test1_1 partition of test1 for values from (0) to (100); postgres=# create table test1_2 partition of test1 for values from (150) to (200); postgres=# create table test1_def partition of test1 default; postgres=# explain select * from test1 where id > 0 and id < 30; QUERY PLAN ---------------------------------------------------------------- Append (cost=0.00..11.83 rows=59 width=11) -> Seq Scan on test1_1 (cost=0.00..5.00 rows=58 width=11) Filter: ((id > 0) AND (id < 30)) -> Seq Scan on test1_def (cost=0.00..6.53 rows=1 width=12) Filter: ((id > 0) AND (id < 30)) (5 rows) There is no need to scan the default partition, but it's scanned. ----- In the current implement, whether the default partition is scanned or not is determined according to each condition of given WHERE clause at get_matching_range_bounds(). In this example, scan_default is set true according to id > 0 because id >= 200 matches the default partition. Similarly, according to id < 30, scan_default is set true. Then, these results are combined according to AND/OR at perform_pruning_combine_step(). In this case, final result's scan_default is set true. The modifications I made are as follows: - get_matching_range_bounds() determines only offsets of range bounds according to each condition - These results are combined at perform_pruning_combine_step() - Whether the default partition is scanned or not is determined at get_matching_partitions() Attached the patch. Any feedback is greatly appreciated. Best regards, --- Yuzuko Hosoya NTT Open Source Software Center ------=_NextPart_000_00E7_01D4CAD2.031333C0 Content-Type: application/octet-stream; name="default_partition_pruning.patch" Content-Transfer-Encoding: quoted-printable Content-Disposition: attachment; filename="default_partition_pruning.patch" diff --git a/src/backend/partitioning/partprune.c = b/src/backend/partitioning/partprune.c=0A= index 8c97219..d46a83c 100644=0A= --- a/src/backend/partitioning/partprune.c=0A= +++ b/src/backend/partitioning/partprune.c=0A= @@ -614,6 +614,7 @@ get_matching_partitions(PartitionPruneContext = *context, List *pruning_steps)=0A= PruneStepResult **results,=0A= *final_result;=0A= ListCell *lc;=0A= + bool scan_default;=0A= =0A= /* If there are no pruning steps then all partitions match. */=0A= if (num_steps =3D=3D 0)=0A= @@ -665,20 +666,23 @@ get_matching_partitions(PartitionPruneContext = *context, List *pruning_steps)=0A= Assert(final_result !=3D NULL);=0A= i =3D -1;=0A= result =3D NULL;=0A= + scan_default =3D final_result->scan_default;=0A= while ((i =3D bms_next_member(final_result->bound_offsets, i)) >=3D 0)=0A= {=0A= int partindex =3D context->boundinfo->indexes[i];=0A= =0A= /*=0A= - * In range and hash partitioning cases, some slots may contain -1,=0A= + * In range and hash partitioning cases, some index values may be -1,=0A= * indicating that no partition has been defined to accept a given=0A= - * range of data or for a given remainder, respectively. The default=0A= - * partition, if any, in case of range partitioning, will be added to=0A= - * the result, because the specified range still satisfies the query's=0A= - * conditions.=0A= + * range of values (that is, the bound at given offset is the upper=0A= + * bound of this unassigned range of values) or for a given remainder,=0A= + * respectively. As it's still part of the queried range of values,=0A= + * add the default partition, if any.=0A= */=0A= if (partindex >=3D 0)=0A= result =3D bms_add_member(result, partindex);=0A= + else=0A= + scan_default |=3D partition_bound_has_default(context->boundinfo);=0A= }=0A= =0A= /* Add the null and/or default partition if needed and if present. */=0A= @@ -688,7 +692,7 @@ get_matching_partitions(PartitionPruneContext = *context, List *pruning_steps)=0A= Assert(partition_bound_accepts_nulls(context->boundinfo));=0A= result =3D bms_add_member(result, context->boundinfo->null_index);=0A= }=0A= - if (final_result->scan_default)=0A= + if (scan_default)=0A= {=0A= Assert(context->strategy =3D=3D PARTITION_STRATEGY_LIST ||=0A= context->strategy =3D=3D PARTITION_STRATEGY_RANGE);=0A= @@ -2202,6 +2206,11 @@ get_matching_hash_bounds(PartitionPruneContext = *context,=0A= * get_matching_list_bounds=0A= * Determine the offsets of list bounds matching the specified value,=0A= * according to the semantics of the given operator strategy=0A= + *=0A= + * scan_default will be set in the returned struct, if the default = partition=0A= + * needs to be scanned, provided one exists at all. scan_null will be = set if=0A= + * the special null-accepting partition needs to be scanned.=0A= + *=0A= * 'opstrategy' if non-zero must be a btree strategy number.=0A= *=0A= * 'value' contains the value to use for pruning.=0A= @@ -2404,8 +2413,17 @@ get_matching_list_bounds(PartitionPruneContext = *context,=0A= * Each datum whose offset is in result is to be treated as the upper = bound of=0A= * the partition that will contain the desired values.=0A= *=0A= - * If default partition needs to be scanned for given values, set = scan_default=0A= - * in result if present.=0A= + * scan_default will be set in the returned struct, if the default = partition=0A= + * needs to be scanned, provided one exists at all. Although note that = we=0A= + * intentionally don't set scan_default in this function if only = because the=0A= + * matching set of values, found by comparing the input values using the=0A= + * specified opstrategy, contains unassigned portions of key space, = which=0A= + * we normally assume to belong to the default partition. We don't = infer=0A= + * that until all steps have been executed, including any combination = steps,=0A= + * because even if such unassinged portion of key space appears to be = part of=0A= + * the set of queried values based on comparisons in the individual = OpExprs,=0A= + * the final set of bounds obtained after combining multiple OpExprs may=0A= + * exclude it.=0A= *=0A= * 'opstrategy' if non-zero must be a btree strategy number.=0A= *=0A= @@ -2431,8 +2449,7 @@ get_matching_range_bounds(PartitionPruneContext = *context,=0A= int *partindices =3D boundinfo->indexes;=0A= int off,=0A= minoff,=0A= - maxoff,=0A= - i;=0A= + maxoff;=0A= bool is_equal;=0A= bool inclusive =3D false;=0A= =0A= @@ -2496,11 +2513,7 @@ get_matching_range_bounds(PartitionPruneContext = *context,=0A= if (nvalues =3D=3D partnatts)=0A= {=0A= /* There can only be zero or one matching partition. */=0A= - if (partindices[off + 1] >=3D 0)=0A= - result->bound_offsets =3D bms_make_singleton(off + 1);=0A= - else=0A= - result->scan_default =3D=0A= - partition_bound_has_default(boundinfo);=0A= + result->bound_offsets =3D bms_make_singleton(off + 1);=0A= return result;=0A= }=0A= else=0A= @@ -2588,57 +2601,21 @@ get_matching_range_bounds(PartitionPruneContext = *context,=0A= maxoff =3D off + 1;=0A= }=0A= =0A= - /*=0A= - * Skip if minoff/maxoff are actually the upper bound of a=0A= - * un-assigned portion of values.=0A= - */=0A= - if (partindices[minoff] < 0 && minoff < boundinfo->ndatums)=0A= - minoff++;=0A= - if (partindices[maxoff] < 0 && maxoff >=3D 1)=0A= - maxoff--;=0A= -=0A= - /*=0A= - * There may exist a range of values unassigned to any=0A= - * non-default partition between the datums at minoff and=0A= - * maxoff. Add the default partition in that case.=0A= - */=0A= - if (partition_bound_has_default(boundinfo))=0A= - {=0A= - for (i =3D minoff; i <=3D maxoff; i++)=0A= - {=0A= - if (partindices[i] < 0)=0A= - {=0A= - result->scan_default =3D true;=0A= - break;=0A= - }=0A= - }=0A= - }=0A= -=0A= Assert(minoff >=3D 0 && maxoff >=3D 0);=0A= result->bound_offsets =3D bms_add_range(NULL, minoff, maxoff);=0A= }=0A= - else if (off >=3D 0) /* !is_equal */=0A= + else=0A= {=0A= /*=0A= * The lookup value falls in the range between some bounds in=0A= * boundinfo. 'off' would be the offset of the greatest bound=0A= * that is <=3D lookup value, so add off + 1 to the result=0A= * instead as the offset of the upper bound of the only=0A= - * partition that may contain the lookup value.=0A= + * partition that may contain the lookup value. If 'off' is=0A= + * -1 indicating that all bounds are greater, then we simply=0A= + * end up adding the first bound's offset, that is, 0.=0A= */=0A= - if (partindices[off + 1] >=3D 0)=0A= - result->bound_offsets =3D bms_make_singleton(off + 1);=0A= - else=0A= - result->scan_default =3D=0A= - partition_bound_has_default(boundinfo);=0A= - }=0A= - else=0A= - {=0A= - /*=0A= - * off < 0: the lookup value is smaller than all bounds, so=0A= - * only the default partition qualifies, if there is one.=0A= - */=0A= - result->scan_default =3D partition_bound_has_default(boundinfo);=0A= + result->bound_offsets =3D bms_make_singleton(off + 1);=0A= }=0A= =0A= return result;=0A= @@ -2736,16 +2713,7 @@ get_matching_range_bounds(PartitionPruneContext = *context,=0A= boundinfo,=0A= nvalues, values,=0A= &is_equal);=0A= - if (off < 0)=0A= - {=0A= - /*=0A= - * All bounds are greater than the key, so we could only=0A= - * expect to find the lookup key in the default partition.=0A= - */=0A= - result->scan_default =3D partition_bound_has_default(boundinfo);=0A= - return result;=0A= - }=0A= - else=0A= + if (off >=3D 0)=0A= {=0A= /*=0A= * See the comment above.=0A= @@ -2786,9 +2754,11 @@ get_matching_range_bounds(PartitionPruneContext = *context,=0A= * instead as the offset of the upper bound of the greatest=0A= * partition that may contain lookup value. If the lookup=0A= * value had exactly matched the bound, but it isn't=0A= - * inclusive, no need add the adjacent partition.=0A= + * inclusive, no need add the adjacent partition. If 'off' is=0A= + * -1 indicating that all bounds are greater, then we simply=0A= + * end up adding the first bound's offset, that is, 0.=0A= */=0A= - else if (!is_equal || inclusive)=0A= + else if (off < 0 || !is_equal || inclusive)=0A= maxoff =3D off + 1;=0A= else=0A= maxoff =3D off;=0A= @@ -2800,58 +2770,43 @@ get_matching_range_bounds(PartitionPruneContext = *context,=0A= break;=0A= }=0A= =0A= + Assert(minoff >=3D 0 && minoff <=3D boundinfo->ndatums);=0A= + Assert(maxoff >=3D 0 && maxoff <=3D boundinfo->ndatums);=0A= +=0A= /*=0A= - * Skip a gap and when doing so, check if the bound contains a finite=0A= - * value to decide if we need to add the default partition. If it's an=0A= - * infinite bound, we need not add the default partition, as having an=0A= - * infinite bound means the partition in question catches any values = that=0A= - * would otherwise be in the default partition.=0A= + * If the smallest partition to return has MINVALUE (negative = infinity) as=0A= + * its lower bound, increment it to point to the next finite bound=0A= + * (supposedly its upper bound), so that we don't advertently end up=0A= + * scanning the default partition.=0A= */=0A= - if (partindices[minoff] < 0)=0A= + if (minoff < boundinfo->ndatums && partindices[minoff] < 0)=0A= {=0A= int lastkey =3D nvalues - 1;=0A= =0A= - if (minoff >=3D 0 &&=0A= - minoff < boundinfo->ndatums &&=0A= - boundinfo->kind[minoff][lastkey] =3D=3D=0A= - PARTITION_RANGE_DATUM_VALUE)=0A= - result->scan_default =3D partition_bound_has_default(boundinfo);=0A= -=0A= - minoff++;=0A= + if (boundinfo->kind[minoff][lastkey] =3D=3D=0A= + PARTITION_RANGE_DATUM_MINVALUE)=0A= + {=0A= + minoff++;=0A= + Assert(boundinfo->indexes[minoff] >=3D 0);=0A= + }=0A= }=0A= =0A= /*=0A= - * Skip a gap. See the above comment about how we decide whether or = not=0A= - * to scan the default partition based whether the datum that will = become=0A= - * the maximum datum is finite or not.=0A= + * If the previous greatest partition has MAXVALUE (positive infinity) = as=0A= + * its upper bound (something only possible to do with multi-column = range=0A= + * partitioning), we scan switch to it as the greatest partition to=0A= + * return. Again, so that we don't advertently end up scanning the=0A= + * default partition.=0A= */=0A= if (maxoff >=3D 1 && partindices[maxoff] < 0)=0A= {=0A= int lastkey =3D nvalues - 1;=0A= =0A= - if (maxoff >=3D 0 &&=0A= - maxoff <=3D boundinfo->ndatums &&=0A= - boundinfo->kind[maxoff - 1][lastkey] =3D=3D=0A= - PARTITION_RANGE_DATUM_VALUE)=0A= - result->scan_default =3D partition_bound_has_default(boundinfo);=0A= -=0A= - maxoff--;=0A= - }=0A= -=0A= - if (partition_bound_has_default(boundinfo))=0A= - {=0A= - /*=0A= - * There may exist a range of values unassigned to any non-default=0A= - * partition between the datums at minoff and maxoff. Add the default=0A= - * partition in that case.=0A= - */=0A= - for (i =3D minoff; i <=3D maxoff; i++)=0A= + if (boundinfo->kind[maxoff - 1][lastkey] =3D=3D=0A= + PARTITION_RANGE_DATUM_MAXVALUE)=0A= {=0A= - if (partindices[i] < 0)=0A= - {=0A= - result->scan_default =3D true;=0A= - break;=0A= - }=0A= + maxoff--;=0A= + Assert(boundinfo->indexes[maxoff] >=3D 0);=0A= }=0A= }=0A= =0A= @@ -3131,14 +3086,23 @@ = perform_pruning_combine_step(PartitionPruneContext *context,=0A= =0A= /*=0A= * A combine step without any source steps is an indication to not = perform=0A= - * any partition pruning, we just return all partitions.=0A= + * any partition pruning, we just return all datum offsets.=0A= */=0A= result =3D (PruneStepResult *) palloc0(sizeof(PruneStepResult));=0A= if (list_length(cstep->source_stepids) =3D=3D 0)=0A= {=0A= PartitionBoundInfo boundinfo =3D context->boundinfo;=0A= =0A= - result->bound_offsets =3D bms_add_range(NULL, 0, boundinfo->ndatums - = 1);=0A= + /*=0A= + * Add all valid offsets into the boundinfo->indexes array. For range=0A= + * partitioning, boundinfo->indexes contains (boundinfo->ndatums + 1)=0A= + * valid entries.=0A= + */=0A= + if (context->strategy =3D=3D PARTITION_STRATEGY_RANGE)=0A= + result->bound_offsets =3D bms_add_range(NULL, 0, boundinfo->ndatums);=0A= + else=0A= + result->bound_offsets =3D bms_add_range(NULL, 0,=0A= + boundinfo->ndatums - 1);=0A= result->scan_default =3D partition_bound_has_default(boundinfo);=0A= result->scan_null =3D partition_bound_accepts_nulls(boundinfo);=0A= return result;=0A= diff --git a/src/test/regress/expected/partition_prune.out = b/src/test/regress/expected/partition_prune.out=0A= index 30946f7..046e722 100644=0A= --- a/src/test/regress/expected/partition_prune.out=0A= +++ b/src/test/regress/expected/partition_prune.out=0A= @@ -517,15 +517,13 @@ explain (costs off) select * from rlp where a <=3D = 31;=0A= Filter: (a <=3D 31)=0A= -> Seq Scan on rlp5_1=0A= Filter: (a <=3D 31)=0A= - -> Seq Scan on rlp5_default=0A= - Filter: (a <=3D 31)=0A= -> Seq Scan on rlp_default_10=0A= Filter: (a <=3D 31)=0A= -> Seq Scan on rlp_default_30=0A= Filter: (a <=3D 31)=0A= -> Seq Scan on rlp_default_default=0A= Filter: (a <=3D 31)=0A= -(29 rows)=0A= +(27 rows)=0A= =0A= explain (costs off) select * from rlp where a =3D 1 or a =3D 7;=0A= QUERY PLAN =0A= @@ -573,11 +571,7 @@ explain (costs off) select * from rlp where a > 20 = and a < 27;=0A= Filter: ((a > 20) AND (a < 27))=0A= -> Seq Scan on rlp4_2=0A= Filter: ((a > 20) AND (a < 27))=0A= - -> Seq Scan on rlp4_default=0A= - Filter: ((a > 20) AND (a < 27))=0A= - -> Seq Scan on rlp_default_default=0A= - Filter: ((a > 20) AND (a < 27))=0A= -(9 rows)=0A= +(5 rows)=0A= =0A= explain (costs off) select * from rlp where a =3D 29;=0A= QUERY PLAN =0A= ------=_NextPart_000_00E7_01D4CAD2.031333C0--