[jira] [Commented] (IMPALA-7564) Conservative FK/PK join type detection with complex equi-join conjuncts
[
https://issues.apache.org/jira/browse/IMPALA-7564?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16662783#comment-16662783
]
Paul Rogers commented on IMPALA-7564:
-
Expanding on the previous note, suppose we have a star schema: a fact table with
(time-stamp, store-id, sale-id, customer-id, cashier-id, lane-id, payment-type,
total-sale, sales-tax, ...)
We then have dimension tables:
(store-id, location, address, phone, ...)
(cachier-id, name, hire-date, ...)
And so on.
If we optimize such a query, we would normally put the dimension tables on the
build side of a join. You can think of a join to three fact tables as a set of
"enrichment filters", each of which adds more information to the query. (First
look up the store, then the cashier, then the customer, ...)
In each case, it should be clear the primary key in the dimension table: the
column where NDV(col) = |table|.
If the dimension table is small, just use it on the build side. No need to
infer a primary key for the fact table, and the join tells us the FK in the
fact table that points to the (inferred) PK of the dimension table.
The challenge is when, due to cardinality estimates, we try to be clever and
put the fact table on the build side. (Maybe we've decided that filters are so
selective that we'll only get 10 sales, but there are 100s of stores, 100Ks of
customers, etc.) What is the PK of the fact table?
In this case, the PK of the fact table very likely (store-id, lane-id,
timestamp), say, very likely has nothing to do with the dimension table
(customer-id). In this case, we can't expect a join with unique keys: we have
to accept that if we put the fact table on the build side, there will be
duplicate keys (the same customer bought multiple times).
The point is, if we step up a level and understand the data model that the
customer has implemented, we can make better decisions than if we attempt to
reverse engineer that model from the query and metadata. (This is, in fact, why
we use HMS I the first place rather than trying to infer schema directly from
the file as other tools do.)
> Conservative FK/PK join type detection with complex equi-join conjuncts
> ---
>
> Key: IMPALA-7564
> URL: https://issues.apache.org/jira/browse/IMPALA-7564
> Project: IMPALA
> Issue Type: Bug
> Components: Frontend
>Affects Versions: Impala 2.12.0, Impala 2.13.0, Impala 3.1.0
>Reporter: bharath v
>Priority: Major
>
> With IMPALA-5547, we predict whether a join is an FK/PK join as follows.
> {noformat}
> // Iterate over all groups of conjuncts that belong to the same joined tuple
> id pair.
> // For each group, we compute the join NDV of the rhs slots and compare
> it to the
> // number of rows in the rhs table.
> for (List fkPkCandidate:
> scanSlotsByJoinedTids.values()) {
> double jointNdv = 1.0;
> for (EqJoinConjunctScanSlots slots: fkPkCandidate) jointNdv *=
> slots.rhsNdv();
> double rhsNumRows = fkPkCandidate.get(0).rhsNumRows();
> if (jointNdv >= Math.round(rhsNumRows * (1.0 -
> FK_PK_MAX_STATS_DELTA_PERC))) {
> // We cannot disprove that the RHS is a PK.
> if (result == null) result = Lists.newArrayList();
> result.addAll(fkPkCandidate);
> }
> }
> {noformat}
> We iterate through all the "simple" equi join conjuncts on the RHS, multiply
> their NDVs and check if it close to rhsNumRows. The issue here is that this
> can result in conservative FK/Pk detection if the equi-join conjuncts are not
> simple (of the form = )
> {noformat}
> /**
> * Returns a new EqJoinConjunctScanSlots for the given equi-join conjunct
> or null if
> * the given conjunct is not of the form = or if the
> underlying
> * table/column of at least one side is missing stats.
> */
> public static EqJoinConjunctScanSlots create(Expr eqJoinConjunct) {
> if (!Expr.IS_EQ_BINARY_PREDICATE.apply(eqJoinConjunct)) return null;
> SlotDescriptor lhsScanSlot =
> eqJoinConjunct.getChild(0).findSrcScanSlot();
> if (lhsScanSlot == null || !hasNumRowsAndNdvStats(lhsScanSlot)) return
> null;
> SlotDescriptor rhsScanSlot =
> eqJoinConjunct.getChild(1).findSrcScanSlot();
> {noformat}
> For example, the following query contains a complex equi-join conjunct
> {{substr(l.c3, 1, 6) = substr(r.c3, 1,6)}}, so while detecting if the left
> outer join is an FK/PK, we just check if
> {{NDVs(r.c1) * NDVs(r.c2) ~ r.numRows()}} which is incorrect. (This happens
> because EqJoinConjunctScanSlots.create() returns null for any non-simple
> predicates which are not considered later).
> {noformat}
> [localhost:21000]> explain select * from test_left l left outer join
> test_right r on l.c1 = r.c1 and l.c2 = r.c2 and substr(l.c3, 1, 6) =
[jira] [Commented] (IMPALA-7564) Conservative FK/PK join type detection with complex equi-join conjuncts
[
https://issues.apache.org/jira/browse/IMPALA-7564?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16646870#comment-16646870
]
Paul Rogers commented on IMPALA-7564:
-
Looked at a few example user queries. I wonder if there is another angle to
attack this issue. The example queries in question appeared to be based on a
classic start-schema data warehouse: a very large fact table and multiple small
dimension tables. If we can infer such a pattern (from cardinality or from HMS
metadata), we can perhaps make a better prediction about join order and which
tables to put on the build vs. probe sides of a join.
Since FK/PK is one aspect of this idea (the PK is in the dimension table, FK in
the fact table), perhaps we can solve the same problem via cardinality analysis
when we don't have good FK/PK data. Would have to look into the details more,
but did want to raise this as a possible path forward.
> Conservative FK/PK join type detection with complex equi-join conjuncts
> ---
>
> Key: IMPALA-7564
> URL: https://issues.apache.org/jira/browse/IMPALA-7564
> Project: IMPALA
> Issue Type: Bug
> Components: Frontend
>Affects Versions: Impala 2.12.0, Impala 2.13.0, Impala 3.1.0
>Reporter: bharath v
>Priority: Major
>
> With IMPALA-5547, we predict whether a join is an FK/PK join as follows.
> {noformat}
> // Iterate over all groups of conjuncts that belong to the same joined tuple
> id pair.
> // For each group, we compute the join NDV of the rhs slots and compare
> it to the
> // number of rows in the rhs table.
> for (List fkPkCandidate:
> scanSlotsByJoinedTids.values()) {
> double jointNdv = 1.0;
> for (EqJoinConjunctScanSlots slots: fkPkCandidate) jointNdv *=
> slots.rhsNdv();
> double rhsNumRows = fkPkCandidate.get(0).rhsNumRows();
> if (jointNdv >= Math.round(rhsNumRows * (1.0 -
> FK_PK_MAX_STATS_DELTA_PERC))) {
> // We cannot disprove that the RHS is a PK.
> if (result == null) result = Lists.newArrayList();
> result.addAll(fkPkCandidate);
> }
> }
> {noformat}
> We iterate through all the "simple" equi join conjuncts on the RHS, multiply
> their NDVs and check if it close to rhsNumRows. The issue here is that this
> can result in conservative FK/Pk detection if the equi-join conjuncts are not
> simple (of the form = )
> {noformat}
> /**
> * Returns a new EqJoinConjunctScanSlots for the given equi-join conjunct
> or null if
> * the given conjunct is not of the form = or if the
> underlying
> * table/column of at least one side is missing stats.
> */
> public static EqJoinConjunctScanSlots create(Expr eqJoinConjunct) {
> if (!Expr.IS_EQ_BINARY_PREDICATE.apply(eqJoinConjunct)) return null;
> SlotDescriptor lhsScanSlot =
> eqJoinConjunct.getChild(0).findSrcScanSlot();
> if (lhsScanSlot == null || !hasNumRowsAndNdvStats(lhsScanSlot)) return
> null;
> SlotDescriptor rhsScanSlot =
> eqJoinConjunct.getChild(1).findSrcScanSlot();
> {noformat}
> For example, the following query contains a complex equi-join conjunct
> {{substr(l.c3, 1, 6) = substr(r.c3, 1,6)}}, so while detecting if the left
> outer join is an FK/PK, we just check if
> {{NDVs(r.c1) * NDVs(r.c2) ~ r.numRows()}} which is incorrect. (This happens
> because EqJoinConjunctScanSlots.create() returns null for any non-simple
> predicates which are not considered later).
> {noformat}
> [localhost:21000]> explain select * from test_left l left outer join
> test_right r on l.c1 = r.c1 and l.c2 = r.c2 and substr(l.c3, 1, 6) =
> substr(r.c3, 1,6);
> Query: explain select * from test_left l left outer join test_right r on l.c1
> = r.c1 and l.c2 = r.c2 and substr(l.c3, 1, 6) = substr(r.c3, 1,6)
> +-+
> | Explain String
> |
> +-+
> | Max Per-Host Resource Reservation: Memory=1.95MB Threads=5
> |
> | Per-Host Resource Estimates: Memory=66MB
> |
> |
> |
> | F02:PLAN FRAGMENT [UNPARTITIONED] hosts=1 instances=1
> |
> | | Per-Host Resources: mem-estimate=0B mem-reservation=0B
> thread-reservation=1 |
> | PLAN-ROOT SINK
> |
> | | mem-estimate=0B mem-reservation=0B thread-reservation=0
> |
> | |
[jira] [Commented] (IMPALA-7564) Conservative FK/PK join type detection with complex equi-join conjuncts
[
https://issues.apache.org/jira/browse/IMPALA-7564?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16635997#comment-16635997
]
bharath v commented on IMPALA-7564:
---
Yep, Hive added some support via HIVE-13290. But that helps only in cases when
the join conjuncts are of = types. I agree that virtual
columns could be of help here (IMPALA-7630).
> Conservative FK/PK join type detection with complex equi-join conjuncts
> ---
>
> Key: IMPALA-7564
> URL: https://issues.apache.org/jira/browse/IMPALA-7564
> Project: IMPALA
> Issue Type: Bug
> Components: Frontend
>Affects Versions: Impala 2.12.0, Impala 2.13.0, Impala 3.1.0
>Reporter: bharath v
>Priority: Major
>
> With IMPALA-5547, we predict whether a join is an FK/PK join as follows.
> {noformat}
> // Iterate over all groups of conjuncts that belong to the same joined tuple
> id pair.
> // For each group, we compute the join NDV of the rhs slots and compare
> it to the
> // number of rows in the rhs table.
> for (List fkPkCandidate:
> scanSlotsByJoinedTids.values()) {
> double jointNdv = 1.0;
> for (EqJoinConjunctScanSlots slots: fkPkCandidate) jointNdv *=
> slots.rhsNdv();
> double rhsNumRows = fkPkCandidate.get(0).rhsNumRows();
> if (jointNdv >= Math.round(rhsNumRows * (1.0 -
> FK_PK_MAX_STATS_DELTA_PERC))) {
> // We cannot disprove that the RHS is a PK.
> if (result == null) result = Lists.newArrayList();
> result.addAll(fkPkCandidate);
> }
> }
> {noformat}
> We iterate through all the "simple" equi join conjuncts on the RHS, multiply
> their NDVs and check if it close to rhsNumRows. The issue here is that this
> can result in conservative FK/Pk detection if the equi-join conjuncts are not
> simple (of the form = )
> {noformat}
> /**
> * Returns a new EqJoinConjunctScanSlots for the given equi-join conjunct
> or null if
> * the given conjunct is not of the form = or if the
> underlying
> * table/column of at least one side is missing stats.
> */
> public static EqJoinConjunctScanSlots create(Expr eqJoinConjunct) {
> if (!Expr.IS_EQ_BINARY_PREDICATE.apply(eqJoinConjunct)) return null;
> SlotDescriptor lhsScanSlot =
> eqJoinConjunct.getChild(0).findSrcScanSlot();
> if (lhsScanSlot == null || !hasNumRowsAndNdvStats(lhsScanSlot)) return
> null;
> SlotDescriptor rhsScanSlot =
> eqJoinConjunct.getChild(1).findSrcScanSlot();
> {noformat}
> For example, the following query contains a complex equi-join conjunct
> {{substr(l.c3, 1, 6) = substr(r.c3, 1,6)}}, so while detecting if the left
> outer join is an FK/PK, we just check if
> {{NDVs(r.c1) * NDVs(r.c2) ~ r.numRows()}} which is incorrect. (This happens
> because EqJoinConjunctScanSlots.create() returns null for any non-simple
> predicates which are not considered later).
> {noformat}
> [localhost:21000]> explain select * from test_left l left outer join
> test_right r on l.c1 = r.c1 and l.c2 = r.c2 and substr(l.c3, 1, 6) =
> substr(r.c3, 1,6);
> Query: explain select * from test_left l left outer join test_right r on l.c1
> = r.c1 and l.c2 = r.c2 and substr(l.c3, 1, 6) = substr(r.c3, 1,6)
> +-+
> | Explain String
> |
> +-+
> | Max Per-Host Resource Reservation: Memory=1.95MB Threads=5
> |
> | Per-Host Resource Estimates: Memory=66MB
> |
> |
> |
> | F02:PLAN FRAGMENT [UNPARTITIONED] hosts=1 instances=1
> |
> | | Per-Host Resources: mem-estimate=0B mem-reservation=0B
> thread-reservation=1 |
> | PLAN-ROOT SINK
> |
> | | mem-estimate=0B mem-reservation=0B thread-reservation=0
> |
> | |
> |
> | 04:EXCHANGE [UNPARTITIONED]
> |
> | | mem-estimate=0B mem-reservation=0B thread-reservation=0
> |
> | | tuple-ids=0,1N row-size=94B cardinality=49334767023
> |
> | | in pipelines: 00(GETNEXT)
> |
> | |
> |
> | F00:PLAN FRAGMENT [RANDOM] hosts=1
[jira] [Commented] (IMPALA-7564) Conservative FK/PK join type detection with complex equi-join conjuncts
[
https://issues.apache.org/jira/browse/IMPALA-7564?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16635978#comment-16635978
]
Philip Zeyliger commented on IMPALA-7564:
-
See HIVE-13290. We'd have to dig out the details, but it looks like Hive is or
has added ways to hint at these. In our world, there's no constraint
validation, but the hint is still a useful one. (I've also heard it requested
for purposes of exporting schemas to tools that visualize and help you build
joins.)
> Conservative FK/PK join type detection with complex equi-join conjuncts
> ---
>
> Key: IMPALA-7564
> URL: https://issues.apache.org/jira/browse/IMPALA-7564
> Project: IMPALA
> Issue Type: Bug
> Components: Frontend
>Affects Versions: Impala 2.12.0, Impala 2.13.0, Impala 3.1.0
>Reporter: bharath v
>Priority: Major
>
> With IMPALA-5547, we predict whether a join is an FK/PK join as follows.
> {noformat}
> // Iterate over all groups of conjuncts that belong to the same joined tuple
> id pair.
> // For each group, we compute the join NDV of the rhs slots and compare
> it to the
> // number of rows in the rhs table.
> for (List fkPkCandidate:
> scanSlotsByJoinedTids.values()) {
> double jointNdv = 1.0;
> for (EqJoinConjunctScanSlots slots: fkPkCandidate) jointNdv *=
> slots.rhsNdv();
> double rhsNumRows = fkPkCandidate.get(0).rhsNumRows();
> if (jointNdv >= Math.round(rhsNumRows * (1.0 -
> FK_PK_MAX_STATS_DELTA_PERC))) {
> // We cannot disprove that the RHS is a PK.
> if (result == null) result = Lists.newArrayList();
> result.addAll(fkPkCandidate);
> }
> }
> {noformat}
> We iterate through all the "simple" equi join conjuncts on the RHS, multiply
> their NDVs and check if it close to rhsNumRows. The issue here is that this
> can result in conservative FK/Pk detection if the equi-join conjuncts are not
> simple (of the form = )
> {noformat}
> /**
> * Returns a new EqJoinConjunctScanSlots for the given equi-join conjunct
> or null if
> * the given conjunct is not of the form = or if the
> underlying
> * table/column of at least one side is missing stats.
> */
> public static EqJoinConjunctScanSlots create(Expr eqJoinConjunct) {
> if (!Expr.IS_EQ_BINARY_PREDICATE.apply(eqJoinConjunct)) return null;
> SlotDescriptor lhsScanSlot =
> eqJoinConjunct.getChild(0).findSrcScanSlot();
> if (lhsScanSlot == null || !hasNumRowsAndNdvStats(lhsScanSlot)) return
> null;
> SlotDescriptor rhsScanSlot =
> eqJoinConjunct.getChild(1).findSrcScanSlot();
> {noformat}
> For example, the following query contains a complex equi-join conjunct
> {{substr(l.c3, 1, 6) = substr(r.c3, 1,6)}}, so while detecting if the left
> outer join is an FK/PK, we just check if
> {{NDVs(r.c1) * NDVs(r.c2) ~ r.numRows()}} which is incorrect. (This happens
> because EqJoinConjunctScanSlots.create() returns null for any non-simple
> predicates which are not considered later).
> {noformat}
> [localhost:21000]> explain select * from test_left l left outer join
> test_right r on l.c1 = r.c1 and l.c2 = r.c2 and substr(l.c3, 1, 6) =
> substr(r.c3, 1,6);
> Query: explain select * from test_left l left outer join test_right r on l.c1
> = r.c1 and l.c2 = r.c2 and substr(l.c3, 1, 6) = substr(r.c3, 1,6)
> +-+
> | Explain String
> |
> +-+
> | Max Per-Host Resource Reservation: Memory=1.95MB Threads=5
> |
> | Per-Host Resource Estimates: Memory=66MB
> |
> |
> |
> | F02:PLAN FRAGMENT [UNPARTITIONED] hosts=1 instances=1
> |
> | | Per-Host Resources: mem-estimate=0B mem-reservation=0B
> thread-reservation=1 |
> | PLAN-ROOT SINK
> |
> | | mem-estimate=0B mem-reservation=0B thread-reservation=0
> |
> | |
> |
> | 04:EXCHANGE [UNPARTITIONED]
> |
> | | mem-estimate=0B mem-reservation=0B thread-reservation=0
> |
> | | tuple-ids=0,1N row-size=94B cardinality=49334767023
> |
> | | in pipelines: 00(GETNEXT)
>
[jira] [Commented] (IMPALA-7564) Conservative FK/PK join type detection with complex equi-join conjuncts
[
https://issues.apache.org/jira/browse/IMPALA-7564?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16635969#comment-16635969
]
Paul Rogers commented on IMPALA-7564:
-
In an RDBMS, the PK is hinted by a unique index. But, Hive has no indexes, so
that hint is not available. Other DB's can add extra metadata to spell out the
ER relationships.
Best would be if HMS identified the PK, FK, and the relationships. A quick
glance at the [HMS ER
diagram|https://community.hortonworks.com/storage/attachments/7748-hive-ms-121.png]
suggests that this information is not available. So, one long-term solution is
to add it. Doing so eliminates the need to guess.
Since this case uses a function as part of the key, another help would be if
HMS can defined computed (AKA "virtual") columns. Then, that computed column
could be identified as a key in the ER relationship.
With all of that, Impala could unambiguously know the user's intent without
having to guess.
> Conservative FK/PK join type detection with complex equi-join conjuncts
> ---
>
> Key: IMPALA-7564
> URL: https://issues.apache.org/jira/browse/IMPALA-7564
> Project: IMPALA
> Issue Type: Bug
> Components: Frontend
>Affects Versions: Impala 2.12.0, Impala 2.13.0, Impala 3.1.0
>Reporter: bharath v
>Priority: Major
>
> With IMPALA-5547, we predict whether a join is an FK/PK join as follows.
> {noformat}
> // Iterate over all groups of conjuncts that belong to the same joined tuple
> id pair.
> // For each group, we compute the join NDV of the rhs slots and compare
> it to the
> // number of rows in the rhs table.
> for (List fkPkCandidate:
> scanSlotsByJoinedTids.values()) {
> double jointNdv = 1.0;
> for (EqJoinConjunctScanSlots slots: fkPkCandidate) jointNdv *=
> slots.rhsNdv();
> double rhsNumRows = fkPkCandidate.get(0).rhsNumRows();
> if (jointNdv >= Math.round(rhsNumRows * (1.0 -
> FK_PK_MAX_STATS_DELTA_PERC))) {
> // We cannot disprove that the RHS is a PK.
> if (result == null) result = Lists.newArrayList();
> result.addAll(fkPkCandidate);
> }
> }
> {noformat}
> We iterate through all the "simple" equi join conjuncts on the RHS, multiply
> their NDVs and check if it close to rhsNumRows. The issue here is that this
> can result in conservative FK/Pk detection if the equi-join conjuncts are not
> simple (of the form = )
> {noformat}
> /**
> * Returns a new EqJoinConjunctScanSlots for the given equi-join conjunct
> or null if
> * the given conjunct is not of the form = or if the
> underlying
> * table/column of at least one side is missing stats.
> */
> public static EqJoinConjunctScanSlots create(Expr eqJoinConjunct) {
> if (!Expr.IS_EQ_BINARY_PREDICATE.apply(eqJoinConjunct)) return null;
> SlotDescriptor lhsScanSlot =
> eqJoinConjunct.getChild(0).findSrcScanSlot();
> if (lhsScanSlot == null || !hasNumRowsAndNdvStats(lhsScanSlot)) return
> null;
> SlotDescriptor rhsScanSlot =
> eqJoinConjunct.getChild(1).findSrcScanSlot();
> {noformat}
> For example, the following query contains a complex equi-join conjunct
> {{substr(l.c3, 1, 6) = substr(r.c3, 1,6)}}, so while detecting if the left
> outer join is an FK/PK, we just check if
> {{NDVs(r.c1) * NDVs(r.c2) ~ r.numRows()}} which is incorrect. (This happens
> because EqJoinConjunctScanSlots.create() returns null for any non-simple
> predicates which are not considered later).
> {noformat}
> [localhost:21000]> explain select * from test_left l left outer join
> test_right r on l.c1 = r.c1 and l.c2 = r.c2 and substr(l.c3, 1, 6) =
> substr(r.c3, 1,6);
> Query: explain select * from test_left l left outer join test_right r on l.c1
> = r.c1 and l.c2 = r.c2 and substr(l.c3, 1, 6) = substr(r.c3, 1,6)
> +-+
> | Explain String
> |
> +-+
> | Max Per-Host Resource Reservation: Memory=1.95MB Threads=5
> |
> | Per-Host Resource Estimates: Memory=66MB
> |
> |
> |
> | F02:PLAN FRAGMENT [UNPARTITIONED] hosts=1 instances=1
> |
> | | Per-Host Resources: mem-estimate=0B mem-reservation=0B
> thread-reservation=1 |
> | PLAN-ROOT SINK
> |
> | | mem-estimate=0B mem-reservation=0B thread-reservation=0
> |
> | |
[jira] [Commented] (IMPALA-7564) Conservative FK/PK join type detection with complex equi-join conjuncts
[
https://issues.apache.org/jira/browse/IMPALA-7564?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16634796#comment-16634796
]
Paul Rogers commented on IMPALA-7564:
-
The particular issue here appears to be the {{substr()}} function. We cannot
know that that function produces unique keys, that {{NDV(substr(foo) =
NDV(foo)}}.
This is a very odd case. Can we use some kind of hint to tell the planner that
the expression is still unique? (That is, the NDV of the expression = base
table row count.)
> Conservative FK/PK join type detection with complex equi-join conjuncts
> ---
>
> Key: IMPALA-7564
> URL: https://issues.apache.org/jira/browse/IMPALA-7564
> Project: IMPALA
> Issue Type: Bug
> Components: Frontend
>Affects Versions: Impala 2.12.0, Impala 2.13.0, Impala 3.1.0
>Reporter: bharath v
>Priority: Major
>
> With IMPALA-5547, we predict whether a join is an FK/PK join as follows.
> {noformat}
> // Iterate over all groups of conjuncts that belong to the same joined tuple
> id pair.
> // For each group, we compute the join NDV of the rhs slots and compare
> it to the
> // number of rows in the rhs table.
> for (List fkPkCandidate:
> scanSlotsByJoinedTids.values()) {
> double jointNdv = 1.0;
> for (EqJoinConjunctScanSlots slots: fkPkCandidate) jointNdv *=
> slots.rhsNdv();
> double rhsNumRows = fkPkCandidate.get(0).rhsNumRows();
> if (jointNdv >= Math.round(rhsNumRows * (1.0 -
> FK_PK_MAX_STATS_DELTA_PERC))) {
> // We cannot disprove that the RHS is a PK.
> if (result == null) result = Lists.newArrayList();
> result.addAll(fkPkCandidate);
> }
> }
> {noformat}
> We iterate through all the "simple" equi join conjuncts on the RHS, multiply
> their NDVs and check if it close to rhsNumRows. The issue here is that this
> can result in conservative FK/Pk detection if the equi-join conjuncts are not
> simple (of the form = )
> {noformat}
> /**
> * Returns a new EqJoinConjunctScanSlots for the given equi-join conjunct
> or null if
> * the given conjunct is not of the form = or if the
> underlying
> * table/column of at least one side is missing stats.
> */
> public static EqJoinConjunctScanSlots create(Expr eqJoinConjunct) {
> if (!Expr.IS_EQ_BINARY_PREDICATE.apply(eqJoinConjunct)) return null;
> SlotDescriptor lhsScanSlot =
> eqJoinConjunct.getChild(0).findSrcScanSlot();
> if (lhsScanSlot == null || !hasNumRowsAndNdvStats(lhsScanSlot)) return
> null;
> SlotDescriptor rhsScanSlot =
> eqJoinConjunct.getChild(1).findSrcScanSlot();
> {noformat}
> For example, the following query contains a complex equi-join conjunct
> {{substr(l.c3, 1, 6) = substr(r.c3, 1,6)}}, so while detecting if the left
> outer join is an FK/PK, we just check if
> {{NDVs(r.c1) * NDVs(r.c2) ~ r.numRows()}} which is incorrect. (This happens
> because EqJoinConjunctScanSlots.create() returns null for any non-simple
> predicates which are not considered later).
> {noformat}
> [localhost:21000]> explain select * from test_left l left outer join
> test_right r on l.c1 = r.c1 and l.c2 = r.c2 and substr(l.c3, 1, 6) =
> substr(r.c3, 1,6);
> Query: explain select * from test_left l left outer join test_right r on l.c1
> = r.c1 and l.c2 = r.c2 and substr(l.c3, 1, 6) = substr(r.c3, 1,6)
> +-+
> | Explain String
> |
> +-+
> | Max Per-Host Resource Reservation: Memory=1.95MB Threads=5
> |
> | Per-Host Resource Estimates: Memory=66MB
> |
> |
> |
> | F02:PLAN FRAGMENT [UNPARTITIONED] hosts=1 instances=1
> |
> | | Per-Host Resources: mem-estimate=0B mem-reservation=0B
> thread-reservation=1 |
> | PLAN-ROOT SINK
> |
> | | mem-estimate=0B mem-reservation=0B thread-reservation=0
> |
> | |
> |
> | 04:EXCHANGE [UNPARTITIONED]
> |
> | | mem-estimate=0B mem-reservation=0B thread-reservation=0
> |
> | | tuple-ids=0,1N row-size=94B cardinality=49334767023
> |
> | | in pipelines: 00(GETNEXT)
[jira] [Commented] (IMPALA-7564) Conservative FK/PK join type detection with complex equi-join conjuncts
[
https://issues.apache.org/jira/browse/IMPALA-7564?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16626577#comment-16626577
]
Paul Rogers commented on IMPALA-7564:
-
Great description. I think we can tease apart some of the concerns.
First, let's define some terms. In a join, we have two tables, t1 and t2. Let
|t1| be the cardinality of t1, and so on.
The goal is to efficiently join all rows in t1 with all rows in t2 where some
predicate holds. (In the worst was of a cartesian join, the predicate can just
be {{true}}.)
The description discusses NDV. This is useful to predict the number of hash
table buckets on the build side, but is not a good predictor of the number of
_rows_ on the build side.
The description also mentions the primary key (PK). A characteristic of a PK in
an RDB is that the PK is unique, enforced by a unique index. We can detect that
we might have a PK in a join:
{noformat}
SELECT ... FROM t1, t2 WHERE t1.a = t1.b
{noformat}
If {{NDV(ti.a) = |ti|}} for i in (1, 2). In practice, there might be some
wiggle room, may be we use {{NDV(ti.a) >= 0.95 * |ti|}}.
On the other hand, we can detect a foreign key if {{NDV(tj.a) << |tjj|}}.
(Where << means much less than.)
Note that these considerations ignore any predicates in the query: they are
statements about the base tables themselves.
We can further cross-check. Let's say the above suggests that {{t1.a}} is the
PK. Then, t1 is a "master" table and t2 is a "detail" table. We can check this.
It should be that {{|t1| << |t2|}}.
If everything checks out, we can guess that {{t1}} should be on the build side
of the query. We can now apply predicates to see what part of {{t1}} will
actually be considered. (Perhaps I{{t1}} is the {{customer}} table, only the
'CA' customers are considered.)
But, what happens if the sleuthing above turns out to give inconclusive
results? We can fall back on a more basic technique.
Compute the cardinality of the relation that results from applying all relevant
predicates to t1. Call this r1. Do the same for t2 to get r2. The general
rule-of-thumb is to consider {{|r1|}} and {{|r2|}} and put the relation with
the smaller cardinality on the build side.
(One could go further and calculate {{|r1| * width(r1)}} where {{width(r1)}} is
the average row width. One would do this if the total memory is more important
than just the total row count, and if we expect that some tables will be much
narrower than others.)
Now for the kicker. Suppose we do both techniques and we find that the PK/FK
analysis gives one answer, the cardinality analysis gives the other. Which
would we pick?
Suppose t1 is the master table. But, after predicates {{|r1| >> |r2|}}. Would
we still pick t1 for the build side? How much smaller would {{|r2|}} have to be
than {{|r1|}} for us to change our minds?
Consider an example. We join customers and orders. But, we only choose orders
for a five-minute period. That results in, say, 1K orders but we have 1M
customers. Should we reverse the probe/build sides?
If we give heavy weight to the effective relation size, then we don't even need
the PK/FK determination. If we give heavy weight to the PK/FK analysis, then we
will choose a suboptimal plan in extreme conditions.
All of this goes to say that this issue is not quite as cut-and-dried as it
seems. An RDB certainly does not always put the PK on the build side; it often
does the relation size analysis described above.
> Conservative FK/PK join type detection with complex equi-join conjuncts
> ---
>
> Key: IMPALA-7564
> URL: https://issues.apache.org/jira/browse/IMPALA-7564
> Project: IMPALA
> Issue Type: Bug
> Components: Frontend
>Affects Versions: Impala 2.12.0, Impala 2.13.0, Impala 3.1.0
>Reporter: bharath v
>Priority: Major
>
> With IMPALA-5547, we predict whether a join is an FK/PK join as follows.
> {noformat}
> // Iterate over all groups of conjuncts that belong to the same joined tuple
> id pair.
> // For each group, we compute the join NDV of the rhs slots and compare
> it to the
> // number of rows in the rhs table.
> for (List fkPkCandidate:
> scanSlotsByJoinedTids.values()) {
> double jointNdv = 1.0;
> for (EqJoinConjunctScanSlots slots: fkPkCandidate) jointNdv *=
> slots.rhsNdv();
> double rhsNumRows = fkPkCandidate.get(0).rhsNumRows();
> if (jointNdv >= Math.round(rhsNumRows * (1.0 -
> FK_PK_MAX_STATS_DELTA_PERC))) {
> // We cannot disprove that the RHS is a PK.
> if (result == null) result = Lists.newArrayList();
> result.addAll(fkPkCandidate);
> }
> }
> {noformat}
> We iterate through all the "simple" equi join conjuncts on the RHS, multiply
> their NDVs and check if it close to rhsNumRows. The
