On Tue, 2005-05-10 at 16:44 +0300, Hannu Krosing wrote:
> On T, 2005-05-10 at 16:31 +0300, Hannu Krosing wrote:
> > On E, 2005-05-09 at 23:30 +0100, Simon Riggs wrote:
>
> > There are 2 possibly expensive steps:
> >
> > 1. the conversion to "AND'ed list of simple clauses" (unknown
> > complexity)
> >
> > 2. matching each of "simple" clauses in the and list with all others
> > (should be N+(N-1)+(N-2)+..+(1) ~= 2N) complexity)
>
> actually not 2N but (N * ((N-1)/2) , thus 3 clauses need 2+1=3 checks
> and 11 clasues need (10+9+..+1) = 55 checks.
Well, it doesn't need to be quite that bad.
We can just check each of the table constraints against each of the
Restrict clauses.
We don't need to test the constraints against themselves, since the
table would be empty if any ever turned out to be mutually exclusive, so
we wouldn't be saving time doing it. Later, we can enforce constraints
to be mutually exclusive at the time they are created.
We don't need to test the Restrict clauses against themselves either,
since we can assume that the user is smart enough to submit SQL that
returns some rows. Eval will pick up the stupid case if there is one.
Anyway, the existing code has an even simpler heuristic for avoiding the
full check...
Best Regards, Simon Riggs
