Re: Lazy JIT IR code generation to increase JIT speed with partitions

On 30-12-2020 02:57, Andres Freund wrote:
> Hi,
> 
> Great to see work in this area!
> 
> On 2020-12-28 09:44:26 +0100, Luc Vlaming wrote:
>> I would like to propose a small patch to the JIT machinery which makes the
>> IR code generation lazy. The reason for postponing the generation of the IR
>> code is that with partitions we get an explosion in the number of JIT
>> functions generated as many child tables are involved, each with their own
>> JITted functions, especially when e.g. partition-aware joins/aggregates are
>> enabled. However, only a fraction of those functions is actually executed
>> because the Parallel Append node distributes the workers among the nodes.
>> With the attached patch we get a lazy generation which makes that this is no
>> longer a problem.
> 
> I unfortunately don't think this is quite good enough, because it'll
> lead to emitting all functions separately, which can also lead to very
> substantial increases of the required time (as emitting code is an
> expensive step). Obviously that is only relevant in the cases where the
> generated functions actually end up being used - which isn't the case in
> your example.
> 
> If you e.g. look at a query like
>    SELECT blub, count(*),sum(zap) FROM foo WHERE blarg = 3 GROUP BY blub;
> on a table without indexes, you would end up with functions for
> 
> - WHERE clause (including deforming)
> - projection (including deforming)
> - grouping key
> - aggregate transition
> - aggregate result projection
> 
> with your patch each of these would be emitted separately, instead of
> one go. Which IIRC increases the required time by a significant amount,
> especially if inlining is done (where each separate code generation ends
> up with copies of the inlined code).
> 
> 
> As far as I can see you've basically falsified the second part of this
> comment (which you moved):
> 
>> +
>> +    /*
>> +     * Don't immediately emit nor actually generate the function.
>> +     * instead do so the first time the expression is actually evaluated.
>> +     * That allows to emit a lot of functions together, avoiding a lot of
>> +     * repeated llvm and memory remapping overhead. It also helps with not
>> +     * compiling functions that will never be evaluated, as can be the case
>> +     * if e.g. a parallel append node is distributing workers between its
>> +     * child nodes.
>> +     */
> 
>> -    /*
>> -     * Don't immediately emit function, instead do so the first time the
>> -     * expression is actually evaluated. That allows to emit a lot of
>> -     * functions together, avoiding a lot of repeated llvm and memory
>> -     * remapping overhead.
>> -     */
> 
> Greetings,
> 
> Andres Freund
> 

Hi,

Happy to help out, and thanks for the info and suggestions.
Also, I should have first searched psql-hackers and the like, as I just 
found out there is already discussions about this in [1] and [2].
However I think the approach I took can be taken independently and then 
other solutions could be added on top.

Assuming I understood all suggestions correctly, the ideas so far are:
1. add a LLVMAddMergeFunctionsPass so that duplicate code is removed and 
not optimized several times (see [1]). Requires all code to be emitted 
in the same module.
2. JIT only parts of the plan, based on cost (see [2]).
3. Cache compilation results to avoid recompilation. this would either 
need a shm capable optimized IR cache or would not work with parallel 
workers.
4. Lazily jitting (this patch)

An idea that might not have been presented in the mailing list yet(?):
5. Only JIT in nodes that process a certain amount of rows. Assuming 
there is a constant overhead for JITting and the goal is to gain runtime.

Going forward I would first try to see if my current approach can work 
out. The only idea that would be counterproductive to my solution would 
be solution 1. Afterwards I'd like to continue with either solution 2, 
5, or 3 in the hopes that we can reduce JIT overhead to a minimum and 
can therefore apply it more broadly.

To test out why and where the JIT performance decreased with my solution 
I improved the test script and added various queries to model some of 
the cases I think we should care about. I have not (yet) done big scale 
benchmarks as these queries seemed to already show enough problems for 
now. Now there are 4 queries which test JITting with/without partitions, 
and with varying amounts of workers and rowcounts. I hope these are 
indeed a somewhat representative set of queries.

As pointed out the current patch does create a degradation in 
performance wrt queries that are not partitioned (basically q3 and q4). 
After looking into those queries I noticed two things:
- q3 is very noisy wrt JIT timings. This seems to be the result of 
something wrt parallel workers starting up the JITting and creating very 
high amounts of noise (e.g. inlining timings varying between 3.8s and 6.2s)
- q4 seems very stable with JIT timings (after the first run).
I'm wondering if this could mean that with parallel workers quite a lot 
of time is spent on startup of the llvm machinery and this gets noisy 
because of OS interaction and the like?

Either way I took q4 to try and fix the regression and noticed something 
interesting, given the comment from Andres: the generation and inlining 
time actually decreased, but the optimization and emission time 
increased. After trying out various things in the llvm_optimize_module 
function and googling a bit it seems that the 
LLVMPassManagerBuilderUseInlinerWithThreshold adds some very expensive 
passes. I tried to construct some queries where this would actually gain 
us but couldnt (yet).

For v2 of the patch-set the first patch slightly changes how we optimize 
the code, which removes the aforementioned degradations in the queries. 
The second patch then makes that partitions work a lot better, but 
interestingly now also q4 gets a lot faster but somehow q3 does not.

Because these findings contradict the suggestions/findings from Andres 
I'm wondering what I'm missing. I would continue and do some TPC-H like 
tests on top, but apart from that I'm not entirely sure where we are 
supposed to gain most from the call to 
LLVMPassManagerBuilderUseInlinerWithThreshold(). Reason is that from the 
scenarios I now tested it seems that the pain is actually in the code 
optimization and possibly rather specific passes and not necessarily in 
how many modules are emitted.

If there are more / better queries / datasets / statistics I can run and 
gather I would be glad to do so :) To me the current results seem 
however fairly promising.

