[C++] Sketch out design for kernels and "query" execution in compute layer

[asfimport]

It would be good to formalize the design of kernels and the controlling query execution layer (e.g. volcano batch model?) to understand the following:

Contracts for kernels:

• Thread safety of kernels?

• When Kernels should allocate memory vs expect preallocated memory?  How to communicate requirements for a kernels memory allocaiton?

• How to communicate the whether a kernels execution is parallelizable across a ChunkedArray?  How to determine if the order to execution across a ChunkedArray is important?

• How to communicate when it is safe to re-use the same buffers and input and output to the same kernel?

  What does the threading model look like for the higher level of control?  Where should synchronization happen?

Reporter: Micah Kornfield / @emkornfield

Related issues:

• [C++] C++ array kernels framework and execution buildout (umbrella issue) (relates to)

_{Note: This issue was originally created as ARROW-4333. Please see the migration documentation for further details.}

[asfimport]

Wes McKinney / @wesm:
Yes, I agree with coming up with a plan for all these concerns. I think the volcano batch model is the way to go. This is what Impala and many other systems use quite successfully

[asfimport]

Micah Kornfield / @emkornfield:
http://www.vldb.org/pvldb/vol4/p539-neumann.pdf might be of interest.   It seems like this reverses the model to some extent (and then goes ahead and disposes of it entirely to compile code).  Caveat (I'm still ramping up on DB systems in general).

[asfimport]

Francois Saint-Jacques / @fsaintjacques:
References I suggest you to check.

• The Design and Implementation of Modern Column-Oriented Database Systems, 2012: This is a long read, but worth the investment. Will give you a broad overview of what are columnar databases and what makes them fast.

• MonetDB/X100: Hyper-Pipelining Query Execution, 2005 foundation paper on how to implement fast query engine for analytics on modern hardware.

• Everything You Always Wanted to Know About Compiled and Vectorized Queries But Were Afraid to Ask, 2018: This is an update to the paper you linked, which studies Compilation vs Vectorization.

• Vectorization vs. Compilation in Query Execution, 2011

• Relaxed Operator Fusion for In-Memory Databases: Making Compilation, Vectorization, and Prefetching Work Together At Last, 2017

• Make the Most out of Your SIMD Investments: Counter Control Flow Divergence in Compiled Query Pipelines, 2018, talks about using AVX-512 masked instructions.

  Anything by:
  Daniel J. Abadi part of the team that wrote CStore which became Vertica. Write less about columnar execution in the last years.
  Peter Boncz behind MonetDB/Vectorwize.
  Thomas Neumann behind Hyper bought by Tableau.
  Andrew Pavlo teaches database course at CMU

  Amazing video lectures of courses at CMU, you can ignore most of the storage layer, concurrency, transaction context. We're interested in execution engine, vectorization, and compilation.

• https://www.youtube.com/playlist?list=PLSE8ODhjZXjYplQRUlrgQKwIAV3es0U6t

• https://www.youtube.com/playlist?list=PLSE8ODhjZXjbjOyrcqgE6_lCV6xvzffSN

• https://www.youtube.com/playlist?list=PLSE8ODhjZXjY2xvwxuKjZT5qFH0sQga8_

• https://www.youtube.com/playlist?list=PLSE8ODhjZXjY0GMWN4X8FIkYNfiu8_Wl9

  The CMU 15-721 Advanced Database Systems schedule is usually a good source of papers.

  Relevant code base:

• Impala

• ClickHouse  

• MapD

• Supersonic

• Peloton

[asfimport]

Wes McKinney / @wesm:
I partially addressed some of these questions in ARROW-8792, but there are other questions viz-a-viz memory reuse and dealing with ChunkedArrays. Perhaps it would be useful to go through these questions and discuss them in the context of the new generic kernel execution framework in arrow/compute

[asfimport]

Wes McKinney / @wesm:
I'd suggest we resolve this and pursue answers to some of the unanswered questions as more specific followups. In particular, I plan to be building multi-kernel expression evaluation in the near future so some of the pipelining/memory reuse questions must be addressed as a part of this