WIP

Changelist

Parallel sample by:

• Parallel sample by:
  • now supports fill with multiple values
  • correctly uses all fill values instead of just the first
  • will now generate radix sorts more frequently, which are 2x-10x faster than our tree-based sort
  • will now only sort unfilled data, instead of sorting both filled and real data
• a mismatch between column and fill value in from-to queries previously caused UnsupportedOperationException and a 500 response code. Now it will return a useful message:
  • Example query: select timestamp, count from trades sample by 1d from '2008-12-28' to '2009-01-05' FILL(1.0)
  • Error: invalid fill value, cannot cast DOUBLE to LONG

Benchmarks

Table of 100m rows.
Schema - (TIMESTAMP, DOUBLE)
Data is over a 1 day period.

With 100m rows

Query:

select timestamp, avg(price) from bench
sample by 1T fill(null)

Fill Range
  stride: '1T'
  values: [null]
    Radix sort light
      keys: [timestamp]
        Async Group By workers: 8
          keys: [timestamp]
          values: [avg(price)]
          filter: null
            PageFrame
                Row forward scan
                Frame forward scan on: bench

Before: timeout (60s)
After: 22.75s

With 10m rows:

Query:

select timestamp, price from (
select timestamp, avg(price) as price from bench4
sample by 1T fill(null)
) limit -1

Before: 13.4s, 12.51s, 14.4s
After: 1.9s, 1.43s, 1.33s

Queries which do not require the sort will be slower, for example:

select max(price) from (
    select timestamp, avg(price) from bench
    sample by 1T fill(null)
)

This is because in the new version, a sort will be generated, and in the old, it would not. However, this was at the cost of the fill not necessarily being correct or filling on the right timestamp.

Alternative

If we allowed group by to return a timestampIndex in this case, even though the result will not be sorted (i.e (timestamp, SCAN_DIRECTION_OTHER), then we could still use parallel fill in its original form. This requires relaxing the rule that timestampIndex means ASC (designated) timestamp.

Notes

This PR reworks the parallel sample by fill in an effort to improve performance and reliability. Previously, the fill would be generated after group by, and before order by. This meant we had to first exhaust the group by result, recording timestamps. Then we filled the rest of the timestamps.

Unfortunately, group by does not guarantee a designated timestamp, making it problematic to identify the correct column to fill. Furthermore, this would cause both filled and unfilled data would be subsequently sorted, so sparse datasets were as expensive to sort as dense datasets.

By moving it to after order by, we ensure that we have a designated timestamp to orient the fill. We also generate radix sort more frequently, which can be 2-10x faster than our tree-based sort. We also only have to sort the unfilled data, leading to a much quicker an dmore efficient sort.