Re: [Sender Address Forgery]Re: [Sender Address Forgery]Re: [HACKERS] path toward faster partition pruning

Hi David.

Thanks for the review.

On 2018/01/12 12:30, David Rowley wrote:
> I've got a few more things for you. I'm only partway through another
> pass, but it makes sense to post what I have now if you're working on
> a new version.
>
> 1. partitioing -> partitioning
>
> * Strategy of a partition clause operator per the partitioing operator class

Fixed.

> 2. get_partitions_from_clauses() modifies partclauses without
> mentioning it in the header. I think you need to either:
>
> a) warn about this in the header comment; or
> b) do a list_copy() before list_concat()
> c) do list_truncate back to the original length after you're done with the list.

Went with (b).

> 3. get_partitions_from_clauses_recurse(), with:
>
> result = bms_add_range(result, 0, partdesc->nparts - 1);
>
> You could change that to bms_add_range(NULL, ...) and ditch the
> assignment of result to NULL at the start of the function.

Done.

> 4. classify_partition_bounding_keys() now returns bool, but the return
> statement is still:
>
> return keys->n_eqkeys + keys->n_minkeys + keys->n_maxkeys + n_keynullness;
>
> my compiler didn't warn about that, but I'd imagine some might.

Oops, my bad.

>
> Instead, can you make it:
>
> if (keys->n_eqkeys > 0 || keys->n_minkeys > 0 ||
> keys->n_maxkeys > 0 || n_keynullness > 0)
> return true;
>
> return false;
>
> probably equal keys are the most likely case, so it'll be good to
> short circuit instead of performing addition on a bunch of stuff we
> don't care about anymore.

Changed it to what Robert suggested downthread.

> 5. In classify_partition_bounding_keys, why do we "continue" here?
>
> clause = rinfo->clause;
> if (rinfo->pseudoconstant &&
> !DatumGetBool(((Const *) clause)->constvalue))
> {
> *constfalse = true;
> continue;
> }
>
> Is there any point in searching further?
>
> Also, if you were consistent with the return value for
> classify_partition_bounding_keys when you've set *constfalse = true;
> you wouldn't need to handle the case twice like you are in
> get_partitions_from_clauses_recurse().

OK, I made classify_partition_bounding_keys() return true whenever set
*constfalse to true.

