Re: Improving RLS planning

On Thu, Nov 3, 2016 at 6:23 PM, Tom Lane <tgl@sss.pgh.pa.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