You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@impala.apache.org by st...@apache.org on 2026/08/20 09:10:44 UTC
(impala) branch master updated: IMPALA-15127: Support HBO for UnionNode cardinality
This is an automated email from the ASF dual-hosted git repository.
asf-gitbox-commits pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/impala.git
The following commit(s) were added to refs/heads/master by this push:
new eab0a04de IMPALA-15127: Support HBO for UnionNode cardinality
eab0a04de is described below
commit eab0a04de5ea7674173ca08ef55e2ef7a6701a50
Author: stiga-huang <hu...@gmail.com>
AuthorDate: Fri Jun 26 08:59:50 2026 +0800
IMPALA-15127: Support HBO for UnionNode cardinality
This extends HBO to support tracking and using cardinality of
UnionNodes. Only FE changes are needed.
HBO Key String
--------------
The HBO key string of a UnionNode consits of the optional LIMIT, the
canonicalized const operands, and the key strings of its children.
To make the HBO key string consistent for different operand orders,
the children are sorted by their concatenated and sorted scan table
names. E.g. an operand with only one table scan in its subtree uses the
table name as the sort key, an operand with multiple table scans uses a
sort key like "tbl1,tbl2,tbl3".
In case when two operands have the same set of table scans, we use the
original order in query for simplicity. Another query that flips their
order will have a different HBO key, which misses the HBO stats. Such
cases are rare in practice, so we keep them unoptimized.
Historical Runs Matching
------------------------
If the HBO key strings match, we pick one from the list of historical
runs corresponding to that key.
UnionNode is the first HBO-supported node type that has multiple
children so we need to extend the existing matching mechanism to
supports matching multiple scan nodes.
Each UnionNode collects all the leaf scan input stats inside its subtree
in pre-order traversal. The order of visiting its children is the same
as the operand order used in the HBO key string.
While matching a historical run, element-wise comparison of all
TScanInputStats entries is performed to ensure they are similar
respectively. Take the following UnionNode runs as an example. The
children (sorted) are ScanNodes A, B, C.
UnionNode UnionNode
/ | \ / | \
A B C A' B' C'
The matching requires similar(A, A') && similar(B, B') && similar(C, C').
Similarity of a scan node pair is checked in the following way:
- If both sides have valid input_rows (come from HMS numRows stats),
compare row count.
- If either input_rows is missing,
- For EXPR_REWRITE, an exact catalog version match means similar.
if catalog versions differ, compare input file sizes.
- For other strategies, catalog version is not a reliable signal,
so compare input file sizes only.
Note that the hash key matching already ensures table names and
conjuncts are matched. It's done before finding the historical run so we
don't need to compare table names or conjuncts here.
For UnionNodes that have only constant operands, there are no scan input
stats. The corresponding HBO value list will have at most one item since
the HBO key matching already ensures the constants are identical.
Testing
- Added FE tests for HBO key strings.
- Added FE tests to matching historical runs.
- Added e2e tests on all UNION types.
Assisted-by: Opus 4.8 (Claude Code)
Change-Id: Ie228f530bdcb171d3b717966673164bf9a4c45c8
Reviewed-on: http://gerrit.cloudera.org:8080/24556
Reviewed-by: Impala Public Jenkins <im...@cloudera.com>
Tested-by: Impala Public Jenkins <im...@cloudera.com>
---
.../org/apache/impala/planner/AggregationNode.java | 1 +
.../impala/planner/CanonicalizationStrategy.java | 11 ++
.../apache/impala/planner/ExprCanonicalizer.java | 12 ++
.../java/org/apache/impala/planner/PlanNode.java | 39 ++++-
.../java/org/apache/impala/planner/ScanNode.java | 8 +
.../java/org/apache/impala/planner/UnionNode.java | 66 ++++++++
.../org/apache/impala/service/HistoricalStats.java | 158 ++++++++---------
.../apache/impala/planner/HboKeyStringTest.java | 188 ++++++++++++++++++++-
.../apache/impala/service/HistoricalStatsTest.java | 180 ++++++++++++++++++++
.../QueryTest/hbo-union-collection-scan.test | 49 ++++++
.../queries/QueryTest/hbo-union-consts.test | 26 +++
.../queries/QueryTest/hbo-union-same-tables.test | 55 ++++++
.../queries/QueryTest/hbo-union.test | 118 +++++++++++++
tests/query_test/test_hbo.py | 36 ++++
14 files changed, 853 insertions(+), 94 deletions(-)
diff --git a/fe/src/main/java/org/apache/impala/planner/AggregationNode.java b/fe/src/main/java/org/apache/impala/planner/AggregationNode.java
index 80c9144cc..15ff2c609 100644
--- a/fe/src/main/java/org/apache/impala/planner/AggregationNode.java
+++ b/fe/src/main/java/org/apache/impala/planner/AggregationNode.java
@@ -842,6 +842,7 @@ public class AggregationNode extends PlanNode implements SpillableOperator {
.append("|groupingSet:")
.append(multiAggInfo_.getIsGroupingSet())
.append("|");
+ if (limit_ > 0) sb.append("limit:").append(limit_).append("|");
List<String> aggClassStrings = new ArrayList<>(aggInfos_.size());
for (AggregateInfo aggInfo : aggInfos_) {
diff --git a/fe/src/main/java/org/apache/impala/planner/CanonicalizationStrategy.java b/fe/src/main/java/org/apache/impala/planner/CanonicalizationStrategy.java
index e8a1ebe07..24617bea1 100644
--- a/fe/src/main/java/org/apache/impala/planner/CanonicalizationStrategy.java
+++ b/fe/src/main/java/org/apache/impala/planner/CanonicalizationStrategy.java
@@ -73,4 +73,15 @@ public enum CanonicalizationStrategy {
throw new IllegalStateException("Unknown strategy: " + this);
}
}
+
+ public static CanonicalizationStrategy fromThrift(TCanonicalizationStrategy t) {
+ switch (t) {
+ case EXPR_REWRITE:
+ return EXPR_REWRITE;
+ case IGNORE_PARTITION_CONSTANTS:
+ return IGNORE_PARTITION_CONSTANTS;
+ default:
+ throw new IllegalStateException("Unknown strategy: " + t);
+ }
+ }
}
diff --git a/fe/src/main/java/org/apache/impala/planner/ExprCanonicalizer.java b/fe/src/main/java/org/apache/impala/planner/ExprCanonicalizer.java
index eaeb181ec..281542e41 100644
--- a/fe/src/main/java/org/apache/impala/planner/ExprCanonicalizer.java
+++ b/fe/src/main/java/org/apache/impala/planner/ExprCanonicalizer.java
@@ -24,6 +24,7 @@ import java.util.List;
import org.apache.impala.analysis.BinaryPredicate;
import org.apache.impala.analysis.Expr;
import org.apache.impala.analysis.InPredicate;
+import org.apache.impala.analysis.LiteralExpr;
import org.apache.impala.analysis.SlotRef;
import org.apache.impala.analysis.ToSqlOptions;
import org.apache.impala.catalog.FeTable;
@@ -45,6 +46,17 @@ public class ExprCanonicalizer {
// Placeholder string used when removing constants from predicates
private static final String CONST = "<CONST>";
+ public static String canonicalizeConstExpr(Expr e) {
+ if (e instanceof LiteralExpr) {
+ // Use "INT" for all integer types to avoid implicit cast by the analyzer
+ String type = e.getType().isIntegerType() ? "INT" : e.getType().toString();
+ return type + ":" + e.toSql();
+ }
+ // TODO: consider evaluating the constant exprs, e.g. "1+1", if the performance
+ // impact is negligible.
+ return e.toSql(ToSqlOptions.FOR_HBO);
+ }
+
/**
* Canonicalizes a list of expressions according to the specified strategy.
*
diff --git a/fe/src/main/java/org/apache/impala/planner/PlanNode.java b/fe/src/main/java/org/apache/impala/planner/PlanNode.java
index d34ddcddb..0f122ec3a 100644
--- a/fe/src/main/java/org/apache/impala/planner/PlanNode.java
+++ b/fe/src/main/java/org/apache/impala/planner/PlanNode.java
@@ -21,6 +21,7 @@ import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
+import java.util.Comparator;
import java.util.EnumMap;
import java.util.HashMap;
import java.util.HashSet;
@@ -29,6 +30,8 @@ import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;
+import java.util.stream.Collectors;
+import java.util.stream.IntStream;
import org.apache.impala.analysis.Analyzer;
import org.apache.impala.analysis.BinaryPredicate;
@@ -1026,6 +1029,38 @@ abstract public class PlanNode extends TreeNode<PlanNode> {
*/
public boolean isCardinalityPreserving() { return false; }
+ record HboKeyedNode(String key, int originalIndex, PlanNode node) {}
+
+ /**
+ * Returns children_ sorted by their concatenated and sorted scan table names.
+ * The sort is stable so two children with the same names preserve their original order
+ * in the query. Another query that flips their order will have a different HBO key
+ * string, which misses the HBO stats. Such cases are rare in practice, so we don't
+ * optimize them for simplicity. The returned list is cached and reused since the order
+ * depends only on table names, which are fixed after tree construction.
+ */
+ protected List<PlanNode> getHboOrderedOperands() {
+ if (hboOrderedOperands_ == null) {
+ hboOrderedOperands_ = IntStream.range(0, children_.size())
+ .mapToObj(i -> {
+ PlanNode node = children_.get(i);
+ List<ScanNode> scans = new ArrayList<>();
+ node.collect(ScanNode.class, scans);
+ String key = scans.stream()
+ .map(ScanNode::getScanTableName)
+ .sorted()
+ .collect(Collectors.joining(","));
+ return new HboKeyedNode(key, i, node);
+ })
+ .sorted(Comparator.comparing(HboKeyedNode::key)
+ .thenComparingInt(HboKeyedNode::originalIndex))
+ .map(HboKeyedNode::node)
+ .collect(Collectors.toList());
+ }
+ return hboOrderedOperands_;
+ }
+ private List<PlanNode> hboOrderedOperands_;
+
/**
* Generates an HBO key string for this node, or null if HBO is not supported.
* This key string represents the logical characteristics that identify similar
@@ -1069,9 +1104,6 @@ abstract public class PlanNode extends TreeNode<PlanNode> {
if (hashKeys.isEmpty()) return;
TPlanNodeRun currRun = new TPlanNodeRun();
appendScanInputStats(currRun);
- if (!currRun.isSetScan_input_stats() || currRun.getScan_input_stats().isEmpty()) {
- return;
- }
Long hboCardinality = HistoricalStats.INSTANCE.getPlanNodeOutputRows(
hashKeys, getDisplayLabel(), currRun);
if (hboCardinality != null) {
@@ -1122,7 +1154,6 @@ abstract public class PlanNode extends TreeNode<PlanNode> {
} else {
msg.setHbo_hash_keys(generateAllHboHashKeys());
}
- return;
}
/**
diff --git a/fe/src/main/java/org/apache/impala/planner/ScanNode.java b/fe/src/main/java/org/apache/impala/planner/ScanNode.java
index 0de5360e3..686ab3ffb 100644
--- a/fe/src/main/java/org/apache/impala/planner/ScanNode.java
+++ b/fe/src/main/java/org/apache/impala/planner/ScanNode.java
@@ -126,6 +126,14 @@ abstract public class ScanNode extends PlanNode {
public TupleDescriptor getTupleDesc() { return desc_; }
+ public String getScanTableName() {
+ if (desc_.getPath() == null || desc_.getPath().getRawPath().isEmpty()) {
+ return desc_.getTable().getFullName();
+ }
+ // Returns the qualified path including collection column names.
+ return desc_.getPath().toString();
+ }
+
@Override
protected boolean shouldPickUpZippingUnnestConjuncts() { return true; }
diff --git a/fe/src/main/java/org/apache/impala/planner/UnionNode.java b/fe/src/main/java/org/apache/impala/planner/UnionNode.java
index 0f2a0d425..7e96a7587 100644
--- a/fe/src/main/java/org/apache/impala/planner/UnionNode.java
+++ b/fe/src/main/java/org/apache/impala/planner/UnionNode.java
@@ -31,7 +31,9 @@ import org.apache.impala.common.ThriftSerializationCtx;
import org.apache.impala.thrift.TExecNodePhase;
import org.apache.impala.thrift.TExplainLevel;
import org.apache.impala.thrift.TExpr;
+import org.apache.impala.thrift.THboStatsType;
import org.apache.impala.thrift.TPlanNode;
+import org.apache.impala.thrift.TPlanNodeRun;
import org.apache.impala.thrift.TPlanNodeType;
import org.apache.impala.thrift.TQueryOptions;
import org.apache.impala.thrift.TUnionNode;
@@ -155,6 +157,10 @@ public class UnionNode extends PlanNode {
numInstances_ = 1;
}
cardinality_ = capCardinalityAtLimit(cardinality_);
+ // Don't need HBO stats if there are only constant operands.
+ if (!children_.isEmpty()) {
+ tryUpdateCardinalityFromHbo(analyzer);
+ }
if (LOG.isTraceEnabled()) {
LOG.trace("stats Union: cardinality=" + Long.toString(cardinality_));
}
@@ -355,6 +361,62 @@ public class UnionNode extends PlanNode {
Preconditions.checkState(false, "Unexpected use of old toThrift() signature.");
}
+ /**
+ * Generates an HBO key string for this union node. Returns null if any child node
+ * doesn't support HBO.
+ * TODO: consider passthrough children in the key for tracking memory usage.
+ */
+ @Override
+ public String generateHboKeyString(THboStatsType statsType,
+ CanonicalizationStrategy strategy) {
+ StringBuilder sb = new StringBuilder(statsType.name()).append(":UnionNode:");
+ if (limit_ > 0) sb.append("limit:").append(limit_).append("|");
+ if (!constExprLists_.isEmpty() && !addConstOpsToHboKeyString(sb)) return null;
+ sb.append("operands:[");
+ boolean first = true;
+ for (PlanNode operand : getHboOrderedOperands()) {
+ String childKey = operand.generateHboKeyString(statsType, strategy);
+ if (childKey == null) return null;
+ if (!first) sb.append(",");
+ sb.append(childKey);
+ first = false;
+ }
+ sb.append("]");
+ return sb.toString();
+ }
+
+ private boolean addConstOpsToHboKeyString(StringBuilder sb) {
+ sb.append("constRows:[");
+ for (int i = 0; i < constExprLists_.size(); i++) {
+ List<Expr> row = constExprLists_.get(i);
+ if (i > 0) sb.append(",");
+
+ sb.append("(");
+ for (int j = 0; j < row.size(); j++) {
+ Expr c = row.get(j);
+ if (!c.isConstant()) {
+ LOG.info("HBO not supported for {} due to nondeterministic expr: {}",
+ getDisplayLabel(), c.toSql());
+ return false;
+ }
+
+ if (j > 0) sb.append(",");
+ sb.append(ExprCanonicalizer.canonicalizeConstExpr(c));
+ }
+ sb.append(")");
+ }
+ sb.append("]|");
+ return true;
+ }
+
+ @Override
+ public void appendScanInputStats(TPlanNodeRun execStats) {
+ // Iterate in the same order as generateHboKeyString()
+ for (PlanNode operand : getHboOrderedOperands()) {
+ operand.appendScanInputStats(execStats);
+ }
+ }
+
@Override
protected void toThrift(TPlanNode msg, ThriftSerializationCtx serialCtx) {
Preconditions.checkState(materializedResultExprLists_.size() == children_.size());
@@ -370,6 +432,10 @@ public class UnionNode extends PlanNode {
msg.union_node = new TUnionNode(
tupleId_.asInt(), texprLists, constTexprLists, firstMaterializedChildIdx_);
msg.node_type = TPlanNodeType.UNION_NODE;
+ // Don't need to write HBO stats if there are only constant operands.
+ if (!children_.isEmpty()) {
+ populateHboThriftFields(msg, serialCtx);
+ }
}
@Override
diff --git a/fe/src/main/java/org/apache/impala/service/HistoricalStats.java b/fe/src/main/java/org/apache/impala/service/HistoricalStats.java
index af4202436..bd3a78e93 100644
--- a/fe/src/main/java/org/apache/impala/service/HistoricalStats.java
+++ b/fe/src/main/java/org/apache/impala/service/HistoricalStats.java
@@ -21,6 +21,7 @@ import java.util.List;
import java.util.Map;
import org.apache.impala.planner.CanonicalizationStrategy;
+import org.apache.impala.thrift.TCanonicalizationStrategy;
import org.apache.impala.thrift.THboStatsType;
import org.apache.impala.thrift.THistoricalStatsUpdate;
import org.apache.impala.thrift.TPlanNodeRun;
@@ -56,81 +57,67 @@ public class HistoricalStats {
cacheBackend_ = new InMemoryCacheBackend(concurrencyLevel, cacheSizeBytes);
}
- private boolean catalogVersionMatches(TPlanNodeRun a, TPlanNodeRun b) {
- if (!a.isSetScan_input_stats() || !b.isSetScan_input_stats()) {
- return false;
- }
- if (a.getScan_input_stats().size() != b.getScan_input_stats().size()) {
- return false;
- }
- for (int i = 0; i < a.getScan_input_stats().size(); i++) {
- TScanInputStats sa = a.getScan_input_stats().get(i);
- TScanInputStats sb = b.getScan_input_stats().get(i);
- if (!(sa.isSetCatalog_version() && sb.isSetCatalog_version()
- && sa.getCatalog_version() == sb.getCatalog_version())) {
- return false;
- }
- }
- return true;
+ private boolean exceedsThreshold(long curr, long hist) {
+ return curr < hist * (1 - similarityThreshold_)
+ || curr > hist * (1 + similarityThreshold_);
}
- private boolean scanInputSizeMatches(TPlanNodeRun a, TPlanNodeRun b) {
- if (!a.isSetScan_input_stats() || !b.isSetScan_input_stats()) {
- return false;
- }
- if (a.getScan_input_stats().isEmpty() || b.getScan_input_stats().isEmpty()) {
- return false;
+ /**
+ * Returns true if {@code currRun} and {@code histRun} are similar enough to share HBO
+ * stats. Each scan-node input is compared independently:
+ * - If both inputs have valid input_rows (>= 0), compare row counts.
+ * - Otherwise (either input_rows is missing):
+ * - For EXPR_REWRITE, an exact catalog version match makes the pair similar;
+ * if catalog versions differ, compare input file sizes.
+ * - For other strategies, catalog version is not a reliable signal, so compare
+ * input file sizes only.
+ * A run matches only if every scan-node pair matches. Note that the hash key matching
+ * already ensures table names and conjuncts are matched.
+ */
+ private boolean scanInputStatsMatch(TPlanNodeRun currRun, TPlanNodeRun histRun,
+ CanonicalizationStrategy strategy) {
+ List<TScanInputStats> currStats = currRun.getScan_input_stats();
+ List<TScanInputStats> histStats = histRun.getScan_input_stats();
+ // UnionNode with only constant operands and its ancestor nodes have no scans.
+ if (!currRun.isSetScan_input_stats() || currStats.isEmpty()) {
+ return !histRun.isSetScan_input_stats() || histStats.isEmpty();
}
- TScanInputStats sa = a.getScan_input_stats().get(0);
- TScanInputStats sb = b.getScan_input_stats().get(0);
- if (!sa.isSetInput_file_size() || !sb.isSetInput_file_size()) return false;
- long x = sa.getInput_file_size();
- long y = sb.getInput_file_size();
- if (x == 0) return y == 0;
- return Math.abs(x - y) / (double)x < similarityThreshold_;
- }
-
- private int getSimilarRunIndexWithoutStats(List<TPlanNodeRun> runs,
- TPlanNodeRun currRun) {
- if (currRun.isSetScan_input_stats()) {
- for (TScanInputStats s : currRun.getScan_input_stats()) {
- Preconditions.checkState(s.isSetInput_rows(),
- "exactMatch is only used when missing numRows but input_rows unset");
- Preconditions.checkState(s.getInput_rows() < 0,
- "exactMatch is only used when missing numRows but got %s", s.getInput_rows());
+ if (currStats.size() != histStats.size()) return false;
+ for (int i = 0; i < currStats.size(); i++) {
+ TScanInputStats sc = currStats.get(i);
+ TScanInputStats sh = histStats.get(i);
+ long currRows = sc.getInput_rows();
+ long histRows = sh.getInput_rows();
+ if (currRows >= 0 && histRows >= 0) {
+ if (exceedsThreshold(currRows, histRows)) return false;
+ } else {
+ // At least one side is missing input_rows. For EXPR_REWRITE, compare the catalog
+ // versions first. Note that for other more aggressive strategies it's unsafe to
+ // depend on catalog versions. E.g. IGNORE_PARTITION_CONSTANTS maps "year=2009"
+ // and "year=2019" to the same partition predicate "year=<CONST>". But "year=2019"
+ // picks no files in the functional.alltypes table. We should depend on the total
+ // input file size for such cases.
+ if (strategy == CanonicalizationStrategy.EXPR_REWRITE
+ && sc.isSetCatalog_version() && sh.isSetCatalog_version()
+ && sc.getCatalog_version() == sh.getCatalog_version()) {
+ continue;
+ }
+ // In the future input_file_size could be unset, e.g. for KuduScanNode.
+ // Currently we just support HdfsScanNode so these should be set.
+ Preconditions.checkState(sc.isSetInput_file_size());
+ Preconditions.checkState(sh.isSetInput_file_size());
+ if (exceedsThreshold(sc.getInput_file_size(), sh.getInput_file_size())) {
+ return false;
+ }
}
}
- // For exact match, first find a run with the exact catalog version. If missing,
- // find a run with the similar scan input size. Note that the hash key matching
- // already ensures conjuncts are the same.
- int sizeMatchIndex = -1;
- for (int i = 0; i < runs.size(); i++) {
- TPlanNodeRun run = runs.get(i);
- if (catalogVersionMatches(run, currRun)) return i;
- if (scanInputSizeMatches(run, currRun)) sizeMatchIndex = i;
- }
- return sizeMatchIndex;
+ return true;
}
- private int getSimilarRunIndexWithNumRows(List<TPlanNodeRun> runs,
- TPlanNodeRun currRun) {
- Preconditions.checkState(currRun.isSetScan_input_stats()
- && !currRun.getScan_input_stats().isEmpty());
+ private int getSimilarRunIndex(List<TPlanNodeRun> runs, TPlanNodeRun currRun,
+ CanonicalizationStrategy strategy) {
for (int i = 0; i < runs.size(); i++) {
- TPlanNodeRun run = runs.get(i);
- // Currently HBO only supports HdfsScanNode which just has one table thus only one
- // scan_input_stat. We just need to compare the first one.
- Preconditions.checkState(run.isSetScan_input_stats()
- && !run.getScan_input_stats().isEmpty());
- long curr = currRun.getScan_input_stats().get(0).getInput_rows();
- long historical = run.getScan_input_stats().get(0).getInput_rows();
- if (curr == 0) {
- if (historical == 0) {
- return i;
- }
- } else if (Math.abs(historical - curr) / (double)curr < similarityThreshold_) {
- return i;
- }
+ if (scanInputStatsMatch(currRun, runs.get(i), strategy)) return i;
}
return -1;
}
@@ -145,7 +132,11 @@ public class HistoricalStats {
TPlanNodeRun currRun = runWithKeys.run;
THboStatsType statsType = runWithKeys.stats_type;
// TODO: handle races from concurrent writers.
- for (String hashKey : runWithKeys.hash_keys.values()) {
+ for (Map.Entry<TCanonicalizationStrategy, String> entry :
+ runWithKeys.hash_keys.entrySet()) {
+ CanonicalizationStrategy strategy =
+ CanonicalizationStrategy.fromThrift(entry.getKey());
+ String hashKey = entry.getValue();
@SuppressWarnings("unchecked")
HistoricalStatsValue<TPlanNodeRun> statsValue =
(HistoricalStatsValue<TPlanNodeRun>) cacheBackend_.getIfPresent(
@@ -154,7 +145,7 @@ public class HistoricalStats {
cacheBackend_.put(statsType, hashKey, new HistoricalStatsValue<>(currRun));
} else {
List<TPlanNodeRun> runs = statsValue.getRuns();
- int similarRunIndex = getSimilarRunIndexWithNumRows(runs, currRun);
+ int similarRunIndex = getSimilarRunIndex(runs, currRun, strategy);
if (similarRunIndex >= 0) {
// Remove the similar one since we are adding a newer run.
runs.remove(similarRunIndex);
@@ -176,49 +167,38 @@ public class HistoricalStats {
* in order from most accurate to most aggressive canonicalization strategy.
* Returns the first match found, or null if no match exists.
*
- * @param hashKeys HBO hash strings keyed by canonicalization strategy
- * @return Number of rows from matched historical run, or null if no match
+ * @param hashKeys HBO hash strings keyed by canonicalization strategy.
+ * @param node display string for the PlanNode. Only used in logging.
+ * @param currRun scan input stats for the current run.
+ * @return Number of rows from matched historical run, or null if no match.
*/
public Long getPlanNodeOutputRows(Map<CanonicalizationStrategy, String> hashKeys,
- String tblName, TPlanNodeRun currRun) {
- Preconditions.checkNotNull(currRun.getScan_input_stats());
- Preconditions.checkArgument(!currRun.getScan_input_stats().isEmpty());
- boolean missingStats = currRun.getScan_input_stats().stream()
- .anyMatch(s -> s.getInput_rows() < 0);
+ String node, TPlanNodeRun currRun) {
for (CanonicalizationStrategy strategy : CanonicalizationStrategy.values()) {
String hashKey = hashKeys.get(strategy);
if (hashKey == null) continue;
- // If scanInputRows is unknown, only allow exact match, i.e. EXPR_REWRITE strategy
- // with catalog version match.
- if (missingStats && strategy != CanonicalizationStrategy.EXPR_REWRITE) break;
@SuppressWarnings("unchecked")
HistoricalStatsValue<TPlanNodeRun> statsValue =
(HistoricalStatsValue<TPlanNodeRun>) cacheBackend_.getIfPresent(
THboStatsType.CARDINALITY, hashKey);
if (statsValue != null) {
List<TPlanNodeRun> runs = statsValue.getRuns();
- int similarRunIndex;
- if (missingStats && strategy == CanonicalizationStrategy.EXPR_REWRITE) {
- similarRunIndex = getSimilarRunIndexWithoutStats(runs, currRun);
- } else {
- similarRunIndex = getSimilarRunIndexWithNumRows(runs, currRun);
- }
+ int similarRunIndex = getSimilarRunIndex(runs, currRun, strategy);
if (similarRunIndex >= 0) {
- // TODO: Consider moving this to the tail.
LOG.debug("HBO cache hit for {} using strategy {} (key: {}, currRun: {}):"
+ "cardinality={}",
- tblName, strategy, hashKey, currRun,
+ node, strategy, hashKey, currRun,
runs.get(similarRunIndex).getNum_rows());
return runs.get(similarRunIndex).getNum_rows();
} else {
LOG.debug("HBO cache miss for {} using strategy {} (key: {}, "
+ "scanInputRows: {}). No similar run",
- tblName, strategy, hashKey, currRun);
+ node, strategy, hashKey, currRun);
}
} else {
LOG.debug("HBO cache miss for {} using strategy {} (key: {}, scanInputRows:"
+ " {}). Hash key not found",
- tblName, strategy, hashKey, currRun);
+ node, strategy, hashKey, currRun);
}
}
return null;
diff --git a/fe/src/test/java/org/apache/impala/planner/HboKeyStringTest.java b/fe/src/test/java/org/apache/impala/planner/HboKeyStringTest.java
index 846f9fbd3..7eadcc4d6 100644
--- a/fe/src/test/java/org/apache/impala/planner/HboKeyStringTest.java
+++ b/fe/src/test/java/org/apache/impala/planner/HboKeyStringTest.java
@@ -30,9 +30,11 @@ import org.apache.impala.analysis.TupleDescriptor;
import org.apache.impala.catalog.Type;
import org.apache.impala.common.FrontendTestBase;
import org.apache.impala.common.ImpalaException;
+import org.apache.impala.common.ThriftSerializationCtx;
import org.apache.impala.service.Frontend.PlanCtx;
import org.apache.impala.testutil.TestUtils;
import org.apache.impala.thrift.THboStatsType;
+import org.apache.impala.thrift.TPlanNode;
import org.apache.impala.thrift.TQueryCtx;
import org.apache.impala.thrift.TQueryOptions;
import org.junit.Test;
@@ -42,7 +44,10 @@ import org.slf4j.LoggerFactory;
import com.google.common.collect.Lists;
import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertNotEquals;
+import static org.junit.Assert.assertNull;
+import static org.junit.Assert.assertTrue;
/**
* Unit tests for HBO key string generation. Verifies the raw key strings (before hashing)
@@ -65,7 +70,11 @@ public class HboKeyStringTest extends FrontendTestBase {
}
private List<PlanFragment> planFragments(String query) throws ImpalaException {
- TQueryOptions options = new TQueryOptions();
+ return planFragments(query, new TQueryOptions());
+ }
+
+ private List<PlanFragment> planFragments(String query, TQueryOptions options)
+ throws ImpalaException {
options.setUse_hbo_stats(true);
options.setStore_hbo_stats(true);
TQueryCtx queryCtx = TestUtils.createQueryContext(options);
@@ -355,4 +364,181 @@ public class HboKeyStringTest extends FrontendTestBase {
// The unsubstituted source column (rawPath_ set) renders identically.
assertEquals("`name`one`", sourceCol.toSql(ToSqlOptions.FOR_HBO));
}
+
+ @Test
+ public void testAggregationNodeLimit() throws ImpalaException {
+ String query = "select distinct id from functional.alltypestiny limit 2";
+ Map<Integer, PlanNode> nodes = collectPlanNodesInDistributedPlan(query);
+ PlanNode aggNode = nodes.get(1);
+ assertEquals("CARDINALITY:AggregationNode:FIRST|preagg:false|groupingSet:false|"
+ + "limit:2|AggClasses:[0:GROUP:id]|CHILD:["
+ + "CARDINALITY:ScanNode:functional.alltypestiny|]",
+ aggNode.generateHboKeyString(
+ THboStatsType.CARDINALITY, CanonicalizationStrategy.EXPR_REWRITE));
+ }
+
+ private UnionNode singleUnion(String query) throws ImpalaException {
+ return singleUnion(query, new TQueryOptions());
+ }
+
+ private UnionNode singleUnion(String query, TQueryOptions options)
+ throws ImpalaException {
+ List<PlanFragment> frags = planFragments(query, options);
+ Map<Integer, PlanNode> nodes = new HashMap<>();
+ collectAllNodes(frags.get(0).getPlanRoot(), nodes);
+ int count = 0;
+ UnionNode union = null;
+ for (PlanNode n : nodes.values()) {
+ if (n instanceof UnionNode) {
+ union = (UnionNode) n;
+ count++;
+ }
+ }
+ assertEquals("Expected exactly one UnionNode for query: " + query, 1, count);
+ return union;
+ }
+
+ @Test
+ public void testUnionNodeKeys() throws ImpalaException {
+ // UNION ALL output cardinality is the sum of the branch cardinalities, which is
+ // independent of the branch order. The HBO key sorts the operands so two unions
+ // whose branches are written in swapped order produce the same key.
+ String q1 = "select id from functional.alltypes where year = 2009 and int_col = 0 "
+ + "union all "
+ + "select id from functional.alltypestiny where int_col = 0";
+ String q2 = "select id from functional.alltypestiny where int_col = 0 "
+ + "union all "
+ + "select id from functional.alltypes where year = 2009 and int_col = 0";
+
+ UnionNode union1 = singleUnion(q1);
+ UnionNode union2 = singleUnion(q2);
+
+ // Operands are sorted by base scan table name, so alltypes comes first.
+ String scanAllER =
+ "CARDINALITY:ScanNode:functional.alltypes|`year` = 2009|int_col = 0|";
+ String scanTinyER = "CARDINALITY:ScanNode:functional.alltypestiny|int_col = 0|";
+ String expectedER = "CARDINALITY:UnionNode:operands:["
+ + scanAllER + "," + scanTinyER + "]";
+ assertEquals(expectedER, union1.generateHboKeyString(
+ THboStatsType.CARDINALITY, CanonicalizationStrategy.EXPR_REWRITE));
+ assertEquals(expectedER, union2.generateHboKeyString(
+ THboStatsType.CARDINALITY, CanonicalizationStrategy.EXPR_REWRITE));
+
+ String scanAllIPC =
+ "CARDINALITY:ScanNode:functional.alltypes|`year`=<CONST>|int_col = 0|";
+ String expectedIPC = "CARDINALITY:UnionNode:operands:["
+ + scanAllIPC + "," + scanTinyER + "]";
+ assertEquals(expectedIPC, union1.generateHboKeyString(
+ THboStatsType.CARDINALITY,
+ CanonicalizationStrategy.IGNORE_PARTITION_CONSTANTS));
+
+ // Both branch orders hash identically for every strategy.
+ for (CanonicalizationStrategy strategy : CanonicalizationStrategy.values()) {
+ assertEquals("Union branch order must not affect the key for " + strategy,
+ union1.generateHboKeyString(THboStatsType.CARDINALITY, strategy),
+ union2.generateHboKeyString(THboStatsType.CARDINALITY, strategy));
+ }
+ }
+
+ @Test
+ public void testUnionWithConstOperands() throws ImpalaException {
+ // Constant select branches are tracked as constOps in the key and do not add
+ // operands.
+ String query = "select id, string_col from functional.alltypes "
+ + "where year = 2009 and int_col = 0 "
+ + "union all select 1, '1' "
+ + "union all select 2, '2'";
+ PlanNode union = singleUnion(query);
+ String scanAllER =
+ "CARDINALITY:ScanNode:functional.alltypes|`year` = 2009|int_col = 0|";
+ String expectedER = "CARDINALITY:UnionNode:"
+ + "constRows:[(INT:1,STRING:'1'),(INT:2,STRING:'2')]|operands:["
+ + scanAllER + "]";
+ assertEquals(expectedER, union.generateHboKeyString(
+ THboStatsType.CARDINALITY, CanonicalizationStrategy.EXPR_REWRITE));
+
+ // Test const-only union
+ Map<Integer, PlanNode> nodes = collectPlanNodesInDistributedPlan(
+ "select 1 union select 2");
+ union = nodes.get(0);
+ PlanNode agg = nodes.get(1);
+ TQueryOptions queryOptions = new TQueryOptions();
+ queryOptions.setStore_hbo_stats(true);
+ ThriftSerializationCtx serialCtx = new ThriftSerializationCtx(queryOptions);
+ // HBO fields of the PlanNode shouldn't be populated for const-only UnionNode.
+ TPlanNode msg = new TPlanNode();
+ union.toThrift(msg, serialCtx);
+ assertFalse(msg.isSetHbo_hash_keys());
+ assertFalse(msg.isSetExec_stats());
+ // HBO still tracks AggregationNode on const-only UnionNode.
+ msg = new TPlanNode();
+ agg.toThrift(msg, serialCtx);
+ assertTrue(msg.isSetHbo_hash_keys());
+ assertTrue(msg.isSetExec_stats());
+ assertEquals(0, msg.getExec_stats().getScan_input_statsSize());
+ assertEquals("CARDINALITY:AggregationNode:FIRST|preagg:false|groupingSet:false|"
+ + "AggClasses:[0:GROUP:1]|CHILD:[CARDINALITY:UnionNode:constRows:"
+ + "[(INT:1),(INT:2)]|operands:[]]",
+ agg.generateHboKeyString(
+ THboStatsType.CARDINALITY, CanonicalizationStrategy.EXPR_REWRITE));
+ }
+
+ @Test
+ public void testUnionWithNondeterministicConst() throws ImpalaException {
+ // A non-deterministic const operand (rand()) cannot be matched against historical
+ // runs, so the whole UnionNode is skipped for HBO.
+ String query = "select rand() union all select id from functional.alltypes";
+ UnionNode union = singleUnion(query);
+ for (CanonicalizationStrategy strategy : CanonicalizationStrategy.values()) {
+ assertNull(union.generateHboKeyString(THboStatsType.CARDINALITY, strategy));
+ }
+ // toThrift must not populate HBO fields for a skipped UnionNode.
+ TQueryOptions queryOptions = new TQueryOptions();
+ queryOptions.setStore_hbo_stats(true);
+ ThriftSerializationCtx serialCtx = new ThriftSerializationCtx(queryOptions);
+ TPlanNode msg = new TPlanNode();
+ union.toThrift(msg, serialCtx);
+ assertFalse(msg.isSetHbo_hash_keys());
+ assertFalse(msg.isSetExec_stats());
+ }
+
+ @Test
+ public void testUnionWithNonLiteralConst() throws ImpalaException {
+ // With expr rewrites disabled, "1 + 1" is not folded to a literal, but it is still
+ // a deterministic constant, so it is tracked in the key via its SQL form.
+ TQueryOptions options = new TQueryOptions();
+ options.setEnable_expr_rewrites(false);
+ String query = "select 1 + 1 union all select id from functional.alltypes";
+ UnionNode union = singleUnion(query, options);
+ String expectedER = "CARDINALITY:UnionNode:constRows:[(1 + 1)]|operands:["
+ + "CARDINALITY:ScanNode:functional.alltypes|]";
+ assertEquals(expectedER, union.generateHboKeyString(
+ THboStatsType.CARDINALITY, CanonicalizationStrategy.EXPR_REWRITE));
+ }
+
+ @Test
+ public void testUnionNodeLimit() throws ImpalaException {
+ String q = "select id from functional.alltypestiny union all values(9),(10) limit 1";
+ Map<Integer, PlanNode> nodes = collectPlanNodesInDistributedPlan(q);
+ String scanKey = "CARDINALITY:ScanNode:functional.alltypestiny|";
+ String innerUnionKey = "CARDINALITY:UnionNode:limit:1|"
+ + "constRows:[(INT:9),(INT:10)]|operands:[]";
+ String outerUnionKey = "CARDINALITY:UnionNode:operands:["
+ + innerUnionKey + "," + scanKey + "]";
+ UnionNode innerUnion = (UnionNode) nodes.get(2);
+ UnionNode outerUnion = (UnionNode) nodes.get(0);
+ assertEquals(innerUnionKey, innerUnion.generateHboKeyString(
+ THboStatsType.CARDINALITY, CanonicalizationStrategy.EXPR_REWRITE));
+ assertEquals(outerUnionKey, outerUnion.generateHboKeyString(
+ THboStatsType.CARDINALITY, CanonicalizationStrategy.EXPR_REWRITE));
+
+ q = "select * from ("
+ + "select id from functional.alltypestiny union all values(9),(10)"
+ + ") t limit 1";
+ UnionNode union = singleUnion(q);
+ String unionKey = "CARDINALITY:UnionNode:limit:1|"
+ + "constRows:[(INT:9),(INT:10)]|operands:[" + scanKey + "]";
+ assertEquals(unionKey, union.generateHboKeyString(
+ THboStatsType.CARDINALITY, CanonicalizationStrategy.EXPR_REWRITE));
+ }
}
diff --git a/fe/src/test/java/org/apache/impala/service/HistoricalStatsTest.java b/fe/src/test/java/org/apache/impala/service/HistoricalStatsTest.java
new file mode 100644
index 000000000..6f6842f0b
--- /dev/null
+++ b/fe/src/test/java/org/apache/impala/service/HistoricalStatsTest.java
@@ -0,0 +1,180 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+package org.apache.impala.service;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNull;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.List;
+
+import org.apache.impala.planner.CanonicalizationStrategy;
+import org.apache.impala.thrift.THboStatsType;
+import org.apache.impala.thrift.TPlanNodeRun;
+import org.apache.impala.thrift.TPlanNodeRunWithKeys;
+import org.apache.impala.thrift.TScanInputStats;
+import org.junit.Test;
+
+/**
+ * Unit tests for the per-scan-node-pair similarity matching in {@link HistoricalStats}.
+ * Exercises the public read/write API directly. The default similarity threshold in tests
+ * (BackendConfig.INSTANCE == null) is 0.1 (10%). Each test uses unique hash keys to avoid
+ * cross-test pollution of the shared singleton cache.
+ */
+public class HistoricalStatsTest {
+
+ private static TScanInputStats scan(long inputRows) {
+ return scan(inputRows, -1, -1);
+ }
+
+ private static TScanInputStats scan(long inputRows, long catalogVersion,
+ long fileSize) {
+ TScanInputStats s = new TScanInputStats();
+ s.setInput_rows(inputRows);
+ s.setCatalog_version(catalogVersion);
+ s.setInput_file_size(fileSize);
+ return s;
+ }
+
+ private static TPlanNodeRun run(long numRows, TScanInputStats... scans) {
+ TPlanNodeRun r = new TPlanNodeRun();
+ List<TScanInputStats> list = new ArrayList<>(Arrays.asList(scans));
+ r.setScan_input_stats(list);
+ r.setNum_rows(numRows);
+ return r;
+ }
+
+ private void write(CanonicalizationStrategy strategy, String key, TPlanNodeRun run) {
+ HistoricalStats.INSTANCE.writePlanNodeStats(
+ new TPlanNodeRunWithKeys(run, Collections.singletonMap(strategy.toThrift(), key),
+ THboStatsType.CARDINALITY));
+ }
+
+ private Long read(CanonicalizationStrategy strategy, String key, TPlanNodeRun run) {
+ return HistoricalStats.INSTANCE.getPlanNodeOutputRows(
+ Collections.singletonMap(strategy, key), "test.tbl", run);
+ }
+
+ /** Both scans have valid input_rows: row-count similarity is used. */
+ @Test
+ public void testRowCountMatchWhenBothValid() {
+ String key = "rows-both-valid";
+ write(CanonicalizationStrategy.EXPR_REWRITE, key, run(500, scan(1000)));
+ // Within 10% -> match.
+ assertEquals(Long.valueOf(500),
+ read(CanonicalizationStrategy.EXPR_REWRITE, key, run(0, scan(1050))));
+ // Beyond 10% -> no match.
+ assertNull(
+ read(CanonicalizationStrategy.EXPR_REWRITE, key, run(0, scan(1200))));
+ }
+
+ /**
+ * Mixed run: one scan has valid rows, the other is missing. The valid pair uses row
+ * counts; the missing pair uses catalog version then file size (EXPR_REWRITE).
+ */
+ @Test
+ public void testMixedValidAndMissingRows() {
+ String key = "rows-mixed";
+ // scan0: rows=1000 (valid); scan1: rows=-1, catalog=5, size=2000.
+ write(CanonicalizationStrategy.EXPR_REWRITE, key,
+ run(777, scan(1000), scan(-1, 5, 2000)));
+
+ // scan0 rows within 10%, scan1 catalog matches -> match.
+ assertEquals(Long.valueOf(777), read(CanonicalizationStrategy.EXPR_REWRITE, key,
+ run(0, scan(1050), scan(-1, 5, 2100))));
+
+ // scan0 rows off -> no match even though scan1 catalog version matches.
+ assertNull(read(CanonicalizationStrategy.EXPR_REWRITE, key,
+ run(0, scan(1300), scan(-1, 5, 2000))));
+
+ // scan1 catalog version differs, file size within 10% -> match.
+ assertEquals(Long.valueOf(777), read(CanonicalizationStrategy.EXPR_REWRITE, key,
+ run(0, scan(1000), scan(-1, 6, 2100))));
+
+ // scan1 catalog version differs and file size off -> no match.
+ assertNull(read(CanonicalizationStrategy.EXPR_REWRITE, key,
+ run(0, scan(1000), scan(-1, 6, 3000))));
+ }
+
+ /**
+ * All rows missing, EXPR_REWRITE: exact catalog version match wins; otherwise fall back
+ * to file size.
+ */
+ @Test
+ public void testAllMissingExprRewrite() {
+ String key = "missing-expr";
+ write(CanonicalizationStrategy.EXPR_REWRITE, key, run(42, scan(-1, 10, 1000)));
+
+ // Catalog version matches -> match (file size irrelevant).
+ assertEquals(Long.valueOf(42),
+ read(CanonicalizationStrategy.EXPR_REWRITE, key, run(0, scan(-1, 10, 9999))));
+ // Catalog differs, file size within 10% -> match.
+ assertEquals(Long.valueOf(42),
+ read(CanonicalizationStrategy.EXPR_REWRITE, key, run(0, scan(-1, 11, 1050))));
+ // Catalog differs, file size off -> no match.
+ assertNull(
+ read(CanonicalizationStrategy.EXPR_REWRITE, key, run(0, scan(-1, 11, 2000))));
+ }
+
+ /**
+ * All rows missing, non-EXPR_REWRITE strategy: catalog version is ignored; only file
+ * size is used.
+ */
+ @Test
+ public void testAllMissingNonExprRewriteUsesFileSizeOnly() {
+ String key = "missing-ignore-part";
+ CanonicalizationStrategy strategy =
+ CanonicalizationStrategy.IGNORE_PARTITION_CONSTANTS;
+ write(strategy, key, run(99, scan(-1, 10, 1000)));
+
+ // Catalog version matches (ignored) but file size off -> no match.
+ assertNull(read(strategy, key, run(0, scan(-1, 10, 2000))));
+ // Catalog version differs but file size within 10% -> match.
+ assertEquals(Long.valueOf(99), read(strategy, key, run(0, scan(-1, 999, 1050))));
+ }
+
+ /** Different number of scans never matches. */
+ @Test
+ public void testSizeMismatch() {
+ String key = "size-mismatch";
+ write(CanonicalizationStrategy.EXPR_REWRITE, key, run(7, scan(1000)));
+ assertNull(read(CanonicalizationStrategy.EXPR_REWRITE, key,
+ run(0, scan(1000), scan(1000, -1, -1))));
+ }
+
+ /**
+ * Write/read consistency: two runs that are "similar" only by file size must be deduped
+ * on write, so the read path returns the newest and never an accumulated stale run.
+ * getSimilarRunIndex returns the first matching index; writes append to the tail. If
+ * dedup failed, the read would return the older run's num_rows (100) instead of the
+ * newer (200).
+ */
+ @Test
+ public void testWriteReadDedupBySize() {
+ String key = "dedup-by-size";
+ // Both rows=-1, different catalog versions, similar file sizes -> similar runs.
+ write(CanonicalizationStrategy.EXPR_REWRITE, key, run(100, scan(-1, 1, 1000)));
+ write(CanonicalizationStrategy.EXPR_REWRITE, key, run(200, scan(-1, 2, 1050)));
+
+ // Newest run returned -> the older one was deduped away on the second write.
+ assertEquals(Long.valueOf(200),
+ read(CanonicalizationStrategy.EXPR_REWRITE, key, run(0, scan(-1, 3, 1020))));
+ }
+}
diff --git a/testdata/workloads/functional-query/queries/QueryTest/hbo-union-collection-scan.test b/testdata/workloads/functional-query/queries/QueryTest/hbo-union-collection-scan.test
new file mode 100644
index 000000000..91e61d503
--- /dev/null
+++ b/testdata/workloads/functional-query/queries/QueryTest/hbo-union-collection-scan.test
@@ -0,0 +1,49 @@
+====
+---- QUERY
+# EXPLAIN the same query ran in test_hbo.py
+EXPLAIN select id from functional_parquet.complextypes_arrays where id > 10
+union all
+select item from functional_parquet.complextypes_arrays.arr1 where item > 10
+---- PLAN
+PLAN-ROOT SINK
+|
+03:EXCHANGE [UNPARTITIONED]
+|
+00:UNION
+| pass-through-operands: all
+| row-size=4B cardinality=2 (from HBO)
+|
+|--02:SCAN HDFS [functional_parquet.complextypes_arrays.arr1]
+| HDFS partitions=1/1 files=1 size=1.06KB
+| predicates: item > 10
+| row-size=4B cardinality=1 (from HBO)
+|
+01:SCAN HDFS [functional_parquet.complextypes_arrays]
+ HDFS partitions=1/1 files=1 size=1.06KB
+ predicates: id > 10
+ row-size=4B cardinality=1 (from HBO)
+====
+---- QUERY
+# Flip the operands. The UnionNode should still hit HBO stats.
+EXPLAIN select item from functional_parquet.complextypes_arrays.arr1 where item > 10
+union all
+select id from functional_parquet.complextypes_arrays where id > 10
+---- PLAN
+PLAN-ROOT SINK
+|
+03:EXCHANGE [UNPARTITIONED]
+|
+00:UNION
+| pass-through-operands: all
+| row-size=4B cardinality=2 (from HBO)
+|
+|--02:SCAN HDFS [functional_parquet.complextypes_arrays]
+| HDFS partitions=1/1 files=1 size=1.06KB
+| predicates: id > 10
+| row-size=4B cardinality=1 (from HBO)
+|
+01:SCAN HDFS [functional_parquet.complextypes_arrays.arr1]
+ HDFS partitions=1/1 files=1 size=1.06KB
+ predicates: item > 10
+ row-size=4B cardinality=1 (from HBO)
+====
diff --git a/testdata/workloads/functional-query/queries/QueryTest/hbo-union-consts.test b/testdata/workloads/functional-query/queries/QueryTest/hbo-union-consts.test
new file mode 100644
index 000000000..9cbcb9f5d
--- /dev/null
+++ b/testdata/workloads/functional-query/queries/QueryTest/hbo-union-consts.test
@@ -0,0 +1,26 @@
+====
+---- QUERY
+# EXPLAIN the same query ran in test_hbo.py. Only ancestors nodes of const-union
+# will be tracked in HBO.
+EXPLAIN select 1 union select 2
+---- PLAN
+PLAN-ROOT SINK
+|
+01:AGGREGATE [FINALIZE]
+| group by: 1
+| row-size=1B cardinality=2 (from HBO)
+|
+00:UNION
+ constant-operands=2
+ row-size=1B cardinality=2
+====
+---- QUERY
+# Test UNION ALL
+EXPLAIN select 1 union all select 2
+---- PLAN
+PLAN-ROOT SINK
+|
+00:UNION
+ constant-operands=2
+ row-size=1B cardinality=2
+====
diff --git a/testdata/workloads/functional-query/queries/QueryTest/hbo-union-same-tables.test b/testdata/workloads/functional-query/queries/QueryTest/hbo-union-same-tables.test
new file mode 100644
index 000000000..9f765580d
--- /dev/null
+++ b/testdata/workloads/functional-query/queries/QueryTest/hbo-union-same-tables.test
@@ -0,0 +1,55 @@
+====
+---- QUERY
+# EXPLAIN the same query ran in test_hbo.py
+EXPLAIN select id from functional.alltypes
+where year = 2009 and int_col = 1 and string_col != 'test_union_same_tables'
+union all
+select id from functional.alltypes
+where year = 2019 and int_col = -1 and string_col != 'test_union_same_tables'
+---- PLAN
+PLAN-ROOT SINK
+|
+03:EXCHANGE [UNPARTITIONED]
+|
+00:UNION
+| row-size=4B cardinality=365 (from HBO)
+|
+|--02:SCAN HDFS [functional.alltypes]
+| partition predicates: `year` = 2019
+| partitions=0/24 files=0 size=0B
+| predicates: int_col = -1, string_col != 'test_union_same_tables'
+| row-size=21B cardinality=0
+|
+01:SCAN HDFS [functional.alltypes]
+ partition predicates: `year` = 2009
+ HDFS partitions=12/24 files=12 size=238.68KB
+ predicates: int_col = 1, string_col != 'test_union_same_tables'
+ row-size=21B cardinality=365 (from HBO)
+====
+---- QUERY
+# Swap the row predicates. The UnionNode shouldn't hit HBO stats.
+EXPLAIN select id from functional.alltypes
+where year = 2009 and int_col = -1 and string_col != 'test_union_same_tables'
+union all
+select id from functional.alltypes
+where year = 2019 and int_col = 1 and string_col != 'test_union_same_tables'
+---- PLAN
+PLAN-ROOT SINK
+|
+03:EXCHANGE [UNPARTITIONED]
+|
+00:UNION
+| row-size=4B cardinality=346
+|
+|--02:SCAN HDFS [functional.alltypes]
+| partition predicates: `year` = 2019
+| partitions=0/24 files=0 size=0B
+| predicates: int_col = 1, string_col != 'test_union_same_tables'
+| row-size=21B cardinality=0
+|
+01:SCAN HDFS [functional.alltypes]
+ partition predicates: `year` = 2009
+ HDFS partitions=12/24 files=12 size=238.68KB
+ predicates: int_col = -1, string_col != 'test_union_same_tables'
+ row-size=21B cardinality=346
+====
diff --git a/testdata/workloads/functional-query/queries/QueryTest/hbo-union.test b/testdata/workloads/functional-query/queries/QueryTest/hbo-union.test
new file mode 100644
index 000000000..ab2318f36
--- /dev/null
+++ b/testdata/workloads/functional-query/queries/QueryTest/hbo-union.test
@@ -0,0 +1,118 @@
+====
+---- QUERY
+# EXPLAIN the same query ran in test_hbo.py. All nodes should hit HBO stats.
+EXPLAIN select id from functional.alltypes
+where year = 2009 and int_col = 1 and string_col != 'test_union'
+union
+select id from functional.alltypestiny
+where int_col = 0 and string_col != 'test_union'
+---- PLAN
+PLAN-ROOT SINK
+|
+06:EXCHANGE [UNPARTITIONED]
+|
+05:AGGREGATE [FINALIZE]
+| group by: id
+| row-size=4B cardinality=369 (from HBO)
+|
+04:EXCHANGE [HASH(id)]
+|
+03:AGGREGATE [STREAMING]
+| group by: id
+| row-size=4B cardinality=369 (from HBO)
+|
+00:UNION
+| row-size=4B cardinality=369 (from HBO)
+|
+|--02:SCAN HDFS [functional.alltypestiny]
+| HDFS partitions=4/4 files=4 size=460B
+| predicates: int_col = 0, string_col != 'test_union'
+| row-size=21B cardinality=4 (from HBO)
+|
+01:SCAN HDFS [functional.alltypes]
+ partition predicates: `year` = 2009
+ HDFS partitions=12/24 files=12 size=238.68KB
+ predicates: int_col = 1, string_col != 'test_union'
+ row-size=21B cardinality=365 (from HBO)
+====
+---- QUERY
+# EXPLAIN the same query but using UNION ALL. The UnionNode should still hit HBO stats.
+EXPLAIN select id from functional.alltypes
+where year = 2009 and int_col = 1 and string_col != 'test_union'
+union all
+select id from functional.alltypestiny
+where int_col = 0 and string_col != 'test_union'
+---- PLAN
+PLAN-ROOT SINK
+|
+03:EXCHANGE [UNPARTITIONED]
+|
+00:UNION
+| row-size=4B cardinality=369 (from HBO)
+|
+|--02:SCAN HDFS [functional.alltypestiny]
+| HDFS partitions=4/4 files=4 size=460B
+| predicates: int_col = 0, string_col != 'test_union'
+| row-size=21B cardinality=4 (from HBO)
+|
+01:SCAN HDFS [functional.alltypes]
+ partition predicates: `year` = 2009
+ HDFS partitions=12/24 files=12 size=238.68KB
+ predicates: int_col = 1, string_col != 'test_union'
+ row-size=21B cardinality=365 (from HBO)
+====
+---- QUERY
+# Same union with the branches written in swapped order.
+EXPLAIN select id from functional.alltypestiny
+where int_col = 0 and string_col != 'test_union'
+union all
+select id from functional.alltypes
+where year = 2009 and int_col = 1 and string_col != 'test_union'
+---- PLAN
+PLAN-ROOT SINK
+|
+03:EXCHANGE [UNPARTITIONED]
+|
+00:UNION
+| row-size=4B cardinality=369 (from HBO)
+|
+|--02:SCAN HDFS [functional.alltypes]
+| partition predicates: `year` = 2009
+| HDFS partitions=12/24 files=12 size=238.68KB
+| predicates: int_col = 1, string_col != 'test_union'
+| row-size=21B cardinality=365 (from HBO)
+|
+01:SCAN HDFS [functional.alltypestiny]
+ HDFS partitions=4/4 files=4 size=460B
+ predicates: int_col = 0, string_col != 'test_union'
+ row-size=21B cardinality=4 (from HBO)
+====
+---- QUERY
+# Change the alltypes operand (the 2nd operand after sorted by HBO key string) to select
+# 0 partitions thus has a different numInputRows. The HBO key strings of UnionNode matches
+# in IGNORE_PARTITION_CONSTANTS strategy but the historical runs matching should
+# distinguish them based on numInputRows.
+EXPLAIN select id from functional.alltypes
+where year = 2019 and int_col = 1 and string_col != 'test_union'
+union all
+select id from functional.alltypestiny
+where int_col = 0 and string_col != 'test_union'
+---- PLAN
+PLAN-ROOT SINK
+|
+03:EXCHANGE [UNPARTITIONED]
+|
+00:UNION
+| row-size=4B cardinality=4
+|
+|--02:SCAN HDFS [functional.alltypestiny]
+| HDFS partitions=4/4 files=4 size=460B
+| predicates: int_col = 0, string_col != 'test_union'
+| row-size=21B cardinality=4 (from HBO)
+|
+01:SCAN HDFS [functional.alltypes]
+ partition predicates: `year` = 2019
+ partitions=0/24 files=0 size=0B
+ predicates: int_col = 1, string_col != 'test_union'
+ row-size=21B cardinality=0
+====
diff --git a/tests/query_test/test_hbo.py b/tests/query_test/test_hbo.py
index d3165743e..04c022ce9 100644
--- a/tests/query_test/test_hbo.py
+++ b/tests/query_test/test_hbo.py
@@ -262,3 +262,39 @@ class TestHBO(ImpalaTestSuite):
where year = 2009 and string_col != 'test_grouping_set'
group by rollup(int_col, string_col, bigint_col)""")
self._run_hbo_explains('QueryTest/hbo-grouping-set')
+
+ def test_union_cardinality(self):
+ self.client.set_configuration(QUERY_OPTIONS)
+ self.execute_query("""
+ select id from functional.alltypes
+ where year = 2009 and int_col = 1 and string_col != 'test_union'
+ union
+ select id from functional.alltypestiny
+ where int_col = 0 and string_col != 'test_union'""")
+ self._run_hbo_explains('QueryTest/hbo-union')
+
+ def test_union_same_tables(self):
+ self.client.set_configuration(QUERY_OPTIONS)
+ self.execute_query("""
+ select id from functional.alltypes
+ where year = 2009 and int_col = 1 and string_col != 'test_union_same_tables'
+ union all
+ select id from functional.alltypes
+ where year = 2019 and int_col = -1 and string_col != 'test_union_same_tables'
+ """)
+ self._run_hbo_explains('QueryTest/hbo-union-same-tables')
+
+ def test_const_only_union(self):
+ """Verify that UNION with only const operands are not tracked in HBO."""
+ self.client.set_configuration(QUERY_OPTIONS)
+ self.execute_query("select 1 union select 2")
+ self._run_hbo_explains('QueryTest/hbo-union-consts')
+
+ def test_union_collection_scan(self):
+ self.client.set_configuration(QUERY_OPTIONS)
+ self.execute_query("""
+ select id from functional_parquet.complextypes_arrays where id > 10
+ union all
+ select item from functional_parquet.complextypes_arrays.arr1 where item > 10
+ """)
+ self._run_hbo_explains('QueryTest/hbo-union-collection-scan')