optimize query pattern used by storage filter

Signed-off-by: Robin Appelman <robin@icewind.nl>

6 files changed, 263 insertions, 5 deletions

diff --git a/lib/private/Files/Search/QueryOptimizer/FlattenNestedBool.php b/lib/private/Files/Search/QueryOptimizer/FlattenNestedBool.php
new file mode 100644
index 00000000000..7f75731fe94
--- /dev/null
+++ b/lib/private/Files/Search/QueryOptimizer/FlattenNestedBool.php
@@ -0,0 +1,30 @@
+<?php
+
+namespace OC\Files\Search\QueryOptimizer;
+
+use OC\Files\Search\SearchBinaryOperator;
+use OCP\Files\Search\ISearchBinaryOperator;
+use OCP\Files\Search\ISearchOperator;
+
+class FlattenNestedBool extends QueryOptimizerStep {
+	public function processOperator(ISearchOperator &$operator) {
+		if (
+			$operator instanceof SearchBinaryOperator && (
+				$operator->getType() === ISearchBinaryOperator::OPERATOR_OR ||
+				$operator->getType() === ISearchBinaryOperator::OPERATOR_AND
+			)
+		) {
+			$newArguments = [];
+			foreach ($operator->getArguments() as $oldArgument) {
+				if ($oldArgument instanceof SearchBinaryOperator && $oldArgument->getType() === $operator->getType()) {
+					$newArguments = array_merge($newArguments, $oldArgument->getArguments());
+				} else {
+					$newArguments[] = $oldArgument;
+				}
+			}
+			$operator->setArguments($newArguments);
+		}
+		parent::processOperator($operator);
+	}
+
+}
diff --git a/lib/private/Files/Search/QueryOptimizer/FlattenSingleArgumentBinaryOperation.php b/lib/private/Files/Search/QueryOptimizer/FlattenSingleArgumentBinaryOperation.php
new file mode 100644
index 00000000000..2c32f2e0174
--- /dev/null
+++ b/lib/private/Files/Search/QueryOptimizer/FlattenSingleArgumentBinaryOperation.php
@@ -0,0 +1,27 @@
+<?php
+
+namespace OC\Files\Search\QueryOptimizer;
+
+use OCP\Files\Search\ISearchBinaryOperator;
+use OCP\Files\Search\ISearchOperator;
+
+/**
+ * replace single argument AND and OR operations with their single argument
+ */
+class FlattenSingleArgumentBinaryOperation extends ReplacingOptimizerStep {
+	public function processOperator(ISearchOperator &$operator): bool {
+		parent::processOperator($operator);
+		if (
+			$operator instanceof ISearchBinaryOperator &&
+			count($operator->getArguments()) === 1 &&
+			(
+				$operator->getType() === ISearchBinaryOperator::OPERATOR_OR ||
+				$operator->getType() === ISearchBinaryOperator::OPERATOR_AND
+			)
+		) {
+			$operator = $operator->getArguments()[0];
+			return true;
+		}
+		return false;
+	}
+}
diff --git a/lib/private/Files/Search/QueryOptimizer/MergeDistributiveOperations.php b/lib/private/Files/Search/QueryOptimizer/MergeDistributiveOperations.php
new file mode 100644
index 00000000000..62ef2cb2e8e
--- /dev/null
+++ b/lib/private/Files/Search/QueryOptimizer/MergeDistributiveOperations.php
@@ -0,0 +1,99 @@
+<?php
+
+namespace OC\Files\Search\QueryOptimizer;
+
+use OC\Files\Search\SearchBinaryOperator;
+use OC\Files\Search\SearchComparison;
+use OCP\Files\Search\ISearchBinaryOperator;
+use OCP\Files\Search\ISearchOperator;
+
+/**
+ * Attempt to transform
+ *
+ * (A AND B) OR (A AND C) into A AND (B OR C)
+ */
+class MergeDistributiveOperations extends ReplacingOptimizerStep {
+	public function processOperator(ISearchOperator &$operator): bool {
+		if (
+			$operator instanceof SearchBinaryOperator &&
+			$this->isAllSameBinaryOperation($operator->getArguments())
+		) {
+			$topLevelType = $operator->getType();
+
+			$groups = $this->groupBinaryOperatorsByChild($operator->getArguments(), 0);
+			$outerOperations = array_map(function (array $operators) use ($topLevelType) {
+				if (count($operators) === 1) {
+					return $operators[0];
+				}
+				/** @var ISearchBinaryOperator $firstArgument */
+				$firstArgument = $operators[0];
+				$outerType = $firstArgument->getType();
+				$extractedLeftHand = $firstArgument->getArguments()[0];
+
+				$rightHandArguments = array_map(function (ISearchOperator $inner) {
+					/** @var ISearchBinaryOperator $inner */
+					$arguments = $inner->getArguments();
+					array_shift($arguments);
+					if (count($arguments) === 1) {
+						return $arguments[0];
+					}
+					return new SearchBinaryOperator($inner->getType(), $arguments);
+				}, $operators);
+				$extractedRightHand = new SearchBinaryOperator($topLevelType, $rightHandArguments);
+				return new SearchBinaryOperator(
+					$outerType,
+					[$extractedLeftHand, $extractedRightHand]
+				);
+			}, $groups);
+			$operator = new SearchBinaryOperator($topLevelType, $outerOperations);
+			parent::processOperator($operator);
+			return true;
+		}
+		return parent::processOperator($operator);
+	}
+
+	/**
+	 * Check that a list of operators is all the same type of (non-empty) binary operators
+	 *
+	 * @param ISearchOperator[] $operators
+	 * @return bool
+	 * @psalm-assert-if-true SearchBinaryOperator[] $operators
+	 */
+	private function isAllSameBinaryOperation(array $operators): bool {
+		$operation = null;
+		foreach ($operators as $operator) {
+			if (!$operator instanceof SearchBinaryOperator) {
+				return false;
+			}
+			if (!$operator->getArguments()) {
+				return false;
+			}
+			if ($operation === null) {
+				$operation = $operator->getType();
+			} else {
+				if ($operation !== $operator->getType()) {
+					return false;
+				}
+			}
+		}
+		return true;
+	}
+
+	/**
+	 * Group a list of binary search operators that have a common argument
+	 *
+	 * @param SearchBinaryOperator[] $operators
+	 * @return SearchBinaryOperator[][]
+	 */
+	private function groupBinaryOperatorsByChild(array $operators, int $index = 0): array {
+		$result = [];
+		foreach ($operators as $operator) {
+			/** @var SearchBinaryOperator|SearchComparison $child */
+			$child = $operator->getArguments()[$index];
+			;
+			$childKey = (string) $child;
+			$result[$childKey][] = $operator;
+		}
+		return array_values($result);
+	}
+}
diff --git a/lib/private/Files/Search/QueryOptimizer/OrEqualsToIn.php b/lib/private/Files/Search/QueryOptimizer/OrEqualsToIn.php
new file mode 100644
index 00000000000..550d85fbda0
--- /dev/null
+++ b/lib/private/Files/Search/QueryOptimizer/OrEqualsToIn.php
@@ -0,0 +1,68 @@
+<?php
+
+namespace OC\Files\Search\QueryOptimizer;
+
+use OC\Files\Search\SearchBinaryOperator;
+use OC\Files\Search\SearchComparison;
+use OCP\Files\Search\ISearchBinaryOperator;
+use OCP\Files\Search\ISearchComparison;
+use OCP\Files\Search\ISearchOperator;
+
+/**
+ * transform (field == A OR field == B ...) into field IN (A, B, ...)
+ */
+class OrEqualsToIn extends ReplacingOptimizerStep {
+	public function processOperator(ISearchOperator &$operator): bool {
+		if (
+			$operator instanceof ISearchBinaryOperator &&
+			$operator->getType() === ISearchBinaryOperator::OPERATOR_OR
+		) {
+			$groups = $this->groupEqualsComparisonsByField($operator->getArguments());
+			$newParts = array_map(function (array $group) {
+				if (count($group) > 1) {
+					// because of the logic from `groupEqualsComparisonsByField` we now that group is all comparisons on the same field
+					/** @var ISearchComparison[] $group */
+					$field = $group[0]->getField();
+					$values = array_map(function (ISearchComparison $comparison) {
+						/** @var string|integer|bool|\DateTime $value */
+						$value = $comparison->getValue();
+						return $value;
+					}, $group);
+					$in = new SearchComparison(ISearchComparison::COMPARE_IN, $field, $values);
+					$in->setQueryHint(ISearchComparison::HINT_PATH_EQ_HASH, $group[0]->getQueryHint(ISearchComparison::HINT_PATH_EQ_HASH, true));
+					return $in;
+				} else {
+					return $group[0];
+				}
+			}, $groups);
+			if (count($newParts) === 1) {
+				$operator = $newParts[0];
+			} else {
+				$operator = new SearchBinaryOperator(ISearchBinaryOperator::OPERATOR_OR, $newParts);
+			}
+			parent::processOperator($operator);
+			return true;
+		}
+		parent::processOperator($operator);
+		return false;
+	}
+
+	/**
+	 * Non-equals operators are put in a separate group for each
+	 *
+	 * @param ISearchOperator[] $operators
+	 * @return ISearchOperator[][]
+	 */
+	private function groupEqualsComparisonsByField(array $operators): array {
+		$result = [];
+		foreach ($operators as $operator) {
+			if ($operator instanceof ISearchComparison && $operator->getType() === ISearchComparison::COMPARE_EQUAL) {
+				$key = $operator->getField() . $operator->getQueryHint(ISearchComparison::HINT_PATH_EQ_HASH, true);
+				$result[$key][] = $operator;
+			} else {
+				$result[] = [$operator];
+			}
+		}
+		return array_values($result);
+	}
+}
diff --git a/lib/private/Files/Search/QueryOptimizer/QueryOptimizer.php b/lib/private/Files/Search/QueryOptimizer/QueryOptimizer.php
index 160b27b7f11..6240ef3367e 100644
--- a/lib/private/Files/Search/QueryOptimizer/QueryOptimizer.php
+++ b/lib/private/Files/Search/QueryOptimizer/QueryOptimizer.php
@@ -29,15 +29,18 @@ class QueryOptimizer {
 	/** @var QueryOptimizerStep[] */
 	private $steps = [];
 
-	public function __construct(
-		PathPrefixOptimizer $pathPrefixOptimizer
-	) {
+	public function __construct() {
+		// note that the order here is relevant
 		$this->steps = [
-			$pathPrefixOptimizer
+			new PathPrefixOptimizer(),
+			new MergeDistributiveOperations(),
+			new FlattenSingleArgumentBinaryOperation(),
+			new OrEqualsToIn(),
+			new FlattenNestedBool(),
 		];
 	}
 
-	public function processOperator(ISearchOperator $operator) {
+	public function processOperator(ISearchOperator &$operator) {
 		foreach ($this->steps as $step) {
 			$step->inspectOperator($operator);
 		}
diff --git a/lib/private/Files/Search/QueryOptimizer/ReplacingOptimizerStep.php b/lib/private/Files/Search/QueryOptimizer/ReplacingOptimizerStep.php
new file mode 100644
index 00000000000..546061522bc
--- /dev/null
+++ b/lib/private/Files/Search/QueryOptimizer/ReplacingOptimizerStep.php
@@ -0,0 +1,31 @@
+<?php
+
+namespace OC\Files\Search\QueryOptimizer;
+
+use OC\Files\Search\SearchBinaryOperator;
+use OCP\Files\Search\ISearchOperator;
+
+/**
+ * Optimizer step that can replace the $operator altogether instead of just modifying it
+ * These steps need some extra logic to properly replace the arguments of binary operators
+ */
+class ReplacingOptimizerStep extends QueryOptimizerStep {
+	/**
+	 * Allow optimizer steps to modify query operators
+	 *
+	 * Returns true if the reference $operator points to a new value
+	 */
+	public function processOperator(ISearchOperator &$operator): bool {
+		if ($operator instanceof SearchBinaryOperator) {
+			$modified = false;
+			$arguments = $operator->getArguments();
+			foreach ($arguments as &$argument) {
+				$modified = $modified || $this->processOperator($argument);
+			}
+			if ($modified) {
+				$operator->setArguments($arguments);
+			}
+		}
+		return false;
+	}
+}