static ExpressionTree convertToCNF(ExpressionTree root) {
      if (root.getChildren() != null) {
        // convert all of the children to CNF
        int size = root.getChildren().size();
        for(int i=0; i < size; ++i) {
          root.getChildren().set(i, convertToCNF(root.getChildren().get(i)));
        }
        if (root.getOperator() == ExpressionTree.Operator.OR) {
          // a list of leaves that weren't under AND expressions
          List<ExpressionTree> nonAndList = new ArrayList<>();
          // a list of AND expressions that we need to distribute
          List<ExpressionTree> andList = new ArrayList<>();
          for(ExpressionTree child: root.getChildren()) {
            if (child.getOperator() == ExpressionTree.Operator.AND) {
              andList.add(child);
            } else if (child.getOperator() == ExpressionTree.Operator.OR) {
              // pull apart the kids of the OR expression
              nonAndList.addAll(child.getChildren());
            } else {
              nonAndList.add(child);
            }
          }
          if (!andList.isEmpty()) {
            if (checkCombinationsThreshold(andList)) {
              root = new ExpressionTree(ExpressionTree.Operator.AND);
              generateAllCombinations(root.getChildren(), andList, nonAndList);
            } else {
              root = new ExpressionTree(TruthValue.YES_NO_NULL);
            }
          }
        }
      }
      return root;
    }
Convert an expression so that the top level operator is AND with OR
operators under it. This routine assumes that all of the NOT operators
have been pushed to the leaves via pushdDownNot.
@param root the expression
@return the normalized expression
storage-api/src/java/org/apache/hadoop/hive/ql/io/sarg/SearchArgumentImpl.java