create optimized filter search

test strict/constraint propagation
test filters dropped due to short-circuit

1 files changed, 308 insertions, 101 deletions

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 <vespa/searchlib/queryeval/simpleresult.h>
+#include <vespa/searchlib/queryeval/emptysearch.h>
+#include <vespa/searchlib/queryeval/full_search.h>
 #include <vespa/searchlib/queryeval/blueprint.h>
 #include <vespa/searchlib/queryeval/intermediate_blueprints.h>
 #include <vespa/searchlib/queryeval/leaf_blueprints.h>
@@ -16,6 +20,7 @@
 #include <vespa/vespalib/util/require.h>
 #include <vespa/vespalib/gtest/gtest.h>
 #include <functional>
+#include <typeindex>
 
 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 <typename T>
-concept FilterFactory = requires(const T &a, bool strict, Constraint upper_or_lower) {
-    { a.createFilterSearch(strict, upper_or_lower) } -> std::same_as<std::unique_ptr<SearchIterator>>;
-};
-
-template <typename T>
-concept FilterFactoryBuilder = requires(T a, std::unique_ptr<Blueprint> bp) {
-    { a.add(std::move(bp)) } -> std::same_as<T&>;
+concept FilterFactory = requires(const T &a, bool strict, Constraint constraint) {
+    { a.createFilterSearch(strict, constraint) } -> std::same_as<std::unique_ptr<SearchIterator>>;
 };
 
 template <typename T>
@@ -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<Blueprint> child;
-    FakeFieldProxy(const FieldSpec &field, std::unique_ptr<Blueprint> child_in)
-      : SimpleLeafBlueprint(field), child(std::move(child_in))
-    {
+    void init() {
         setParent(child->getParent());
         child->setParent(this);
     }
+    LeafProxy(std::unique_ptr<Blueprint> child_in)
+      : SimpleLeafBlueprint({}), child(std::move(child_in)) { init(); }
+    LeafProxy(const FieldSpec &field, std::unique_ptr<Blueprint> 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<Blueprint> 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<Blueprint> 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<Blueprint> hits(const std::vector<uint32_t> &docs) {
     return std::make_unique<SimpleBlueprint>(make_result(docs));
 }
 
+// check filter creation parameters
+std::unique_ptr<Blueprint> check(std::unique_ptr<Blueprint> child, bool expect_inherit_strict, bool expect_same_constraint) {
+    return std::make_unique<CheckParamsProxy>(std::move(child), expect_inherit_strict, expect_same_constraint);
+}
+
+// check that create filter is not called
+std::unique_ptr<Blueprint> dropped(std::unique_ptr<Blueprint> child) {
+    return std::make_unique<CheckDroppedProxy>(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 <FilterFactoryBuilder Builder>
-    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 <ChildCollector Builder>
+    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<std::unique_ptr<SearchIterator>(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<Blueprint> 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<Blueprint> 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<Blueprint> 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<Blueprint> child) {
         auto child_field = blueprint.getNextChildField(field);
-        auto term = std::make_unique<FakeFieldProxy>(child_field, std::move(child));
+        auto term = std::make_unique<LeafProxy>(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<Blueprint> 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<Blueprint> 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<Blueprint> child) {
         auto child_field = blueprint.getNextChildField(field);
-        auto term = std::make_unique<FakeFieldProxy>(child_field, std::move(child));
+        auto term = std::make_unique<LeafProxy>(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<Blueprint> child) {
         auto child_field = blueprint.getNextChildField(field);
-        auto term = std::make_unique<FakeFieldProxy>(child_field, std::move(child));
+        auto term = std::make_unique<LeafProxy>(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<Blueprint> child) {
         auto child_field = blueprint.getNextChildField("foo", 3);
-        auto term = std::make_unique<FakeFieldProxy>(child_field, std::move(child));
+        auto term = std::make_unique<LeafProxy>(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<T>
 struct Make {
     T blueprint;
     template <typename ... Args>
-    Make(Args && ... args) : blueprint(std::forward<Args>(args)...) {}
-    Make &add(std::unique_ptr<Blueprint> 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>(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<uint32_t> &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<uint32_t> &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<uint32_t> &docs) { return Expect(docs); }
 };
 
 template <FilterFactory Blueprint>
+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<MultiSearch*>(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 <FilterFactory Blueprint>
+void verify(const Blueprint &blueprint, bool strict, const Expect &expect) {
+    for (auto constraint: {lower_bound, upper_bound}) {
+        verify(blueprint, strict, constraint, expect);
+    }
+}
+
+template <FilterFactory Blueprint>
 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<OrBlueprint>().add(child_list), expected);
-    verify(Make<EquivAdapter>().add(child_list), expected);
-    verify(Make<WeightedSetTermAdapter>().add(child_list), expected);
-    verify(Make<DotProductAdapter>().add(child_list), expected);
-    verify(Combine(Blueprint::create_atmost_or_filter).add(child_list), expected, Expect::empty());
-    verify(Make<WeakAndBlueprint>(100).add(child_list), expected, Expect::empty());
-    verify(Make<SourceBlenderAdapter>().add(child_list), expected, Expect::empty());
-    verify(Make<ParallelWeakAndAdapter>().add(child_list), expected, Expect::empty());
+    verify(Combine(Blueprint::create_or_filter, child_list), expected);
+    verify(Make<OrBlueprint>(child_list), expected);
+    verify(Make<EquivAdapter>(child_list), expected);
+    verify(Make<WeightedSetTermAdapter>(child_list), expected);
+    verify(Make<DotProductAdapter>(child_list), expected);
+    verify(Combine(Blueprint::create_atmost_or_filter, child_list), expected, Expect::empty());
+    verify(Make<WeakAndBlueprint>(child_list, 100), expected, Expect::empty());
+    verify(Make<SourceBlenderAdapter>(child_list), expected, Expect::empty());
+    verify(Make<ParallelWeakAndAdapter>(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<AndBlueprint>().add(child_list), expected);
-    verify(Combine(Blueprint::create_atmost_and_filter).add(child_list), expected, Expect::empty());
-    verify(Make<NearBlueprint>(3).add(child_list), expected, Expect::empty());
-    verify(Make<ONearBlueprint>(3).add(child_list), expected, Expect::empty());
-    verify(Make<SimplePhraseAdapter>().add(child_list), expected, Expect::empty());
-    verify(Make<SameElementAdapter>().add(child_list), expected, Expect::empty());
+    verify(Combine(Blueprint::create_and_filter, child_list), expected);
+    verify(Make<AndBlueprint>(child_list), expected);
+    verify(Combine(Blueprint::create_atmost_and_filter, child_list), expected, Expect::empty());
+    verify(Make<NearBlueprint>(child_list, 3), expected, Expect::empty());
+    verify(Make<ONearBlueprint>(child_list, 3), expected, Expect::empty());
+    verify(Make<SimplePhraseAdapter>(child_list), expected, Expect::empty());
+    verify(Make<SameElementAdapter>(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<AndNotBlueprint>().add(child_list), expected);
+    verify(Combine(Blueprint::create_andnot_filter, child_list), expected);
+    verify(Make<AndNotBlueprint>(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<RankBlueprint>().add(child_list1), Expect::hits({1,2,3}));
-    verify(Make<RankBlueprint>().add(child_list2), Expect::empty());
-    verify(Make<RankBlueprint>().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<RankBlueprint>(child_list1), Expect::hits({1,2,3}));
+    verify(Make<RankBlueprint>(child_list2), Expect::empty());
+    verify(Make<RankBlueprint>(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()