FoundationDB/fdb-record-layer

better match simple predicates to indexes using functions that are not invertable, and effectively invertible

Opened this issue · 0 comments

Example 1

We have an index on 15 - y, it can be used for a query predicate y < 10!
Something should turn minus(15, y) into f(y) and then that says

  1. invertible and
  2. order-preserving: reverse to yield f(y) > 5

This works because y < 10 can be matched to minus(15, y) if we then have a ComparisonCompensation that is applied to the right side obtaining minus(15, 10) and then 5.

This currently does not work because the underlying arithmetic function takes more than one argument.

Example 2

String prefix index, index is on something like prefix(a, 10), data indexes two records: 'United States of America',
'United States of Petoria'. Query is a = 'United States of America'.

In order to not return both entries the predicate needs to be reapplied as a residual. Mathematically, the function prefix(...) is not invertable, thus we would need to reapply the predicate.