docMatchTree: compute document ids lazily
Instead of precomputing all document ids for a docMatchTree, we compute
them lazily based on a predicate.
Change-Id: I3acf414f6bb18fc1d71f2cde2bdc784c3dd984b3
diff --git a/matchtree.go b/matchtree.go
index 4c04779..66d9372 100644
--- a/matchtree.go
+++ b/matchtree.go
@@ -82,10 +82,20 @@
matches(cp *contentProvider, cost int, known map[matchTree]bool) (match bool, sure bool)
}
+// docMatchTree iterates over documents for which predicate(docID) returns true.
type docMatchTree struct {
+ // the number of documents in a shard.
+ numDocs uint32
+
+ predicate func(docID uint32) bool
+
+ // provides additional information about the reason why the docMatchTree was
+ // created.
+ reason string
+
// mutable
- docs []uint32
- current []uint32
+ firstDone bool
+ docID uint32
}
type bruteForceMatchTree struct {
@@ -157,15 +167,8 @@
}
func (t *docMatchTree) prepare(doc uint32) {
- for len(t.docs) > 0 && t.docs[0] < doc {
- t.docs = t.docs[1:]
- }
- i := 0
- for ; i < len(t.docs) && t.docs[i] == doc; i++ {
- }
-
- t.current = t.docs[:i]
- t.docs = t.docs[i:]
+ t.docID = doc
+ t.firstDone = true
}
func (t *andMatchTree) prepare(doc uint32) {
@@ -204,10 +207,16 @@
// nextDoc
func (t *docMatchTree) nextDoc() uint32 {
- if len(t.docs) == 0 {
- return maxUInt32
+ var start uint32
+ if t.firstDone {
+ start = t.docID + 1
}
- return t.docs[0]
+ for i := start; i < t.numDocs; i++ {
+ if t.predicate(i) {
+ return i
+ }
+ }
+ return maxUInt32
}
func (t *bruteForceMatchTree) nextDoc() uint32 {
@@ -264,7 +273,7 @@
}
func (t *docMatchTree) String() string {
- return fmt.Sprintf("docs%v", t.docs)
+ return fmt.Sprintf("doc(%s)", t.reason)
}
func (t *andMatchTree) String() string {
@@ -348,7 +357,7 @@
// all matches() methods.
func (t *docMatchTree) matches(cp *contentProvider, cost int, known map[matchTree]bool) (bool, bool) {
- return len(t.current) > 0, true
+ return t.predicate(cp.idx), true
}
func (t *bruteForceMatchTree) matches(cp *contentProvider, cost int, known map[matchTree]bool) (bool, bool) {
@@ -677,14 +686,12 @@
if !ok {
return &noMatchTree{"lang"}, nil
}
- docs := make([]uint32, 0, len(d.languages))
- for d, l := range d.languages {
- if l == code {
- docs = append(docs, uint32(d))
- }
- }
return &docMatchTree{
- docs: docs,
+ reason: "language",
+ numDocs: uint32(len(d.languages)),
+ predicate: func(docID uint32) bool {
+ return d.languages[docID] == code
+ },
}, nil
case *query.Symbol:
