Re: path toward faster partition pruning

On 3 November 2017 at 17:32, David Rowley <david(dot)rowley(at)2ndquadrant(dot)com> wrote:
> 2. This code is way more complex than it needs to be.
>
> if (num_parts > 0)
> {
> int j;
>
> all_indexes = (int *) palloc(num_parts * sizeof(int));
> j = 0;
> if (min_part_idx >= 0 && max_part_idx >= 0)
> {
> for (i = min_part_idx; i <= max_part_idx; i++)
> all_indexes[j++] = i;
> }
> if (!bms_is_empty(other_parts))
> while ((i = bms_first_member(other_parts)) >= 0)
> all_indexes[j++] = i;
> if (j > 1)
> qsort((void *) all_indexes, j, sizeof(int), intcmp);
> }
>
> It looks like the min/max partition stuff is just complicating things
> here. If you need to build this array of all_indexes[] anyway, I don't
> quite understand the point of the min/max. It seems like min/max would
> probably work a bit nicer if you didn't need the other_parts
> BitmapSet, so I recommend just getting rid of min/max completely and
> just have a BitmapSet with bit set for each partition's index you
> need, you'd not need to go to the trouble of performing a qsort on an
> array and you could get rid of quite a chunk of code too.
>
> The entire function would then not be much more complex than:
>
> partindexes = get_partitions_from_clauses(parent, partclauses);
>
> while ((i = bms_first_member(partindexes)) >= 0)
> {
> AppendRelInfo *appinfo = rel->part_appinfos[i];
> result = lappend(result, appinfo);
> }
>
> Then you can also get rid of your intcmp() function too.

I've read a bit more of the patch and I think even more now that the
min/max stuff should be removed.

I understand that you'll be bsearching for a lower and upper bound for
cases like:

SELECT * FROM pt WHERE key BETWEEN 10 and 20;

but it looks like the min and max range stuff is thrown away if the
query is written as:

SELECT * FROM pt WHERE key BETWEEN 10 and 20 OR key BETWEEN 30 AND 40;

from reading the code, it seems like partset_union() would be called
in this case and if the min/max of each were consecutive then the
min/max range would get merged, but there's really a lot of code to
support this. I think it would be much better to invent
bms_add_range() and just use a Bitmapset to store the partition
indexes to scan. You could simply use bms_union for OR cases and
bms_intersect() or AND cases. It seems this would allow removal of
this complex code. It looks like this would allow you to remove all
the partset_range_* macros too.

I've attached a patch which implements bms_add_range() which will save
you from having to write the tight loops to call bms_add_member() such
as the ones in partset_union(). Those would not be so great if there
was a huge number of partitions as the Bitmapset->words[] array could
be expanded many more times than required. bms_add_range() will handle
that much more efficiently with a maximum of 1 repalloc() for the
whole operation. It would also likely faster since it's working at the
bitmapword level rather than bit level.

--
David Rowley http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services