Write DataFusion paper for (SIGMOD / VLDB / ICDE)

@Dandandan

UPDATE: Final paper: https://dl.acm.org/doi/10.1145/3626246.3653368

Task List for SIGMOD Paper:

Per #6782 (comment), here is a list of TODO items:

Issues Blocking Full Performance Results

Issues that would make the results more compelling

(TO FILE or Find): Ensure performance doesn't degrade with larger core counts on some queries

Is your feature request related to a problem or challenge?

I would like to increase awareness of DataFusion in the broader technical community. One way to build mindshare is to get a paper / talk published in a prestigious conference like VLDB or SIGMOD

Writing a paper is a good way to show the strength of the arrow/datafusion.
Through the papers, more teachers, students and researcher may be involved, and contribute to the project.

Describe the solution you'd like

I would like to write a paper that explains DataFusion
Thesis: "You don't need a tightly integrated execution system to get good performance"

These blogs have some good material in the introduction
https://arrow.apache.org/blog/2023/06/24/datafusion-25.0.0/
https://arrow.apache.org/blog/2023/01/19/datafusion-16.0.0/

Then we would compare and contrast the approaches of other tightly integrated systems like pola.rs and duckdb to DataFusion

We would then describe the architecture of DataFusion and its many extension points (DataFrame, functions, aggregates, window functions, sinks, etc)

Performance:
Show DataFusion in the same ballpark as DuckDB for aggregation, grouping, etc (e.g. TPCH)
We already have this for querying parquet

Describe alternatives you've considered

VLDB: https://vldb.org/2024/?call-for-industrial-track

Submissions open	December 6, 2023
Short abstracts deadline	February 16, 2024
Full papers or extended abstracts deadline	March 1, 2024
Notifications	May 8, 2024
Camera-ready	June 15, 2024

SIGMOD: https://2024.sigmod.org/calls_papers_important_dates.shtml

Industrial track: https://2024.sigmod.org/comingsoon.shtml (TBD)

Research paper submission round 4 (All Deadlines are 11:59 PM Pacific Time)

October 15, 2023: Paper submission
November 26-28, 2023: Author feedback phase
December 20, 2023: Notification of accept/reject/review again
January 20, 2024: Revised paper submission
February 23, 2024: Final notification of accept/reject

ICDE:

Industrial Track: https://icde2024.github.io/CFP_industry.html

All deadlines below are 5 PM Pacific Time.

Paper submission: Monday, November 20, 2023
Notification of accept/reject: Wednesday, January 31, 2024
Camera-ready deadline: Thursday, March 28, 2024

Additional context

No response

Some ideas about the paper:

Thesis:

We demonstrate it is possible to get DuckDB like performance using standards like Parquet and Arrow as the internal interchange format, both inside of and outside of the engine. Previously the conventional wisdom has been that such performance levels require a tightly integrated engine where the disk format, in memory layout, and processing engine are engineered in tandem to work well together.

While the engineering effort required for such an engine is large, it is possible by leveraging the open source model and Apache governance model to poll resources amongst users. Given the availablity of fast, standards based, interoperable vectorized engines like DataFusion, we predict a Cambrian explosion of new analytic systems which would not have been possible before if they had to create their own engines

Background

(Section on Arrow) -- including in memory model, compute kernels, and Flight / FlightSQL

(Section on Parquet)

(Section on tokio -- aka not have to reinvent the scheduler)

(DataFusion usecases, examples of systems built on DataFusion)

Architecture

Internally DataFusion uses Arrow as the interchange between operators, though internally different, non standard formats are used (such as the Arrow Row Format)

Describe planning at a high level

List extension points + briefly describe how users can extend the engine (and how that is desiged for speed)

UDF (everyone does this)
UDAF (everyone does this)
UDWF
Optimizer Rules
Custom Operators
Own catalog
Own partition pruning / elimination rules
Provide information on sortedness

List briefly the features of the engine

parquet / predicate pushdown with late materialization
use of tokio scheduler and the benfits of that model (has good NUMA performance given how tasks are scheduled). Also note that use of morsel driven parallelism doesn't solve the typical bottneck on priorities -- memory
group hash aggregates -- templated code
Joins (TBD)
Sophisticated sort based optimizations (including pre-sorted data) streaming group by, merge-join,
"Partition Pruning" (Pruning predicate) for custom catalog support

Performance

(TPCH / ClickBench results)

Parquet / pushdown results

Talk about bespoke file format vs only using Parquet

Related work

Velox (focuses on the execution engine side)
Apache Calcite (focuses on sql and frontend)
DataFusion has all the pieces of the toolkit (sql frontend, logical plan, and execution plans)

Ideas for experiments I would like to run

Comparisons to existing systems:

SQL based

