optimize query pattern used by storage filter

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

5 files changed, 341 insertions, 0 deletions

diff --git a/tests/lib/Files/Cache/SearchBuilderTest.php b/tests/lib/Files/Cache/SearchBuilderTest.php
index 5eb1a0252f0..45fa17bd227 100644
--- a/tests/lib/Files/Cache/SearchBuilderTest.php
+++ b/tests/lib/Files/Cache/SearchBuilderTest.php
@@ -154,6 +154,7 @@ class SearchBuilderTest extends TestCase {
 			[new SearchComparison(ISearchComparison::COMPARE_LIKE, 'name', 'foo%'), [0, 1]],
 			[new SearchComparison(ISearchComparison::COMPARE_EQUAL, 'mimetype', 'image/jpg'), [0]],
 			[new SearchComparison(ISearchComparison::COMPARE_LIKE, 'mimetype', 'image/%'), [0, 1]],
+			[new SearchComparison(ISearchComparison::COMPARE_IN, 'mimetype', ['image/jpg', 'image/png']), [0, 1]],
 			[new SearchBinaryOperator(ISearchBinaryOperator::OPERATOR_AND, [
 				new SearchComparison(ISearchComparison::COMPARE_EQUAL, 'size', 50),
 				new SearchComparison(ISearchComparison::COMPARE_LESS_THAN, 'mtime', 125)
diff --git a/tests/lib/Files/Search/QueryOptimizer/CombinedTests.php b/tests/lib/Files/Search/QueryOptimizer/CombinedTests.php
new file mode 100644
index 00000000000..c1d0428176d
--- /dev/null
+++ b/tests/lib/Files/Search/QueryOptimizer/CombinedTests.php
@@ -0,0 +1,45 @@
+<?php
+
+namespace Test\Files\Search\QueryOptimizer;
+
+use OC\Files\Search\QueryOptimizer\QueryOptimizer;
+use OC\Files\Search\SearchBinaryOperator;
+use OC\Files\Search\SearchComparison;
+use OCP\Files\Search\ISearchBinaryOperator;
+use OCP\Files\Search\ISearchComparison;
+use Test\TestCase;
+
+class CombinedTests extends TestCase {
+	private QueryOptimizer $optimizer;
+
+	protected function setUp(): void {
+		parent::setUp();
+
+		$this->optimizer = new QueryOptimizer();
+	}
+
+	public function testBasicOrOfAnds() {
+		$operator = new SearchBinaryOperator(
+			ISearchBinaryOperator::OPERATOR_OR,
+			[
+				new SearchBinaryOperator(ISearchBinaryOperator::OPERATOR_AND, [
+					new SearchComparison(ISearchComparison::COMPARE_EQUAL, "storage", 1),
+					new SearchComparison(ISearchComparison::COMPARE_EQUAL, "path", "foo"),
+				]),
+				new SearchBinaryOperator(ISearchBinaryOperator::OPERATOR_AND, [
+					new SearchComparison(ISearchComparison::COMPARE_EQUAL, "storage", 1),
+					new SearchComparison(ISearchComparison::COMPARE_EQUAL, "path", "bar"),
+				]),
+				new SearchBinaryOperator(ISearchBinaryOperator::OPERATOR_AND, [
+					new SearchComparison(ISearchComparison::COMPARE_EQUAL, "storage", 1),
+					new SearchComparison(ISearchComparison::COMPARE_EQUAL, "path", "asd"),
+				])
+			]
+		);
+		$this->assertEquals('((storage eq 1 and path eq "foo") or (storage eq 1 and path eq "bar") or (storage eq 1 and path eq "asd"))', $operator->__toString());
+
+		$this->optimizer->processOperator($operator);
+
+		$this->assertEquals('(storage eq 1 and path in ["foo","bar","asd"])', $operator->__toString());
+	}
+}
diff --git a/tests/lib/Files/Search/QueryOptimizer/FlattenNestedBoolTest.php b/tests/lib/Files/Search/QueryOptimizer/FlattenNestedBoolTest.php
new file mode 100644
index 00000000000..a21f2a19b90
--- /dev/null
+++ b/tests/lib/Files/Search/QueryOptimizer/FlattenNestedBoolTest.php
@@ -0,0 +1,42 @@
+<?php
+
+namespace Test\Files\Search\QueryOptimizer;
+
+use OC\Files\Search\QueryOptimizer\FlattenNestedBool;
+use OC\Files\Search\QueryOptimizer\FlattenSingleArgumentBinaryOperation;
+use OC\Files\Search\SearchBinaryOperator;
+use OC\Files\Search\SearchComparison;
+use OCP\Files\Search\ISearchBinaryOperator;
+use OCP\Files\Search\ISearchComparison;
+use Test\TestCase;
+
+class FlattenNestedBoolTest extends TestCase {
+	private $optimizer;
+	private $simplifier;
+
+	protected function setUp(): void {
+		parent::setUp();
+
+		$this->optimizer = new FlattenNestedBool();
+		$this->simplifier = new FlattenSingleArgumentBinaryOperation();
+	}
+
+	public function testOrs() {
+		$operator = new SearchBinaryOperator(
+			ISearchBinaryOperator::OPERATOR_OR,
+			[
+				new SearchComparison(ISearchComparison::COMPARE_EQUAL, "path", "foo"),
+				new SearchBinaryOperator(ISearchBinaryOperator::OPERATOR_OR, [
+					new SearchComparison(ISearchComparison::COMPARE_EQUAL, "path", "bar"),
+					new SearchComparison(ISearchComparison::COMPARE_EQUAL, "path", "asd"),
+				])
+			]
+		);
+		$this->assertEquals('(path eq "foo" or (path eq "bar" or path eq "asd"))', $operator->__toString());
+
+		$this->optimizer->processOperator($operator);
+		$this->simplifier->processOperator($operator);
+
+		$this->assertEquals('(path eq "foo" or path eq "bar" or path eq "asd")', $operator->__toString());
+	}
+}
diff --git a/tests/lib/Files/Search/QueryOptimizer/MergeDistributiveOperationsTest.php b/tests/lib/Files/Search/QueryOptimizer/MergeDistributiveOperationsTest.php
new file mode 100644
index 00000000000..49a241a41af
--- /dev/null
+++ b/tests/lib/Files/Search/QueryOptimizer/MergeDistributiveOperationsTest.php
@@ -0,0 +1,133 @@
+<?php
+
+namespace Test\Files\Search\QueryOptimizer;
+
+use OC\Files\Search\QueryOptimizer\FlattenSingleArgumentBinaryOperation;
+use OC\Files\Search\QueryOptimizer\MergeDistributiveOperations;
+use OC\Files\Search\SearchBinaryOperator;
+use OC\Files\Search\SearchComparison;
+use OCP\Files\Search\ISearchBinaryOperator;
+use OCP\Files\Search\ISearchComparison;
+use Test\TestCase;
+
+class MergeDistributiveOperationsTest extends TestCase {
+	private $optimizer;
+	private $simplifier;
+
+	protected function setUp(): void {
+		parent::setUp();
+
+		$this->optimizer = new MergeDistributiveOperations();
+		$this->simplifier = new FlattenSingleArgumentBinaryOperation();
+	}
+
+	public function testBasicOrOfAnds() {
+		$operator = new SearchBinaryOperator(
+			ISearchBinaryOperator::OPERATOR_OR,
+			[
+				new SearchBinaryOperator(ISearchBinaryOperator::OPERATOR_AND, [
+					new SearchComparison(ISearchComparison::COMPARE_EQUAL, "storage", 1),
+					new SearchComparison(ISearchComparison::COMPARE_EQUAL, "path", "foo"),
+				]),
+				new SearchBinaryOperator(ISearchBinaryOperator::OPERATOR_AND, [
+					new SearchComparison(ISearchComparison::COMPARE_EQUAL, "storage", 1),
+					new SearchComparison(ISearchComparison::COMPARE_EQUAL, "path", "bar"),
+				]),
+				new SearchBinaryOperator(ISearchBinaryOperator::OPERATOR_AND, [
+					new SearchComparison(ISearchComparison::COMPARE_EQUAL, "storage", 1),
+					new SearchComparison(ISearchComparison::COMPARE_EQUAL, "path", "asd"),
+				])
+			]
+		);
+		$this->assertEquals('((storage eq 1 and path eq "foo") or (storage eq 1 and path eq "bar") or (storage eq 1 and path eq "asd"))', $operator->__toString());
+
+		$this->optimizer->processOperator($operator);
+		$this->simplifier->processOperator($operator);
+
+		$this->assertEquals('(storage eq 1 and (path eq "foo" or path eq "bar" or path eq "asd"))', $operator->__toString());
+	}
+
+	public function testDontTouchIfNotSame() {
+		$operator = new SearchBinaryOperator(
+			ISearchBinaryOperator::OPERATOR_OR,
+			[
+				new SearchBinaryOperator(ISearchBinaryOperator::OPERATOR_AND, [
+					new SearchComparison(ISearchComparison::COMPARE_EQUAL, "storage", 1),
+					new SearchComparison(ISearchComparison::COMPARE_EQUAL, "path", "foo"),
+				]),
+				new SearchBinaryOperator(ISearchBinaryOperator::OPERATOR_AND, [
+					new SearchComparison(ISearchComparison::COMPARE_EQUAL, "storage", 2),
+					new SearchComparison(ISearchComparison::COMPARE_EQUAL, "path", "bar"),
+				]),
+				new SearchBinaryOperator(ISearchBinaryOperator::OPERATOR_AND, [
+					new SearchComparison(ISearchComparison::COMPARE_EQUAL, "storage", 3),
+					new SearchComparison(ISearchComparison::COMPARE_EQUAL, "path", "asd"),
+				])
+			]
+		);
+		$this->assertEquals('((storage eq 1 and path eq "foo") or (storage eq 2 and path eq "bar") or (storage eq 3 and path eq "asd"))', $operator->__toString());
+
+		$this->optimizer->processOperator($operator);
+		$this->simplifier->processOperator($operator);
+
+		$this->assertEquals('((storage eq 1 and path eq "foo") or (storage eq 2 and path eq "bar") or (storage eq 3 and path eq "asd"))', $operator->__toString());
+	}
+
+	public function testMergePartial() {
+		$operator = new SearchBinaryOperator(
+			ISearchBinaryOperator::OPERATOR_OR,
+			[
+				new SearchBinaryOperator(ISearchBinaryOperator::OPERATOR_AND, [
+					new SearchComparison(ISearchComparison::COMPARE_EQUAL, "storage", 1),
+					new SearchComparison(ISearchComparison::COMPARE_EQUAL, "path", "foo"),
+				]),
+				new SearchBinaryOperator(ISearchBinaryOperator::OPERATOR_AND, [
+					new SearchComparison(ISearchComparison::COMPARE_EQUAL, "storage", 1),
+					new SearchComparison(ISearchComparison::COMPARE_EQUAL, "path", "bar"),
+				]),
+				new SearchBinaryOperator(ISearchBinaryOperator::OPERATOR_AND, [
+					new SearchComparison(ISearchComparison::COMPARE_EQUAL, "storage", 2),
+					new SearchComparison(ISearchComparison::COMPARE_EQUAL, "path", "asd"),
+				])
+			]
+		);
+		$this->assertEquals('((storage eq 1 and path eq "foo") or (storage eq 1 and path eq "bar") or (storage eq 2 and path eq "asd"))', $operator->__toString());
+
+		$this->optimizer->processOperator($operator);
+		$this->simplifier->processOperator($operator);
+
+		$this->assertEquals('((storage eq 1 and (path eq "foo" or path eq "bar")) or (storage eq 2 and path eq "asd"))', $operator->__toString());
+	}
+
+	public function testOptimizeInside() {
+		$operator = new SearchBinaryOperator(
+			ISearchBinaryOperator::OPERATOR_AND,
+			[
+				new SearchBinaryOperator(
+					ISearchBinaryOperator::OPERATOR_OR,
+					[
+						new SearchBinaryOperator(ISearchBinaryOperator::OPERATOR_AND, [
+							new SearchComparison(ISearchComparison::COMPARE_EQUAL, "storage", 1),
+							new SearchComparison(ISearchComparison::COMPARE_EQUAL, "path", "foo"),
+						]),
+						new SearchBinaryOperator(ISearchBinaryOperator::OPERATOR_AND, [
+							new SearchComparison(ISearchComparison::COMPARE_EQUAL, "storage", 1),
+							new SearchComparison(ISearchComparison::COMPARE_EQUAL, "path", "bar"),
+						]),
+						new SearchBinaryOperator(ISearchBinaryOperator::OPERATOR_AND, [
+							new SearchComparison(ISearchComparison::COMPARE_EQUAL, "storage", 1),
+							new SearchComparison(ISearchComparison::COMPARE_EQUAL, "path", "asd"),
+						])
+					]
+				),
+				new SearchComparison(ISearchComparison::COMPARE_EQUAL, "mimetype", "text")
+			]
+		);
+		$this->assertEquals('(((storage eq 1 and path eq "foo") or (storage eq 1 and path eq "bar") or (storage eq 1 and path eq "asd")) and mimetype eq "text")', $operator->__toString());
+
+		$this->optimizer->processOperator($operator);
+		$this->simplifier->processOperator($operator);
+
+		$this->assertEquals('((storage eq 1 and (path eq "foo" or path eq "bar" or path eq "asd")) and mimetype eq "text")', $operator->__toString());
+	}
+}
diff --git a/tests/lib/Files/Search/QueryOptimizer/OrEqualsToInTest.php b/tests/lib/Files/Search/QueryOptimizer/OrEqualsToInTest.php
new file mode 100644
index 00000000000..23b2a6ca07a
--- /dev/null
+++ b/tests/lib/Files/Search/QueryOptimizer/OrEqualsToInTest.php
@@ -0,0 +1,120 @@
+<?php
+
+namespace Test\Files\Search\QueryOptimizer;
+
+use OC\Files\Search\QueryOptimizer\FlattenSingleArgumentBinaryOperation;
+use OC\Files\Search\QueryOptimizer\OrEqualsToIn;
+use OC\Files\Search\SearchBinaryOperator;
+use OC\Files\Search\SearchComparison;
+use OCP\Files\Search\ISearchBinaryOperator;
+use OCP\Files\Search\ISearchComparison;
+use Test\TestCase;
+
+class OrEqualsToInTest extends TestCase {
+	private $optimizer;
+	private $simplifier;
+
+	protected function setUp(): void {
+		parent::setUp();
+
+		$this->optimizer = new OrEqualsToIn();
+		$this->simplifier = new FlattenSingleArgumentBinaryOperation();
+	}
+
+	public function testOrs() {
+		$operator = new SearchBinaryOperator(
+			ISearchBinaryOperator::OPERATOR_OR,
+			[
+				new SearchComparison(ISearchComparison::COMPARE_EQUAL, "path", "foo"),
+				new SearchComparison(ISearchComparison::COMPARE_EQUAL, "path", "bar"),
+				new SearchComparison(ISearchComparison::COMPARE_EQUAL, "path", "asd"),
+			]
+		);
+		$this->assertEquals('(path eq "foo" or path eq "bar" or path eq "asd")', $operator->__toString());
+
+		$this->optimizer->processOperator($operator);
+		$this->simplifier->processOperator($operator);
+
+		$this->assertEquals('path in ["foo","bar","asd"]', $operator->__toString());
+	}
+
+	public function testOrsMultipleFields() {
+		$operator = new SearchBinaryOperator(
+			ISearchBinaryOperator::OPERATOR_OR,
+			[
+				new SearchComparison(ISearchComparison::COMPARE_EQUAL, "path", "foo"),
+				new SearchComparison(ISearchComparison::COMPARE_EQUAL, "path", "bar"),
+				new SearchComparison(ISearchComparison::COMPARE_EQUAL, "fileid", 1),
+				new SearchComparison(ISearchComparison::COMPARE_EQUAL, "fileid", 2),
+				new SearchComparison(ISearchComparison::COMPARE_EQUAL, "mimetype", "asd"),
+			]
+		);
+		$this->assertEquals('(path eq "foo" or path eq "bar" or fileid eq 1 or fileid eq 2 or mimetype eq "asd")', $operator->__toString());
+
+		$this->optimizer->processOperator($operator);
+		$this->simplifier->processOperator($operator);
+
+		$this->assertEquals('(path in ["foo","bar"] or fileid in [1,2] or mimetype eq "asd")', $operator->__toString());
+	}
+
+	public function testPreserveHints() {
+		$operator = new SearchBinaryOperator(
+			ISearchBinaryOperator::OPERATOR_OR,
+			[
+				new SearchComparison(ISearchComparison::COMPARE_EQUAL, "path", "foo"),
+				new SearchComparison(ISearchComparison::COMPARE_EQUAL, "path", "bar"),
+				new SearchComparison(ISearchComparison::COMPARE_EQUAL, "path", "asd"),
+			]
+		);
+		foreach ($operator->getArguments() as $argument) {
+			$argument->setQueryHint(ISearchComparison::HINT_PATH_EQ_HASH, false);
+		}
+		$this->assertEquals('(path eq "foo" or path eq "bar" or path eq "asd")', $operator->__toString());
+
+		$this->optimizer->processOperator($operator);
+		$this->simplifier->processOperator($operator);
+
+		$this->assertEquals('path in ["foo","bar","asd"]', $operator->__toString());
+		$this->assertEquals(false, $operator->getQueryHint(ISearchComparison::HINT_PATH_EQ_HASH, true));
+	}
+
+	public function testOrSomeEq() {
+		$operator = new SearchBinaryOperator(
+			ISearchBinaryOperator::OPERATOR_OR,
+			[
+				new SearchComparison(ISearchComparison::COMPARE_EQUAL, "path", "foo"),
+				new SearchComparison(ISearchComparison::COMPARE_EQUAL, "path", "bar"),
+				new SearchComparison(ISearchComparison::COMPARE_LIKE, "path", "asd%"),
+			]
+		);
+		$this->assertEquals('(path eq "foo" or path eq "bar" or path like "asd%")', $operator->__toString());
+
+		$this->optimizer->processOperator($operator);
+		$this->simplifier->processOperator($operator);
+
+		$this->assertEquals('(path in ["foo","bar"] or path like "asd%")', $operator->__toString());
+	}
+
+	public function testOrsInside() {
+		$operator = new SearchBinaryOperator(
+			ISearchBinaryOperator::OPERATOR_AND,
+			[
+				new SearchComparison(ISearchComparison::COMPARE_EQUAL, "mimetype", "text"),
+				new SearchBinaryOperator(
+					ISearchBinaryOperator::OPERATOR_OR,
+					[
+						new SearchComparison(ISearchComparison::COMPARE_EQUAL, "path", "foo"),
+						new SearchComparison(ISearchComparison::COMPARE_EQUAL, "path", "bar"),
+						new SearchComparison(ISearchComparison::COMPARE_EQUAL, "path", "asd"),
+					]
+				)
+			]
+		);
+		$this->assertEquals('(mimetype eq "text" and (path eq "foo" or path eq "bar" or path eq "asd"))', $operator->__toString());
+
+		$this->optimizer->processOperator($operator);
+		$this->simplifier->processOperator($operator);
+
+		$this->assertEquals('(mimetype eq "text" and path in ["foo","bar","asd"])', $operator->__toString());
+	}
+}