Repository: blevesearch/bleve
Pull request #1426 (2020-06-30 14:32:17)

remove TooManyClauses limitation when optimizable
Observation: When a search does not perform scoring and does not
need location information, disjunction queries are optimized by
directly OR'ing the underlying bitset.  This avoids all the
usual multi-iterator disjunction logic.  However, in it's
traditional form, we still have a TooManyClauses limit, and
this makes sense as all the underlying iterators are still
in memory at one time.

Observation: The MultiTerm search is unique in that we have a
flat list of terms that are used to build the disjunction.
This is significant because it means we can ensure that
all the underlying searchers are optimizable.

By combining these two observations we can introduce a new mode
of operation for the MultiTerm search.  When it does not perform
scoring and does not need location information, we can do a new
optimization where we create smaller batches of disjunctions
which are immediately optimizable into a single term searcher.
By repeating this process across all terms, we end up with
the correct searcher, and we never had more than the batch
size iterators built in memory at one time.

UnadornedPostingsIteratorBitmap was refactored to also
implement OptimizablePostingsIterator, this allows us
to keep the in-progress final iterator in each batch,
simplifying the logic.

A new optimization mode "disjunction:unadorned-force" was
introduced.  It behaves exacdtly the same as
"disjunction:unadorned" only it always performs the
optimization without regard for the cardinality of the
underlying iterators.

mschoch: I dislike all the duplicated code, but working with `[]string` and `[][]byte` up and down the stack is a preexisting condition.
mschoch: Action item for @mschoch, review if UnadornedPostingsIterator1Hit should be enhanced to satisfy OptimizablePostingsIterator as well (probably).
mschoch: It tuns out it isn't possible for UnadornedPostingsIterator1Hit to implement OptimizablePostingsIterator, as it cannot represent more than 1 hit (as required by ReplaceActualBitmap).  This actually exposes a failure mode for this optimization and more work is required.
mschoch: OK, I have now concluded that it isn't an actual problem, but I'd like to include a description of the original concern, and why I've concluded it isn't an issue.

Concern:

Since `UnadornedPostingsIterator1Hit` doesn't implement `OptimizablePostingsIterator`, while the `optimizeCompositeSearcher` attempts to combine N searchers down into 1 searcher, it could fail because one of the underlying Postings iterators from a previous round of optimization was using `UnadornedPostingsIterator1Hit`, thus causing the attempted optimization to fail.

Why I no longer think this is a valid concern:

The type of optimization we're performing `"disjunction:unadorned-force"` never creates instances of `UnadornedPostingsIterator1Hit`, it always uses `UnadornedPostingsIteratorBitmap` here: https://github.com/blevesearch/bleve/blob/master/index/scorch/optimize.go#L392

Further, since the MultiTermSearcher creates all the child searchers directly from a list of terms, there is no possibility of the result of any other optimization being a part of this optimization.
mschoch: Please review my last comment @sreekanth-cb 
sreekanth-cb: @mschoch , yes these comments make sense. 
does it make sense to have a UT which may explore that single finalSearcher coming out of another set of finalSearchers built from previous levels..
mschoch: @sreekanth-cb based on your feedback:

1.  You asked that the test perform multiple rounds batches of optimization to verify that each time we reduce to a single searcher, and the logic is sound for multiple iterations.  It turns out the test was already doing 2 batches.  There are 4 term searchers, and the max clauses is adjusted 2, thus requiring 2 loop iterations.

2.  I added code to assert that the expected number of searchers is started (6, the 4 original term searchers, one optimized searcher from the first batch, and then the final search resulting from the second batch).

3.  I added code to assert that all started searchers were closed.

4.  Item 3 reveal failures due to 2 reasons, first the final searcher was not closed in the unit test (fixed).  Second, the optimize.go did not bump stats when creating new optimized term searchers (fixed).
mschoch: @sreekanth-cb ping for re-review as github isn't showing that option.
sreekanth-cb: 👍 


Patch:
diff --git a/index/scorch/optimize.go b/index/scorch/optimize.go
index b9cb9228..f23fdfb8 100644
--- a/index/scorch/optimize.go
+++ b/index/scorch/optimize.go
@@ -16,10 +16,10 @@ package scorch
 
 import (
 	"fmt"
-
 	"github.com/RoaringBitmap/roaring"
 	"github.com/blevesearch/bleve/index"
 	"github.com/blevesearch/bleve/index/scorch/segment"
+	"sync/atomic"
 )
 
 var OptimizeConjunction = true