> 6. I think it would be nicer if get_partitions_from_ne_clauses returns
> a set of partitions that could be excluded.
>
> So instead of:
>
> * get_partitions_from_ne_clauses
> *
> * Return partitions of relation that satisfy all <> operator clauses in
> * ne_clauses. Only ever called if relation is a list partitioned table.
>
> Have:
>
> * get_partitions_from_ne_clauses
> *
> * Returns a Bitmapset of partitions that can be safely excluded due to
> * not-equal clauses existing for all possible partition values. It is only
> * valid to call this for LIST partitioned tables.
>
> and instead of:
>
> result = bms_add_range(NULL, 0, partdesc->nparts - 1);
> result = bms_del_members(result, excluded_parts);
> bms_free(excluded_parts);
>
> return result;
>
> Just do:
>
> return excluded_parts;
>
> and in get_partitions_from_clauses_recurse(), do bms_del_members
> instead of bms_int_members.
>
> there's less bit shuffling and it seems cleaner. Perhaps the function
> name would need to be changed if we're inverting the meaning too.
>
> (I've attached a patch which makes this change along with an idea in #8 below)

Thanks for the suggestions... (comment continues below)

> 7. The following comment claims the function sets *datum, but there's
> no param by that name:
>
> /*
> * partkey_datum_from_expr
> * Extract constant value from expr and set *datum to that value
> */
> static bool
> partkey_datum_from_expr(PartitionKey key, int partkeyidx,
> Expr *expr, Datum *value)

Fixed.

> 8. The code in get_partitions_from_ne_clauses() does perform quite a
> few nested loops. I think a more simple way to would be to track the
> offsets you've seen in a Bitmapset. This would save you having to
> check for duplicates, as an offset can only contain a single datum.
> You'd just need to build a couple of arrays after that, one to sum up
> the offsets found per partition, and one for the total datums allowed
> in the partition. If the numbers match then you can remove the
> partition.
>
> I've written this and attached it to this email. It saves about 50
> lines of code and should perform much better for complex cases, for
> example, a large NOT IN list. This also implements #6.

I liked your patch, so incorporated it, except, I feel slightly
uncomfortable about the new name that you chose for the function because
it sounds a bit generic. I mean the function solves a very specific
problem and have very strict requirements for calling it. It's not like
we could pass it just any partitioned relation and/or just any set of
clauses. It has to be a list-partitioned table and the list of clauses
must contain only the clauses containing compatible <> operators. Checks
for those requirements are carried out in yet another place, that is,
classify_partition_bounding_keys().

Perhaps we can live with that though, because it's not a publicly
available function, but someone might get confused in the future.

> 9. "the same" -> "it"
>
> /*
> * In case of NOT IN (..), we get a '<>', which while not
> * listed as part of any operator family, we are able to
> * handle the same if its negator is indeed a part of the
> * partitioning operator family.
> */

Done.

> 10. in classify_partition_bounding_keys: "0" -> "false"
>
> /* Return if no work to do below. */
> if (!will_compute_keys || *constfalse)
> return 0;
>
> Likewise for:
>
> if (*constfalse)
> return 0;

Have fixed these per an earlier comment in this email.

> 11. I don't see partition_bound_bsearch used anywhere below the
> following comment:
>
> * Generate bounding tuple(s).
> *
> * We look up partitions in the partition bound descriptor using, say,
> * partition_bound_bsearch(), which expects a Datum (or Datums if multi-
> * column key). So, extract the same out of the constant argument of
> * each clause.
>
> I also don't know what the comment is trying to say.

The comment is no longer very intelligible to me too. I just wanted to
say here that, *elsewhere*, we will use a function like
partition_bound_bsearch() to look up partitions from the clauses we
matched against individual partition key columns. That function expects
the lookup key to be in a Datum array form, not a list-of-clauses form.
So, we must construct the lookup key(s) by extracting constant values out
the clauses.

I tried to rewrite it that way. Hope that's a bit clearer.

> 12.
>
> * operator and sets *incl if equality is implied
>
> should be:
>
> * operator and set *incl to true if the operator's strategy is inclusive.

Done that way.

> 13. What does "the same" mean in:
>
> * and add this one directly to the result. Caller would
> * arbitrarily choose one of the many and perform
> * partition-pruning with the same. It's possible that mutual

It means "the one that caller would arbitrarily choose of the many that
this function will return to it". Anyway, I changed "the same" to "it".

> I think you quite often use "the same" to mean "it". Can you change that?

I guess that's just one of my many odd habits when writing English, all of
which I'm trying to get rid of, but apparently with limited success. Must
try harder. :)

> 14. Not sure what parameter you're talking about here.
>
> * Evaluate 'leftarg op rightarg' and set *result to its value.
> *
> * leftarg and rightarg referred to above actually refer to the constant
> * operand (Datum) of the clause contained in the parameters leftarg and
> * rightarg below, respectively. And op refers to the operator of the
> * clause contained in the parameter op below.

I rewrote the above comment block as:

* Try to compare the constant arguments of 'leftarg' and 'rightarg', in that
* order, using the operator of 'op' and set *result to the result of this
* comparison.

Is that any better?

> 15. "the latter" is normally used when you're referring to the last
> thing in a list which was just mentioned. In this case, leftarg_const
> and rightarg_const is the list, so "the latter" should mean
> rightarg_const, but I think you mean to compare them using the
> operator.
>
> * If the leftarg_const and rightarg_const are both of the type expected
> * by op's operator, then compare them using the latter.

Rewrote it as:

* We can compare leftarg_const and rightarg_const using op's operator
* only if both are of the type expected by it.

> 16. There are a few things to improve with the following comment:
>
> /*
> * Hash partitioning stores partition keys containing nulls in regular
> * partitions. That is, the code that determines the hash partition for
> * a given row admits nulls in the partition key when computing the key's
> * hash. So, here we treat any IS NULL clauses on partition key columns as
> * equality keys, along with any other non-null values coming from equality
> * operator clauses.
> */
>
> "admits" is not the correct word here, and "hash" should be "correct",
> but there are more mistakes, so might be easier just to rewrite to:
>
> /*
> * Since tuples with NULL values in the partition key columns are
> stored in regular partitions,
> * we'll treat any IS NULL clauses here as regular equality clauses.
> /*

Agreed that your version is better, so went with it.

> 17. The following example will cause get_partitions_for_keys_hash to misbehave:
>
> create table hashp (a int, b int) partition by hash (a, b);
> create table hashp1 partition of hashp for values with (modulus 4, remainder 0);
> create table hashp2 partition of hashp for values with (modulus 4, remainder 1);
> create table hashp3 partition of hashp for values with (modulus 4, remainder 3);
> create table hashp4 partition of hashp for values with (modulus 4, remainder 2);
> explain select * from hashp where a = 1 and a is null;
>
> The following code assumes that you'll never get a NULL test for a key
> that has an equality test, and ends up trying to prune partitions
> thinking we got compatible clauses for both partition keys.

Yeah, I think this example helps spot a problem. I thought we'd never get
to get_partitions_for_keys_hash() for the above query, because we
should've been able to prove much earlier that the particular clause
combination should be always false (a cannot be both non-null 1 and null).
Now, because the planner itself doesn't substitute a constant-false for
that, I taught classify_partition_bounding_keys() to do so. It would now
return constfalse=true if it turns out that clauses in the input list lead
to contradictory nullness condition for a given partition column.

> memset(keyisnull, false, sizeof(keyisnull));
> for (i = 0; i < partkey->partnatts; i++)
> {
> if (bms_is_member(i, keys->keyisnull))
> {
> keys->n_eqkeys++;
> keyisnull[i] = true;
> }
> }
>
> /*
> * Can only do pruning if we know all the keys and they're all equality
> * keys including the nulls that we just counted above.
> */
> if (keys->n_eqkeys == partkey->partnatts)
>
> The above code will need to be made smarter. It'll likely crash if you
> change "b" to a pass-by-ref type.

