You are viewing a plain text version of this content. The canonical link for it is here.
Posted to gitbox@hive.apache.org by "rubenada (via GitHub)" <gi...@apache.org> on 2026/05/21 07:06:27 UTC
[PR] HIVE-28911: Improve SEARCH expansion to exploit <> operator [hive]
rubenada opened a new pull request, #6503:
URL: https://github.com/apache/hive/pull/6503
### What changes were proposed in this pull request?
Improve SEARCH expansion to exploit <> operator.
SEARCH operator can be used to represent many types of range predicates including the inequality operator (<>).
For example `d_dom <> 10 and d_dom <> 20` can be represented as `SEARCH($9, Sarg[(-∞..10), (10..20), (20..+∞)])`.
Currently, after SEARCH expansion the following expression will be generated: `OR(<($9, 10), >($9, 20), AND(>($9, 10), <($9, 20)))`; with the proposed change we shall get the original (and simpler) `AND(<>($9, 10), <>($9, 20))`.
### Why are the changes needed?
Exploit the inequality operator when expanding ranges to generate simpler and slightly more efficient expressions.
### Does this PR introduce _any_ user-facing change?
No.
### How was this patch tested?
Unit test added.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
Re: [PR] HIVE-28911: Improve SEARCH expansion to exploit <> operator [hive]
Posted by "sonarqubecloud[bot] (via GitHub)" <gi...@apache.org>.
sonarqubecloud[bot] commented on PR #6503:
URL: https://github.com/apache/hive/pull/6503#issuecomment-4595735152
## [](https://sonarcloud.io/dashboard?id=apache_hive&pullRequest=6503) **Quality Gate passed**
Issues
 [3 New issues](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=6503&issueStatuses=OPEN,CONFIRMED&sinceLeakPeriod=true)
 [0 Accepted issues](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=6503&issueStatuses=ACCEPTED)
