You are viewing a plain text version of this content. The canonical link for it is here.

Posted to reviews@impala.apache.org by "fifteencai (Code Review)" <ge...@cloudera.org> on 2021/04/12 13:28:16 UTC

[Impala-ASF-CR] IMPALA-10445: Adjust NDV's precision/scale by query option

fifteencai has uploaded this change for review. ( http://gerrit.cloudera.org:8080/17306


Change subject: IMPALA-10445: Adjust NDV's precision/scale by query option
......................................................................

IMPALA-10445: Adjust NDV's precision/scale by query option

In this commit, we introduced a new Query Option to control NDV's default HyperLogLog scale.

Since IMPALA-2658, we can trade additional memory for more accurate estimation by setting larger `scale`.
The scale is decided by SQL writers. However, it is a bumpy road to smoothly upgrade ndv by setting
scales larger than the default value of 2. Here lies 2 reasons, firstly, SQL writers are reluctant to
lower expectations, they prone to write ndv(id, 10) other than ndv(id, 9), ndv(id, 8) and so on. But
larger scales like 10 will use much more memories, especially when there are `group by`s with high
cardinality. So it is wiser to let cluster admin to choose appropriate scale instead. Secondly, The
queries are stored in a BI tool's configuration DB. Rewriting thousands of SQLs is a risky job.

In this commit, we introduced a new Query Option `DEFAULT_NDV_SCALE`. During to its runtime essence, We
can either set it before query submission according to cluster's overall load, or set it by placing a
default query option for dynamic resource pool.

We also modified the `Analyzer` to make sure APPX_COUNT_DISTINCT works with this query option. So if
needed, we can degrade the service by transforming `count (distinct id)` to `ndv(id, scale)`.

Implementation details:

- The default value of DEFAULT_NDV_SCALE is 2, so we won't change the default ndv behavior.
- We port `CountDistinctToNdv` transform logic from `SelectStmt.analyze()` to `ExprRewriter`, making
it compatible with further rewrite rules.
- The newly added rewrite rule `DefaultNdvScaleRule` is applied after `CountDistinctToNdvRule`.

Usage:

To set a default ndv scale:
```
SET DEFAULT_NDV_SCALE = 10;  -- The range is [1, 10]
```

To unset:
```
SET DEFAULT_NDV_SCALE = 2;
```

Here are test results of a typical workload (cardinality = 40,090,650):
+=====================================================================+
|   Metric    | Count Distinct |    NDV2    |    NDV5    |    NDV10   |
+---------------------------------------------------------------------+
|  Memory(GB) |       3.83     |    1.84    |    1.85    |     1.89   |
| Duration(s) |      182.89    |   30.22    |    29.72   |     29.24  |
|  ErrorRate  |        0%      |    1.8%    |    1.17%   |     0.06%  |
+=====================================================================+

Testing:
1) Added 3 unit test cases in `ExprRewriteRulesTest`.
2) Added 5 unit test cases in `ExprRewriterTest`.
3) Ran all front-end unit test, passed.
4) Added a new query-option test.

Change-Id: I1669858a6e8252e167b464586e8d0b6cb0d0bd50
---
M be/src/service/query-options-test.cc
M be/src/service/query-options.cc
M be/src/service/query-options.h
M common/thrift/ImpalaService.thrift
M common/thrift/Query.thrift
M fe/src/main/java/org/apache/impala/analysis/Analyzer.java
M fe/src/main/java/org/apache/impala/analysis/SelectStmt.java
A fe/src/main/java/org/apache/impala/rewrite/CountDistinctToNdvRule.java
A fe/src/main/java/org/apache/impala/rewrite/DefaultNdvScaleRule.java
M fe/src/test/java/org/apache/impala/analysis/ExprRewriteRulesTest.java
M fe/src/test/java/org/apache/impala/analysis/ExprRewriterTest.java
11 files changed, 190 insertions(+), 34 deletions(-)



  git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/06/17306/1
-- 
To view, visit http://gerrit.cloudera.org:8080/17306
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newchange
Gerrit-Change-Id: I1669858a6e8252e167b464586e8d0b6cb0d0bd50
Gerrit-Change-Number: 17306
Gerrit-PatchSet: 1
Gerrit-Owner: fifteencai <fi...@tencent.com>

[Impala-ASF-CR] IMPALA-10445: Adjust NDV's scale with query option

Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.

Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/17306 )

Change subject: IMPALA-10445: Adjust NDV's scale with query option
......................................................................


Patch Set 15:

Build Successful 

https://jenkins.impala.io/job/gerrit-code-review-checks/8577/ : Initial code review checks passed. Use gerrit-verify-dryrun-external or gerrit-verify-dryrun to run full precommit tests.