Hmm, not sure why. It seems to work:

create table hp (a int, b text) partition by hash (a, b);
create table hp1 partition of hp for values with (modulus 4, remainder 0);
create table hp2 partition of hp for values with (modulus 4, remainder 1);
create table hp3 partition of hp for values with (modulus 4, remainder 3);
create table hp4 partition of hp for values with (modulus 4, remainder 2);

insert into hp values (1, 'xxx');
INSERT 0 1

select tableoid::regclass, * from hp;
tableoid | a | b
----------+---+-----
hp1 | 1 | xxx
(1 row)

insert into hp (a) values (1);
INSERT 0 1

insert into hp (b) values ('xxx');
INSERT 0 1

select tableoid::regclass, * from hp where a is null;
tableoid | a | b
----------+---+-----
hp2 | | xxx
(1 row)

select tableoid::regclass, * from hp where b is null;
tableoid | a | b
----------+---+---
hp1 | 1 |
(1 row)

select tableoid::regclass, * from hp where a = 1 and b is null;
tableoid | a | b
----------+---+---
hp1 | 1 |
(1 row)

select tableoid::regclass, * from hp where a is null and b = 'xxx';
tableoid | a | b
----------+---+-----
hp2 | | xxx
(1 row)

> 18. The following code:
>
> int other_idx = -1;
>
> /*
> * Only a designated partition accepts nulls, which if there
> * exists one, return the same.
> */
> if (partition_bound_accepts_nulls(boundinfo) ||
> partition_bound_has_default(boundinfo))
> other_idx = partition_bound_accepts_nulls(boundinfo)
> ? boundinfo->null_index
> : boundinfo->default_index;
> if (other_idx >= 0)
> return bms_make_singleton(other_idx);
> else
> return NULL;
>
> should be simplified to:
>
> /*
> * NULLs may only exist in the NULL partition, or in the
> * default, if there's no NULL partition.
> */
> if (partition_bound_accepts_nulls(boundinfo))
> return bms_make_singleton(boundinfo->null_index);
> else if (partition_bound_has_default(boundinfo))
> return bms_make_singleton(boundinfo->default_index);
> return NULL;

Agreed, done that way.

> 19. "exists" -> "are"
>
> * If there are no datums to compare keys with, but there exist
> * partitions, it must be the default partition.
>
> also, instead of writing "it must be the default partition." it should
> be better to say "just return the default partition."

OK, done.

> 20. I don't think the return NULL should ever hit, is it worth putting
> a comment to say /* shouldn't happen */
>
> if (boundinfo->ndatums == 0)
> {
> if (partition_bound_has_default(boundinfo))
> return bms_make_singleton(boundinfo->default_index);
> else
> return NULL;
> }

I added a /* shouldn't happen */ comment next to return NULL.

> 21. Can the following comment does not explain the situation well:
>
> /*
> * boundinfo->ndatums - 1 is the last valid list partition datums
> * index.
> */
>
> There's really no possible non-default partition for this case, so
> perhaps we should just return the default, if one exists. We do go on
> to check the n_maxkeys needlessly for this case. At the very least the
> comment should be changed to:
>
> /*
> * minkeys values are greater than any non-default partition.
> * We'll check that for case below.
> */
>
> but I think it's worth just doing the default partition check there
> and returning it, or NULL. It should help reduce confusion.

Yep, done.

Attached v20. Thanks again.

Regards,
Amit