@@ -37,7 +37,11 @@ func (s *IndexSnapshotTermFieldReader) Optimize(kind string,
 	}
 
 	if OptimizeDisjunctionUnadorned && kind == "disjunction:unadorned" {
-		return s.optimizeDisjunctionUnadorned(octx)
+		return s.optimizeDisjunctionUnadorned(octx, OptimizeDisjunctionUnadornedMinChildCardinality)
+	}
+
+	if OptimizeDisjunctionUnadorned && kind == "disjunction:unadorned-force" {
+		return s.optimizeDisjunctionUnadorned(octx, 0)
 	}
 
 	return octx, nil
@@ -265,6 +269,7 @@ OUTER:
 		oTFR.iterators[i] = segment.NewUnadornedPostingsIteratorFromBitmap(bm)
 	}
 
+	atomic.AddUint64(&o.snapshot.parent.stats.TotTermSearchersStarted, uint64(1))
 	return oTFR, nil
 }
 
@@ -275,9 +280,12 @@ OUTER:
 // term-vectors are not required, and instead only the internal-id's
 // are needed.
 func (s *IndexSnapshotTermFieldReader) optimizeDisjunctionUnadorned(
-	octx index.OptimizableContext) (index.OptimizableContext, error) {
+	octx index.OptimizableContext, minChildCardinality uint64) (index.OptimizableContext, error) {
 	if octx == nil {
-		octx = &OptimizeTFRDisjunctionUnadorned{snapshot: s.snapshot}
+		octx = &OptimizeTFRDisjunctionUnadorned{
+			snapshot: s.snapshot,
+			minChildCardinality: minChildCardinality,
+		}
 	}
 
 	o, ok := octx.(*OptimizeTFRDisjunctionUnadorned)
@@ -298,6 +306,8 @@ type OptimizeTFRDisjunctionUnadorned struct {
 	snapshot *IndexSnapshot
 
 	tfrs []*IndexSnapshotTermFieldReader
+
+	minChildCardinality uint64
 }
 
 var OptimizeTFRDisjunctionUnadornedTerm = []byte("<disjunction:unadorned>")
@@ -332,7 +342,7 @@ func (o *OptimizeTFRDisjunctionUnadorned) Finish() (rv index.Optimized, err erro
 		// Heuristic to skip the optimization if all the constituent
 		// bitmaps are too small, where the processing & resource
 		// overhead to create the OR'ed bitmap outweighs the benefit.
-		if cMax < OptimizeDisjunctionUnadornedMinChildCardinality {
+		if cMax < o.minChildCardinality {
 			return nil, nil
 		}
 	}
@@ -392,5 +402,6 @@ func (o *OptimizeTFRDisjunctionUnadorned) Finish() (rv index.Optimized, err erro
 		oTFR.iterators[i] = segment.NewUnadornedPostingsIteratorFromBitmap(bm)
 	}
 
+	atomic.AddUint64(&o.snapshot.parent.stats.TotTermSearchersStarted, uint64(1))
 	return oTFR, nil
 }
diff --git a/index/scorch/segment/unadorned.go b/index/scorch/segment/unadorned.go
index 9a4d6c76..56e75234 100644
--- a/index/scorch/segment/unadorned.go
+++ b/index/scorch/segment/unadorned.go
@@ -72,6 +72,19 @@ func (i *UnadornedPostingsIteratorBitmap) Size() int {
 	return reflectStaticSizeUnadornedPostingsIteratorBitmap
 }
 
+func (i *UnadornedPostingsIteratorBitmap)  ActualBitmap() *roaring.Bitmap {
+	return i.actualBM
+}
+
+func (i *UnadornedPostingsIteratorBitmap)  DocNum1Hit() (uint64, bool) {
+	return 0, false
+}
+
+func (i *UnadornedPostingsIteratorBitmap)  ReplaceActual(actual *roaring.Bitmap) {
+	i.actualBM = actual
+	i.actual = actual.Iterator()
+}
+
 func NewUnadornedPostingsIteratorFromBitmap(bm *roaring.Bitmap) PostingsIterator {
 	return &UnadornedPostingsIteratorBitmap{
 		actualBM: bm,
diff --git a/search/searcher/search_disjunction.go b/search/searcher/search_disjunction.go
index 4ad33b6f..f47da27c 100644
--- a/search/searcher/search_disjunction.go
+++ b/search/searcher/search_disjunction.go
@@ -16,7 +16,6 @@ package searcher
 
 import (
 	"fmt"
-
 	"github.com/blevesearch/bleve/index"
 	"github.com/blevesearch/bleve/search"
 )
@@ -37,6 +36,11 @@ func NewDisjunctionSearcher(indexReader index.IndexReader,
 	return newDisjunctionSearcher(indexReader, qsearchers, min, options, true)
 }
 
+func optionsDisjunctionOptimizable(options search.SearcherOptions) bool {
+	rv := options.Score == "none" && !options.IncludeTermVectors
+	return rv
+}
+
 func newDisjunctionSearcher(indexReader index.IndexReader,
 	qsearchers []search.Searcher, min float64, options search.SearcherOptions,
 	limit bool) (search.Searcher, error) {
@@ -44,7 +48,7 @@ func newDisjunctionSearcher(indexReader index.IndexReader,
 	// do not need extra information like freq-norm's or term vectors
 	// and the requested min is simple
 	if len(qsearchers) > 1 && min <= 1 &&
-		options.Score == "none" && !options.IncludeTermVectors {
+		optionsDisjunctionOptimizable(options) {
 		rv, err := optimizeCompositeSearcher("disjunction:unadorned",
 			indexReader, qsearchers, options)
 		if err != nil || rv != nil {
diff --git a/search/searcher/search_multi_term.go b/search/searcher/search_multi_term.go
index 1c60d4a7..85aacc17 100644
--- a/search/searcher/search_multi_term.go
+++ b/search/searcher/search_multi_term.go
@@ -15,6 +15,7 @@
 package searcher
 
 import (
+	"fmt"
 	"github.com/blevesearch/bleve/index"
 	"github.com/blevesearch/bleve/search"
 )
@@ -22,10 +23,113 @@ import (
 func NewMultiTermSearcher(indexReader index.IndexReader, terms []string,
 	field string, boost float64, options search.SearcherOptions, limit bool) (
 	search.Searcher, error) {
-	if limit && tooManyClauses(len(terms)) {
-		return nil, tooManyClausesErr(field, len(terms))
+
+	if tooManyClauses(len(terms)) {
+		if optionsDisjunctionOptimizable(options) {
+			return optimizeMultiTermSearcher(indexReader, terms, field, boost, options)
+		}
+		if limit {
+			return nil, tooManyClausesErr(field, len(terms))
+		}
+	}
+
+	qsearchers, err  := makeBatchSearchers(indexReader, terms, field, boost, options)
+	if err != nil {
+		return nil, err
 	}
 
+	// build disjunction searcher of these ranges
+	return newMultiTermSearcherInternal(indexReader, qsearchers, field, boost,
+		options, limit)
+}
+
+func NewMultiTermSearcherBytes(indexReader index.IndexReader, terms [][]byte,
+	field string, boost float64, options search.SearcherOptions, limit bool) (
+	search.Searcher, error) {
+
+	if tooManyClauses(len(terms)) {
+		if optionsDisjunctionOptimizable(options) {
+			return optimizeMultiTermSearcherBytes(indexReader, terms, field, boost, options)
+		}
+
+		if limit {
+			return nil, tooManyClausesErr(field, len(terms))
+		}
+	}
+
+	qsearchers, err  := makeBatchSearchersBytes(indexReader, terms, field, boost, options)
+	if err != nil {
+		return nil, err
+	}
+
+	// build disjunction searcher of these ranges
+	return newMultiTermSearcherInternal(indexReader, qsearchers, field, boost,
+		options, limit)
+}
+
+func newMultiTermSearcherInternal(indexReader index.IndexReader,
+	searchers []search.Searcher, field string, boost float64,
+	options search.SearcherOptions, limit bool) (
+	search.Searcher, error) {
+
+	// build disjunction searcher of these ranges
+	searcher, err := newDisjunctionSearcher(indexReader, searchers, 0, options,
+		limit)
+	if err != nil {
+		for _, s := range searchers {
+			_ = s.Close()
+		}
+		return nil, err
+	}
+
+	return searcher, nil
+}
+
+func optimizeMultiTermSearcher(indexReader index.IndexReader, terms []string,
+	field string, boost float64, options search.SearcherOptions) (
+	search.Searcher, error) {
+	var finalSearcher search.Searcher
+	for len(terms) > 0 {
+		var batchTerms []string
+		if len(terms) > DisjunctionMaxClauseCount {
+			batchTerms = terms[:DisjunctionMaxClauseCount]
+			terms = terms[DisjunctionMaxClauseCount:]
+		} else {
+			batchTerms = terms
+			terms = nil
+		}
+		batch, err := makeBatchSearchers(indexReader, batchTerms, field, boost, options)
+		if err != nil {
+			return nil, err
+		}
+		if finalSearcher != nil {
+			batch = append(batch, finalSearcher)
+		}
+		cleanup := func() {
+			for _, searcher := range batch {
+				if searcher != nil {
+					_ = searcher.Close()
+				}
+			}
+		}
+		finalSearcher, err =  optimizeCompositeSearcher("disjunction:unadorned-force",
+			indexReader, batch, options)
+		// all searchers in batch should be closed, regardless of error or optimization failure
+		// either we're returning, or continuing and only finalSearcher is needed for next loop
+		cleanup()
+		if err != nil {
+			return nil, err
+		}
+		if finalSearcher == nil {
+			return nil, fmt.Errorf("unable to optimize")
+		}
+	}
+	return finalSearcher, nil
+}
+
+func makeBatchSearchers(indexReader index.IndexReader, terms []string, field string,
+	boost float64, options search.SearcherOptions) ([]search.Searcher, error) {
+
 	qsearchers := make([]search.Searcher, len(terms))
 	qsearchersClose := func() {
 		for _, searcher := range qsearchers {
@@ -42,17 +146,54 @@ func NewMultiTermSearcher(indexReader index.IndexReader, terms []string,
 			return nil, err
 		}
 	}
-	// build disjunction searcher of these ranges
-	return newMultiTermSearcherBytes(indexReader, qsearchers, field, boost,
-		options, limit)
+	return qsearchers, nil
 }
 
-func NewMultiTermSearcherBytes(indexReader index.IndexReader, terms [][]byte,
-	field string, boost float64, options search.SearcherOptions, limit bool) (
+func optimizeMultiTermSearcherBytes(indexReader index.IndexReader, terms [][]byte,
+	field string, boost float64, options search.SearcherOptions) (
 	search.Searcher, error) {
-	if limit && tooManyClauses(len(terms)) {
-		return nil, tooManyClausesErr(field, len(terms))
+
+	var finalSearcher search.Searcher
+	for len(terms) > 0 {
+		var batchTerms [][]byte
+		if len(terms) > DisjunctionMaxClauseCount {
+			batchTerms = terms[:DisjunctionMaxClauseCount]
+			terms = terms[DisjunctionMaxClauseCount:]
+		} else {
+			batchTerms = terms
+			terms = nil
+		}
+		batch, err := makeBatchSearchersBytes(indexReader, batchTerms, field, boost, options)
+		if err != nil {
+			return nil, err
+		}
+		if finalSearcher != nil {
+			batch = append(batch, finalSearcher)
+		}
+		cleanup := func() {
+			for _, searcher := range batch {
+				if searcher != nil {
+					_ = searcher.Close()
+				}
+			}
+		}
+		finalSearcher, err =  optimizeCompositeSearcher("disjunction:unadorned-force",
+			indexReader, batch, options)
+		// all searchers in batch should be closed, regardless of error or optimization failure
+		// either we're returning, or continuing and only finalSearcher is needed for next loop
+		cleanup()
+		if err != nil {
+			return nil, err
+		}
+		if finalSearcher == nil {
+			return nil, fmt.Errorf("unable to optimize")
+		}
 	}
+	return finalSearcher, nil
+}
+
+func makeBatchSearchersBytes(indexReader index.IndexReader, terms [][]byte, field string,
+	boost float64, options search.SearcherOptions) ([]search.Searcher, error) {
 
 	qsearchers := make([]search.Searcher, len(terms))
 	qsearchersClose := func() {
@@ -70,24 +211,5 @@ func NewMultiTermSearcherBytes(indexReader index.IndexReader, terms [][]byte,
 			return nil, err
 		}
 	}
-	return newMultiTermSearcherBytes(indexReader, qsearchers, field, boost,
-		options, limit)
-}
-
-func newMultiTermSearcherBytes(indexReader index.IndexReader,
-	searchers []search.Searcher, field string, boost float64,
-	options search.SearcherOptions, limit bool) (
-	search.Searcher, error) {
-
-	// build disjunction searcher of these ranges
-	searcher, err := newDisjunctionSearcher(indexReader, searchers, 0, options,
-		limit)
-	if err != nil {
-		for _, s := range searchers {
-			_ = s.Close()
-		}
-		return nil, err
-	}
-
-	return searcher, nil
+	return qsearchers, nil
 }


Test patch:
diff --git a/search/searcher/search_term_range_test.go b/search/searcher/search_term_range_test.go
index cd4e8911..ec8935c3 100644
--- a/search/searcher/search_term_range_test.go
+++ b/search/searcher/search_term_range_test.go
@@ -15,7 +15,11 @@
 package searcher
 
 import (
+	"github.com/blevesearch/bleve/index/scorch"
+	"io/ioutil"
+	"os"
 	"reflect"
+	"sort"
 	"testing"
 
 	"github.com/blevesearch/bleve/search"
@@ -199,3 +203,82 @@ func TestTermRangeSearch(t *testing.T) {
 	}
 
 }
+
+func TestTermRangeSearchTooManyTerms(t *testing.T) {
+	dir, _ := ioutil.TempDir("", "scorchTwoDoc")
+	defer func() {
+		_ = os.RemoveAll(dir)
+	}()
+
+	scorchIndex := initTwoDocScorch(dir)
+
+	// use lower limit for this test
+	origLimit := DisjunctionMaxClauseCount
+	DisjunctionMaxClauseCount = 2
+	defer func() {
+		DisjunctionMaxClauseCount = origLimit
+	}()
+
+	scorchReader, err := scorchIndex.Reader()
+	if err != nil {
+		t.Error(err)
+	}
+	defer func() {
+		err := scorchReader.Close()
+		if err != nil {
+			t.Fatal(err)
+		}
+	}()
+
+	var want = []string{"1", "3", "4", "5"}
+	var truth = true
+	searcher, err := NewTermRangeSearcher(scorchReader, []byte("bobert"), []byte("ravi"),
+		&truth, &truth, "name", 1.0, search.SearcherOptions{Score: "none", IncludeTermVectors: false})
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	var got []string
+	ctx := &search.SearchContext{
+		DocumentMatchPool: search.NewDocumentMatchPool(
+			searcher.DocumentMatchPoolSize(), 0),
+	}
+	next, err := searcher.Next(ctx)
+	i := 0
+	for err == nil && next != nil {
+		extId, err := scorchReader.ExternalID(next.IndexInternalID)
+		if err != nil {
+			t.Fatal(err)
+		}
+		got = append(got, extId)
+		ctx.DocumentMatchPool.Put(next)
+		next, err = searcher.Next(ctx)
+		i++
+	}
+	if err != nil {
+		t.Fatalf("error iterating searcher: %v", err)
+	}
+	err = searcher.Close()
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	// check that the expected number of term searchers were started
+	// 6 = 4 original terms, 1 optimized after first round, then final searcher
+	// from the last round
+	statsMap := scorchIndex.(*scorch.Scorch).StatsMap()
+	if statsMap["term_searchers_started"].(uint64) != 6 {
+		t.Errorf("expected 6 term searchers started, got %d", statsMap["term_searchers_started"])
+	}
+	// check that all started searchers were closed
+	if statsMap["term_searchers_started"] != statsMap["term_searchers_finished"] {
+		t.Errorf("expected all term searchers closed, %d started %d closed",
+			statsMap["term_searchers_started"], statsMap["term_searchers_finished"])
+	}
+
+	sort.Strings(got)
+	if !reflect.DeepEqual(got, want) {
+		t.Errorf("expected: %#v, got %#v", want, got)
+	}
+
+}
\ No newline at end of file