Re: Declarative partitioning

On Fri, Aug 5, 2016 at 8:10 AM, Ashutosh Bapat
<ashutosh.bapat@enterprisedb.com> wrote:
> On Fri, Aug 5, 2016 at 5:21 PM, Robert Haas <robertmhaas@gmail.com> wrote:
>> On Fri, Aug 5, 2016 at 6:53 AM, Ashutosh Bapat
>> <ashutosh.bapat@enterprisedb.com> wrote:
>> > The lists for list partitioned tables are stored as they are specified
>> > by
>> > the user. While searching for a partition to route tuple to, we compare
>> > it
>> > with every list value of every partition. We might do something better
>> > similar to what's been done to range partitions. The list of values for
>> > a
>> > given partition can be stored in ascending/descending sorted order. Thus
>> > a
>> > binary search can be used to check whether given row's partition key
>> > column
>> > has same value as one in the list. The partitions can then be stored in
>> > the
>> > ascending/descending order of the least/greatest values of corresponding
>> > partitions.
>>
>> +1.  Here as with range partitions, we must be sure to know which
>> opclass should be used for the comparisons.
>>
>> > We might be able to eliminate search in a given partition if its
>> > lowest value is higher than the given value or its higher value is lower
>> > than the given value.
>>
>> I don't think I understand this part.
>
> Consider lists ('e', 'i', 'f'), ('h', 'd','m') and ('l', 'b', 'a') for a
> list partitioned tables. I am suggesting that we arrange them as
> ('a','b','l'), ('d', 'h', 'm') and ('e', 'f', 'i'). If the given row (either
> for comparison or for inserting) has value 'c', we will search for it in
> ('a','b','l') but will be eliminate other two partitions since the second's
> partition's lowest value is higher than 'c' and lowest values of rest of the
> partitions are higher than that of the second partition. Without this order
> among the partitions, we will have to compare lowest values of all the
> partitions.

I would think that for that case what we'd want to do is create two
lists.  One looks like this:

[ 'a', 'b', 'd', 'e', f', 'h', 'i', 'l', 'm' ]

The other looks like this:

[3, 3, 2, 1, 1, 2, 1, 1, 3, 2]

Given a particular value, bsearch the first list.  If the value is not
found, it's not in any partition.  If it is found, then go look up the
same array index in the second list; that's the containing partition.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company