[Performance] Trie index cache when one input is data reference

[prasanthj]

Short description

any_prefix_match and any_suffix_match builtin constructs a trie index internally every time the builtin is invoked. If the input is a reference to data there is possibility of caching the trie index until the data changes.

• OPA version: 0.57.0
• OPA Playground: https://play.openpolicyagent.org/p/tm52e9LgUM

When the data is around 80k paths, the p99 latency reported by opa bench is ~200ms of which about ~150ms is added by #5946 as per the slack discussion below.

Expected behavior

Reuse trie index when data does not change for the any_prefix_match and any_suffix_match builtin

Additional context

https://openpolicyagent.slack.com/archives/CBR63TK2A/p1698428765461689 thread has additional context

[ashutosh-narkar]

FYI there is existing work to resolve #5946 in #6040

[stale]

This issue has been automatically marked as inactive because it has not had any activity in the last 30 days. Although currently inactive, the issue could still be considered and actively worked on in the future. More details about the use-case this issue attempts to address, the value provided by completing it or possible solutions to resolve it would help to prioritize the issue.

[anderseknert]

This would be fairly easy to do now using the new inter-query value cached passed to the built-in functions. Similarly to #7081 which was merged before today. @prasanthj if you still have a need for this, or if this would help anyone else, let us know!

[prasanthj]

@anderseknert This will definitely be useful. For now, I am using a workaround of maintaining the trie outside of opa evaluator because of this issue.

[stale]

This issue has been automatically marked as inactive because it has not had any activity in the last 30 days. Although currently inactive, the issue could still be considered and actively worked on in the future. More details about the use-case this issue attempts to address, the value provided by completing it or possible solutions to resolve it would help to prioritize the issue.