private PredicateParseResult parsePredicateList()

in pinot-controller/src/main/java/org/apache/pinot/controller/recommender/rules/utils/QueryInvertedSortedIndexRecommender.java [339:515]
147 lines of code
27 McCabe index (conditional complexity)

  private PredicateParseResult parsePredicateList(FilterContext predicateList, int depth) {
    LOGGER.debug("parsePredicateList: Parsing predicate list: {}", predicateList.toString());
    FilterContext.Type type = predicateList.getType();
    // case:AND connected predicates
    if (type == FilterContext.Type.AND) {
      LOGGER.trace("parsePredicateList: Parsing AND list {}", predicateList.toString());
      FixedLenBitset candidateDims = mutableEmptySet();
      double nESI = NESI_ZERO;
      double percentSelected = PERCENT_SELECT_ALL;
      List<PredicateParseResult> childResults = new ArrayList<>();
      boolean isPureBitmap = false;

      // Recursively eval child predicates
      for (int i = 0; i < predicateList.getChildren().size(); i++) {
        PredicateParseResult childResult = parsePredicateList(predicateList.getChildren().get(i), depth + 1);
        if (childResult != null) {
          childResults.add(childResult);
        }
      }

      // Sort child candidates based on the priority
      childResults = reorderAndPredicateList(childResults);
      LOGGER.debug("parsePredicateList: AND: Reordered child results: {}", childResults);
      if (childResults.get(childResults.size() - 1).getIteratorEvalPriority()
          .compareTo(IteratorEvalPriorityEnum.INDEXED) <= 0) {
        isPureBitmap = true;
      }

      // Calculate the estimated columns scanned with no indices applied
      for (PredicateParseResult childResult : childResults) {
        nESI += childResult.getnESI() * percentSelected;
        percentSelected *= childResult.getPercentSelected();
      }

      // Recommend nothing if all child predicates already have indices
      if (isPureBitmap) {
        return PredicateParseResult.PredicateParseResultBuilder.aPredicateParseResult()
            .setCandidateDims(FixedLenBitset.IMMUTABLE_EMPTY_SET)
            .setIteratorEvalPriorityEnum(IteratorEvalPriorityEnum.INDEXED)
            .setRecommendationPriorityEnum(RecommendationPriorityEnum.BITMAP).setnESI(nESI)
            .setPercentSelected(percentSelected).setnESIWithIdx(nESI).build();
      }

      Map<RecommendationPriorityEnum, List<PredicateParseResult>> groupedPredicates = childResults.stream()
          .collect(Collectors.groupingBy(PredicateParseResult::getRecommendationPriorityEnum, Collectors.toList()));

      // Recommend nothing if any nested predicate list cannot be converted to a bitmap by applying sorted/inverted
      // indices
      if (groupedPredicates.containsKey(RecommendationPriorityEnum.NESTED) || (
          !groupedPredicates.containsKey(RecommendationPriorityEnum.BITMAP) && !groupedPredicates
              .containsKey(RecommendationPriorityEnum.CANDIDATE_SCAN))) {
        return PredicateParseResult.PredicateParseResultBuilder.aPredicateParseResult()
            .setCandidateDims(FixedLenBitset.IMMUTABLE_EMPTY_SET)
            .setIteratorEvalPriorityEnum(IteratorEvalPriorityEnum.AND)
            .setRecommendationPriorityEnum(RecommendationPriorityEnum.NESTED).setnESI(nESI)
            .setPercentSelected(percentSelected).setnESIWithIdx(nESI).build();
      }

      // Recommend one predicate having min percent docs selected to apply indices on,
      // from the scanning based predicates
      Optional<PredicateParseResult> newCandidateOptional =
          groupedPredicates.getOrDefault(RecommendationPriorityEnum.CANDIDATE_SCAN, Collections.emptyList()).stream()
              .filter(
                  PredicateParseResult::hasCandidateDim) // The predicate should be index applicable to be recommended
              .min(Comparator.comparing(PredicateParseResult::getPercentSelected));

      double bitmapPercentSelected = PERCENT_SELECT_ALL;
      double bitmapNESIWithIdx = NESI_ZERO;
      for (PredicateParseResult predicateParseResult : groupedPredicates
          .getOrDefault(RecommendationPriorityEnum.BITMAP, Collections.emptyList())) {
        bitmapPercentSelected *= predicateParseResult.getPercentSelected();
        bitmapNESIWithIdx += predicateParseResult.getnESIWithIdx();
        candidateDims.union(predicateParseResult.getCandidateDims());
      }

      if (depth > NESTED_SECOND_LEVEL) {
        if (groupedPredicates.containsKey(RecommendationPriorityEnum.BITMAP)) {
          newCandidateOptional = Optional.empty();
        }
      } else {
        if (newCandidateOptional.isPresent()
            && newCandidateOptional.get().getPercentSelected() > bitmapPercentSelected) {
          newCandidateOptional = Optional.empty();
        }
      }
      newCandidateOptional
          .ifPresent(predicateParseResult -> candidateDims.union(predicateParseResult.getCandidateDims()));

      // Calculate the estimated columns scanned with recommended indices applied
      double percentSelectedWithIdx =
          newCandidateOptional.map(PredicateParseResult::getPercentSelected).orElse(PERCENT_SELECT_ALL);
      double nESIWithIdx = newCandidateOptional.map(PredicateParseResult::getnESIWithIdx).orElse(NESI_ZERO);

      percentSelectedWithIdx *= bitmapPercentSelected;
      nESIWithIdx += bitmapNESIWithIdx;

      for (PredicateParseResult predicateParseResult : groupedPredicates
          .getOrDefault(RecommendationPriorityEnum.CANDIDATE_SCAN, Collections.emptyList())) {
        if (predicateParseResult != newCandidateOptional.orElse(null)) {
          nESIWithIdx += predicateParseResult.getnESI() * percentSelectedWithIdx;
          percentSelectedWithIdx *= predicateParseResult.getPercentSelected();
        }
      }

      for (PredicateParseResult predicateParseResult : groupedPredicates
          .getOrDefault(RecommendationPriorityEnum.NON_CANDIDATE_SCAN, Collections.emptyList())) {
        nESIWithIdx += predicateParseResult.getnESI() * percentSelectedWithIdx;
        percentSelectedWithIdx *= predicateParseResult.getPercentSelected();
      }

      return PredicateParseResult.PredicateParseResultBuilder.aPredicateParseResult().setCandidateDims(candidateDims)
          .setIteratorEvalPriorityEnum(IteratorEvalPriorityEnum.AND)
          .setRecommendationPriorityEnum(RecommendationPriorityEnum.BITMAP).setnESI(nESI)
          .setPercentSelected(percentSelected).setnESIWithIdx(nESIWithIdx).build();
    } else if (type == FilterContext.Type.OR) {
      // case:OR connected predicates
      LOGGER.trace("parsePredicateList: OR Parsing  list: {}", predicateList.toString());
      List<PredicateParseResult> childResults = new ArrayList<>();
      FixedLenBitset candidateDims = mutableEmptySet();
      double nESI = NESI_ZERO;
      double nESIWithIdx = NESI_ZERO;
      double percentSelected = PERCENT_SELECT_ZERO;
      boolean isPureBitmap = true;
      boolean isBitmapConvertable = true;

      // Recursively eval child predicates
      for (int i = 0; i < predicateList.getChildren().size(); i++) {
        PredicateParseResult childResult = parsePredicateList(predicateList.getChildren().get(i), depth + 1);
        if (childResult != null) {
          childResults.add(childResult);
        }
      }
      LOGGER.debug("parsePredicateList: OR: childResults {}", childResults);
      // Recommend all child candidates if by doing this the or predicate can be reduced to a bitmap iterator
      for (PredicateParseResult childResult : childResults) {
        nESI += childResult.getnESI();
        percentSelected += childResult.getPercentSelected();
        nESIWithIdx += childResult.getnESIWithIdx();
        candidateDims.union(childResult.getCandidateDims());
        if (!childResult.isBitmapConvertable()) { //Contains column that can not be converted to a Bitmap iterator
          isBitmapConvertable = false;
        }
        if (childResult.getIteratorEvalPriority().compareTo(IteratorEvalPriorityEnum.INDEXED) > 0) {
          isPureBitmap = false;
        }
      }
      LOGGER.trace("parsePredicateList: OR: parsePredicateList(): isPureBitmap {} hasCandidateDim {}", isPureBitmap,
          isBitmapConvertable);
      percentSelected = Math.min(percentSelected, PERCENT_SELECT_ALL);

      if (isPureBitmap) {
        return PredicateParseResult.PredicateParseResultBuilder.aPredicateParseResult().setCandidateDims(candidateDims)
            .setIteratorEvalPriorityEnum(IteratorEvalPriorityEnum.INDEXED)
            .setRecommendationPriorityEnum(RecommendationPriorityEnum.BITMAP).setnESI(nESI)
            .setPercentSelected(percentSelected).setnESIWithIdx(nESIWithIdx).build();
      } else if (isBitmapConvertable) { // The current and predicate cannot be converted to a bitmap by applying indices
        return PredicateParseResult.PredicateParseResultBuilder.aPredicateParseResult().setCandidateDims(candidateDims)
            .setIteratorEvalPriorityEnum(IteratorEvalPriorityEnum.OR)
            .setRecommendationPriorityEnum(RecommendationPriorityEnum.BITMAP).setnESI(nESI)
            .setPercentSelected(percentSelected).setnESIWithIdx(nESIWithIdx).build();
      } else {
        return PredicateParseResult.PredicateParseResultBuilder.aPredicateParseResult()
            .setCandidateDims(FixedLenBitset.IMMUTABLE_EMPTY_SET)
            .setIteratorEvalPriorityEnum(IteratorEvalPriorityEnum.OR)
            .setRecommendationPriorityEnum(RecommendationPriorityEnum.NESTED).setnESI(nESI)
            .setPercentSelected(percentSelected).setnESIWithIdx(nESI).build();
      }
    } else if (type == FilterContext.Type.NOT) {
      assert predicateList.getChildren().size() == 1;
      return parsePredicateList(predicateList.getChildren().get(0), depth);
    } else {
      // case:Leaf predicate
      PredicateParseResult predicateParseResult = parseLeafPredicate(predicateList, depth);
      LOGGER.debug("parsePredicateList: Parsed a leaf predicate: {}", predicateParseResult);
      return predicateParseResult;
    }
  }