From 618bc8df1805247c896a852f102a306dd980ec9e Mon Sep 17 00:00:00 2001 From: Håvard Pettersen Date: Thu, 27 Oct 2022 09:32:16 +0000 Subject: create optimized filter search test strict/constraint propagation test filters dropped due to short-circuit --- .../queryeval/filter_search/filter_search_test.cpp | 409 ++++++++++++++++----- 1 file changed, 308 insertions(+), 101 deletions(-) (limited to 'searchlib/src/tests/queryeval') diff --git a/searchlib/src/tests/queryeval/filter_search/filter_search_test.cpp b/searchlib/src/tests/queryeval/filter_search/filter_search_test.cpp index ecb7ee3b48b..8748124d6f0 100644 --- a/searchlib/src/tests/queryeval/filter_search/filter_search_test.cpp +++ b/searchlib/src/tests/queryeval/filter_search/filter_search_test.cpp @@ -1,6 +1,10 @@ // Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +#pragma GCC diagnostic ignored "-Winline" + #include +#include +#include #include #include #include @@ -16,6 +20,7 @@ #include #include #include +#include namespace search::fef { class TermFieldMatchDataArray; } namespace search::fef { class MatchData; } @@ -33,13 +38,8 @@ constexpr auto upper_bound = Constraint::UPPER_BOUND; const uint32_t docid_limit = 100; template -concept FilterFactory = requires(const T &a, bool strict, Constraint upper_or_lower) { - { a.createFilterSearch(strict, upper_or_lower) } -> std::same_as>; -}; - -template -concept FilterFactoryBuilder = requires(T a, std::unique_ptr bp) { - { a.add(std::move(bp)) } -> std::same_as; +concept FilterFactory = requires(const T &a, bool strict, Constraint constraint) { + { a.createFilterSearch(strict, constraint) } -> std::same_as>; }; template @@ -56,18 +56,53 @@ struct DefaultBlueprint : Blueprint { SearchIteratorUP createSearch(MatchData &, bool) const override { abort(); } }; -// add the use of a field to a leaf blueprint (SimplePhraseBlueprint asserts on this) -struct FakeFieldProxy : SimpleLeafBlueprint { +// proxy class used to make various decorators for leaf blueprints +// may be used directly to add the use of a field to a leaf blueprint +struct LeafProxy : SimpleLeafBlueprint { std::unique_ptr child; - FakeFieldProxy(const FieldSpec &field, std::unique_ptr child_in) - : SimpleLeafBlueprint(field), child(std::move(child_in)) - { + void init() { setParent(child->getParent()); child->setParent(this); } + LeafProxy(std::unique_ptr child_in) + : SimpleLeafBlueprint({}), child(std::move(child_in)) { init(); } + LeafProxy(const FieldSpec &field, std::unique_ptr child_in) + : SimpleLeafBlueprint(field), child(std::move(child_in)) { init(); } SearchIteratorUP createLeafSearch(const TermFieldMatchDataArray &, bool) const override { abort(); } - SearchIteratorUP createFilterSearch(bool strict, Constraint upper_or_lower) const override { - return child->createFilterSearch(strict, upper_or_lower); + SearchIteratorUP createFilterSearch(bool strict, Constraint constraint) const override { + return child->createFilterSearch(strict, constraint); + } +}; + +// check strictness and filter constraints when creating a filter search +struct CheckParamsProxy : LeafProxy { + static bool current_strict; // <- changed by test + static Constraint current_constraint; // <- changed by test + bool expect_inherit_strict; + bool expect_same_constraint; + CheckParamsProxy(std::unique_ptr child_in, bool expect_inherit_strict_in, bool expect_same_constraint_in) + : LeafProxy(std::move(child_in)), + expect_inherit_strict(expect_inherit_strict_in), expect_same_constraint(expect_same_constraint_in) {} + SearchIteratorUP createFilterSearch(bool strict, Constraint constraint) const override { + EXPECT_EQ(strict, (current_strict && expect_inherit_strict)); + EXPECT_EQ((constraint == current_constraint), expect_same_constraint); + return child->createFilterSearch(strict, constraint); + } +}; +bool CheckParamsProxy::current_strict = false; +Constraint CheckParamsProxy::current_constraint = lower_bound; + +// check dropped blueprints (due to short-circuit) +struct CheckDroppedProxy : LeafProxy { + mutable bool used; + CheckDroppedProxy(std::unique_ptr child_in) + : LeafProxy(std::move(child_in)), used(false) {} + SearchIteratorUP createFilterSearch(bool strict, Constraint constraint) const override { + used = true; + return child->createFilterSearch(strict, constraint); + } + ~CheckDroppedProxy() override { + EXPECT_EQ(used, false); } }; @@ -118,6 +153,16 @@ std::unique_ptr hits(const std::vector &docs) { return std::make_unique(make_result(docs)); } +// check filter creation parameters +std::unique_ptr check(std::unique_ptr child, bool expect_inherit_strict, bool expect_same_constraint) { + return std::make_unique(std::move(child), expect_inherit_strict, expect_same_constraint); +} + +// check that create filter is not called +std::unique_ptr dropped(std::unique_ptr child) { + return std::make_unique(std::move(child)); +} + // Describes blueprint children with a list of simple factories that // can later be used to create them. struct Children { @@ -137,12 +182,21 @@ struct Children { list.push_back([](){ return ::empty(); }); return *this; } - template - Builder &apply(Builder &builder) const { + Children &check(bool expect_inherit_strict, bool expect_same_constraint) { + Factory old_factory = list.back(); + list.back() = [=](){ return ::check(old_factory(), expect_inherit_strict, expect_same_constraint); }; + return *this; + } + Children &dropped() { + Factory old_factory = list.back(); + list.back() = [=](){ return ::dropped(old_factory()); }; + return *this; + } + template + void apply(Builder &builder) const { for (const Factory &make_child: list) { - builder.add(make_child()); + builder.addChild(make_child()); } - return builder; } }; @@ -152,20 +206,16 @@ struct Combine { using factory_fun = std::function(const Blueprint::Children &, bool, Constraint)>; factory_fun fun; Blueprint::Children list; - Combine(factory_fun fun_in) noexcept : fun(fun_in), list() {} - Combine &add(std::unique_ptr child) { - list.push_back(std::move(child)); - return *this; + Combine(factory_fun fun_in, const Children &child_list) : fun(fun_in), list() { + child_list.apply(*this); } - Combine &add(const Children &children) { - return children.apply(*this); + void addChild(std::unique_ptr child) { + list.push_back(std::move(child)); } - auto createFilterSearch(bool strict, Constraint upper_or_lower) const { - return fun(list, strict, upper_or_lower); + auto createFilterSearch(bool strict, Constraint constraint) const { + return fun(list, strict, constraint); } - ~Combine(); }; -Combine::~Combine() = default; // enable Make-ing source blender struct SourceBlenderAdapter { @@ -175,8 +225,8 @@ struct SourceBlenderAdapter { void addChild(std::unique_ptr child) { blueprint.addChild(std::move(child)); } - auto createFilterSearch(bool strict, Constraint upper_or_lower) const { - return blueprint.createFilterSearch(strict, upper_or_lower); + auto createFilterSearch(bool strict, Constraint constraint) const { + return blueprint.createFilterSearch(strict, constraint); } }; @@ -187,11 +237,11 @@ struct SimplePhraseAdapter { SimplePhraseAdapter() : field("foo", 3, 7), blueprint(field, false) {} void addChild(std::unique_ptr child) { auto child_field = blueprint.getNextChildField(field); - auto term = std::make_unique(child_field, std::move(child)); + auto term = std::make_unique(child_field, std::move(child)); blueprint.addTerm(std::move(term)); } - auto createFilterSearch(bool strict, Constraint upper_or_lower) const { - return blueprint.createFilterSearch(strict, upper_or_lower); + auto createFilterSearch(bool strict, Constraint constraint) const { + return blueprint.createFilterSearch(strict, constraint); } }; @@ -203,8 +253,8 @@ struct EquivAdapter { void addChild(std::unique_ptr child) { blueprint.addTerm(std::move(child), 1.0); } - auto createFilterSearch(bool strict, Constraint upper_or_lower) const { - return blueprint.createFilterSearch(strict, upper_or_lower); + auto createFilterSearch(bool strict, Constraint constraint) const { + return blueprint.createFilterSearch(strict, constraint); } }; @@ -216,8 +266,8 @@ struct WeightedSetTermAdapter { void addChild(std::unique_ptr child) { blueprint.addTerm(std::move(child), 100); } - auto createFilterSearch(bool strict, Constraint upper_or_lower) const { - return blueprint.createFilterSearch(strict, upper_or_lower); + auto createFilterSearch(bool strict, Constraint constraint) const { + return blueprint.createFilterSearch(strict, constraint); } }; @@ -228,11 +278,11 @@ struct DotProductAdapter { DotProductAdapter() : field("foo", 3, 7), blueprint(field) {} void addChild(std::unique_ptr child) { auto child_field = blueprint.getNextChildField(field); - auto term = std::make_unique(child_field, std::move(child)); + auto term = std::make_unique(child_field, std::move(child)); blueprint.addTerm(std::move(term), 100); } - auto createFilterSearch(bool strict, Constraint upper_or_lower) const { - return blueprint.createFilterSearch(strict, upper_or_lower); + auto createFilterSearch(bool strict, Constraint constraint) const { + return blueprint.createFilterSearch(strict, constraint); } }; @@ -243,11 +293,11 @@ struct ParallelWeakAndAdapter { ParallelWeakAndAdapter() : field("foo", 3, 7), blueprint(field, 100, 0.0, 1.0) {} void addChild(std::unique_ptr child) { auto child_field = blueprint.getNextChildField(field); - auto term = std::make_unique(child_field, std::move(child)); + auto term = std::make_unique(child_field, std::move(child)); blueprint.addTerm(std::move(term), 100); } - auto createFilterSearch(bool strict, Constraint upper_or_lower) const { - return blueprint.createFilterSearch(strict, upper_or_lower); + auto createFilterSearch(bool strict, Constraint constraint) const { + return blueprint.createFilterSearch(strict, constraint); } }; @@ -257,11 +307,11 @@ struct SameElementAdapter { SameElementAdapter() : blueprint("foo", false) {} void addChild(std::unique_ptr child) { auto child_field = blueprint.getNextChildField("foo", 3); - auto term = std::make_unique(child_field, std::move(child)); + auto term = std::make_unique(child_field, std::move(child)); blueprint.addTerm(std::move(term)); } - auto createFilterSearch(bool strict, Constraint upper_or_lower) const { - return blueprint.createFilterSearch(strict, upper_or_lower); + auto createFilterSearch(bool strict, Constraint constraint) const { + return blueprint.createFilterSearch(strict, constraint); } }; @@ -272,26 +322,21 @@ requires ChildCollector struct Make { T blueprint; template - Make(Args && ... args) : blueprint(std::forward(args)...) {} - Make &add(std::unique_ptr child) { - blueprint.addChild(std::move(child)); - return *this; - } - Make &add(const Children &children) { - return children.apply(*this); + Make(const Children &child_list, Args && ... args) : blueprint(std::forward(args)...) { + child_list.apply(blueprint); } - auto createFilterSearch(bool strict, Constraint upper_or_lower) const { - return blueprint.createFilterSearch(strict, upper_or_lower); + auto createFilterSearch(bool strict, Constraint constraint) const { + return blueprint.createFilterSearch(strict, constraint); } }; // what kind of results are we expecting from a filter search? struct Expect { - Trinary matches_any; + Trinary matches_any = Trinary::Undefined; SimpleResult docs; - Expect(const std::vector &docs_in) - : matches_any(Trinary::Undefined), docs(make_result(docs_in)) {} - Expect(Trinary matches_any_in) : matches_any(matches_any_in), docs() { + size_t children = 0; + Expect(const std::vector &docs_in) : docs(make_result(docs_in)) {} + Expect(Trinary matches_any_in) : matches_any(matches_any_in) { REQUIRE(matches_any != Trinary::Undefined); if (matches_any == Trinary::True) { docs = make_full_result(); @@ -299,25 +344,53 @@ struct Expect { docs = make_empty_result(); } } + Expect &child_count(size_t n) { children = n; return *this; } static Expect empty() { return Expect(Trinary::False); } static Expect full() { return Expect(Trinary::True); } static Expect hits(const std::vector &docs) { return Expect(docs); } }; +template +void verify(const Blueprint &blueprint, bool strict, Constraint constraint, const Expect &expect) { + CheckParamsProxy::current_strict = strict; + CheckParamsProxy::current_constraint = constraint; + auto filter = blueprint.createFilterSearch(strict, constraint); + if (expect.children > 0) { + ASSERT_EQ(filter->isMultiSearch(), true); + EXPECT_EQ(static_cast(filter.get())->getChildren().size(), expect.children); + } + EXPECT_EQ(filter->matches_any(), expect.matches_any); + switch (filter->matches_any()) { + case Trinary::True: + EXPECT_EQ(std::type_index(typeid(*filter)), std::type_index(typeid(FullSearch))); + break; + case Trinary::False: + EXPECT_EQ(std::type_index(typeid(*filter)), std::type_index(typeid(EmptySearch))); + default: + break; + } + SimpleResult actual; + if (strict) { + actual.searchStrict(*filter, docid_limit); + } else { + actual.search(*filter, docid_limit); + } + EXPECT_EQ(actual, expect.docs); +} + +template +void verify(const Blueprint &blueprint, bool strict, const Expect &expect) { + for (auto constraint: {lower_bound, upper_bound}) { + verify(blueprint, strict, constraint, expect); + } +} + template void verify(const Blueprint &blueprint, const Expect &upper, const Expect &lower) { for (auto constraint: {lower_bound, upper_bound}) { const Expect &expect = (constraint == upper_bound) ? upper : lower; for (bool strict: {false, true}) { - auto filter = blueprint.createFilterSearch(strict, constraint); - EXPECT_EQ(filter->matches_any(), expect.matches_any); - SimpleResult actual; - if (strict) { - actual.searchStrict(*filter, docid_limit); - } else { - actual.search(*filter, docid_limit); - } - EXPECT_EQ(actual, expect.docs); + verify(blueprint, strict, constraint, expect); } } } @@ -345,56 +418,190 @@ TEST(FilterSearchTest, default_blueprint) { TEST(FilterSearchTest, simple_or) { auto child_list = Children() - .hits({5, 10}) - .hits({7}) - .hits({3, 11}); + .hits({5, 10}).check(true, true) + .hits({7}).check(true, true) + .hits({3, 11}).check(true, true); auto expected = Expect::hits({3, 5, 7, 10, 11}); - verify(Combine(Blueprint::create_or_filter).add(child_list), expected); - verify(Make().add(child_list), expected); - verify(Make().add(child_list), expected); - verify(Make().add(child_list), expected); - verify(Make().add(child_list), expected); - verify(Combine(Blueprint::create_atmost_or_filter).add(child_list), expected, Expect::empty()); - verify(Make(100).add(child_list), expected, Expect::empty()); - verify(Make().add(child_list), expected, Expect::empty()); - verify(Make().add(child_list), expected, Expect::empty()); + verify(Combine(Blueprint::create_or_filter, child_list), expected); + verify(Make(child_list), expected); + verify(Make(child_list), expected); + verify(Make(child_list), expected); + verify(Make(child_list), expected); + verify(Combine(Blueprint::create_atmost_or_filter, child_list), expected, Expect::empty()); + verify(Make(child_list, 100), expected, Expect::empty()); + verify(Make(child_list), expected, Expect::empty()); + verify(Make(child_list), expected, Expect::empty()); } TEST(FilterSearchTest, simple_and) { auto child_list = Children() - .hits({1, 2, 3, 4, 5, 6}) - .hits({2, 4, 6, 7}) - .hits({1, 4, 6, 7, 10}); + .hits({1, 2, 3, 4, 5, 6}).check(true, true) + .hits({2, 4, 6, 7}).check(false, true) + .hits({1, 4, 6, 7, 10}).check(false, true); auto expected = Expect::hits({4, 6}); - verify(Combine(Blueprint::create_and_filter).add(child_list), expected); - verify(Make().add(child_list), expected); - verify(Combine(Blueprint::create_atmost_and_filter).add(child_list), expected, Expect::empty()); - verify(Make(3).add(child_list), expected, Expect::empty()); - verify(Make(3).add(child_list), expected, Expect::empty()); - verify(Make().add(child_list), expected, Expect::empty()); - verify(Make().add(child_list), expected, Expect::empty()); + verify(Combine(Blueprint::create_and_filter, child_list), expected); + verify(Make(child_list), expected); + verify(Combine(Blueprint::create_atmost_and_filter, child_list), expected, Expect::empty()); + verify(Make(child_list, 3), expected, Expect::empty()); + verify(Make(child_list, 3), expected, Expect::empty()); + verify(Make(child_list), expected, Expect::empty()); + verify(Make(child_list), expected, Expect::empty()); } TEST(FilterSearchTest, simple_andnot) { auto child_list = Children() - .hits({1, 2, 3, 4, 5, 6}) - .hits({2, 4, 6}) - .hits({4, 6, 7}); + .hits({1, 2, 3, 4, 5, 6}).check(true, true) + .hits({2, 4, 6}).check(false, false) + .hits({4, 6, 7}).check(false, false); auto expected = Expect::hits({1, 3, 5}); - verify(Combine(Blueprint::create_andnot_filter).add(child_list), expected); - verify(Make().add(child_list), expected); + verify(Combine(Blueprint::create_andnot_filter, child_list), expected); + verify(Make(child_list), expected); } TEST(FilterSearchTest, rank_filter) { auto child_list1 = Children().hits({1,2,3}).empty().full(); auto child_list2 = Children().empty().hits({1,2,3}).full(); auto child_list3 = Children().full().hits({1,2,3}).empty(); - verify(Combine(Blueprint::create_first_child_filter).add(child_list1), Expect::hits({1,2,3})); - verify(Combine(Blueprint::create_first_child_filter).add(child_list2), Expect::empty()); - verify(Combine(Blueprint::create_first_child_filter).add(child_list3), Expect::full()); - verify(Make().add(child_list1), Expect::hits({1,2,3})); - verify(Make().add(child_list2), Expect::empty()); - verify(Make().add(child_list3), Expect::full()); + verify(Combine(Blueprint::create_first_child_filter, child_list1), Expect::hits({1,2,3})); + verify(Combine(Blueprint::create_first_child_filter, child_list2), Expect::empty()); + verify(Combine(Blueprint::create_first_child_filter, child_list3), Expect::full()); + verify(Make(child_list1), Expect::hits({1,2,3})); + verify(Make(child_list2), Expect::empty()); + verify(Make(child_list3), Expect::full()); +} + +TEST(FilterSearchTest, or_short_circuit) { + auto child_list = Children() + .hits({5, 10}).check(true, true) + .full().check(true, true) + .hits({3, 11}).check(true, true).dropped(); + verify(Combine(Blueprint::create_or_filter, child_list), + Expect::full()); +} + +TEST(FilterSearchTest, or_pruning) { + auto child_list = Children() + .empty().check(true, true) + .empty().check(true, true) + .empty().check(true, true); + verify(Combine(Blueprint::create_or_filter, child_list), + Expect::empty()); +} + +TEST(FilterSearchTest, or_partial_pruning) { + auto child_list = Children() + .hits({5, 10}).check(true, true) + .empty().check(true, true) + .hits({3, 11}).check(true, true); + verify(Combine(Blueprint::create_or_filter, child_list), + Expect::hits({3, 5, 10, 11}).child_count(2)); +} + +TEST(FilterSearchTest, and_short_circuit) { + auto child_list = Children() + .hits({1, 2, 3}).check(true, true) + .empty().check(false, true) + .hits({2, 3, 4}).check(false, true).dropped(); + verify(Combine(Blueprint::create_and_filter, child_list), + Expect::empty()); +} + +TEST(FilterSearchTest, and_pruning) { + auto child_list = Children() + .full().check(true, true) + .full().check(false, true) + .full().check(false, true); + verify(Combine(Blueprint::create_and_filter, child_list), + Expect::full()); +} + +TEST(FilterSearchTest, and_partial_pruning) { + auto child_list = Children() + .hits({1, 2, 3}).check(true, true) + .full().check(false, true) + .hits({2, 3, 4}).check(false, true); + verify(Combine(Blueprint::create_and_filter, child_list), + Expect::hits({2, 3}).child_count(2)); +} + +TEST(FilterSearchTest, andnot_positive_short_circuit) { + auto child_list = Children() + .empty().check(true, true) + .hits({1, 2, 3}).check(false, false).dropped(); + verify(Combine(Blueprint::create_andnot_filter, child_list), + Expect::empty()); +} + +TEST(FilterSearchTest, andnot_negative_short_circuit) { + auto child_list = Children() + .hits({1, 2, 3}).check(true, true) + .hits({1}).check(false, false) + .full().check(false, false) + .hits({3}).check(false, false).dropped(); + verify(Combine(Blueprint::create_andnot_filter, child_list), + Expect::empty()); +} + +TEST(FilterSearchTest, andnot_negative_pruning) { + auto child_list = Children() + .full().check(true, true) + .empty().check(false, false) + .empty().check(false, false) + .empty().check(false, false); + verify(Combine(Blueprint::create_andnot_filter, child_list), + Expect::full()); +} + +TEST(FilterSearchTest, andnot_partial_negative_pruning) { + auto child_list = Children() + .hits({1, 2, 3}).check(true, true) + .hits({1}).check(false, false) + .empty().check(false, false) + .hits({3}).check(false, false); + verify(Combine(Blueprint::create_andnot_filter, child_list), + Expect::hits({2}).child_count(3)); +} + +TEST(FilterSearchTest, first_or_child_can_be_partially_pruned) { + auto child_list = Children() + .empty().check(true, true) + .hits({5, 10}).check(true, true) + .hits({3, 11}).check(true, true); + verify(Combine(Blueprint::create_or_filter, child_list), + Expect::hits({3, 5, 10, 11}).child_count(2)); +} + +TEST(FilterSearchTest, first_and_child_can_only_be_partially_pruned_when_nonstrict) { + auto child_list = Children() + .full().check(true, true) + .hits({1, 2, 3}).check(false, true) + .hits({2, 3, 4}).check(false, true); + verify(Combine(Blueprint::create_and_filter, child_list), true, + Expect::hits({2, 3}).child_count(3)); + verify(Combine(Blueprint::create_and_filter, child_list), false, + Expect::hits({2, 3}).child_count(2)); +} + +TEST(FilterSearchTest, first_negative_andnot_child_can_be_partially_pruned) { + auto child_list = Children() + .hits({1, 2, 3}).check(true, true) + .empty().check(false, false) + .hits({1}).check(false, false) + .hits({3}).check(false, false); + verify(Combine(Blueprint::create_andnot_filter, child_list), + Expect::hits({2}).child_count(3)); +} + +TEST(FilterSearchTest, need_atleast_one_child) { + verify(Combine(Blueprint::create_and_filter, Children().full()), Expect::full()); + verify(Combine(Blueprint::create_or_filter, Children().empty()), Expect::empty()); + verify(Combine(Blueprint::create_andnot_filter, Children().full()), Expect::full()); + EXPECT_THROW(verify(Combine(Blueprint::create_and_filter, Children()), Expect::empty()), + vespalib::RequireFailedException); + EXPECT_THROW(verify(Combine(Blueprint::create_or_filter, Children()), Expect::empty()), + vespalib::RequireFailedException); + EXPECT_THROW(verify(Combine(Blueprint::create_andnot_filter, Children()), Expect::empty()), + vespalib::RequireFailedException); } GTEST_MAIN_RUN_ALL_TESTS() -- cgit v1.2.3