Re: Making clausesel.c Smarter

On Tue, Apr 4, 2017 at 8:12 AM, David Rowley
<david(dot)rowley(at)2ndquadrant(dot)com> wrote:
> Result Comparison
>
> Master median tps Patch median tps comparison
> Test 1 6993.7 6714.3 104.16%
> Test 2 7053.1 6921.6 101.90%
> Test 3 5137.2 4954.2 103.69%
> Test 4 27.1 19.4 139.72%
> Test 5 54.1 51.4 105.28%
> Test 6 9328.1 9478.2 98.42%
>
> Results Analyzed:
>
> Test 1 has caused planning to slow down 4.16%. There's quite a bit of
> noise from the results, but I think this indicates there is some
> overhead to having to add items to the cslist and searching the cslist
> when new quals are seen.
>
> Test 2 has a lesser slowdown than test 1, as this test will excercise
> the existing rqlist caching in master too. Patched does a little more
> work adding the equality condition to the list too.
>
> Test 3 similar to test 1
>
> Test 4 adds quite an overhead and causes 0.5 million comparisons to
> find the expressions in the cslist.
>
> Test 5 shows less overhead than test 4 since the Master code has to
> also do the expression caching and searching.
>
> Test 6 is a control test

That's consistent with the operation being quadratic.

While I was about to point it out, the old code was quadratic too, so
it sucks in both versions. This version only adds other opexprs to the
list and makes the quadratic cost easier to run into, but it's nothing
new.

I don't think there's an easy fix for that. You'd have to build a hash
table of expression nodes or something of the sort to avoid the
quadratic cost. If you can do that, by all means, but that's a much
bigger patch.