iotdb-core/tsfile/src/main/java/org/apache/iotdb/tsfile/read/expression/util/ExpressionOptimizer.java

/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 */

package org.apache.iotdb.tsfile.read.expression.util;

import org.apache.iotdb.tsfile.exception.filter.QueryFilterOptimizationException;
import org.apache.iotdb.tsfile.read.common.Path;
import org.apache.iotdb.tsfile.read.expression.ExpressionType;
import org.apache.iotdb.tsfile.read.expression.IBinaryExpression;
import org.apache.iotdb.tsfile.read.expression.IExpression;
import org.apache.iotdb.tsfile.read.expression.IUnaryExpression;
import org.apache.iotdb.tsfile.read.expression.impl.BinaryExpression;
import org.apache.iotdb.tsfile.read.expression.impl.GlobalTimeExpression;
import org.apache.iotdb.tsfile.read.expression.impl.SingleSeriesExpression;
import org.apache.iotdb.tsfile.read.filter.basic.Filter;
import org.apache.iotdb.tsfile.read.filter.factory.FilterFactory;

import java.util.List;

public class ExpressionOptimizer {

  private ExpressionOptimizer() {}

  public static ExpressionOptimizer getInstance() {
    return QueryFilterOptimizerHelper.INSTANCE;
  }

  /**
   * try to remove GlobalTimeExpression.
   *
   * @param expression IExpression to be transferred
   * @param selectedSeries selected series
   * @return an executable query filter, whether a GlobalTimeExpression or All leaf nodes are
   *     SingleSeriesExpression
   */
  public IExpression optimize(IExpression expression, List<Path> selectedSeries)
      throws QueryFilterOptimizationException {
    if (expression instanceof IUnaryExpression) {
      return expression;
    } else if (expression instanceof IBinaryExpression) {
      ExpressionType relation = expression.getType();
      IExpression left = ((IBinaryExpression) expression).getLeft();
      IExpression right = ((IBinaryExpression) expression).getRight();
      if (left.getType() == ExpressionType.GLOBAL_TIME
          && right.getType() == ExpressionType.GLOBAL_TIME) {
        return combineTwoGlobalTimeFilter(
            (GlobalTimeExpression) left, (GlobalTimeExpression) right, expression.getType());
      } else if (left.getType() == ExpressionType.GLOBAL_TIME
          && right.getType() != ExpressionType.GLOBAL_TIME) {
        return handleOneGlobalTimeFilter(
            (GlobalTimeExpression) left, right, selectedSeries, relation);
      } else if (left.getType() != ExpressionType.GLOBAL_TIME
          && right.getType() == ExpressionType.GLOBAL_TIME) {
        return handleOneGlobalTimeFilter(
            (GlobalTimeExpression) right, left, selectedSeries, relation);
      } else if (left.getType() != ExpressionType.GLOBAL_TIME
          && right.getType() != ExpressionType.GLOBAL_TIME) {
        try {
          IExpression regularLeft = optimize(left, selectedSeries);
          IExpression regularRight = optimize(right, selectedSeries);
          IBinaryExpression midRet = null;
          if (relation == ExpressionType.AND) {
            midRet = BinaryExpression.and(regularLeft, regularRight);
          } else if (relation == ExpressionType.OR) {
            midRet = BinaryExpression.or(regularLeft, regularRight);
          } else {
            throw new UnsupportedOperationException("unsupported IExpression type: " + relation);
          }
          if (midRet.getLeft().getType() == ExpressionType.GLOBAL_TIME
              || midRet.getRight().getType() == ExpressionType.GLOBAL_TIME) {
            return optimize(midRet, selectedSeries);
          } else {
            return midRet;
          }
        } catch (StackOverflowError stackOverflowError) {
          throw new QueryFilterOptimizationException("StackOverflowError is encountered.");
        }
      }
    }
    throw new UnsupportedOperationException(
        "unknown IExpression type: " + expression.getClass().getName());
  }

  private IExpression handleOneGlobalTimeFilter(
      GlobalTimeExpression globalTimeExpression,
      IExpression expression,
      List<Path> selectedSeries,
      ExpressionType relation)
      throws QueryFilterOptimizationException {
    IExpression regularRightIExpression = optimize(expression, selectedSeries);
    if (regularRightIExpression instanceof GlobalTimeExpression) {
      return combineTwoGlobalTimeFilter(
          globalTimeExpression, (GlobalTimeExpression) regularRightIExpression, relation);
    }
    if (relation == ExpressionType.AND) {
      addTimeFilterToQueryFilter((globalTimeExpression).getFilter(), regularRightIExpression);
      return regularRightIExpression;
    } else if (relation == ExpressionType.OR) {
      IExpression afterTransform =
          pushGlobalTimeFilterToAllSeries(globalTimeExpression, selectedSeries);
      return mergeSecondTreeToFirstTree(afterTransform, regularRightIExpression);
    }
    throw new QueryFilterOptimizationException("unknown relation in IExpression:" + relation);
  }

