Improve RLS planning by marking individual quals with security levels.

In an RLS query, we must ensure that security filter quals are evaluated
before ordinary query quals, in case the latter contain "leaky" functions
that could expose the contents of sensitive rows.  The original
implementation of RLS planning ensured this by pushing the scan of a
secured table into a sub-query that it marked as a security-barrier view.
Unfortunately this results in very inefficient plans in many cases, because
the sub-query cannot be flattened and gets planned independently of the
rest of the query.

To fix, drop the use of sub-queries to enforce RLS qual order, and instead
mark each qual (RestrictInfo) with a security_level field establishing its
priority for evaluation.  Quals must be evaluated in security_level order,
except that "leakproof" quals can be allowed to go ahead of quals of lower
security_level, if it's helpful to do so.  This has to be enforced within
the ordering of any one list of quals to be evaluated at a table scan node,
and we also have to ensure that quals are not chosen for early evaluation
(i.e., use as an index qual or TID scan qual) if they're not allowed to go
ahead of other quals at the scan node.

This is sufficient to fix the problem for RLS quals, since we only support
RLS policies on simple tables and thus RLS quals will always exist at the
table scan level only.  Eventually these qual ordering rules should be
enforced for join quals as well, which would permit improving planning for
explicit security-barrier views; but that's a task for another patch.

Note that FDWs would need to be aware of these rules --- and not, for
example, send an insecure qual for remote execution --- but since we do
not yet allow RLS policies on foreign tables, the case doesn't arise.
This will need to be addressed before we can allow such policies.

Patch by me, reviewed by Stephen Frost and Dean Rasheed.

Discussion: https://postgr.es/m/8185.1477432701@sss.pgh.pa.us

1 files changed, 55 insertions, 6 deletions

diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 6703dc384d6..a329dd1e10d 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -16,6 +16,8 @@
  */
 #include "postgres.h"
 
+#include <limits.h>
+
 #include "access/stratnum.h"
 #include "catalog/pg_type.h"
 #include "nodes/makefuncs.h"
