DeepOLA: Project Tracker

[pyongjoo]

Paper Writing

• Create an Overleaf project (https://www.overleaf.com/5719128663sfwhtyzcgfmq)
• Experiment section
• Discuss outline
• Main method section
• Background section
• Related work section
• Introduction section

Our Implementation

• (T1) In place of ArrayRow, we have another class for DataFrame
  • Conceptually, we process partition by partition. What is a partition? A partition = A dataframe (with projected/subset of columns).
  • We need to pass a series of (DataFrame, Meta)
  • How can we read/construct DataFrame in partitions?
    • rust arrow already supports iterator-based reads (we doubt it has)
    • pre-partition a table into multiple csv files
• (T2, which is blocked by T1) Convert join-free TPC-H queries into a node-based structure
• (T3) hash table thing (for joins, it is better to keep hash tables, rather than constructing them for every partition)
• (T4, blocked by T3) Convert with-join TPC-H queries into a node-based structure
• (T5) Do something for ``where subquery''
• (T6, blocked T5) Convert remaining (i.e., with-subquery) TPC-H queries
• Example: https://github.com/illinoisdata/DeepOLA/blob/main/rust/runtime/examples/tpch/q1.rs
• Supawit: working on estimation logic

Experiments: end-to-end

• Setup
  • Dataset: We mainly use skewed TPC-H datasets (1GB)
  • Comparison I against OLA: Ours vs WanderJoin (Q3, Q7, Q10)
  • Comparison II against OLA: Ours vs ProgressiveDB (Q1, Q6)
• Ours
  • Convert TPC-H queries into our Nodes Tracker: Link
  • Collect numbers for 1GB (toy experiments) Google Sheet: Link
  • Collect numbers for 10GB 50GB (we may use different scales)
  • Query analysis document
• Others
  • Traditional query engines (non OLA)
    • Polars (https://github.com/pola-rs/polars)
      • Try polars
    • Postgres
    • Arav: Presto (Hive connector, read csv data (not parquet)):
      • link to our dataset
      • https://github.com/illinoisdata/labwiki/wiki/Setting-up-a-Presto-cluster
      • Upload CSV files to HDFS
      • Create (external) tables on CSV files
      • Run some test queries
      • Arav will discuss with Yongjoo how to run TPC-H queries
      • Upload the results of 22 TPC-H queries on Presto for 10GB dataset to our Google sheet
      • Create a PR containing 22 TPC-H queries runnable on Presto (Assign Nikhil for reviewer)
      • To collect reliable query latencies of 22 TPC-H queries for Presto on 10 GB dataset
        • Learn how to clear cache (turn off and on Presto, and measure latency again; clear OS cache; learn if we can clear cache HDFS)
        • Write script to measure cold-start latency
  • OLA engines
    • Arav: Wander join / XDB (http://www.cs.utah.edu/~lifeifei/papers/wanderjoin.pdf)
      • Use the same Azure machines (only for this experiment)
      • This is the Github repository: https://github.com/InitialDLab/XDB
      • Test 3 TPC-H queries
      • Wanderjoin is very accurate; so trying to vary the distribution of TPCH dataset
        • We adopted some well-known existing method to alter the distribution (link1) (link2)
      • Measure the latency of 3 TPC-H queries (Numbers: 3, 7, 10) (https://docs.google.com/spreadsheets/d/1Qy9cytnXFpkjA1mEkU44dDxOIHsSSwKoKNxKHQAreqM/edit?usp=sharing)
    • Suwen: ProgressiveDB (http://www.vldb.org/pvldb/vol12/p1814-berg.pdf)
      • Check its GitHub repository (https://github.com/DataManagementLab/progressiveDB)
      • See what resources we need (e.g., Ubuntu machine), Try to understand limitation (limited set of queries)
      • Discuss with Yongjoo how to set things up actually
      • IntelliJ -> Maven (mvn compile or mvn build -> jar files.)
      • Will update code to GitHub (as a new branch)
      • Will double data type supports
      • Converted data types from double/float to int using Pandas
      • Will bulk insert CSV data to Postgres (or ProgressiveDB)
      • Analyze why partitioning (or preparing) for 1GB tpch dataset is taking so long
      • Start measure latencies (exact query examples, definition of latencies)
      • Google sheet
      • Google sheet for skewed data
      • Sample data for running polars

Experiments: estimation accuracy

• Task I: Estimate sum (for both (1) randomly shuffled data and (2) somehow sorted data)
  • Use TPC-H query 12 because the query is relatively simple.
  • Prepare datasets (i.e., with randomly generated o_orderpriority and systematically generated o_orderpriority)
  • Ours
  • Closed form (https://web.ma.utexas.edu/users/parker/sampling/woreplshort.htm)
  • Bayesian (https://asterix.ics.uci.edu/pub/vldb11-oa.pdf)
• Task II: Estimate count-distinct (for both (1) randomly shuffle data and (2) somehow sorted data)
  • Use TPCH query 16 because that seems to be the only count-distinct query.
  • Prepare datasets (i.e., shuffled partsupp and non-shuffled partsupp)
  • Ours
  • Closed form (http://vldb.org/conf/1995/P311.PDF)

Experiments: others

• Impact of batch size

Reference

• TPC-H queries: https://github.com/dragansah/tpch-dbgen/tree/master/tpch-queries

[pyongjoo]

Our Definition of Cardinality (of each partition)

Single Table

Suppose a query is select count(*) from single_table where arbitrary_predicate.

And we have partitions of single_table: [P1, P2, ..., P10]. Let c(P1) denote the cardinality of P1, which is the number of rows in P1. Likewise for other partitions, e.g., c(P2), and so on.

A(P1) means the query answer only based on P1. A(P2) means the query answer based on P1 and P2.

Training data = [ (c(P1), A(P1)), (c(P1)+c(P2), A(P2)), ... ] \union c(single_table)

Two Tables

Suppose a query is select count(*) from table1 inner join table2 on join_predicate where arbitrary_predicate.

We will have for example 10 partitions for each table1 and table2, which we denote their sizes by c(P11), c(P12), ... for table1, and c(P21), c(P22), ... for table2.

And we define the cardinality of the join as follows: c(Pj) = min( c(P1j), c(P2j) ) .

Actual data generation for lineitem and orders

1. Join lineitem and orders
2. Shuffle them using some algorithm
3. Place roughly (for example) 1/10th of data into P1, and so on

[pyongjoo]

Experiment List

@nikhil96sher Can you propose an initial list of experiments to run? What's the purpose of each experiment?

[nikhil96sher]

Initial List of Experiments

Comparison with Baselines

1. Comparison with other Online Aggregation Methods
   • Goal 1: Better performance (in terms of first result time and overall processing time) than existing Online Aggregation Methods.
   • Goal 2: Larger scope of queries covered. The number of queries that can be supported from the benchmark.
   • Comparison with Baselines
     • WanderJoin
     • ProgressiveDB
2. Comparison with other Approximate Query Methods
   • Goal 1: Forecast provides better and faster approximation than other AQP Baselines.
   • Goal 2: Larger scope of queries covered. The number of queries that can be supported from the benchmark.
   • Comparison with Baselines
     • VerdictDB
     • DeepDB
3. Comparison with other Exact Query Methods
   • Goal 1: Overall Processing Time: To show that the degradation is not significant.
   • Goal 2: Lower Peak Memory Usage: We are able to process larger size/scale of data on a smaller machine.
   • Comparison with Baselines
     • Postgres
     • Presto
     • Pandas
     • Raw Polars

Ablation Study

1. Changing the number of partitions for a given scale.
   • Goal 1: How to decide on the ideal number of partitions.
2. Different Forecast Models
   • Goal 1: Forecast provides better approximation than just scale multiplication.
   • Goal 2: How to choose a specific forecast model?
3. Study of time taken by different nodes in a query. Which nodes/operations takes most time.

[pyongjoo]

How to run Polars experiments for TPC-H queries

• Step 1: Suwen to submit a script / and get it merged
• Step 2: Implement remaining queries
  • Suwen: 3n+1
  • Arav: 3n+2
  • Riya: 3n