tree fc7bd0ce30c306ade830ffe19e62aef9613592ef
parent 950973a1680432735319f0992620b6425ba1ec57
author Tim Armstrong <tarmstrong@cloudera.com> 1570427738 -0700
committer Impala Public Jenkins <impala-public-jenkins@cloudera.com> 1570680651 +0000

IMPALA-9015: improve mt_dop scan scheduling

Implement longest-processing time algorithm for assigning scan ranges
to instances within a host. This is a standard algorithm that works
well in practice and solves some specific bugs in the current
algorithm.

The previous approach tended to assign multiple ranges to the
first instance and induce skew. E.g. if the ranges were
[3, 4, 5, 6] and it had 4 instances, it would assign
[3, 4], [5], [6], []. This also had the unfortunate consequence
that not all instances actually got allocated scan ranges,
making scheduling hard to reason about.

Testing:
Added a unit test for the core algorithm that checks directly
that it fixes that above problems.

Perf:
The algorithm is O(n log n) instead of O(n), where n is the
number of scan ranges allocated to a backend. This seems
worthwhile to get more even work distribution because
the payoff can be significant in may cases.

I ran a single node perf run of TPC-H scale 30 with
mt_dop=4 and saw significant perf improvements:

Report Generated on 2019-10-07
Run Description: "ccd741856d0e18be9c89087da71d9fc59f1c75ad vs 37d3df99e588b0e9080660c472c3bb06a08361ac"

Cluster Name: UNKNOWN
Lab Run Info: UNKNOWN
Impala Version:          impalad version 3.4.0-SNAPSHOT RELEASE ()
Baseline Impala Version: impalad version 3.4.0-SNAPSHOT RELEASE ()

+----------+-----------------------+---------+------------+------------+----------------+
| Workload | File Format           | Avg (s) | Delta(Avg) | GeoMean(s) | Delta(GeoMean) |
+----------+-----------------------+---------+------------+------------+----------------+
| TPCH(30) | parquet / none / none | 8.51    | -3.78%     | 5.70       | -4.07%         |
+----------+-----------------------+---------+------------+------------+----------------+