Looking forward to your thoughts & suggestions.

With regards,
Luc
Swarm64

===================================
Results from the test script on my machine:

  parameters: jit=on workers=5 jit-inline=0 jit-optimize=0
  query1: HEAD       - 08.088901 #runs=5 #JIT=12014
  query1: HEAD+01    - 06.369646 #runs=5 #JIT=12014
  query1: HEAD+01+02 - 01.248596 #runs=5 #JIT=1044
  query2: HEAD       - 17.628126 #runs=5 #JIT=24074
  query2: HEAD+01    - 10.786114 #runs=5 #JIT=24074
  query2: HEAD+01+02 - 01.262084 #runs=5 #JIT=1083
  query3: HEAD       - 00.220141 #runs=5 #JIT=29
  query3: HEAD+01    - 00.210917 #runs=5 #JIT=29
  query3: HEAD+01+02 - 00.229575 #runs=5 #JIT=25
  query4: HEAD       - 00.052305 #runs=100 #JIT=10
  query4: HEAD+01    - 00.038319 #runs=100 #JIT=10
  query4: HEAD+01+02 - 00.018533 #runs=100 #JIT=3

  parameters: jit=on workers=50 jit-inline=0 jit-optimize=0
  query1: HEAD       - 14.922044 #runs=5 #JIT=102104
  query1: HEAD+01    - 11.356347 #runs=5 #JIT=102104
  query1: HEAD+01+02 - 00.641409 #runs=5 #JIT=1241
  query2: HEAD       - 18.477133 #runs=5 #JIT=40122
  query2: HEAD+01    - 11.028579 #runs=5 #JIT=40122
  query2: HEAD+01+02 - 00.872588 #runs=5 #JIT=1087
  query3: HEAD       - 00.235587 #runs=5 #JIT=209
  query3: HEAD+01    - 00.219597 #runs=5 #JIT=209
  query3: HEAD+01+02 - 00.233975 #runs=5 #JIT=127
  query4: HEAD       - 00.052534 #runs=100 #JIT=10
  query4: HEAD+01    - 00.038881 #runs=100 #JIT=10
  query4: HEAD+01+02 - 00.018268 #runs=100 #JIT=3

  parameters: jit=on workers=50 jit-inline=1e+06 jit-optimize=0
  query1: HEAD       - 12.696588 #runs=5 #JIT=102104
  query1: HEAD+01    - 12.279387 #runs=5 #JIT=102104
  query1: HEAD+01+02 - 00.512643 #runs=5 #JIT=1211
  query2: HEAD       - 12.091824 #runs=5 #JIT=40122
  query2: HEAD+01    - 11.543042 #runs=5 #JIT=40122
  query2: HEAD+01+02 - 00.774382 #runs=5 #JIT=1088
  query3: HEAD       - 00.122208 #runs=5 #JIT=209
  query3: HEAD+01    - 00.114153 #runs=5 #JIT=209
  query3: HEAD+01+02 - 00.139906 #runs=5 #JIT=131
  query4: HEAD       - 00.033125 #runs=100 #JIT=10
  query4: HEAD+01    - 00.029818 #runs=100 #JIT=10
  query4: HEAD+01+02 - 00.015099 #runs=100 #JIT=3

  parameters: jit=on workers=50 jit-inline=0 jit-optimize=1e+06
  query1: HEAD       - 02.760343 #runs=5 #JIT=102104
  query1: HEAD+01    - 02.742944 #runs=5 #JIT=102104
  query1: HEAD+01+02 - 00.460169 #runs=5 #JIT=1292
  query2: HEAD       - 02.396965 #runs=5 #JIT=40122
  query2: HEAD+01    - 02.394724 #runs=5 #JIT=40122
  query2: HEAD+01+02 - 00.425303 #runs=5 #JIT=1089
  query3: HEAD       - 00.186633 #runs=5 #JIT=209
  query3: HEAD+01    - 00.189623 #runs=5 #JIT=209
  query3: HEAD+01+02 - 00.193272 #runs=5 #JIT=125
  query4: HEAD       - 00.013277 #runs=100 #JIT=10
  query4: HEAD+01    - 00.012078 #runs=100 #JIT=10
  query4: HEAD+01+02 - 00.004846 #runs=100 #JIT=3

  parameters: jit=on workers=50 jit-inline=1e+06 jit-optimize=1e+06
  query1: HEAD       - 02.339973 #runs=5 #JIT=102104
  query1: HEAD+01    - 02.333525 #runs=5 #JIT=102104
  query1: HEAD+01+02 - 00.342824 #runs=5 #JIT=1243
  query2: HEAD       - 02.268987 #runs=5 #JIT=40122
  query2: HEAD+01    - 02.248729 #runs=5 #JIT=40122
  query2: HEAD+01+02 - 00.306829 #runs=5 #JIT=1088
  query3: HEAD       - 00.084531 #runs=5 #JIT=209
  query3: HEAD+01    - 00.091616 #runs=5 #JIT=209
  query3: HEAD+01+02 - 00.08668  #runs=5 #JIT=127
  query4: HEAD       - 00.005371 #runs=100 #JIT=10
  query4: HEAD+01    - 00.0053   #runs=100 #JIT=10
  query4: HEAD+01+02 - 00.002422 #runs=100 #JIT=3

===================================
[1] 
https://www.postgresql.org/message-id/flat/7736C40E-6DB5-4E7A-8FE3-4B2AB8E22793%40elevated-dev.com
[2] 
https://www.postgresql.org/message-id/flat/CAApHDvpQJqLrNOSi8P1JLM8YE2C%2BksKFpSdZg%3Dq6sTbtQ-v%3Daw%40mail.gmail.com