@@ -78,9 +80,16 @@ static bool reconsider_full_join_clause(PlannerInfo *root,
  * care to mark an EquivalenceClass if it came from any such clauses.  Also,
  * we have to check that both sides are either pseudo-constants or strict
  * functions of Vars, else they might not both go to NULL above the outer
- * join.  (This is the reason why we need a failure return.  It's more
+ * join.  (This is the main reason why we need a failure return.  It's more
  * convenient to check this case here than at the call sites...)
  *
+ * We also reject proposed equivalence clauses if they contain leaky functions
+ * and have security_level above zero.  The EC evaluation rules require us to
+ * apply certain tests at certain joining levels, and we can't tolerate
+ * delaying any test on security_level grounds.  By rejecting candidate clauses
+ * that might require security delays, we ensure it's safe to apply an EC
+ * clause as soon as it's supposed to be applied.
+ *
  * On success return, we have also initialized the clause's left_ec/right_ec
  * fields to point to the EquivalenceClass representing it.  This saves lookup
  * effort later.
@@ -120,6 +129,10 @@ process_equivalence(PlannerInfo *root, RestrictInfo *restrictinfo,
 	Assert(restrictinfo->left_ec == NULL);
 	Assert(restrictinfo->right_ec == NULL);
 
+	/* Reject if it is potentially postponable by security considerations */
+	if (restrictinfo->security_level > 0 && !restrictinfo->leakproof)
+		return false;
+
 	/* Extract info from given clause */
 	Assert(is_opclause(clause));
 	opno = ((OpExpr *) clause)->opno;
@@ -275,6 +288,10 @@ process_equivalence(PlannerInfo *root, RestrictInfo *restrictinfo,
 		{
 			ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
 			ec1->ec_below_outer_join |= below_outer_join;
+			ec1->ec_min_security = Min(ec1->ec_min_security,
+									   restrictinfo->security_level);
+			ec1->ec_max_security = Max(ec1->ec_max_security,
+									   restrictinfo->security_level);
 			/* mark the RI as associated with this eclass */
 			restrictinfo->left_ec = ec1;
 			restrictinfo->right_ec = ec1;
@@ -306,6 +323,10 @@ process_equivalence(PlannerInfo *root, RestrictInfo *restrictinfo,
 		ec1->ec_has_const |= ec2->ec_has_const;
 		/* can't need to set has_volatile */
 		ec1->ec_below_outer_join |= ec2->ec_below_outer_join;
+		ec1->ec_min_security = Min(ec1->ec_min_security,
+								   ec2->ec_min_security);
+		ec1->ec_max_security = Max(ec1->ec_max_security,
+								   ec2->ec_max_security);
 		ec2->ec_merged = ec1;
 		root->eq_classes = list_delete_ptr(root->eq_classes, ec2);
 		/* just to avoid debugging confusion w/ dangling pointers: */
@@ -315,6 +336,10 @@ process_equivalence(PlannerInfo *root, RestrictInfo *restrictinfo,
 		ec2->ec_relids = NULL;
 		ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
 		ec1->ec_below_outer_join |= below_outer_join;
+		ec1->ec_min_security = Min(ec1->ec_min_security,
+								   restrictinfo->security_level);
+		ec1->ec_max_security = Max(ec1->ec_max_security,
+								   restrictinfo->security_level);
 		/* mark the RI as associated with this eclass */
 		restrictinfo->left_ec = ec1;
 		restrictinfo->right_ec = ec1;
@@ -329,6 +354,10 @@ process_equivalence(PlannerInfo *root, RestrictInfo *restrictinfo,
 							false, item2_type);
 		ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
 		ec1->ec_below_outer_join |= below_outer_join;
+		ec1->ec_min_security = Min(ec1->ec_min_security,
+								   restrictinfo->security_level);
+		ec1->ec_max_security = Max(ec1->ec_max_security,
+								   restrictinfo->security_level);
 		/* mark the RI as associated with this eclass */
 		restrictinfo->left_ec = ec1;
 		restrictinfo->right_ec = ec1;
@@ -343,6 +372,10 @@ process_equivalence(PlannerInfo *root, RestrictInfo *restrictinfo,
 							false, item1_type);
 		ec2->ec_sources = lappend(ec2->ec_sources, restrictinfo);
 		ec2->ec_below_outer_join |= below_outer_join;
+		ec2->ec_min_security = Min(ec2->ec_min_security,
+								   restrictinfo->security_level);
+		ec2->ec_max_security = Max(ec2->ec_max_security,
+								   restrictinfo->security_level);
 		/* mark the RI as associated with this eclass */
 		restrictinfo->left_ec = ec2;
 		restrictinfo->right_ec = ec2;
@@ -366,6 +399,8 @@ process_equivalence(PlannerInfo *root, RestrictInfo *restrictinfo,
 		ec->ec_below_outer_join = below_outer_join;
 		ec->ec_broken = false;
 		ec->ec_sortref = 0;
+		ec->ec_min_security = restrictinfo->security_level;
+		ec->ec_max_security = restrictinfo->security_level;
 		ec->ec_merged = NULL;
 		em1 = add_eq_member(ec, item1, item1_relids, item1_nullable_relids,
 							false, item1_type);
@@ -639,6 +674,8 @@ get_eclass_for_sort_expr(PlannerInfo *root,
 	newec->ec_below_outer_join = false;
 	newec->ec_broken = false;
 	newec->ec_sortref = sortref;
+	newec->ec_min_security = UINT_MAX;
+	newec->ec_max_security = 0;
 	newec->ec_merged = NULL;
 
 	if (newec->ec_has_volatile && sortref == 0) /* should not happen */
@@ -834,6 +871,7 @@ generate_base_implied_equalities_const(PlannerInfo *root,
 								 bms_copy(ec->ec_relids),
 								 bms_union(cur_em->em_nullable_relids,
 										   const_em->em_nullable_relids),
+								 ec->ec_min_security,
 								 ec->ec_below_outer_join,
 								 cur_em->em_is_const);
 	}
@@ -890,6 +928,7 @@ generate_base_implied_equalities_no_const(PlannerInfo *root,
 									 bms_copy(ec->ec_relids),
 									 bms_union(prev_em->em_nullable_relids,
 											   cur_em->em_nullable_relids),
+									 ec->ec_min_security,
 									 ec->ec_below_outer_join,
 									 false);
 		}
@@ -1313,7 +1352,13 @@ select_equality_operator(EquivalenceClass *ec, Oid lefttype, Oid righttype)
 
 		opno = get_opfamily_member(opfamily, lefttype, righttype,
 								   BTEqualStrategyNumber);
-		if (OidIsValid(opno))
+		if (!OidIsValid(opno))
+			continue;
+		/* If no barrier quals in query, don't worry about leaky operators */
+		if (ec->ec_max_security == 0)
+			return opno;
+		/* Otherwise, insist that selected operators be leakproof */
+		if (get_func_leakproof(get_opcode(opno)))
 			return opno;
 	}
 	return InvalidOid;
@@ -1380,7 +1425,8 @@ create_join_clause(PlannerInfo *root,
 										bms_union(leftem->em_relids,
 												  rightem->em_relids),
 										bms_union(leftem->em_nullable_relids,
-											   rightem->em_nullable_relids));
+												rightem->em_nullable_relids),
+										ec->ec_min_security);
 
 	/* Mark the clause as redundant, or not */
 	rinfo->parent_ec = parent_ec;
@@ -1691,7 +1737,8 @@ reconsider_outer_join_clause(PlannerInfo *root, RestrictInfo *rinfo,
 												   innervar,
 												   cur_em->em_expr,
 												   bms_copy(inner_relids),
-											bms_copy(inner_nullable_relids));
+											 bms_copy(inner_nullable_relids),
+												   cur_ec->ec_min_security);
 			if (process_equivalence(root, newrinfo, true))
 				match = true;
 		}
@@ -1833,7 +1880,8 @@ reconsider_full_join_clause(PlannerInfo *root, RestrictInfo *rinfo)
 													   leftvar,
 													   cur_em->em_expr,
 													   bms_copy(left_relids),
-											 bms_copy(left_nullable_relids));
+											  bms_copy(left_nullable_relids),
+													cur_ec->ec_min_security);
 				if (process_equivalence(root, newrinfo, true))
 					matchleft = true;
 			}
@@ -1847,7 +1895,8 @@ reconsider_full_join_clause(PlannerInfo *root, RestrictInfo *rinfo)
 													   rightvar,
 													   cur_em->em_expr,
 													   bms_copy(right_relids),
-											bms_copy(right_nullable_relids));
+											 bms_copy(right_nullable_relids),
+													cur_ec->ec_min_security);
 				if (process_equivalence(root, newrinfo, true))
 					matchright = true;
 			}