Re: [HACKERS] Runtime Partition Pruning

Hi David,

On 2018/04/06 12:27, David Rowley wrote:
> (sending my reply in parts for concurrency)
>
> On 6 April 2018 at 14:39, Amit Langote <Langote_Amit_f8(at)lab(dot)ntt(dot)co(dot)jp> wrote:
>> I think we can save some space here by not having the pointers stored
>> here. Instead of passing the pointer itself in the recursive calls to
>> find_subplans_for_extparams_recurse, et al, just pass the entire array and
>> an offset to use for the given recursive invocation.
>
> hmm, where would those offsets be stored? I don't want to have to do
> any linear searching to determine the offset, which is why I just
> stored the pointer to the flat array. It seems very efficient to me to
> do this. Remember that this pruning can occur per tuple in cases like
> parameterized nested loops.
>
> Are you worried about memory consumption? It's one pointer per
> partition. I imagine there's lots more allocated for DML on a
> partitioned table as it needs to store maps to map attribute numbers.
>
> Or are you thinking the saving of storing an array of 32-bit int
> values is better than the array of probably 64-bit pointers? So
> requires half the space?

Yeah, just copy it from the PartitionPruneInfo like you're doing for
subnodeindex:

memcpy(partrelprune->subpartindex, pinfo->subpartindex,
sizeof(int) * pinfo->nparts);

Instead I see ExecSetupPartitionPruning is now doing this:

/*
* Setup the PartitionedRelPruning's subpartprune so that we can
* quickly find sub-PartitionedRelPruning details for any
* sub-partitioned tables that this partitioned table contains.
* We need to be able to find these quickly during our recursive
* search to find all matching subnodes.
*/
for (j = 0; j < pinfo->nparts; j++)
{
int subpartidx = pinfo->subpartindex[j];

Assert(subpartidx < list_length(partitionpruneinfo));

if (subpartidx >= 0)
partrelprune->subpartprune[j] = &partrelprunes[subpartidx];
else
partrelprune->subpartprune[j] = NULL;
}

With that in place, pass the index/offset instead of the pointer to the
next recursive invocation of find_subplans_*, along with the array
containing all PartitionedRelPruning's.

So, where you have in each of find_subplans_*:

if (partrelprune->subnodeindex[i] >= 0)
*validsubplans = bms_add_member(*validsubplans,
partrelprune->subnodeindex[i]);
else if (partrelprune->subpartprune[i] != NULL)
find_subplans_for_allparams_recurse(partrelprune->subpartprune[i],
validsubplans);

I'm proposing that you do:

if (partrelprune->subnodeindex[i] >= 0)
*validsubplans = bms_add_member(*validsubplans,
partrelprune->subnodeindex[i]);
else if (partrelprune->subpartindex[i] >= 0)
find_subplans_for_allparams_recurse(all_partrelprunes,
partrelprune->subpartindex[i],
validsubplans);

And at the top of each of find_subplans_*:

ParitionedRelPruning *partrelprune = all_partrelprunes[offset];

where the signature is:

static void
find_subplans_for_allparams_recurse(
PartitionRelPruning **all_partrelprune,
int offset,
Bitmapset **validsubplans)

The all_partrelprune above refers to the flat array in PartitionPruning.
On the first call from ExecFindMatchingSubPlans, et al, you'd pass 0 for
offset to start pruning with the root parent's PartitionedRelPruning. All
the values contained in subnodeindex and subpartindex are indexes into the
global array (whole-tree that is) anyway and that fact would be more
apparent if we use this code structure, imho.

>> If you look at ExecFindPartition used for tuple routing, you may see that
>> there no recursion at all. Similarly find_subplans_for_extparams_recurse,
>> et al might be able to avoid recursion if similar tricks are used.
>
> That seems pretty different. That's looking for a single node in a
> tree, so just is following a single path from the root, it never has
> to go back up a level and look down any other paths.
>
> What we need for the find_subplans_for_extparams_recurse is to find
> all nodes in the entire tree which match the given clause. Doing this
> without recursion would require some sort of stack so we can go back
> up a level and search again down another branch. There are ways
> around this without using recursion, sure, but I don't think any of
> them will be quite as convenient and simple. The best I can think of
> is to palloc some stack manually and use some depth_level to track
> which element to use. An actual stack seems more simple. I can't
> quite think of a good way to know in advance how many elements we'd
> need to palloc.

Hmm, yeah. I just remembered that I had to give up suggesting this a
while back on this thread. So, okay, you don't need to do anything about
this.

>> Finally about having two different functions for different sets of Params:
>> can't we have just named find_subplans_for_params_recurse() and use the
>> appropriate one based on the value of some parameter? I can't help but
>> notice the duplication of code.
>
> I had decided not to make this one function previously as I didn't
> really want to add unnecessary branching in the code. After
> implementing it, it does not look as bad as I thought.

You could at the top of, say, find_subplans_for_params_recurse(..., bool
extparam):

Bitmapset *params = extparam
? partrelprune->extparams
: partrelprune->allparams;

ISTT, find_subplans_for_extparams_recurse and
find_subplans_for_allparams_recurse contain the exact same code except
these two lines in the two functions, respectively:

if (!bms_is_empty(partrelprune->extparams))
{
context->safeparams = partrelprune->extparams;

if (!bms_is_empty(partrelprune->allparams))
{
context->safeparams = partrelprune->allparams;

I didn't suggest the same for say ExecFindInitialMatchingSubPlans and
ExecFindMatchingSubPlans because they seem to be at least a bit different
in their missions. IIUC, the former has to do index value adjustment
(those in subnodeindex and subpartindex) after having discovered a new set
of matching partitions in the tree after pruning with external params at
Append/MergeAppend startup and those params won't change after that point.

Thanks,
Amit