generate a better optimized query for path prefix search filters

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

11 files changed, 201 insertions, 9 deletions

diff --git a/lib/composer/composer/autoload_classmap.php b/lib/composer/composer/autoload_classmap.php
index 70a784a5ac1..0218fd44102 100644
--- a/lib/composer/composer/autoload_classmap.php
+++ b/lib/composer/composer/autoload_classmap.php
@@ -1117,6 +1117,9 @@ return array(
     'OC\\Files\\ObjectStore\\Swift' => $baseDir . '/lib/private/Files/ObjectStore/Swift.php',
     'OC\\Files\\ObjectStore\\SwiftFactory' => $baseDir . '/lib/private/Files/ObjectStore/SwiftFactory.php',
     'OC\\Files\\ObjectStore\\SwiftV2CachingAuthService' => $baseDir . '/lib/private/Files/ObjectStore/SwiftV2CachingAuthService.php',
+    'OC\\Files\\Search\\QueryOptimizer\\PathPrefixOptimizer' => $baseDir . '/lib/private/Files/Search/QueryOptimizer/PathPrefixOptimizer.php',
+    'OC\\Files\\Search\\QueryOptimizer\\QueryOptimizer' => $baseDir . '/lib/private/Files/Search/QueryOptimizer/QueryOptimizer.php',
+    'OC\\Files\\Search\\QueryOptimizer\\QueryOptimizerStep' => $baseDir . '/lib/private/Files/Search/QueryOptimizer/QueryOptimizerStep.php',
     'OC\\Files\\Search\\SearchBinaryOperator' => $baseDir . '/lib/private/Files/Search/SearchBinaryOperator.php',
     'OC\\Files\\Search\\SearchComparison' => $baseDir . '/lib/private/Files/Search/SearchComparison.php',
     'OC\\Files\\Search\\SearchOrder' => $baseDir . '/lib/private/Files/Search/SearchOrder.php',
diff --git a/lib/composer/composer/autoload_static.php b/lib/composer/composer/autoload_static.php
index 93a73ef08fd..17eb949609e 100644
--- a/lib/composer/composer/autoload_static.php
+++ b/lib/composer/composer/autoload_static.php
@@ -1146,6 +1146,9 @@ class ComposerStaticInit53792487c5a8370acc0b06b1a864ff4c
         'OC\\Files\\ObjectStore\\Swift' => __DIR__ . '/../../..' . '/lib/private/Files/ObjectStore/Swift.php',
         'OC\\Files\\ObjectStore\\SwiftFactory' => __DIR__ . '/../../..' . '/lib/private/Files/ObjectStore/SwiftFactory.php',
         'OC\\Files\\ObjectStore\\SwiftV2CachingAuthService' => __DIR__ . '/../../..' . '/lib/private/Files/ObjectStore/SwiftV2CachingAuthService.php',
+        'OC\\Files\\Search\\QueryOptimizer\\PathPrefixOptimizer' => __DIR__ . '/../../..' . '/lib/private/Files/Search/QueryOptimizer/PathPrefixOptimizer.php',
+        'OC\\Files\\Search\\QueryOptimizer\\QueryOptimizer' => __DIR__ . '/../../..' . '/lib/private/Files/Search/QueryOptimizer/QueryOptimizer.php',
+        'OC\\Files\\Search\\QueryOptimizer\\QueryOptimizerStep' => __DIR__ . '/../../..' . '/lib/private/Files/Search/QueryOptimizer/QueryOptimizerStep.php',
         'OC\\Files\\Search\\SearchBinaryOperator' => __DIR__ . '/../../..' . '/lib/private/Files/Search/SearchBinaryOperator.php',
         'OC\\Files\\Search\\SearchComparison' => __DIR__ . '/../../..' . '/lib/private/Files/Search/SearchComparison.php',
         'OC\\Files\\Search\\SearchOrder' => __DIR__ . '/../../..' . '/lib/private/Files/Search/SearchOrder.php',
diff --git a/lib/private/Files/Cache/QuerySearchHelper.php b/lib/private/Files/Cache/QuerySearchHelper.php
index 683b580d9d1..e065e95e4fd 100644
--- a/lib/private/Files/Cache/QuerySearchHelper.php
+++ b/lib/private/Files/Cache/QuerySearchHelper.php
@@ -25,6 +25,7 @@
  */
 namespace OC\Files\Cache;
 
+use OC\Files\Search\QueryOptimizer\QueryOptimizer;
 use OC\Files\Search\SearchBinaryOperator;
 use OC\SystemConfig;
 use OCP\Files\Cache\ICache;
@@ -47,19 +48,23 @@ class QuerySearchHelper {
 	private $logger;
 	/** @var SearchBuilder */
 	private $searchBuilder;
+	/** @var QueryOptimizer */
+	private $queryOptimizer;
 
 	public function __construct(
 		IMimeTypeLoader $mimetypeLoader,
 		IDBConnection $connection,
 		SystemConfig $systemConfig,
 		ILogger $logger,
-		SearchBuilder $searchBuilder
+		SearchBuilder $searchBuilder,
+		QueryOptimizer $queryOptimizer
 	) {
 		$this->mimetypeLoader = $mimetypeLoader;
 		$this->connection = $connection;
 		$this->systemConfig = $systemConfig;
 		$this->logger = $logger;
 		$this->searchBuilder = $searchBuilder;
+		$this->queryOptimizer = $queryOptimizer;
 	}
 
 	protected function getQueryBuilder() {
@@ -115,15 +120,17 @@ class QuerySearchHelper {
 				->andWhere($builder->expr()->eq('tag.uid', $builder->createNamedParameter($user->getUID())));
 		}
 
-		$searchExpr = $this->searchBuilder->searchOperatorToDBExpr($builder, $searchQuery->getSearchOperation());
-		if ($searchExpr) {
-			$query->andWhere($searchExpr);
-		}
-
 		$storageFilters = array_values(array_map(function (ICache $cache) {
 			return $cache->getQueryFilterForStorage();
 		}, $caches));
-		$query->andWhere($this->searchBuilder->searchOperatorToDBExpr($builder, new SearchBinaryOperator(ISearchBinaryOperator::OPERATOR_OR, $storageFilters)));
+		$storageFilter = new SearchBinaryOperator(ISearchBinaryOperator::OPERATOR_OR, $storageFilters);
+		$filter = new SearchBinaryOperator(ISearchBinaryOperator::OPERATOR_AND, [$searchQuery->getSearchOperation(), $storageFilter]);
+		$this->queryOptimizer->processOperator($filter);
+
+		$searchExpr = $this->searchBuilder->searchOperatorToDBExpr($builder, $filter);
+		if ($searchExpr) {
+			$query->andWhere($searchExpr);
+		}
 
 		$this->searchBuilder->addSearchOrdersToQuery($query, $searchQuery->getOrder());
 
diff --git a/lib/private/Files/Cache/SearchBuilder.php b/lib/private/Files/Cache/SearchBuilder.php
index be38e5622bf..003d3ac15e7 100644
--- a/lib/private/Files/Cache/SearchBuilder.php
+++ b/lib/private/Files/Cache/SearchBuilder.php
@@ -87,7 +87,7 @@ class SearchBuilder {
 
 	/**
 	 * @param IQueryBuilder $builder
-	 * @param ISearchOperator $operator
+	 * @param ISearchOperator[] $operators
 	 */
 	public function searchOperatorArrayToDBExprArray(IQueryBuilder $builder, array $operators) {
 		return array_filter(array_map(function ($operator) use ($builder) {
@@ -97,6 +97,7 @@ class SearchBuilder {
 
 	public function searchOperatorToDBExpr(IQueryBuilder $builder, ISearchOperator $operator) {
 		$expr = $builder->expr();
+
 		if ($operator instanceof ISearchBinaryOperator) {
 			if (count($operator->getArguments()) === 0) {
 				return null;
@@ -166,7 +167,7 @@ class SearchBuilder {
 			$field = 'tag.category';
 		} elseif ($field === 'fileid') {
 			$field = 'file.fileid';
-		} elseif ($field === 'path' && $type === ISearchComparison::COMPARE_EQUAL) {
+		} elseif ($field === 'path' && $type === ISearchComparison::COMPARE_EQUAL && $operator->getQueryHint(ISearchComparison::HINT_PATH_EQ_HASH, true)) {
 			$field = 'path_hash';
 			$value = md5((string)$value);
 		}
diff --git a/lib/private/Files/Search/QueryOptimizer/PathPrefixOptimizer.php b/lib/private/Files/Search/QueryOptimizer/PathPrefixOptimizer.php
new file mode 100644
index 00000000000..eea4b430578
--- /dev/null
+++ b/lib/private/Files/Search/QueryOptimizer/PathPrefixOptimizer.php
@@ -0,0 +1,58 @@
+<?php
+
+declare(strict_types=1);
+/**
+ * @copyright Copyright (c) 2021 Robin Appelman <robin@icewind.nl>
+ *
+ * @license GNU AGPL version 3 or any later version
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Affero General Public License as
+ * published by the Free Software Foundation, either version 3 of the
+ * License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Affero General Public License for more details.
+ *
+ * You should have received a copy of the GNU Affero General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ */
+
+namespace OC\Files\Search\QueryOptimizer;
+
+use OCP\Files\Search\ISearchBinaryOperator;
+use OCP\Files\Search\ISearchComparison;
+use OCP\Files\Search\ISearchOperator;
+
+class PathPrefixOptimizer extends QueryOptimizerStep {
+	public function escapeLikeParameter(string $param): string {
+		return addcslashes($param, '\\_%');
+	}
+
+	public function processOperator(ISearchOperator &$operator) {
+		// normally the `path = "$prefix"` search query part of the prefix filter would be generated as an `path_hash = md5($prefix)` sql query
+		// since the `path_hash` sql column usually provides much faster querying that selecting on the `path` sql column
+		//
+		// however, since we're already doing a filter on the `path` column in the form of `path LIKE "$prefix/%"`
+		// generating a `path = "$prefix"` sql query lets the database handle use the same column for both expressions and potentially use the same index
+		if ($operator instanceof ISearchBinaryOperator && $operator->getType() === ISearchBinaryOperator::OPERATOR_OR && count($operator->getArguments()) == 2) {
+			$a = $operator->getArguments()[0];
+			$b = $operator->getArguments()[1];
+			if ($a instanceof ISearchComparison && $b instanceof ISearchComparison && $a->getField() === 'path' && $b->getField() === 'path') {
+				if ($a->getType() === ISearchComparison::COMPARE_LIKE_CASE_SENSITIVE && $b->getType() === ISearchComparison::COMPARE_EQUAL
+					&& $a->getValue() === $this->escapeLikeParameter($b->getValue()) . '/%') {
+					$b->setQueryHint(ISearchComparison::HINT_PATH_EQ_HASH, false);
+				}
+				if ($b->getType() === ISearchComparison::COMPARE_LIKE_CASE_SENSITIVE && $a->getType() === ISearchComparison::COMPARE_EQUAL
+					&& $b->getValue() === $this->escapeLikeParameter($a->getValue()) . '/%') {
+					$a->setQueryHint(ISearchComparison::HINT_PATH_EQ_HASH, false);
+				}
+			}
+		}
+
+		parent::processOperator($operator);
+	}
+}
diff --git a/lib/private/Files/Search/QueryOptimizer/QueryOptimizer.php b/lib/private/Files/Search/QueryOptimizer/QueryOptimizer.php
new file mode 100644
index 00000000000..1635e50335a
--- /dev/null
+++ b/lib/private/Files/Search/QueryOptimizer/QueryOptimizer.php
@@ -0,0 +1,45 @@
+<?php
+
+declare(strict_types=1);
+/**
+ * @copyright Copyright (c) 2021 Robin Appelman <robin@icewind.nl>
+ *
+ * @license GNU AGPL version 3 or any later version
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Affero General Public License as
+ * published by the Free Software Foundation, either version 3 of the
+ * License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Affero General Public License for more details.
+ *
+ * You should have received a copy of the GNU Affero General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ */
+
+namespace OC\Files\Search\QueryOptimizer;
+
+use OCP\Files\Search\ISearchOperator;
+
+class QueryOptimizer {
+	/** @var QueryOptimizerStep[] */
+	private $steps = [];
+
+	public function __construct(
+		PathPrefixOptimizer $pathPrefixOptimizer
+	) {
+		$this->steps = [
+			$pathPrefixOptimizer
+		];
+	}
+
+	public function processOperator(ISearchOperator $operator) {
+		foreach ($this->steps as $step) {
+			$step->processOperator($operator);
+		}
+	}
+}
diff --git a/lib/private/Files/Search/QueryOptimizer/QueryOptimizerStep.php b/lib/private/Files/Search/QueryOptimizer/QueryOptimizerStep.php
new file mode 100644
index 00000000000..4f683899723
--- /dev/null
+++ b/lib/private/Files/Search/QueryOptimizer/QueryOptimizerStep.php
@@ -0,0 +1,37 @@
+<?php
+
+declare(strict_types=1);
+/**
+ * @copyright Copyright (c) 2021 Robin Appelman <robin@icewind.nl>
+ *
+ * @license GNU AGPL version 3 or any later version
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Affero General Public License as
+ * published by the Free Software Foundation, either version 3 of the
+ * License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Affero General Public License for more details.
+ *
+ * You should have received a copy of the GNU Affero General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ */
+
+namespace OC\Files\Search\QueryOptimizer;
+
+use OCP\Files\Search\ISearchBinaryOperator;
+use OCP\Files\Search\ISearchOperator;
+
+class QueryOptimizerStep {
+	public function processOperator(ISearchOperator &$operator) {
+		if ($operator instanceof ISearchBinaryOperator) {
+			foreach ($operator->getArguments() as $argument) {
+				$this->processOperator($argument);
+			}
+		}
+	}
+}
diff --git a/lib/private/Files/Search/SearchBinaryOperator.php b/lib/private/Files/Search/SearchBinaryOperator.php
index 3ebbae06e3e..d7bba8f1b4e 100644
--- a/lib/private/Files/Search/SearchBinaryOperator.php
+++ b/lib/private/Files/Search/SearchBinaryOperator.php
@@ -30,6 +30,7 @@ class SearchBinaryOperator implements ISearchBinaryOperator {
 	private $type;
 	/** @var ISearchOperator[] */
 	private $arguments;
+	private $hints = [];
 
 	/**
 	 * SearchBinaryOperator constructor.
@@ -55,4 +56,12 @@ class SearchBinaryOperator implements ISearchBinaryOperator {
 	public function getArguments() {
 		return $this->arguments;
 	}
+
+	public function getQueryHint(string $name, $default) {
+		return $this->hints[$name] ?? $default;
+	}
+
+	public function setQueryHint(string $name, $value): void {
+		$this->hints[$name] = $value;
+	}
 }
diff --git a/lib/private/Files/Search/SearchComparison.php b/lib/private/Files/Search/SearchComparison.php
index 83d8904776a..ab5a4d0ed73 100644
--- a/lib/private/Files/Search/SearchComparison.php
+++ b/lib/private/Files/Search/SearchComparison.php
@@ -31,6 +31,7 @@ class SearchComparison implements ISearchComparison {
 	private $field;
 	/** @var string|integer|\DateTime */
 	private $value;
+	private $hints = [];
 
 	/**
 	 * SearchComparison constructor.
@@ -65,4 +66,12 @@ class SearchComparison implements ISearchComparison {
 	public function getValue() {
 		return $this->value;
 	}
+
+	public function getQueryHint(string $name, $default) {
+		return $this->hints[$name] ?? $default;
+	}
+
+	public function setQueryHint(string $name, $value): void {
+		$this->hints[$name] = $value;
+	}
 }
diff --git a/lib/public/Files/Search/ISearchComparison.php b/lib/public/Files/Search/ISearchComparison.php
index 36d10824653..8ebaeced304 100644
--- a/lib/public/Files/Search/ISearchComparison.php
+++ b/lib/public/Files/Search/ISearchComparison.php
@@ -35,6 +35,8 @@ interface ISearchComparison extends ISearchOperator {
 	public const COMPARE_LIKE = 'like';
 	public const COMPARE_LIKE_CASE_SENSITIVE = 'clike';
 
+	public const HINT_PATH_EQ_HASH = 'path_eq_hash'; // transform `path = "$path"` into `path_hash = md5("$path")`, on by default
+
 	/**
 	 * Get the type of comparison, one of the ISearchComparison::COMPARE_* constants
 	 *
diff --git a/lib/public/Files/Search/ISearchOperator.php b/lib/public/Files/Search/ISearchOperator.php
index bcf2fb86573..1799b97c1ca 100644
--- a/lib/public/Files/Search/ISearchOperator.php
+++ b/lib/public/Files/Search/ISearchOperator.php
@@ -26,4 +26,22 @@ namespace OCP\Files\Search;
  * @since 12.0.0
  */
 interface ISearchOperator {
+	/**
+	 * Get a query builder hint by name
+	 *
+	 * @param string $name
+	 * @param $default
+	 * @return mixed
+	 * @since 23.0.0
+	 */
+	public function getQueryHint(string $name, $default);
+
+	/**
+	 * Get a query builder hint
+	 *
+	 * @param string $name
+	 * @param $value
+	 * @since 23.0.0
+	 */
+	public function setQueryHint(string $name, $value): void;
 }