Techniques are provided for a database server to identify a query that comprises an access check operator specifying a data access control policy, and if so, to re-write the query to produce an optimized query execution plan. A first technique rewrites a query comprising an access check operator based on the privileges associated with the database principal requesting the query. The rewritten query exposes the access predicates relevant to the requesting principal to subsequent database optimization processes. A second technique rewrites a query comprising an access check operator that specifies a data security policy that does not include a denied privilege. A third technique rewrites a query that comprises an access check operator specifying one or more database table columns that store row-specific access control lists. The rewritten queries are used to generate a query execution plan that provides for several query execution optimizations.