  /**
   * This method merge the second input, which is of tree structure, to the first parameter. It
   * visits all leaf nodes, which are SingleSeriesExpressions, or AndExpression in right Expression,
   * merge them to the right position in leftExpression.
   *
   * @param leftExpression The IExpression transformed from GlobalTimeExpression, which might have
   *     already be updated and merged.
   * @param rightExpression The IExpression to be merged into the first IExpression
   * @return a merged IExpression, which is initially based on the input leftExpression
   */
  private IExpression mergeSecondTreeToFirstTree(
      IExpression leftExpression, IExpression rightExpression) {
    if (rightExpression.getType() == ExpressionType.SERIES) {
      SingleSeriesExpression leaf = (SingleSeriesExpression) rightExpression;
      updateFilterWithOr(leftExpression, leaf.getFilter(), leaf.getSeriesPath());
      return leftExpression;
    } else if (rightExpression.getType() == ExpressionType.OR) {
      IExpression leftChild = ((BinaryExpression) rightExpression).getLeft();
      IExpression rightChild = ((BinaryExpression) rightExpression).getRight();
      leftExpression = mergeSecondTreeToFirstTree(leftExpression, leftChild);
      leftExpression = mergeSecondTreeToFirstTree(leftExpression, rightChild);
      return leftExpression;
    } else {
      return BinaryExpression.or(leftExpression, rightExpression);
    }
  }

  /**
   * This method search the node in the input expression, whose path is identical to the input path,
   * then merges its filter and the input filter with relation OR.
   *
   * @return true if the input filter is merged.
   */
  private boolean updateFilterWithOr(IExpression expression, Filter filter, Path path) {
    if (expression.getType() == ExpressionType.SERIES
        && ((SingleSeriesExpression) expression).getSeriesPath().equals(path)) {
      Filter nodeFilter = ((SingleSeriesExpression) expression).getFilter();
      nodeFilter = FilterFactory.or(nodeFilter, filter);
      ((SingleSeriesExpression) expression).setFilter(nodeFilter);
      return true;
    } else if (expression.getType() == ExpressionType.OR) {
      assert expression instanceof BinaryExpression;
      IExpression left = ((BinaryExpression) expression).getLeft();
      IExpression right = ((BinaryExpression) expression).getRight();
      return updateFilterWithOr(left, filter, path) || updateFilterWithOr(right, filter, path);
    } else {
      return false;
    }
  }

  /**
   * Combine GlobalTimeExpression with all selected series. example: input:
   * GlobalTimeExpression(timeFilter) Selected Series: path1, path2, path3 output: QueryFilterOR(
   * QueryFilterOR( SingleSeriesExpression(path1, timeFilter), SingleSeriesExpression(path2,
   * timeFilter) ), SingleSeriesExpression(path3, timeFilter) )
   *
   * @return a DNF query filter without GlobalTimeExpression
   */
  private IExpression pushGlobalTimeFilterToAllSeries(
      GlobalTimeExpression timeFilter, List<Path> selectedSeries)
      throws QueryFilterOptimizationException {
    if (selectedSeries.isEmpty()) {
      throw new QueryFilterOptimizationException("size of selectSeries could not be 0");
    }
    IExpression expression =
        new SingleSeriesExpression(selectedSeries.get(0), timeFilter.getFilter());
    for (int i = 1; i < selectedSeries.size(); i++) {
      expression =
          BinaryExpression.or(
              expression,
              new SingleSeriesExpression(selectedSeries.get(i), timeFilter.getFilter()));
    }
    return expression;
  }

  /** Combine TimeFilter with all SeriesFilters in the expression. */
  private void addTimeFilterToQueryFilter(Filter timeFilter, IExpression expression) {
    if (expression instanceof SingleSeriesExpression) {
      addTimeFilterToSeriesFilter(timeFilter, (SingleSeriesExpression) expression);
    } else if (expression instanceof BinaryExpression) {
      addTimeFilterToQueryFilter(timeFilter, ((BinaryExpression) expression).getLeft());
      addTimeFilterToQueryFilter(timeFilter, ((BinaryExpression) expression).getRight());
    } else {
      throw new UnsupportedOperationException(
          "IExpression should contains only SingleSeriesExpression but other type is found:"
              + expression.getClass().getName());
    }
  }

  /**
   * Merge the timeFilter with the filter in SingleSeriesExpression with AndExpression. example:
   * input: timeFilter SingleSeriesExpression(path, filter) output: SingleSeriesExpression( path,
   * AndExpression(filter, timeFilter) )
   */
  private void addTimeFilterToSeriesFilter(
      Filter timeFilter, SingleSeriesExpression singleSeriesExp) {
    singleSeriesExp.setFilter(FilterFactory.and(singleSeriesExp.getFilter(), timeFilter));
  }

  /**
   * combine two GlobalTimeExpression by merge the TimeFilter in each GlobalTimeExpression. example:
   * input: QueryFilterAnd/OR( GlobalTimeExpression(timeFilter1), GlobalTimeExpression(timeFilter2)
   * ) output: GlobalTimeExpression( AndExpression/OR(timeFilter1, timeFilter2) )
   */
  private GlobalTimeExpression combineTwoGlobalTimeFilter(
      GlobalTimeExpression left, GlobalTimeExpression right, ExpressionType type) {
    if (type == ExpressionType.AND) {
      return new GlobalTimeExpression(FilterFactory.and(left.getFilter(), right.getFilter()));
    } else if (type == ExpressionType.OR) {
      return new GlobalTimeExpression(FilterFactory.or(left.getFilter(), right.getFilter()));
    }
    throw new UnsupportedOperationException("unrecognized QueryFilterOperatorType :" + type);
  }

  private static class QueryFilterOptimizerHelper {

    private static final ExpressionOptimizer INSTANCE = new ExpressionOptimizer();
  }
}