Re: Improving RLS planning

On 8 November 2016 at 16:46, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> On Thu, Nov 3, 2016 at 6:23 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>>> I think that ordering might be sub-optimal if you had a mix of
>>> leakproof quals and security quals and the cost of some security quals
>>> were significantly higher than the cost of some other quals. Perhaps
>>> all leakproof quals should be assigned security_level 0, to allow them
>>> to be checked earlier if they have a lower cost (whether or not they
>>> are security quals), and only leaky quals would have a security_level
>>> greater than zero. Rule 1 would then not need to check whether the
>>> qual was leakproof, and you probably wouldn't need the separate
>>> "leakproof" bool field on RestrictInfo.
>>
>> Hm, but it would also force leakproof quals to be evaluated in front
>> of potentially-cheaper leaky quals, whether or not that's semantically
>> necessary.
>>

True. That's also what currently happens with RLS and SB views because
leakproof quals are pushed down into subqueries without considering
their cost. It would be nice to do better than that.

>> I experimented with ignoring security_level altogether for leakproof
>> quals, but I couldn't make it work properly, because that didn't lead to
>> a comparison rule that satisfies transitivity. For instance, consider
>> three quals:
>> A: cost 1, security_level 1, leaky
>> B: cost 2, security_level 1, leakproof
>> C: cost 3, security_level 0, leakproof
>> A should sort before B, since same security_level and lower cost;
>> B should sort before C, since lower cost and leakproof;
>> but A must sort after C, since higher security_level and leaky.
>
> Yeah, this is pretty thorny. IIUC, all leaky quals of a given
> security level must be evaluated before any quals of the next higher
> security level, or we have a security problem. Beyond that, we'd
> *prefer* to evaluate cheaper quals first (though perhaps we ought to
> be also thinking about how selective they are) but that's "just" a
> matter of how good the query plan is. So in this example, security
> dictates that C must precede A, but that's it. We can pick between
> C-A-B, C-B-A, and B-C-A based on cost. C-B-A is clearly inferior to
> either of the other two, but it's less obvious whether C-A-B or B-C-A
> is better. If you expect each predicate to have a selectivity of 50%,
> then C-A-B costs 3+(0.5*1)+(0.25*2) = 4 while B-C-A costs
> 2+(0.5*3)+(0.25*1) = 3.75, so B-C-A is better. But now make the cost
> of B and C 18 and 20 while keeping the cost of A at 1. Now C-A-B
> costs 20+(0.5*1)+(0.25*18) = 25 while B-C-A costs 18+(0.5*20)+(0.25*1)
> = 28.25, so now C-A-B is better.
>
> So I think any attempt to come up with a transitive comparison rule is
> doomed. We could do something like: sort by cost then security level;
> afterwards, allow leakproof qual to migrate forward as many position
> as is possible without passing a qual that is either higher-cost or
> (non-leakproof and lower security level). So in the above example we
> would start by sorting the like C-A-B and then check whether B can
> move forward; it can't, so we're done. If all operators were
> leakproof, this would essentially turn into an insertion-sort that
> orders them strictly by cost, whereas if they're all leaky, it orders
> strictly by security level and then by cost. With a mix of leaky and
> non-leaky operators you get something in the middle.
>
> I'm not sure that this is practically better than the hack you
> proposed, but I wanted to take the time to comment on the theory here,
> as I see it anyway.
>

Yes, I think you're right. It doesn't look possible to invent a
transitive comparison rule.

I thought perhaps the rule could be to only "push down" a leakproof
qual (change it to a lower security_level) if there are more expensive
quals at the lower level, but as you point out, this doesn't guarantee
cheaper execution.

Regards,
Dean