Measures
 [0 Security Hotspots](https://sonarcloud.io/project/security_hotspots?id=apache_hive&pullRequest=6503&issueStatuses=OPEN,CONFIRMED&sinceLeakPeriod=true)
 [0.0% Coverage on New Code](https://sonarcloud.io/component_measures?id=apache_hive&pullRequest=6503&metric=new_coverage&view=list)
 [0.0% Duplication on New Code](https://sonarcloud.io/component_measures?id=apache_hive&pullRequest=6503&metric=new_duplicated_lines_density&view=list)
<!-- sqra-placement-anchor -->
[See analysis details on SonarQube Cloud](https://sonarcloud.io/dashboard?id=apache_hive&pullRequest=6503)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
Re: [PR] HIVE-28911: Improve SEARCH expansion to exploit <> operator [hive]
Posted by "sonarqubecloud[bot] (via GitHub)" <gi...@apache.org>.
sonarqubecloud[bot] commented on PR #6503:
URL: https://github.com/apache/hive/pull/6503#issuecomment-4604967458
## [](https://sonarcloud.io/dashboard?id=apache_hive&pullRequest=6503) **Quality Gate passed**
Issues
 [2 New issues](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=6503&issueStatuses=OPEN,CONFIRMED&sinceLeakPeriod=true)
 [0 Accepted issues](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=6503&issueStatuses=ACCEPTED)
Measures
 [0 Security Hotspots](https://sonarcloud.io/project/security_hotspots?id=apache_hive&pullRequest=6503&issueStatuses=OPEN,CONFIRMED&sinceLeakPeriod=true)
 [0.0% Coverage on New Code](https://sonarcloud.io/component_measures?id=apache_hive&pullRequest=6503&metric=new_coverage&view=list)
 [0.0% Duplication on New Code](https://sonarcloud.io/component_measures?id=apache_hive&pullRequest=6503&metric=new_duplicated_lines_density&view=list)
<!-- sqra-placement-anchor -->
[See analysis details on SonarQube Cloud](https://sonarcloud.io/dashboard?id=apache_hive&pullRequest=6503)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
Re: [PR] HIVE-28911: Improve SEARCH expansion to exploit <> operator [hive]
Posted by "zabetak (via GitHub)" <gi...@apache.org>.
zabetak commented on code in PR #6503:
URL: https://github.com/apache/hive/pull/6503#discussion_r3362996283
##########
ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/SearchTransformer.java:
##########
@@ -72,30 +72,44 @@ public SearchTransformer(RexBuilder rexBuilder, RexCall search, final RexUnknown
this.unknownContext = unknownContext;
}
+ /**
+ * Transforms the SEARCH expression into an equivalent RexNode expression.
+ * Warning: when called from a shuttle, callers of this method should consider flattening AND/OR expressions
+ * afterward, to get the same result as applying {@link SearchTransformer.Shuttle}.
+ */
public RexNode transform() {
PerfLogger perfLogger = SessionState.getPerfLogger();
perfLogger.perfLogBegin(this.getClass().getName(), PerfLogger.SEARCH_TRANSFORMER);
- RangeConverter<C> consumer = new RangeConverter<>(rexBuilder, operandType, ref);
- RangeSets.forEach(sarg.rangeSet, consumer);
-
List<RexNode> orList = new ArrayList<>();
if (sarg.nullAs == RexUnknownAs.TRUE && unknownContext != RexUnknownAs.TRUE) {
orList.add(rexBuilder.makeCall(SqlStdOperatorTable.IS_NULL, ref));
}
- switch (consumer.inLiterals.size()) {
- case 0:
- break;
- case 1:
- orList.add(rexBuilder.makeCall(SqlStdOperatorTable.EQUALS, ref, consumer.inLiterals.get(0)));
- break;
- default:
- List<RexNode> operands = new ArrayList<>(consumer.inLiterals.size() + 1);
- operands.add(ref);
- operands.addAll(consumer.inLiterals);
- orList.add(rexBuilder.makeCall(HiveIn.INSTANCE, operands));
+
+ if (sarg.isComplementedPoints()) {
Review Comment:
In fact we could negate the entire sarg (not only the rangeset) if that leads to a simpler more efficient expansion. This would evolve negating the operators (IS NULL, =, IN, etc.), and changing the `orList` into an `andList`.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
Re: [PR] HIVE-28911: Improve SEARCH expansion to exploit <> operator [hive]
Posted by "rubenada (via GitHub)" <gi...@apache.org>.
rubenada commented on code in PR #6503:
URL: https://github.com/apache/hive/pull/6503#discussion_r3363703339
##########
ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/SearchTransformer.java:
##########
@@ -72,30 +72,44 @@ public SearchTransformer(RexBuilder rexBuilder, RexCall search, final RexUnknown
this.unknownContext = unknownContext;
}
+ /**
+ * Transforms the SEARCH expression into an equivalent RexNode expression.
+ * Warning: when called from a shuttle, callers of this method should consider flattening AND/OR expressions
+ * afterward, to get the same result as applying {@link SearchTransformer.Shuttle}.
+ */
public RexNode transform() {
PerfLogger perfLogger = SessionState.getPerfLogger();
perfLogger.perfLogBegin(this.getClass().getName(), PerfLogger.SEARCH_TRANSFORMER);
- RangeConverter<C> consumer = new RangeConverter<>(rexBuilder, operandType, ref);
- RangeSets.forEach(sarg.rangeSet, consumer);
-
List<RexNode> orList = new ArrayList<>();
if (sarg.nullAs == RexUnknownAs.TRUE && unknownContext != RexUnknownAs.TRUE) {
orList.add(rexBuilder.makeCall(SqlStdOperatorTable.IS_NULL, ref));
}
- switch (consumer.inLiterals.size()) {
- case 0:
- break;
- case 1:
- orList.add(rexBuilder.makeCall(SqlStdOperatorTable.EQUALS, ref, consumer.inLiterals.get(0)));
- break;
- default:
- List<RexNode> operands = new ArrayList<>(consumer.inLiterals.size() + 1);
- operands.add(ref);
- operands.addAll(consumer.inLiterals);
- orList.add(rexBuilder.makeCall(HiveIn.INSTANCE, operands));
+
+ if (sarg.isComplementedPoints()) {
Review Comment:
What that would look like? Try systematically the "normal" sarg expansion and the negated one, and pick the "simpler" one?
I guess we could try... but could we consider that a follow-up, separate task, out of the scope of the current PR?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
Re: [PR] HIVE-28911: Improve SEARCH expansion to exploit <> operator [hive]
Posted by "zabetak (via GitHub)" <gi...@apache.org>.
zabetak commented on code in PR #6503:
URL: https://github.com/apache/hive/pull/6503#discussion_r3394322278
##########
ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/SearchTransformer.java:
##########
@@ -72,30 +72,44 @@ public SearchTransformer(RexBuilder rexBuilder, RexCall search, final RexUnknown
this.unknownContext = unknownContext;
}
+ /**
+ * Transforms the SEARCH expression into an equivalent RexNode expression.
+ * Warning: when called from a shuttle, callers of this method should consider flattening AND/OR expressions
+ * afterward, to get the same result as applying {@link SearchTransformer.Shuttle}.
+ */
public RexNode transform() {
PerfLogger perfLogger = SessionState.getPerfLogger();
perfLogger.perfLogBegin(this.getClass().getName(), PerfLogger.SEARCH_TRANSFORMER);
- RangeConverter<C> consumer = new RangeConverter<>(rexBuilder, operandType, ref);
- RangeSets.forEach(sarg.rangeSet, consumer);
-
List<RexNode> orList = new ArrayList<>();
if (sarg.nullAs == RexUnknownAs.TRUE && unknownContext != RexUnknownAs.TRUE) {
orList.add(rexBuilder.makeCall(SqlStdOperatorTable.IS_NULL, ref));
}
- switch (consumer.inLiterals.size()) {
- case 0:
- break;
- case 1:
- orList.add(rexBuilder.makeCall(SqlStdOperatorTable.EQUALS, ref, consumer.inLiterals.get(0)));
- break;
- default:
- List<RexNode> operands = new ArrayList<>(consumer.inLiterals.size() + 1);
- operands.add(ref);
- operands.addAll(consumer.inLiterals);
- orList.add(rexBuilder.makeCall(HiveIn.INSTANCE, operands));
+
+ if (sarg.isComplementedPoints()) {
Review Comment:
Logged https://issues.apache.org/jira/browse/HIVE-29657 for the ideas discussed here.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
Re: [PR] HIVE-28911: Improve SEARCH expansion to exploit <> operator [hive]
Posted by "sonarqubecloud[bot] (via GitHub)" <gi...@apache.org>.
sonarqubecloud[bot] commented on PR #6503:
URL: https://github.com/apache/hive/pull/6503#issuecomment-4544957985
## [](https://sonarcloud.io/dashboard?id=apache_hive&pullRequest=6503) **Quality Gate passed**
Issues
 [1 New issue](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=6503&issueStatuses=OPEN,CONFIRMED&sinceLeakPeriod=true)
 [0 Accepted issues](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=6503&issueStatuses=ACCEPTED)
Measures
 [0 Security Hotspots](https://sonarcloud.io/project/security_hotspots?id=apache_hive&pullRequest=6503&issueStatuses=OPEN,CONFIRMED&sinceLeakPeriod=true)
 [0.0% Coverage on New Code](https://sonarcloud.io/component_measures?id=apache_hive&pullRequest=6503&metric=new_coverage&view=list)
 [0.0% Duplication on New Code](https://sonarcloud.io/component_measures?id=apache_hive&pullRequest=6503&metric=new_duplicated_lines_density&view=list)
<!-- sqra-placement-anchor -->
[See analysis details on SonarQube Cloud](https://sonarcloud.io/dashboard?id=apache_hive&pullRequest=6503)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
Re: [PR] HIVE-28911: Improve SEARCH expansion to exploit <> operator [hive]
Posted by "sonarqubecloud[bot] (via GitHub)" <gi...@apache.org>.
sonarqubecloud[bot] commented on PR #6503:
URL: https://github.com/apache/hive/pull/6503#issuecomment-4546678232
## [](https://sonarcloud.io/dashboard?id=apache_hive&pullRequest=6503) **Quality Gate passed**
Issues
 [1 New issue](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=6503&issueStatuses=OPEN,CONFIRMED&sinceLeakPeriod=true)
 [0 Accepted issues](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=6503&issueStatuses=ACCEPTED)
Measures
 [0 Security Hotspots](https://sonarcloud.io/project/security_hotspots?id=apache_hive&pullRequest=6503&issueStatuses=OPEN,CONFIRMED&sinceLeakPeriod=true)
 [0.0% Coverage on New Code](https://sonarcloud.io/component_measures?id=apache_hive&pullRequest=6503&metric=new_coverage&view=list)
 [0.0% Duplication on New Code](https://sonarcloud.io/component_measures?id=apache_hive&pullRequest=6503&metric=new_duplicated_lines_density&view=list)
<!-- sqra-placement-anchor -->
[See analysis details on SonarQube Cloud](https://sonarcloud.io/dashboard?id=apache_hive&pullRequest=6503)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
Re: [PR] HIVE-28911: Improve SEARCH expansion to exploit <> operator [hive]
Posted by "sonarqubecloud[bot] (via GitHub)" <gi...@apache.org>.
sonarqubecloud[bot] commented on PR #6503:
URL: https://github.com/apache/hive/pull/6503#issuecomment-4600525890
## [](https://sonarcloud.io/dashboard?id=apache_hive&pullRequest=6503) **Quality Gate passed**
Issues
 [7 New issues](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=6503&issueStatuses=OPEN,CONFIRMED&sinceLeakPeriod=true)
 [0 Accepted issues](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=6503&issueStatuses=ACCEPTED)
Measures
 [0 Security Hotspots](https://sonarcloud.io/project/security_hotspots?id=apache_hive&pullRequest=6503&issueStatuses=OPEN,CONFIRMED&sinceLeakPeriod=true)
 [0.0% Coverage on New Code](https://sonarcloud.io/component_measures?id=apache_hive&pullRequest=6503&metric=new_coverage&view=list)
 [0.0% Duplication on New Code](https://sonarcloud.io/component_measures?id=apache_hive&pullRequest=6503&metric=new_duplicated_lines_density&view=list)
<!-- sqra-placement-anchor -->
[See analysis details on SonarQube Cloud](https://sonarcloud.io/dashboard?id=apache_hive&pullRequest=6503)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
Re: [PR] HIVE-28911: Improve SEARCH expansion to exploit <> operator [hive]
Posted by "rubenada (via GitHub)" <gi...@apache.org>.
rubenada commented on code in PR #6503:
URL: https://github.com/apache/hive/pull/6503#discussion_r3363693382
##########
ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/stats/FilterSelectivityEstimator.java:
##########
@@ -628,14 +628,23 @@ private RexNode makeLiteral(C value) {
private double compute() {
final List<RexNode> inLiterals = new ArrayList<>();
final List<Double> rangeSelectivities = new ArrayList<>();
- for (Range<C> range : sarg.rangeSet.asRanges()) {
- if (!range.hasLowerBound() && !range.hasUpperBound()) {
- return 1.0; // "all" range
+ final List<Double> searchSelectivities = new ArrayList<>();
+
+ if (sarg.isComplementedPoints()) {
+ // Generate 'ref <> value1 AND ... AND ref <> valueN'
+ List<RexNode> notEq = sarg.rangeSet.complement().asRanges().stream()
+ .map(range -> rexBuilder.makeCall(SqlStdOperatorTable.NOT_EQUALS, ref, makeLiteral(range.lowerEndpoint())))
+ .toList();
+ searchSelectivities.add(RexUtil.composeConjunction(rexBuilder, notEq).accept(FilterSelectivityEstimator.this));
+ } else {
Review Comment:
Uhmmm... you're right, the original version (which uses histograms) would have a more accurate estimation than the proposed one with NOT_EQUALS (which is estimated simply with ndv-1/ndv , which can be quite off). However, it might be possible that histograms are not available in general (so the original version would default to a hadcoded selectivity), whereas the sub-optimal optimization with NOT_EQUALS uses a more generally available ndv estimated value (and this estimation, although not perfect, would be better than the hardcoded value of the original version).
Having said that, I guess we should try to aim for the better solution, and trust that statistics would be available, so I lean towards reverting the change in this file.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
Re: [PR] HIVE-28911: Improve SEARCH expansion to exploit <> operator [hive]
Posted by "sonarqubecloud[bot] (via GitHub)" <gi...@apache.org>.
sonarqubecloud[bot] commented on PR #6503:
URL: https://github.com/apache/hive/pull/6503#issuecomment-4648978038
## [](https://sonarcloud.io/dashboard?id=apache_hive&pullRequest=6503) **Quality Gate passed**
Issues
 [1 New issue](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=6503&issueStatuses=OPEN,CONFIRMED&sinceLeakPeriod=true)
 [0 Accepted issues](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=6503&issueStatuses=ACCEPTED)
Measures
 [0 Security Hotspots](https://sonarcloud.io/project/security_hotspots?id=apache_hive&pullRequest=6503&issueStatuses=OPEN,CONFIRMED&sinceLeakPeriod=true)
 [0.0% Coverage on New Code](https://sonarcloud.io/component_measures?id=apache_hive&pullRequest=6503&metric=new_coverage&view=list)
 [0.0% Duplication on New Code](https://sonarcloud.io/component_measures?id=apache_hive&pullRequest=6503&metric=new_duplicated_lines_density&view=list)
<!-- sqra-placement-anchor -->
[See analysis details on SonarQube Cloud](https://sonarcloud.io/dashboard?id=apache_hive&pullRequest=6503)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
Re: [PR] HIVE-28911: Improve SEARCH expansion to exploit <> operator [hive]
Posted by "zabetak (via GitHub)" <gi...@apache.org>.
zabetak commented on code in PR #6503:
URL: https://github.com/apache/hive/pull/6503#discussion_r3372441852
##########
ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/SearchTransformer.java:
##########
@@ -72,30 +72,44 @@ public SearchTransformer(RexBuilder rexBuilder, RexCall search, final RexUnknown
this.unknownContext = unknownContext;
}
+ /**
+ * Transforms the SEARCH expression into an equivalent RexNode expression.
+ * Warning: when called from a shuttle, callers of this method should consider flattening AND/OR expressions
+ * afterward, to get the same result as applying {@link SearchTransformer.Shuttle}.
+ */
public RexNode transform() {
PerfLogger perfLogger = SessionState.getPerfLogger();
perfLogger.perfLogBegin(this.getClass().getName(), PerfLogger.SEARCH_TRANSFORMER);
- RangeConverter<C> consumer = new RangeConverter<>(rexBuilder, operandType, ref);
- RangeSets.forEach(sarg.rangeSet, consumer);
-
List<RexNode> orList = new ArrayList<>();
if (sarg.nullAs == RexUnknownAs.TRUE && unknownContext != RexUnknownAs.TRUE) {
orList.add(rexBuilder.makeCall(SqlStdOperatorTable.IS_NULL, ref));
}
- switch (consumer.inLiterals.size()) {
- case 0:
- break;
- case 1:
- orList.add(rexBuilder.makeCall(SqlStdOperatorTable.EQUALS, ref, consumer.inLiterals.get(0)));
- break;
- default:
- List<RexNode> operands = new ArrayList<>(consumer.inLiterals.size() + 1);
- operands.add(ref);
- operands.addAll(consumer.inLiterals);
- orList.add(rexBuilder.makeCall(HiveIn.INSTANCE, operands));
+
+ if (sarg.isComplementedPoints()) {
Review Comment:
Yeap, that's the idea; check both and pick the simpler. In fact, the `sarg.isComplementedPoints` is already doing this in a systematic fashion but I was suggesting to generalize it a bit more.
I am also in favor of doing this in a follow-up (if necessary) and not as part of this PR, which is almost ready to merge.
##########
ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/stats/FilterSelectivityEstimator.java:
##########
@@ -628,14 +628,23 @@ private RexNode makeLiteral(C value) {
private double compute() {
final List<RexNode> inLiterals = new ArrayList<>();
final List<Double> rangeSelectivities = new ArrayList<>();
- for (Range<C> range : sarg.rangeSet.asRanges()) {
- if (!range.hasLowerBound() && !range.hasUpperBound()) {
- return 1.0; // "all" range
+ final List<Double> searchSelectivities = new ArrayList<>();
+
+ if (sarg.isComplementedPoints()) {
+ // Generate 'ref <> value1 AND ... AND ref <> valueN'
+ List<RexNode> notEq = sarg.rangeSet.complement().asRanges().stream()
+ .map(range -> rexBuilder.makeCall(SqlStdOperatorTable.NOT_EQUALS, ref, makeLiteral(range.lowerEndpoint())))
+ .toList();
+ searchSelectivities.add(RexUtil.composeConjunction(rexBuilder, notEq).accept(FilterSelectivityEstimator.this));
+ } else {
Review Comment:
> However, it might be possible that histograms are not available in general...
When histograms are not available then I guess all the following ranges are gonna fall to the hard-coded default selectivity:
```
SEARCH($0, Sarg[(50..100)])
SEARCH($0, Sarg[(50..100]])
SEARCH($0, Sarg[[50..100)])
SEARCH($0, Sarg[[50..100]])
SEARCH($0, Sarg[[50..+∞)])
SEARCH($0, Sarg[(-∞..100]])
...
```
However, if we have more stats available (i.e., NDV, min, max, null counts) for column `$0` then possibly we could return something more accurate than `1/3` (or `selDisjuction(1/3, 1/3)`) even though histograms are missing. If we implement this improvement then also `SEARCH` expressions with complemented points (such as the one below) could benefit for better selectivities.
```
SEARCH($0, Sarg[(-∞..10), (10..20), (20..30), (30, +∞)])
```
Estimates are not the main focus of this PR so I would be fine to keep the code simpler at this stage and log another JIRA ticket for targeting the bigger problem "Improve range selectivity estimations in the absence of histograms".
Another caveat is that if we have a large complement then we are going to perform a potentially expensive check + transform + tree traversal just for the purpose of selectivity that may be quite off and may not worth it overall.
For the above, I am also leaning towards reverting the change for the time being.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
Re: [PR] HIVE-28911: Improve SEARCH expansion to exploit <> operator [hive]
Posted by "sonarqubecloud[bot] (via GitHub)" <gi...@apache.org>.
sonarqubecloud[bot] commented on PR #6503:
URL: https://github.com/apache/hive/pull/6503#issuecomment-4510050811
## [](https://sonarcloud.io/dashboard?id=apache_hive&pullRequest=6503) **Quality Gate passed**
Issues
 [1 New issue](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=6503&issueStatuses=OPEN,CONFIRMED&sinceLeakPeriod=true)
 [0 Accepted issues](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=6503&issueStatuses=ACCEPTED)
Measures
 [0 Security Hotspots](https://sonarcloud.io/project/security_hotspots?id=apache_hive&pullRequest=6503&issueStatuses=OPEN,CONFIRMED&sinceLeakPeriod=true)
 [0.0% Coverage on New Code](https://sonarcloud.io/component_measures?id=apache_hive&pullRequest=6503&metric=new_coverage&view=list)
 [0.0% Duplication on New Code](https://sonarcloud.io/component_measures?id=apache_hive&pullRequest=6503&metric=new_duplicated_lines_density&view=list)
<!-- sqra-placement-anchor -->
[See analysis details on SonarQube Cloud](https://sonarcloud.io/dashboard?id=apache_hive&pullRequest=6503)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
Re: [PR] HIVE-28911: Improve SEARCH expansion to exploit <> operator [hive]
Posted by "zabetak (via GitHub)" <gi...@apache.org>.
zabetak commented on code in PR #6503:
URL: https://github.com/apache/hive/pull/6503#discussion_r3356327939
##########
ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/stats/FilterSelectivityEstimator.java:
##########
@@ -628,14 +628,23 @@ private RexNode makeLiteral(C value) {
private double compute() {
final List<RexNode> inLiterals = new ArrayList<>();
final List<Double> rangeSelectivities = new ArrayList<>();
- for (Range<C> range : sarg.rangeSet.asRanges()) {
- if (!range.hasLowerBound() && !range.hasUpperBound()) {
- return 1.0; // "all" range
+ final List<Double> searchSelectivities = new ArrayList<>();
+
+ if (sarg.isComplementedPoints()) {
+ // Generate 'ref <> value1 AND ... AND ref <> valueN'
+ List<RexNode> notEq = sarg.rangeSet.complement().asRanges().stream()
+ .map(range -> rexBuilder.makeCall(SqlStdOperatorTable.NOT_EQUALS, ref, makeLiteral(range.lowerEndpoint())))
+ .toList();
+ searchSelectivities.add(RexUtil.composeConjunction(rexBuilder, notEq).accept(FilterSelectivityEstimator.this));
+ } else {
Review Comment:
Does this form lead to better selectivity estimates than what we had before? If not then we don't necessarily need to change it. The purpose of this code is to compute a good selectivity for the SEARCH predicate not to transform it to something else.
##########
ql/src/java/org/apache/hadoop/hive/ql/optimizer/calcite/SearchTransformer.java:
##########
@@ -72,30 +72,44 @@ public SearchTransformer(RexBuilder rexBuilder, RexCall search, final RexUnknown
this.unknownContext = unknownContext;
}
+ /**
+ * Transforms the SEARCH expression into an equivalent RexNode expression.
+ * Warning: when called from a shuttle, callers of this method should consider flattening AND/OR expressions
+ * afterward, to get the same result as applying {@link SearchTransformer.Shuttle}.
+ */
public RexNode transform() {
PerfLogger perfLogger = SessionState.getPerfLogger();
perfLogger.perfLogBegin(this.getClass().getName(), PerfLogger.SEARCH_TRANSFORMER);
- RangeConverter<C> consumer = new RangeConverter<>(rexBuilder, operandType, ref);
- RangeSets.forEach(sarg.rangeSet, consumer);
-
List<RexNode> orList = new ArrayList<>();
if (sarg.nullAs == RexUnknownAs.TRUE && unknownContext != RexUnknownAs.TRUE) {
orList.add(rexBuilder.makeCall(SqlStdOperatorTable.IS_NULL, ref));
}
- switch (consumer.inLiterals.size()) {
- case 0:
- break;
- case 1:
- orList.add(rexBuilder.makeCall(SqlStdOperatorTable.EQUALS, ref, consumer.inLiterals.get(0)));
- break;
- default:
- List<RexNode> operands = new ArrayList<>(consumer.inLiterals.size() + 1);
- operands.add(ref);
- operands.addAll(consumer.inLiterals);
- orList.add(rexBuilder.makeCall(HiveIn.INSTANCE, operands));
+
+ if (sarg.isComplementedPoints()) {
Review Comment:
When the sarg is not strictly a complement then I guess we cannot handle it. Examples:
```sql
... WHERE NOT ( x = 10 OR x = 20 OR (x > 30 AND x < 50))
... WHERE (x <> 10 AND x <> 20 AND (x <= 30 OR x >= 50))
```
One way to cover those would be to apply the existing `RangeConverter` on `sarg.rangeSet.complement()` and invert the EQUALS and HiveIn operators in the switch. The challenge here is when to use the `sarg.rangeSet` and when its complement. A naive choice could be to base the decision on `sarg.rangeSet.asRanges().size()` or something along these lines.
Anyways, the change here is fine as it is so we can log a another ticket and follow-up there if its worth to do it or not.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
Re: [PR] HIVE-28911: Improve SEARCH expansion to exploit <> operator [hive]
Posted by "zabetak (via GitHub)" <gi...@apache.org>.
zabetak merged PR #6503:
URL: https://github.com/apache/hive/pull/6503
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
Re: [PR] HIVE-28911: Improve SEARCH expansion to exploit <> operator [hive]
Posted by "rubenada (via GitHub)" <gi...@apache.org>.
rubenada closed pull request #6503: HIVE-28911: Improve SEARCH expansion to exploit <> operator
URL: https://github.com/apache/hive/pull/6503
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
Re: [PR] HIVE-28911: Improve SEARCH expansion to exploit <> operator [hive]
Posted by "sonarqubecloud[bot] (via GitHub)" <gi...@apache.org>.
sonarqubecloud[bot] commented on PR #6503:
URL: https://github.com/apache/hive/pull/6503#issuecomment-4594169533
## [](https://sonarcloud.io/dashboard?id=apache_hive&pullRequest=6503) **Quality Gate passed**
Issues
 [3 New issues](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=6503&issueStatuses=OPEN,CONFIRMED&sinceLeakPeriod=true)
 [0 Accepted issues](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=6503&issueStatuses=ACCEPTED)
Measures
 [0 Security Hotspots](https://sonarcloud.io/project/security_hotspots?id=apache_hive&pullRequest=6503&issueStatuses=OPEN,CONFIRMED&sinceLeakPeriod=true)
 [0.0% Coverage on New Code](https://sonarcloud.io/component_measures?id=apache_hive&pullRequest=6503&metric=new_coverage&view=list)
 [0.0% Duplication on New Code](https://sonarcloud.io/component_measures?id=apache_hive&pullRequest=6503&metric=new_duplicated_lines_density&view=list)
<!-- sqra-placement-anchor -->
[See analysis details on SonarQube Cloud](https://sonarcloud.io/dashboard?id=apache_hive&pullRequest=6503)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
Re: [PR] HIVE-28911: Improve SEARCH expansion to exploit <> operator [hive]
Posted by "sonarqubecloud[bot] (via GitHub)" <gi...@apache.org>.
sonarqubecloud[bot] commented on PR #6503:
URL: https://github.com/apache/hive/pull/6503#issuecomment-4525912544
## [](https://sonarcloud.io/dashboard?id=apache_hive&pullRequest=6503) **Quality Gate passed**
Issues
 [1 New issue](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=6503&issueStatuses=OPEN,CONFIRMED&sinceLeakPeriod=true)
 [0 Accepted issues](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=6503&issueStatuses=ACCEPTED)
Measures
 [0 Security Hotspots](https://sonarcloud.io/project/security_hotspots?id=apache_hive&pullRequest=6503&issueStatuses=OPEN,CONFIRMED&sinceLeakPeriod=true)
 [0.0% Coverage on New Code](https://sonarcloud.io/component_measures?id=apache_hive&pullRequest=6503&metric=new_coverage&view=list)
 [0.0% Duplication on New Code](https://sonarcloud.io/component_measures?id=apache_hive&pullRequest=6503&metric=new_duplicated_lines_density&view=list)
<!-- sqra-placement-anchor -->
[See analysis details on SonarQube Cloud](https://sonarcloud.io/dashboard?id=apache_hive&pullRequest=6503)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
Re: [PR] HIVE-28911: Improve SEARCH expansion to exploit <> operator [hive]
Posted by "sonarqubecloud[bot] (via GitHub)" <gi...@apache.org>.
sonarqubecloud[bot] commented on PR #6503:
URL: https://github.com/apache/hive/pull/6503#issuecomment-4506317122
## [](https://sonarcloud.io/dashboard?id=apache_hive&pullRequest=6503) **Quality Gate passed**
Issues
 [6 New issues](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=6503&issueStatuses=OPEN,CONFIRMED&sinceLeakPeriod=true)
 [0 Accepted issues](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=6503&issueStatuses=ACCEPTED)
Measures
 [0 Security Hotspots](https://sonarcloud.io/project/security_hotspots?id=apache_hive&pullRequest=6503&issueStatuses=OPEN,CONFIRMED&sinceLeakPeriod=true)
 [0.0% Coverage on New Code](https://sonarcloud.io/component_measures?id=apache_hive&pullRequest=6503&metric=new_coverage&view=list)
 [1.3% Duplication on New Code](https://sonarcloud.io/component_measures?id=apache_hive&pullRequest=6503&metric=new_duplicated_lines_density&view=list)
<!-- sqra-placement-anchor -->
[See analysis details on SonarQube Cloud](https://sonarcloud.io/dashboard?id=apache_hive&pullRequest=6503)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
Re: [PR] HIVE-28911: Improve SEARCH expansion to exploit <> operator [hive]
Posted by "rubenada (via GitHub)" <gi...@apache.org>.
rubenada commented on PR #6503:
URL: https://github.com/apache/hive/pull/6503#issuecomment-4648227607
Thanks for the review @zabetak .
As agreed, I have reverted the changes in FilterSelectivityEstimator, and created ticket 29652 to address the potential improvements of range selectivity estimations in the absence of histograms.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
Re: [PR] HIVE-28911: Improve SEARCH expansion to exploit <> operator [hive]
Posted by "sonarqubecloud[bot] (via GitHub)" <gi...@apache.org>.
sonarqubecloud[bot] commented on PR #6503:
URL: https://github.com/apache/hive/pull/6503#issuecomment-4591823355
## [](https://sonarcloud.io/dashboard?id=apache_hive&pullRequest=6503) **Quality Gate passed**
Issues
 [3 New issues](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=6503&issueStatuses=OPEN,CONFIRMED&sinceLeakPeriod=true)
 [0 Accepted issues](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=6503&issueStatuses=ACCEPTED)
Measures
 [0 Security Hotspots](https://sonarcloud.io/project/security_hotspots?id=apache_hive&pullRequest=6503&issueStatuses=OPEN,CONFIRMED&sinceLeakPeriod=true)
 [0.0% Coverage on New Code](https://sonarcloud.io/component_measures?id=apache_hive&pullRequest=6503&metric=new_coverage&view=list)
 [0.0% Duplication on New Code](https://sonarcloud.io/component_measures?id=apache_hive&pullRequest=6503&metric=new_duplicated_lines_density&view=list)
<!-- sqra-placement-anchor -->
[See analysis details on SonarQube Cloud](https://sonarcloud.io/dashboard?id=apache_hive&pullRequest=6503)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org