private long calculateUnmatchedRowsForOuter(HiveConf conf, long inputRowCount,
        List<String> joinKeys, Statistics statistics, long distinctUnmatched) {
      // Extract the ndv from each of the columns involved in the join
      List<Long> distinctVals = new ArrayList<>();
      for (String col: joinKeys) {
        ColStatistics cs = statistics.getColumnStatisticsFromColName(col);
        if (cs != null) {
          distinctVals.add(cs.getCountDistint());
        }
      }
      // Compute the number of distinct values based on configuration property
      long distinctVal;
      if (distinctVals.isEmpty()) {
        distinctVal = 2L;
      } else {
        if (joinKeys.size() > 1 && conf.getBoolVar(HiveConf.ConfVars.HIVE_STATS_CORRELATED_MULTI_KEY_JOINS)) {
          distinctVal = Collections.max(distinctVals);
        } else {
          distinctVal = StatsUtils.addWithExpDecay(distinctVals);
        }
      }
      // If we have a greater number of unmatched values than number of distinct values,
      // we just return the number of rows in the input as we can assume there are no
      // matches
      if (distinctUnmatched >= distinctVal) {
        return inputRowCount;
      }
      // Otherwise, divide the number of input rows by the number of distinct values
      // and divide by the number of distinct values unmatched
      return StatsUtils.safeMult(inputRowCount / distinctVal, distinctUnmatched);
    }
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