Re: Improving RLS planning

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.
>
> 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.

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