+----------+----------+-----------------------+--------+-------------+------------+-----------+----------------+-------+----------------+---------+--------+
| Workload | Query    | File Format           | Avg(s) | Base Avg(s) | Delta(Avg) | StdDev(%) | Base StdDev(%) | Iters | Median Diff(%) | MW Zval | Tval   |
+----------+----------+-----------------------+--------+-------------+------------+-----------+----------------+-------+----------------+---------+--------+
| TPCH(30) | TPCH-Q11 | parquet / none / none | 3.08   | 3.04        |   +1.11%   |   0.72%   |   1.09%        | 5     |   +1.52%       | 0.58    | 1.88   |
| TPCH(30) | TPCH-Q2  | parquet / none / none | 1.83   | 1.83        |   -0.01%   |   3.68%   |   1.25%        | 5     |   +2.00%       | 0.00    | -0.00  |
| TPCH(30) | TPCH-Q9  | parquet / none / none | 36.29  | 36.17       |   +0.32%   |   2.22%   |   2.94%        | 5     |   +0.56%       | 0.00    | 0.20   |
| TPCH(30) | TPCH-Q8  | parquet / none / none | 5.80   | 5.93        |   -2.06%   |   0.61%   |   0.94%        | 5     |   -1.74%       | -2.02   | -4.14  |
| TPCH(30) | TPCH-Q3  | parquet / none / none | 8.91   | 9.15        |   -2.62%   |   3.54%   |   3.96%        | 5     |   -2.17%       | -0.87   | -1.12  |
| TPCH(30) | TPCH-Q15 | parquet / none / none | 3.38   | 3.46        |   -2.30%   |   0.82%   |   0.68%        | 5     |   -2.54%       | -2.31   | -4.89  |
| TPCH(30) | TPCH-Q6  | parquet / none / none | 1.62   | 1.67        |   -2.73%   |   2.52%   |   0.12%        | 5     |   -2.88%       | -1.15   | -2.49  |
| TPCH(30) | TPCH-Q20 | parquet / none / none | 3.67   | 3.78        |   -3.06%   |   1.12%   |   1.69%        | 5     |   -2.69%       | -2.31   | -3.41  |
| TPCH(30) | TPCH-Q4  | parquet / none / none | 3.08   | 3.18        |   -3.05%   |   1.22%   |   0.32%        | 5     |   -2.86%       | -2.31   | -5.57  |
| TPCH(30) | TPCH-Q14 | parquet / none / none | 5.52   | 5.72        |   -3.56%   |   1.35%   |   1.02%        | 5     |   -3.60%       | -2.31   | -4.81  |
| TPCH(30) | TPCH-Q16 | parquet / none / none | 2.32   | 2.41        |   -3.86%   |   1.04%   |   1.64%        | 5     |   -3.99%       | -2.02   | -4.50  |
| TPCH(30) | TPCH-Q7  | parquet / none / none | 24.22  | 25.27       |   -4.15%   |   0.40%   |   2.01%        | 5     |   -3.74%       | -2.31   | -4.55  |
| TPCH(30) | TPCH-Q18 | parquet / none / none | 8.64   | 8.99        |   -3.97%   |   1.02%   |   0.47%        | 5     |   -4.27%       | -2.31   | -8.15  |
| TPCH(30) | TPCH-Q12 | parquet / none / none | 3.38   | 3.53        |   -4.28%   |   1.67%   |   1.39%        | 5     |   -4.26%       | -2.31   | -4.51  |
| TPCH(30) | TPCH-Q5  | parquet / none / none | 11.77  | 12.28       |   -4.18%   |   0.72%   |   0.94%        | 5     |   -4.62%       | -2.31   | -8.06  |
| TPCH(30) | TPCH-Q17 | parquet / none / none | 7.65   | 8.05        |   -4.98%   |   1.03%   |   2.09%        | 5     |   -4.68%       | -2.31   | -4.82  |
| TPCH(30) | TPCH-Q21 | parquet / none / none | 27.97  | 29.52       | I -5.27%   |   0.78%   |   0.39%        | 5     | I -5.16%       | -2.31   | -14.17 |
| TPCH(30) | TPCH-Q1  | parquet / none / none | 4.92   | 5.24        | I -6.05%   |   3.59%   |   2.32%        | 5     | I -6.79%       | -1.73   | -3.30  |
| TPCH(30) | TPCH-Q19 | parquet / none / none | 4.56   | 4.92        | I -7.33%   |   1.55%   |   0.90%        | 5     | I -8.50%       | -2.31   | -9.64  |
| TPCH(30) | TPCH-Q22 | parquet / none / none | 2.09   | 2.28        | I -8.40%   |   1.95%   |   1.85%        | 5     | I -9.21%       | -2.31   | -7.29  |
| TPCH(30) | TPCH-Q13 | parquet / none / none | 10.83  | 11.84       | I -8.55%   |   0.53%   |   0.57%        | 5     | I -9.34%       | -2.31   | -25.56 |
| TPCH(30) | TPCH-Q10 | parquet / none / none | 5.63   | 6.22        | I -9.53%   |   0.75%   |   0.73%        | 5     | I -10.46%      | -2.31   | -21.37 |
+----------+----------+-----------------------+--------+-------------+------------+-----------+----------------+-------+----------------+---------+--------+

Change-Id: I45ed2dab835efeb64bb74891cb43065894892682
Reviewed-on: http://gerrit.cloudera.org:8080/14381
Reviewed-by: Impala Public Jenkins <impala-public-jenkins@cloudera.com>
Tested-by: Impala Public Jenkins <impala-public-jenkins@cloudera.com>