The general solution is overly complicated. Everything is simpler if you decompose the calculation into its two parts: the inverse append and the join with the fanout predicate. First project fanout to get the set of prefixes:

predicate fanOut2(string prefix, int res) { exists(string s | prefix = s + "." and fanOut(s, res)) }
predicate prefix(string prefix) { fanOut(prefix, _) }

Then do the inverse append:

predicate invAp(string s, string prefix, string suffix) {
  strings(s) and
  prefix(prefix) and
  s = prefix + suffix
}

Then join:

predicate invApJoined(string s, int i, string suffix) {
  exists(string prefix | invAp(s, prefix, suffix) and fanOut2(prefix, i))
}

This should have the same performance characteristic as the regex-based version, since the regex version also effectively performs the projected CP of strings and prefix.

Everything is simpler if you decompose the calculation into its two parts: the inverse append and the join with the fanout predicate.

Right, only problem is that this doesn't work unless we bind s up-front (in my example this was easy). In my actual use-cases the strings are only bound as part of a big recursion, and constraining them via an additional input predicate would lead to two recursive calls instead of one (and be somewhat clunky).

Right, only problem is that this doesn't work unless we bind s up-front (in my example this was easy). In my actual use-cases the strings are only bound as part of a big recursion, and constraining them via an additional input predicate would lead to two recursive calls instead of one (and be somewhat clunky).

Granted, I haven't looked at your actual use-case, but I don't see how that makes a difference. Constructing the regex is essentially equivalent to the projection to the prefix column, so if your complex solution works, then the simple ought to as well.

Another way to phrase the simple solution is as follows: You have a big CP because the join-orderer needs to pick fanout/2 at some point, but if you replace fanout(s, i) with the equivalent fanout(s, _) and fanout(s, i) then a much better join-order becomes possible, since the use of s can be sandwich'ed between picking fanout(s, _) and fanout(s, i). In this case the use happens to be an inverse append, but that's actually irrelevant.

Turns out that the effect of the inverse-append changes were in fact not helping at all, and that the actual performance improvements were the other changes, so I have reverted.