-- 
To view, visit http://gerrit.cloudera.org:8080/17306
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I1669858a6e8252e167b464586e8d0b6cb0d0bd50
Gerrit-Change-Number: 17306
Gerrit-PatchSet: 15
Gerrit-Owner: fifteencai <fi...@tencent.com>
Gerrit-Reviewer: Aman Sinha <am...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Qifan Chen <qc...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: fifteencai <fi...@tencent.com>
Gerrit-Comment-Date: Wed, 14 Apr 2021 14:50:25 +0000
Gerrit-HasComments: No

[Impala-ASF-CR] IMPALA-10445: Adjust NDV's scale with query option

Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.

Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/17306 )

Change subject: IMPALA-10445: Adjust NDV's scale with query option
......................................................................


Patch Set 17: Code-Review+2


-- 
To view, visit http://gerrit.cloudera.org:8080/17306
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I1669858a6e8252e167b464586e8d0b6cb0d0bd50
Gerrit-Change-Number: 17306
Gerrit-PatchSet: 17
Gerrit-Owner: fifteencai <fi...@tencent.com>
Gerrit-Reviewer: Aman Sinha <am...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Qifan Chen <qc...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: fifteencai <fi...@tencent.com>
Gerrit-Comment-Date: Wed, 21 Apr 2021 03:01:44 +0000
Gerrit-HasComments: No

[Impala-ASF-CR] IMPALA-10445: Adjust NDV's scale with query option

Posted by "fifteencai (Code Review)" <ge...@cloudera.org>.

fifteencai has posted comments on this change. ( http://gerrit.cloudera.org:8080/17306 )

Change subject: IMPALA-10445: Adjust NDV's scale with query option
......................................................................


Patch Set 15:

Resolved assert problem in newly added unit tests.


-- 
To view, visit http://gerrit.cloudera.org:8080/17306
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I1669858a6e8252e167b464586e8d0b6cb0d0bd50
Gerrit-Change-Number: 17306
Gerrit-PatchSet: 15
Gerrit-Owner: fifteencai <fi...@tencent.com>
Gerrit-Reviewer: Aman Sinha <am...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Qifan Chen <qc...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: fifteencai <fi...@tencent.com>
Gerrit-Comment-Date: Wed, 14 Apr 2021 15:18:07 +0000
Gerrit-HasComments: No

[Impala-ASF-CR] IMPALA-10445: Adjust NDV's scale with query option

Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.

Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/17306 )

Change subject: IMPALA-10445: Adjust NDV's scale with query option
......................................................................


Patch Set 17:

Build started: https://jenkins.impala.io/job/gerrit-verify-dryrun/7088/ DRY_RUN=false


-- 
To view, visit http://gerrit.cloudera.org:8080/17306
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I1669858a6e8252e167b464586e8d0b6cb0d0bd50
Gerrit-Change-Number: 17306
Gerrit-PatchSet: 17
Gerrit-Owner: fifteencai <fi...@tencent.com>
Gerrit-Reviewer: Aman Sinha <am...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Qifan Chen <qc...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: fifteencai <fi...@tencent.com>
Gerrit-Comment-Date: Wed, 21 Apr 2021 03:01:45 +0000
Gerrit-HasComments: No

[Impala-ASF-CR] IMPALA-10445: Adjust NDV's scale with query option

Posted by "fifteencai (Code Review)" <ge...@cloudera.org>.

