Constraint Exclusion (Partitioning)

Recently submitted to -patches. Copied here for further discussion.

On Mon, 2005-06-27 at 01:41 +0100, Simon Riggs wrote:
> I enclose a fully working implementation of Constraint Exclusion, a very
> basic form of Partitioning. Initial review is requested, to allow us all
> to assess what further work is required on this prior to Beta freeze.
> 
> Patch against current cvstip; passes make check and all special tests.
> 
> The main purpose of this feature is to reduce access time against large
> tables that have been split into partitions by using the PostgreSQL
> inheritance facility. It has been written in a very generic way allowing
> a whole range of applications.
> 
> If
>     a) a table is part of an inheritance set
>     b) the table has check constraints defined upon it
>     c) enable_constraint_exclusion = true
> 
> then the planner will attempt to use the definition of the Constraints
> to see if that relation could ever have rows in it that the query might
> see. *No* additional SQL DDL syntax is required to define this.
> 
> Only query clauses of the form ATTR OP CONSTANT will be considered, in a
> very similar way to the way partial indexes work already.
> 
> The code changes effect only the planner, building upon the partial
> index logic to allow refutation as well as implication.
> 
> There are clearly many questions to be answered by me and I'm happy to
> do so, so please fire away. My hope is to get a more polished form of
> this functionality into 8.1. Further developments on Partitioning are
> foreseen, though the feature submitted today is the main building block
> for any further work/optimization in this area and so additional
> features will be discussed at a later time.
> 
> A full test suite has been specially written for this feature. This is
> included here also, though no attempt has been made as yet to integrate
> that with the main regression test suite (as yet). Required files are
> included in a single tar file with this email. Extract these to the
> PostgreSQL installation directory and run using ./testprange.sh
> The test suite executes around 100 queries against 7 different database
> designs, comparing results with/without the new enable option. Full and
> pruned EXPLAINs are also derived during execution to allow easier
> analysis of the success of the exclusion process (view the
> testprange_t*e.out files).
> 
> There are no cases where any of the test queries returns a logically
> incorrect answer; hence fully working. There are a few cases where
> queries have not been optimised as far as possible; in those cases
> checks on my propositional logic are requested... This is extremely
> complex and my expectation is that testers/reviewers will find at least
> of couple of logic improvements. The most frequent queries are believed
> to work optimally.
> 

> Main questions:
> 1. How should we handle the case where *all* inherited relations are
> excluded? (This is not currently covered in the code).
> 2. Should this feature be available for all queries or just inherited
> relations?
> 3. And should we extend RelOptInfo to include constraint information?
> 4. Do we want to integrate the test suite also?
> 5. Presumably a section under Performance tips would be appropriate to
> document this feature? (As well as section in run-time parameters).
> 
> Additional thoughts:
> 1. We should be able to optimise the case where there is only a single
> non-excluded relation by removing the Append node.
>