Clickbench (DataFusion + DuckDB on parquet)
TPCH (DataFusion + DuckDB on parquet)
h2o.ai (DataFusion + DuckDB in parquet)

DataFrame

Some sort of comparison with Pol.rs on aggregation
Some sort of comparison with pandas

Scalabilty performance

Also it would be awesome to have charts showing DataFusion scaling:

Performance as number of cores increases (ideally this would be linear)
Memory Usage vs input data size

Since I imagine there will be some tweaks given these numbers, having the run and chart generation automated would be very helpful

Other material:
fast grouping: https://www.influxdata.com/blog/aggregating-millions-groups-fast-apache-arrow-datafusion/
querying parquet with subsecond latency: https://www.influxdata.com/blog/querying-parquet-millisecond-latency/

I have begun work on this paper. I am planning to submit it to the SIGMOD industrial track https://2024.sigmod.org/calls_industrial_track_papers.shtml

I am planning to use Overleaf (recommended by the ACM) rather than setup the latex stuff myself, as it worked well when I used it on another paper earlier this year,

Here is the overleaf https://www.overleaf.com/read/qjhrxqhgksvr -- right now not much more than the template

If you are interested in being an author and helping to write the paper, please let me know. I am especially looking for help help running benchmarks / generating performance numbers as described in #6782 (comment)

@alamb

Some initial thoughts for the paper organization after checking the current version:

1. Introduction (1 page)
	- The deconstructed system(against conventional wisdom), the Apache way
	- technical methodology: Vectorized execution / Columnar input/output/intermediate / Pull mode with Morsel benefits

2. Background (1-1.5 pages)
	- The mature of ecosystem, columnar format parquet, in-mem format arrow, high performance thread scheduler tokio, and the surge of generalized relational algebra substrait
	- The needs for a deconstructured engine (high performance, and highly customizable)
		- an open engine for high performance (influxdb/ streamingdb/distrubuted olap)
		- an standard, extensible planner for resue (dask-sql,)
		- an general purpose parser sqlparser-rs (for TP, AP and streaming)

3. Design (3-4 pages)
	- Engine overview
	- execution model and scheduler
	- sort and the row model
	- aggregate and the aggregator model

4. Optimizations (1-1.5 pages)
	- Late materialization and predicate pushdown
	- Predicate prunning

5. Extensibilities (1 page)
	- UDF / UDAF
	- data source
	- catalog
	- parser?
	- ?

6. Benchmarks (2-3 pages)
	- micro-bench?
		- for sort?
		- for agg?
		- for scheduler?
	- e2e-bench
		- tpc-h?
		- clickbench?
		- ?

7. Related work (0.75 page)
	- Velox
	- DuckDB
	- Spark Photon

8. Conclusion (0.25 page)
	- the open source, the Apache way we believe
	- always pursing for performance start from real world problems

After some discussion with @alamb, we agreed that we could start with this above structure first and adapt it as we proceed.

@alamb

I incorporated the above structure into the paper, but split the background part into two sections:

2. Foundational Ecosystem
3. Deconstructing the Database,

Section 2 mainly talks about DataFusion's foundation technologies/systems, and Section 3 keeps the material from the analytical database that @alamb has previously shared the philosophy and vision of DataFusion.

I also finished my first pass for section 2, Foundational Ecosystem.

@yjshen

Thank you @yjshen -- this is amazing ❤️ . I plan to take a pass through the architecture section later this morning, and see how far I get. I also hope to start working on some diagrams to emphasize some of the points in the paper.

@yjshen

Here is my summary of the state of this project so far. Please correct me if I got it wrong:

Current Author List:

Goal:

The goal is to submit an industrial track paper to SIGMOD 2024:

"The Industrial Track of SIGMOD 2024 covers all aspects of innovative commercial or industrial-strength data management systems and solutions. We also welcome novel applications of data management systems and experience in applying recent research advances to problems relevant to the database industry."

Paper submission: Monday, November 20, 2023
Notification of accept/reject: Wednesday, January 31, 2024
Camera-ready deadline: Thursday, March 28, 2024

Proposed Timeline:

End of August: Rough Draft complete
Sep / Oct: Improve results, hone language
Nov: Submit paper

Logistics

We will use overleaf to write the paper. Anyone should be able to see the current state of the paper here https://www.overleaf.com/read/qjhrxqhgksvr and the authors have write access
We will coordinate / communicate in the open on this ticket (per the Apache Way)
We will use the google drawing / PDF export for diagrams: Google Drive folder

I will also add a todo / task list to the description of this ticket for us to coordinate on remaining open work

@JayjeetAtGithub

What is a good way to provide feedback? Can we open a chat somewhere for more quick/detailed discussions?

@JayjeetAtGithub The scalability graph look be more interpretable if it's presented in log-scale or exponential with the speedup shown as 1x,2x,4x,8x, 16x etc.

