Re: Binary search in ScalarArrayOpExpr for OR'd constant arrays

On 4/11/21 12:03 AM, David Rowley wrote:
> On Sat, 10 Apr 2021 at 10:32, Tomas Vondra
> <tomas(dot)vondra(at)enterprisedb(dot)com> wrote:
>> But I think the puzzle is not so much about v5 vs v6, but more about v5
>> vs. master. I still don't understand how v5 managed to be faster than
>> master, but maybe I'm missing something.
>
> Well, v5 wrapped ScalarArrayOpExpr inside HashedScalarArrayOpExpr, but
> didn't add cases for HashedScalarArrayOpExpr in all locations where it
> should have. For example, fix_expr_common() has a case for
> ScalarArrayOpExpr, but if we gave it a HashedScalarArrayOpExpr it
> would have very little work to do.
>
> I've not gone and proved that's the exact reason why the planner
> became faster, but I really don't see any other reason.
>
>> Maybe the right solution is to rely on the estimates, but then also
>> enable the hashing if we significantly cross the threshold during
>> execution. So for example we might get estimate 10 rows, and calculate
>> that the hashing would start winning at 100 rows, so we start without
>> hashing. But then at execution if we get 200 rows, we build the hash
>> table and start using it.
>
> To do that, we'd need to store the number of evaluations of the
> function somewhere. I'm not really sure that would be a good idea as I
> imagine we'd need to store that in ExprEvalStep. I imagine if that
> was a good idea then we'd have done the same for JIT.
>

Sure, we'd need to track the number of lookups, but I'd imagine that's
fairly cheap and we can stop once we switch to hash mode.

I'm not sure "JIT does not do that" is really a proof it's a bad idea.
My guess is it wasn't considered back then, and the current heuristics
is the simplest possible. So maybe it's the other way and we should
consider to do the same thing for JIT?

FWIW if we look at what JIT does, it'd argue it supports the approach to
trust the estimates. Because if we under-estimate stuff, the cost won't
exceed the "jit_above_cost" threshold, and we won't use JIT.

>
>> On 4/9/21 1:21 AM, David Rowley wrote:
>>> time values are in seconds:
>>>
>>> pg-master 28.07
>>> prepared 11.28
>>> simple 16.79
>>>
>>> pg-v6 15.86
>>> prepared 5.23
>>> simple 10.63
>>>
>>> So, the overall result when applying the total time is 177%.
>>>
>>
>> Not sure how you got those numbers, or how it explains the results.
>
> I got it by doing "1 / tps * 1000" to get the time it would take to
> execute 1000 transactions of each of your tests. I then grouped by
> patch, mode and took the sum of the calculated number. My point was
> that overall the patch is significantly faster. I was trying to
> highlight that the 0 and 1 row test take up very little time and the
> overhead of building the hash table is only showing up because the
> query executes so quickly.
>

Ah, I see. TBH I don't think combining the results gives us a very
meaningful value - those cases were quite arbitrary, but summing them
together like this assumes the workload has about 25% of each. But if
your workload is exclusively 0/1/5 rows it's going to be hit.

> FWIW, I think executing a large IN clause on a table that has 0 rows
> is likely not that interesting a case to optimise for. That's not the
> same as a query that just returns 0 rows due to filtering out hundreds
> or thousands of rows during execution. The overhead of building the
> hash table is not going to show up very easily in that sort of case.
>

Yeah, it's probably true that queries with long IN lists are probably
dealing with many input rows. And you're right we don't really care
about how many rows are ultimately produced by the query (or even the
step with the IN list) - if we spent a lot of time to filter the rows
before applying the IN list, the time to initialize the hash table is
probably just noise.

I wonder what's the relationship between the length of the IN list and
the minimum number of rows needed for the hash to start winning.

>> I understand why the prepared mode got slower. I don't understand how
>> the simple mode got faster.
>
> I very much imagine v5 was faster at planning due to the unfinished
> nature of the patch. I'd not added support for HashedScalarArrayOpExpr
> in all the places I should have. That would result in the planner
> skipping lots of work that it needs to do. The way I got it to work
> was to add it, then just add enough cases in the planner to handle
> HashedScalarArrayOpExpr so I didn't get any errors. I stopped after
> that just to show the idea. Lack of errors does not mean it was
> correct. At least setrefs.c was not properly handling
> HashedScalarArrayOpExpr.
>
> I really think it would be best if we just ignore the performance of
> v5. Looking at the performance of a patch that was incorrectly
> skipping a bunch of required work does not seem that fair.
>

Aha! I was assuming v5 was correct, but if that assumption is incorrect
then the whole "v5 speedup" is just an illusion, aAnd you're right we
should simply ignore that. Thanks for the explanation!

regards

--
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company