fifteencai has uploaded a new patch set (#14). ( http://gerrit.cloudera.org:8080/17306 )

Change subject: IMPALA-10445: Adjust NDV's scale with query option
......................................................................

IMPALA-10445: Adjust NDV's scale with query option

This is a new way to control NDV's scale.

Since IMPALA-2658, we can trade memory for more accurate
estimation by setting larger `scale` in SQL function
NDV(<expr>, <scale>). However the use of larger NDV scale requires
the modification of SQL queries which may not be practical in certain
applications:

- Firstly, SQL writers are reluctant to lower that scale. They prone
to fill up the scale, which will make the cluster unstable. Especially
when there are `group by`s with high cardinalities. So it is wiser to
let cluster admin other than sql writer choose appropriate scale.

- Secondly, In some application scenarios, queries are stored in DBs.
In a BI system, for example, rewriting thousands of SQLs is risky.

In this commit, we introduced a new Query Option `DEFAULT_NDV_SCALE`
with the following semantics:

1. The allowed value is in the range [1..10];
2. Previously, the scale used in NDV(<expr>) functions was fixed at 2.
Now the scale is provided by the newly added query options.
3. It does not influence the NDV scale for SQL function
NDV(<expr>, <scale>) in which the NDV scale is provided by the 2nd
argument <scale>.

We also refactored method `Analyze` to make sure APPX_COUNT_DISTINCT
can work with this query option. After this, cluster admins can
substitute `count(distinct <expr>)` with `ndv(<expr>, scale)`.

Implementation details:

- The default value of DEFAULT_NDV_SCALE is 2, so we won't change
the default ndv behavior.
- We port `CountDistinctToNdv` transform logic from
`SelectStmt.analyze()` to `ExprRewriter`, making it compatible with
further rewrite rules.
- The newly added rewrite rule `DefaultNdvScaleRule` is applied
after `CountDistinctToNdvRule`.

Usage:

To set a default ndv scale:
```
SET DEFAULT_NDV_SCALE = 10;
```

To unset:
```
SET DEFAULT_NDV_SCALE = 2;
```

Here are test results of a typical workload (cardinality=40,090,650):
+====================================================================+
|   Metric    | Count Distinct |    NDV2    |    NDV5    |    NDV10  |
+--------------------------------------------------------------------+
|  Memory(GB) |       3.83     |    1.84    |    1.85    |     1.89  |
| Duration(s) |      182.89    |   30.22    |    29.72   |     29.24 |
|  ErrorRate  |        0%      |    1.8%    |    1.17%   |     0.06% |
+====================================================================+

Testing:
1) Added 3 unit test cases in `ExprRewriteRulesTest`.
2) Added 5 unit test cases in `ExprRewriterTest`.
3) Ran all front-end unit test, passed.
4) Added a new query-option test.

Change-Id: I1669858a6e8252e167b464586e8d0b6cb0d0bd50
---
M be/src/service/query-options-test.cc
M be/src/service/query-options.cc
M be/src/service/query-options.h
M common/thrift/ImpalaService.thrift
M common/thrift/Query.thrift
M fe/src/main/java/org/apache/impala/analysis/Analyzer.java
M fe/src/main/java/org/apache/impala/analysis/SelectStmt.java
A fe/src/main/java/org/apache/impala/rewrite/CountDistinctToNdvRule.java
A fe/src/main/java/org/apache/impala/rewrite/DefaultNdvScaleRule.java
M fe/src/test/java/org/apache/impala/analysis/ExprRewriteRulesTest.java
M fe/src/test/java/org/apache/impala/analysis/ExprRewriterTest.java
11 files changed, 312 insertions(+), 34 deletions(-)


  git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/06/17306/14
-- 
To view, visit http://gerrit.cloudera.org:8080/17306
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I1669858a6e8252e167b464586e8d0b6cb0d0bd50
Gerrit-Change-Number: 17306
Gerrit-PatchSet: 14
Gerrit-Owner: fifteencai <fi...@tencent.com>
Gerrit-Reviewer: Aman Sinha <am...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Qifan Chen <qc...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: fifteencai <fi...@tencent.com>

[Impala-ASF-CR] IMPALA-10445: Adjust NDV's scale with query option

Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.

Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/17306 )

Change subject: IMPALA-10445: Adjust NDV's scale with query option
......................................................................


Patch Set 11:

Build Failed 

https://jenkins.impala.io/job/gerrit-code-review-checks/8570/ : Initial code review checks failed. See linked job for details on the failure.


-- 
To view, visit http://gerrit.cloudera.org:8080/17306
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I1669858a6e8252e167b464586e8d0b6cb0d0bd50
Gerrit-Change-Number: 17306
Gerrit-PatchSet: 11
Gerrit-Owner: fifteencai <fi...@tencent.com>
Gerrit-Reviewer: Aman Sinha <am...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Qifan Chen <qc...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: fifteencai <fi...@tencent.com>
Gerrit-Comment-Date: Wed, 14 Apr 2021 08:15:09 +0000
Gerrit-HasComments: No

[Impala-ASF-CR] IMPALA-10445: Adjust NDV's scale with query option

Posted by "Qifan Chen (Code Review)" <ge...@cloudera.org>.

