Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Faster hash joiner with vectorized execution

cockroachlabs.com

Post reply on HN
Print view View original

1–10 of 21 posts

Re: Faster hash joiner with vectorized execution

#2

Post by evrydayhustling »

Pretty impactful work for an intern! One thing I would have liked to see, both from a process and communication standpoint, is leading with some stats on how much faster the vectorized loops are in isolation from the surrounding engine.

It's always good practice to dig into a deep project like this with some napkin estimates of how much you stand to gain, and how much overhead you can afford to spend setting yourself up for the faster computation. (Not to mention how much of your own time is merited!)

Re: Faster hash joiner with vectorized execution

#5

Post by asubiotto »

evrydayhustling wrote: post #2

Pretty impactful work for an intern! One thing I would have liked to see, both from a process and communication standpoint, is leading with some stats on how much faster the vectorized loops are in isolation from the surrounding engine. It's always good practice to dig into a deep project like this with some napkin estimates of how much you stand to gain, and how much overhead you can afford to spend setting yourself…

Indeed! We spent some time running isolated benchmarks before deciding to dive into the project: https://github.com/jordanlewis/exectoy

Re: Faster hash joiner with vectorized execution

#8

Post by obl »

The "core" of the trick is nice : amortizing interpreter dispatch over many items. (ignoring the column layout/SIMD stuff which basically helps in any case)

Essentially it's turning :

  LOAD
    DISPATCH
    OP1
    DISPATCH
    OP2
    ... (once per operation in the expression)
  STORE
  ... (once per row)
into

  DISPATCH
    LOAD
    OP1
    STORE
    LOAD
    OP1
    STORE
    ... (once per row)
  DISPATCH
  ... (once per operation in the expression)
The nice trade-off here is that you don't require code generation to do that, but it's still not optimal.

If you can generate code it's even better to fuse the operations, to get something like :

  LOAD
    OP1
    OP2
    ...
  STORE
  LOAD
  ...
It helps because even though you can tune your batch size to get mostly cached loads and stores, it's still not free.

For example on Haswell you can only issue 1 store per cycle, so if OP is a single add you're leaving up to 3/4 of your theoretical ALU throughput on the table.

Re: Faster hash joiner with vectorized execution

#9

Post by DLA »

angelachang27 wrote: post #4

Hey everyone, I'm the intern who did this work, happy to answer any questions if you have them!

Your work is awesome as is your excellent detailed writeup. Appreciate the links and refs to the background papers also. Thank you for helping make CRDB even better. You should be very proud of this work.
Post reply on HN