I found one issue in the benchmarks.

Thank you for taking a look. It'd be great if double checked all the config parameters and our usage of APIs on both sides to make sure we don't accidentally distort any measurement.

I found one issue in the benchmarks.

Thank you for taking a look. It'd be great if double checked all the config parameters and our usage of APIs on both sides to make sure we don't accidentally distort any measurement.

I did review this quite extensively when working on the benchmarks and I believe they are defensible. The runner scripts are based on the (duckdb authored) scripts to run ClickBench (that use fetchall):

https://github.com/ClickHouse/ClickBench/blob/1a8ecca8808378da011a3050d648cb9dbd2a1d95/duckdb-parquet/query.py#L15

So while we can (and should) improve the scripts if the paper is accepted for publication, I recommend keeping the existing results that have fetchall for the draft because:

we used the same methodology as experts in DuckDB
the overall conclusion is the same, even if the some of the relative numbers are slightly different

I have started collecting "things to do if the paper is accepted" in #8373

Ok, well the deadline is past so I am going to claim we have 'written' the paper and closing this ticket. We'll track the status of the paper in #8373 for anyone interested

In addition to DuckDB and pola.rs, have you considered comparing Clickhouse?

@JasonLi-cn

In addition to DuckDB and pola.rs, have you considered comparing Clickhouse?

Hi @JasonLi-cn -- One comparison DataFusion and ClickHouse is ClickBench https://benchmark.clickhouse.com/

While similar, I think DataFusion and ClickBench are different enough to make comparing hard. ClickBench is a real database management, and unlike DataFusion it targets end-users rather than developers of other database systems.

@JasonLi-cn

In addition to DuckDB and pola.rs, have you considered comparing Clickhouse?

Hi @JasonLi-cn -- One comparison DataFusion and ClickHouse is ClickBench https://benchmark.clickhouse.com/

While similar, I think DataFusion and ClickBench are different enough to make comparing hard. ClickBench is a real database management, and unlike DataFusion it targets end-users rather than developers of other database systems.

thanks~

In case someone is looking for it, here is the draft we submitted:
DataFusion_Query_Engine___SIGMOD_2024.pdf

congrats on the submission - sorry that i was not able to find time to contribute. hopefully the draft gets good reception!

Our paper was accepted. See more details on #8373 (comment)

Hi, it looks like the link posted on 1/9 is broken. Is there a place to find the finalized paper? Thanks

@rohitrastogi

Hi, it looks like the link posted on 1/9 is broken. Is there a place to find the finalized paper? Thanks

@rohitrastogi -- We don't have the final draft of the paper yet (we will have it by the end of the month -- March 28). Here is the draft we submitted:
DataFusion_Query_Engine___SIGMOD_2024 (8).pdf

Final paper draft can be found here: #8373 (comment)

Final ACM link: https://dl.acm.org/doi/10.1145/3626246.3653368

Navigation Menu

Repository navigation

Write DataFusion paper for (SIGMOD / VLDB / ICDE) #6782

Is your feature request related to a problem or challenge?

Describe the solution you'd like

Describe alternatives you've considered

Additional context

Thesis:

Background

Architecture

Performance

Related work

Comparisons to existing systems:

SQL based

DataFrame

Scalabilty performance

Current Author List:

Goal:

Proposed Timeline:

Logistics

101 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Write DataFusion paper for (SIGMOD / VLDB / ICDE) #6782

Description

Is your feature request related to a problem or challenge?

Describe the solution you'd like

Describe alternatives you've considered

Additional context

Activity

alamb commented on Jul 11, 2023

Thesis:

Background

Architecture

Performance

Related work

alamb commented on Jul 11, 2023

Comparisons to existing systems:

SQL based

DataFrame

Scalabilty performance

alamb commented on Aug 6, 2023

alamb commented on Aug 6, 2023

yjshen commented on Aug 14, 2023

yjshen commented on Aug 14, 2023

alamb commented on Aug 14, 2023

alamb commented on Aug 15, 2023

Current Author List:

Goal:

Proposed Timeline:

Logistics

Dandandan commented on Aug 16, 2023

101 remaining items

ozankabak commented on Nov 30, 2023

alamb commented on Nov 30, 2023

alamb commented on Nov 30, 2023

alamb commented on Dec 1, 2023

JasonLi-cn commented on Dec 10, 2023

alamb commented on Dec 11, 2023

JasonLi-cn commented on Dec 12, 2023

alamb commented on Jan 9, 2024

jimexist commented on Jan 10, 2024

alamb commented on Feb 4, 2024

rohitrastogi commented on Mar 13, 2024

alamb commented on Mar 13, 2024

alamb commented on Mar 31, 2024

alamb commented on Jul 9, 2024

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions