Implement loop-invariant code motion optimization

[tsandall]

Today OPA does not implement any loop-invariant optimizations. One obvious improvement would be to avoid the equivalent of independent but nested for-loops. For example:

allow {
  some i, j
  input.groups[i] = "admin"
  input.actions[j] = "delete_users"
}

In this case, the two expressions in the allow rule are independent, however, the runtime complexity is the product of groups and actions. Users can turn the product into a sum by splitting these statements into helper rules like this:

allow {
  user_has_admin
  action_is_delete_users
}

user_has_admin {
  some i
  input.groups[i] = "admin"
}

action_is_delete_users {
  some j
  input.actions[j] = "delete_users"
}

The query optimization could be implemented by analyzing statements in the rule body to identify expressions that iterate. The expressions could be split into groups and those groups could be rewritten into helper rules with different names.

[stale[bot]]

This issue has been automatically marked as inactive because it has not had any activity in the last 30 days.