private long inferPKFKRelationship(int numAttr, List<Operator<? extends OperatorDesc>> parents,
        CommonJoinOperator<? extends JoinDesc> jop) {
      long newNumRows = -1;
      if (numAttr != 1) {
        return newNumRows;
      }

      // If numAttr is 1, this means we join on one single key column.
      Map<Integer, ColStatistics> parentsWithPK = getPrimaryKeyCandidates(parents);

      // We only allow one single PK.
      if (parentsWithPK.size() != 1) {
        LOG.debug("STATS-" + jop.toString() + ": detects none/multiple PK parents.");
        return newNumRows;
      }
      Integer pkPos = parentsWithPK.keySet().iterator().next();
      ColStatistics csPK = parentsWithPK.values().iterator().next();

      // infer foreign key candidates positions
      Map<Integer, ColStatistics> csFKs = getForeignKeyCandidates(parents, csPK);

      // we allow multiple foreign keys (snowflake schema)
      // csfKs.size() + 1 == parents.size() means we have a single PK and all
      // the rest ops are FKs.
      if (csFKs.size() + 1 == parents.size()) {
        newNumRows = getCardinality(parents, pkPos, csPK, csFKs, jop);

        // some debug information
        if (LOG.isDebugEnabled()) {
          List<String> parentIds = Lists.newArrayList();

          // print primary key containing parents
          for (Integer i : parentsWithPK.keySet()) {
            parentIds.add(parents.get(i).toString());
          }
          LOG.debug("STATS-" + jop.toString() + ": PK parent id(s) - " + parentIds);
          parentIds.clear();

          // print foreign key containing parents
          for (Integer i : csFKs.keySet()) {
            parentIds.add(parents.get(i).toString());
          }
          LOG.debug("STATS-" + jop.toString() + ": FK parent id(s) - " + parentIds);
        }
      }
      return newNumRows;
    }
JOIN operator can yield any of the following three cases <ul><li>The values of join keys are
disjoint in both relations in which case T(RXS) = 0 (we need histograms for this)</li> <li>Join
key is primary key on relation R and foreign key on relation S in which case every tuple in S
will have a tuple in R T(RXS) = T(S) (we need histograms for this)</li> <li>Both R &amp; S relation
have same value for join-key. Ex: bool column with all true values T(RXS) = T(R) * T(S) (we
need histograms for this. counDistinct = 1 and same value)</li></ul>
<p>
In the absence of histograms, we can use the following general case
<p>
<b>2 Relations, 1 attribute</b>
<p>
T(RXS) = (T(R)*T(S))/max(V(R,Y), V(S,Y)) where Y is the join attribute
<p>
<b>2 Relations, 2 attributes</b>
<p>
T(RXS) = T(R)*T(S)/max(V(R,y1), V(S,y1)) * max(V(R,y2), V(S,y2)), where y1 and y2 are the join
attributes
<p>
<b>3 Relations, 1 attributes</b>
<p>
T(RXSXQ) = T(R)*T(S)*T(Q)/top2largest(V(R,y), V(S,y), V(Q,y)), where y is the join attribute
<p>
<b>3 Relations, 2 attributes</b>
<p>
T(RXSXQ) = T(R)*T(S)*T(Q)/top2largest(V(R,y1), V(S,y1), V(Q,y1)) * top2largest(V(R,y2), V(S,y2), V(Q,y2)),
where y1 and y2 are the join attributes
<p>
<i>Worst case:</i> If no column statistics are available, then T(RXS) = joinFactor * max(T(R),
T(S)) * (numParents - 1) will be used as heuristics. joinFactor is from hive.stats.join.factor
hive config. In the worst case, since we do not know any information about join keys (and hence
which of the 3 cases to use), we let it to the user to provide the join factor.
<p>
<i>For more information, refer 'Estimating The Cost Of Operations' chapter in
"Database Systems: The Complete Book" by Garcia-Molina et. al.</i>
</p>
ql/src/java/org/apache/hadoop/hive/ql/optimizer/stats/annotation/StatsRulesProcFactory.java