Re: Auto Partitioning - Mailing list pgsql-hackers

Hi,

NikhilS wrote:
>> The following things are TODOs:
>>
>> iv) Auto generate rules using the checks mentioned for the partitions, to
>> handle INSERTs/DELETEs/UPDATEs to navigate them to the appropriate child.
>> Note that checks specified directly on the master table will get 
>> inherited
>> automatically.
> 
> Am planning to do the above by using the check constraint specified for 
> each
> partition. This constraint's raw_expr field ends up becoming the 
> whereClause
> for the rule specific to that partition.

I appreciate you efforts, but I'm not sure if this has been discussed 
enough. There seem to be two ideas floating around:
 - you are heading for automating the current kludge, which involves   creating partitions and constraints by hand.
AFAICT,you want to   support list and range partitioning.
 
 - Simon Riggs has proposed partitioning functions, which could easily   handle any type of partitioning (hash, list,
rangeand any mix of   those).
 

Both proposals do not have much to do with the missing multi-table 
indices. It's clear to me that we have to implement those someday, anyway.

AFAICT, the first proposal does not ease the task of writing correct 
constraints, so that we are sure that each row ends up in only exactly 
one partition. The second would.

But the second proposal makes it hard for the planner to choose the 
right partitions, i.e. if you request a range of ids, the planner would 
have to query the partitioning function for every possible value. The 
first variant could use constraint exclusion for that.

None of the two has gone as far as thinking about switching from one 
partitioning rule set to another. That gets especially hard if you 
consider database restarts during re-partitioning.


Here are some thought I have come up with recently. This is all about 
how to partition and not about how to implement multi-table indices. 
Sorry if this got somewhat longish. And no, this is certainly not for 
8.3 ;-)

I don't like partitioning rules, which leave open questions, i.e. when 
there are values for which the system does not have an answer (and would 
have to fall back to a default) or even worse, where it could give 
multiple correct answers. Given that premise, I see only two basic 
partitioning types:
 - splits: those can be used for what's commonly known as list and range   partitioning. If you want customers A-M to
endup on partition 1 and   customers N-Z on partition 2 you would split between M and N. (That   way, the system would
stillknow what to do with a customer name   beginning with an @ sign, for example. The only requirement for a   split
isthat the underlying data type supports comparison   operators.)
 
 - modulo: I think this is commonly known as hash partitioning. It   requires an integer input, possibly by hashing,
andcalculates the   remainder of a division by n. That should give an equal distribution   among n partitions.
 

Besides the expression to work on, a split always needs one argument, 
the split point, and divides into two buckets. A modulo splits into two 
or more buckets and needs the divisor as an argument.

Of course, these two types can be combined. I like to think of these 
combinations as trees. Let me give you a simple examlpe:
                         table customers                               |                               |
      split @ name >= 'N'                        /               \                       /                 \
        part1              part2
 



A combination of the two would look like:
                         table invoices                               |                               |
     split @ id >= 50000                        /               \                       /                 \
hash(id) modulo 3         part4                 /    |     \                /     |      \             part1   part2
part3


Knowledge of these trees would allow the planner to choose more wisely, 
i.e. given a comparative condition (WHERE id > 100000) it could check 
the splits in the partitioning tree and only scan the partitions 
necessary. Likewise with an equality condition (WHERE id = 1234).

As it's a better definition of the partitioning rules, the planner would 
not have to check constraints of all partitions, as the current 
constraint exclusion feature does. It might even be likely that querying 
this partitioning tree and then scanning the single-table index will be 
faster than an index scan on a multi-table index. At least, I cannot see 
why it should be any slower.

Such partitioning rule sets would allow us to re-partition by adding a 
split node on top of the tree. The split point would have to increment 
together with the progress of moving around the rows among the 
partitions, so that the database would always be in a consistent state 
regarding partitioning.

Additionally, it's easy to figure out, when no or only few moving around 
is necessary, i.e. when adding a split @ id >= 1000 to a table which 
only has ids < 1000.



I believe that this is a well defined partitioning rule set, which has 
more information for the planner than a partitioning function could ever 
have. And it is less of a foot-gun than hand written constraints, 
because it does not allow the user to specify illegal partitioning rules 
(i.e. it's always guaranteed, that every row ends up in only one partition).

Of course, it's far more work than either of the above proposals, but 
maybe we can go there step by step? Maybe, NikhilS proposal is more like 
a step towards such a beast?

Feedback of any form is very welcome.

Regards

Markus