Qifan Chen has posted comments on this change. ( http://gerrit.cloudera.org:8080/17306 )

Change subject: IMPALA-10445: Adjust NDV's scale with query option
......................................................................


Patch Set 9:

(6 comments)

Looks good to me!

http://gerrit.cloudera.org:8080/#/c/17306/9//COMMIT_MSG
Commit Message:

http://gerrit.cloudera.org:8080/#/c/17306/9//COMMIT_MSG@12
PS9, Line 12: estimation by setting larger `scale`. That scale is decided by SQL
in SQL function NDV(<expr>, <scale>)


http://gerrit.cloudera.org:8080/#/c/17306/9//COMMIT_MSG@11
PS9, Line 11: Since IMPALA-2658, we can trade memory for more accurate
            : estimation by setting larger `scale`. That scale is decided by SQL
            : writers. However, it is a bumpy road for cluster admins to allow for
            : larger scales. Here lies 2 reasons:
May rewrite the sentence as follows.

Since IMPALA-2658, we can trade memory for more accurate
estimation by setting larger NDV scale in SQL function NDV(<expr>, <scale>). However, the use of larger NDV scale requires the modification of the NDV function in queries which may not be practical in certain applications.


http://gerrit.cloudera.org:8080/#/c/17306/9//COMMIT_MSG@24
PS9, Line 24: In this commit, we introduced a new Query Option `DEFAULT_NDV_SCALE`.
            : During to the advantage of query option, Cluster admins can either tune
            : 1 desired query, or influence upcoming queries by placing a default
            : query option in a dynamic resource pool.
This paragraph can be rewritten as follows.

In this commit, we introduced a new Query Option `DEFAULT_NDV_SCALE` with the following semantics.

1. The allowed value is in the range [2..10];
2. The value of the query option is the default NDV scale for the SQL function of form NDV(<expr>). Previously, the NDV scale used in such functions is fixed at 2;
3. It does not influence the NDV scale for SQL function NDV(<expr>, <scale>) in which the NDV scale is provided by the 2nd argument <scale>.


http://gerrit.cloudera.org:8080/#/c/17306/9/common/thrift/ImpalaService.thrift
File common/thrift/ImpalaService.thrift:

http://gerrit.cloudera.org:8080/#/c/17306/9/common/thrift/ImpalaService.thrift@655
PS9, Line 655: , make it easier to change NDV's scale
may change to " to SQL NDV function NDV(<expr>.


http://gerrit.cloudera.org:8080/#/c/17306/9/fe/src/main/java/org/apache/impala/rewrite/CountDistinctToNdvRule.java
File fe/src/main/java/org/apache/impala/rewrite/CountDistinctToNdvRule.java:

http://gerrit.cloudera.org:8080/#/c/17306/9/fe/src/main/java/org/apache/impala/rewrite/CountDistinctToNdvRule.java@58
PS9, Line 58: Do function name substitution
Probably should say "Create the substituted form".


http://gerrit.cloudera.org:8080/#/c/17306/9/fe/src/main/java/org/apache/impala/rewrite/DefaultNdvScaleRule.java
File fe/src/main/java/org/apache/impala/rewrite/DefaultNdvScaleRule.java:

http://gerrit.cloudera.org:8080/#/c/17306/9/fe/src/main/java/org/apache/impala/rewrite/DefaultNdvScaleRule.java@38
PS9, Line 38: DefaultNdvScaleRule
I wonder if this rule can be merged to the CountDistinctToNdvRule. That is, if APPX_COUNT_DISTINCT query option is set, we fire that rule. Within that rule, we check for query option DEFAULT_NDV_SCALE and form NDV() function in two ways: NDV(<expr>) if the value of DEFAULT_NDV_SCALE is 2, or NDV(<expr>, <scale>) otherwise.



-- 
To view, visit http://gerrit.cloudera.org:8080/17306
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I1669858a6e8252e167b464586e8d0b6cb0d0bd50
Gerrit-Change-Number: 17306
Gerrit-PatchSet: 9
Gerrit-Owner: fifteencai <fi...@tencent.com>
Gerrit-Reviewer: Aman Sinha <am...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Qifan Chen <qc...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Comment-Date: Tue, 13 Apr 2021 17:40:26 +0000
Gerrit-HasComments: Yes

[Impala-ASF-CR] IMPALA-10445: Adjust NDV's scale with query option

Posted by "fifteencai (Code Review)" <ge...@cloudera.org>.

fifteencai has posted comments on this change. ( http://gerrit.cloudera.org:8080/17306 )

Change subject: IMPALA-10445: Adjust NDV's scale with query option
......................................................................


Patch Set 16:

Hi, Can we merge this patch now?


-- 
To view, visit http://gerrit.cloudera.org:8080/17306
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I1669858a6e8252e167b464586e8d0b6cb0d0bd50
Gerrit-Change-Number: 17306
Gerrit-PatchSet: 16
Gerrit-Owner: fifteencai <fi...@tencent.com>
Gerrit-Reviewer: Aman Sinha <am...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Qifan Chen <qc...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: fifteencai <fi...@tencent.com>
Gerrit-Comment-Date: Wed, 21 Apr 2021 01:03:51 +0000
Gerrit-HasComments: No