Re: [HACKERS] advanced partition matching algorithm for partition-wise join

On Fri, Jul 20, 2018 at 3:13 AM, Dmitry Dolgov <9erthalion6(at)gmail(dot)com> wrote:
>
> It's of course wrong, it's going to be O(max(m, n)) as you said, but
> the point is still valid - if we have partitions A1, A2 from one side
> and B1, ..., BN on another side, we can skip necessary the
> partitions from B that are between e.g. A1 and A2 faster with
> binary search.

That's possible only when there is no default partition and the join
is an inner join. For an outer join, we need to include all the
partitions on the outer side, so we can't just skip over some
partitions. In case of a default partition, it can take place of a
missing partition, so we can't skip partitions using binary search.
The code right now works for all the cases and is O(n). I agree that
it can be optimized for certain cases, but
1. those cases are rare enough that we can ignore those right now. How
many times we would encounter the case you have quoted, for example?
Usually the ranges will be continuous only differing in the first or
last partition e.g time-series data.
2. The code is enough complex right now and it's also a lot. Making it
complicated further is not the worth the rare use cases. If we get
complaints from the field, we can certainly improve it in future. But
I would wait for those complaints before improving it further.

--
Best Wishes,
Ashutosh Bapat
EnterpriseDB Corporation
The Postgres Database Company