Refactor keys and queries in datastore service and implementation.

impl/memory/datastore_index_selection.go

 // Copyright 2015 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 package memory
 
 import (
         "bytes"
         "fmt"
         "sort"
@@ skipping 30 matching lines @@
         // limits of the inequality and/or full sort order. This is ONLY a suffix,
         // and it will be appended to the prefix during iteration.
         start []byte
         end   []byte
 
         // metadata describing the total number of columns that this query requires to
         // execute perfectly.
         numCols int
 }
 
-type IndexDefinitionSortable struct {
+type indexDefinitionSortable struct {
         // eqFilts is the list of ACTUAL prefix columns. Note that it may contain
         // redundant columns! (e.g. (tag, tag) is a perfectly valid prefix, becuase
         // (tag=1, tag=2) is a perfectly valid query).
         eqFilts []ds.IndexColumn
         coll    *memCollection
 }
 
-func (i *IndexDefinitionSortable) hasAncestor() bool {
+func (i *indexDefinitionSortable) hasAncestor() bool {
         return len(i.eqFilts) > 0 && i.eqFilts[0].Property == "__ancestor__"
 }
 
-func (i *IndexDefinitionSortable) numEqHits(c *constraints) int {
+func (i *indexDefinitionSortable) numEqHits(c *constraints) int {
         ret := 0
         for _, filt := range i.eqFilts {
                 if _, ok := c.constraints[filt.Property]; ok {
                         ret++
                 }
         }
         return ret
 }
 
-type IndexDefinitionSortableSlice []IndexDefinitionSortable
+type indexDefinitionSortableSlice []indexDefinitionSortable
 
-func (s IndexDefinitionSortableSlice) Len() int      { return len(s) }
-func (s IndexDefinitionSortableSlice) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
-func (s IndexDefinitionSortableSlice) Less(i, j int) bool {
-        a, b := s[i], s[j]
+func (idxs indexDefinitionSortableSlice) Len() int      { return len(idxs) }
+func (idxs indexDefinitionSortableSlice) Swap(i, j int) { idxs[i], idxs[j] = idxs[j], idxs[i] }
+func (idxs indexDefinitionSortableSlice) Less(i, j int) bool {
+        a, b := idxs[i], idxs[j]
         if a.coll == nil && b.coll != nil {
                 return true
         } else if a.coll != nil && b.coll == nil {
                 return false
         }
 
         cmp := len(a.eqFilts) - len(b.eqFilts)
         if cmp < 0 {
                 return true
         } else if cmp > 0 {
                 return false
         }
         for k, col := range a.eqFilts {
                 ocol := b.eqFilts[k]
-                if col.Direction == ds.ASCENDING && ocol.Direction == ds.DESCENDING {
+                if !col.Descending && ocol.Descending {
                         return true
-                } else if col.Direction == ds.DESCENDING && ocol.Direction == ds.ASCENDING {
+                } else if col.Descending && !ocol.Descending {
                         return false
                 }
                 if col.Property < ocol.Property {
                         return true
                 } else if col.Property > ocol.Property {
                         return false
                 }
         }
         return false
 }
 
-// maybeAddDefinition possibly adds a new IndexDefinitionSortable to this slice.
+// maybeAddDefinition possibly adds a new indexDefinitionSortable to this slice.
 // It's only added if it could be useful in servicing q, otherwise this function
 // is a noop.
 //
 // This returns true iff the proposed index is OK and depletes missingTerms to
 // empty.
 //
 // If the proposed index is PERFECT (e.g. contains enough columns to cover all
 // equality filters, and also has the correct suffix), idxs will be replaced
 // with JUST that index, and this will return true.
-func (idxs *IndexDefinitionSortableSlice) maybeAddDefinition(q *reducedQuery, s *memStore, missingTerms stringset.Set, id *ds.IndexDefinition) bool {
+func (idxs *indexDefinitionSortableSlice) maybeAddDefinition(q *reducedQuery, s *memStore, missingTerms stringset.Set, id *ds.IndexDefinition) bool {
         // Kindless queries are handled elsewhere.
         if id.Kind != q.kind {
                 impossible(
                         fmt.Errorf("maybeAddDefinition given index with wrong kind %q v %q", id.Kind, q.kind))
         }
 
         // If we're an ancestor query, and the index is compound, but doesn't include
         // an Ancestor field, it doesn't work. Builtin indexes can be used for
         // ancestor queries (and have !Ancestor), assuming that it's only equality
         // filters (plus inequality on __key__), or a single inequality.
@@ skipping 48 matching lines @@
         // index's potential just because the collection doesn't exist. If it's
         // a builtin and it doesn't exist, it still needs to be one of the 'possible'
         // indexes... it just means that the user's query will end up with no results.
         coll := s.GetCollection(
                 fmt.Sprintf("idx:%s:%s", q.ns, serialize.ToBytes(*id.PrepForIdxTable())))
 
         // First, see if it's a perfect match. If it is, then our search is over.
         //
         // A perfect match contains ALL the equality filter columns (or more, since
         // we can use residuals to fill in the extras).
-        toAdd := IndexDefinitionSortable{coll: coll}
+        toAdd := indexDefinitionSortable{coll: coll}
         toAdd.eqFilts = eqFilts
         for _, sb := range toAdd.eqFilts {
                 missingTerms.Del(sb.Property)
         }
 
         perfect := false
         if len(sortBy) == q.numCols {
                 perfect = true
                 for k, num := range numByProp {
                         if num < q.eqFilters[k].Len() {
                                 perfect = false
                                 break
                         }
                 }
         }
         if perfect {
-                *idxs = IndexDefinitionSortableSlice{toAdd}
+                *idxs = indexDefinitionSortableSlice{toAdd}
         } else {
                 *idxs = append(*idxs, toAdd)
         }
         return missingTerms.Len() == 0
 }
 
 // getRelevantIndexes retrieves the relevant indexes which could be used to
 // service q. It returns nil if it's not possible to service q with the current
 // indexes.
-func getRelevantIndexes(q *reducedQuery, s *memStore) (IndexDefinitionSortableSlice, error) {
+func getRelevantIndexes(q *reducedQuery, s *memStore) (indexDefinitionSortableSlice, error) {
         missingTerms := stringset.New(len(q.eqFilters))
         for k := range q.eqFilters {
                 if k == "__ancestor__" {
                         // ancestor is not a prefix which can be satisfied by a single index. It
                         // must be satisfied by ALL indexes (and has special logic for this in
                         // the addDefinition logic)
                         continue
                 }
                 missingTerms.Add(k)
         }
-        idxs := IndexDefinitionSortableSlice{}
+        idxs := indexDefinitionSortableSlice{}
 
         // First we add builtins
         // add
         //   idx:KIND
         if idxs.maybeAddDefinition(q, s, missingTerms, &ds.IndexDefinition{
                 Kind: q.kind,
         }) {
                 return idxs, nil
         }
 
@@ skipping 15 matching lines @@
                         Kind: q.kind,
                         SortBy: []ds.IndexColumn{
                                 {Property: prop},
                         },
                 }) {
                         return idxs, nil
                 }
                 if idxs.maybeAddDefinition(q, s, missingTerms, &ds.IndexDefinition{
                         Kind: q.kind,
                         SortBy: []ds.IndexColumn{
-                                {Property: prop, Direction: ds.DESCENDING},
+                                {Property: prop, Descending: true},
                         },
                 }) {
                         return idxs, nil
                 }
         }
 
         // Try adding all compound indexes whose suffix matches.
         suffix := &ds.IndexDefinition{
                 Kind:     q.kind,
                 Ancestor: q.eqFilters["__ancestor__"] != nil,
@@ skipping 13 matching lines @@
                 }
                 terms := missingTerms.ToSlice()
                 if serializationDeterministic {
                         sort.Strings(terms)
                 }
                 for _, term := range terms {
                         remains.SortBy = append(remains.SortBy, ds.IndexColumn{Property: term})
                 }
                 remains.SortBy = append(remains.SortBy, q.suffixFormat...)
                 last := remains.SortBy[len(remains.SortBy)-1]
-                if last.Direction == ds.ASCENDING {
+                if !last.Descending {
                         // this removes the __key__ column, since it's implicit.
                         remains.SortBy = remains.SortBy[:len(remains.SortBy)-1]
                 }
                 if remains.Builtin() {
                         impossible(
                                 fmt.Errorf("recommended missing index would be a builtin: %s", remains))
                 }
                 return nil, fmt.Errorf(
                         "Your indexes are insufficient! Try adding:\n  %s", remains)
         }
 
         return idxs, nil
 }
 
 // generate generates a single iterDefinition for the given index.
-func generate(q *reducedQuery, idx *IndexDefinitionSortable, c *constraints) *iterDefinition {
+func generate(q *reducedQuery, idx *indexDefinitionSortable, c *constraints) *iterDefinition {
         def := &iterDefinition{
                 c:     idx.coll,
                 start: q.start,
                 end:   q.end,
         }
         toJoin := make([][]byte, len(idx.eqFilts))
         for _, sb := range idx.eqFilts {
                 val := c.peel(sb.Property)
-                if sb.Direction == ds.DESCENDING {
+                if sb.Descending {
                         val = invert(val)
                 }
                 toJoin = append(toJoin, val)
         }
         def.prefix = bjoin(toJoin...)
         def.prefixLen = len(def.prefix)
 
         if q.eqFilters["__ancestor__"] != nil && !idx.hasAncestor() {
                 // The query requires an ancestor, but the index doesn't explicitly have it
                 // as part of the prefix (otherwise it would have been the first eqFilt
@@ skipping 16 matching lines @@
 
                 // Intentionally do NOT update prefixLen. This allows multiIterator to
                 // correctly include the entire key in the shared iterator suffix, instead
                 // of just the remainder.
 
                 // chop the terminal null byte off the q.ancestor key... we can accept
                 // anything which is a descendant or an exact match.  Removing the last byte
                 // from the key (the terminating null) allows this trick to work. Otherwise
                 // it would be a closed range of EXACTLY this key.
                 chopped := []byte(anc[:len(anc)-1])
-                if q.suffixFormat[0].Direction == ds.DESCENDING {
+                if q.suffixFormat[0].Descending {
                         chopped = invert(chopped)
                 }
                 def.prefix = bjoin(def.prefix, chopped)
 
                 // Update start and end, since we know that if they contain anything, they
                 // contain values for the __key__ field.
                 if def.start != nil {
                         offset := 0
                         if len(q.suffixFormat) > 1 {
                                 chunks, _ := parseSuffix(q.ns, q.suffixFormat, def.start, 1)
@@ skipping 84 matching lines @@
                         continue
                 }
                 ret.constraints[prop] = bvals
         }
         return ret
 }
 
 // getIndexes returns a set of iterator definitions. Iterating over these
 // will result in matching suffixes.
 func getIndexes(q *reducedQuery, s *memStore) ([]*iterDefinition, error) {
-        relevantIdxs := IndexDefinitionSortableSlice(nil)
+        relevantIdxs := indexDefinitionSortableSlice(nil)
         if q.kind == "" {
                 if coll := s.GetCollection("ents:" + q.ns); coll != nil {
-                        relevantIdxs = IndexDefinitionSortableSlice{{coll: coll}}
+                        relevantIdxs = indexDefinitionSortableSlice{{coll: coll}}
                 }
         } else {
                 err := error(nil)
                 relevantIdxs, err = getRelevantIndexes(q, s)
                 if err != nil {
                         return nil, err
                 }
         }
         if len(relevantIdxs) == 0 {
-                return nil, errQueryDone
+                return nil, ds.ErrNullQuery
         }
 
         // This sorts it so that relevantIdxs goes less filters -> more filters. We
         // traverse this list backwards, however, so we traverse it in more filters ->
         // less filters order.
         sort.Sort(relevantIdxs)
 
         constraints := calculateConstraints(q)
 
         ret := []*iterDefinition{}
         for !constraints.empty() || len(ret) == 0 {
-                bestIdx := (*IndexDefinitionSortable)(nil)
+                bestIdx := (*indexDefinitionSortable)(nil)
                 if len(ret) == 0 {
                         // if ret is empty, take the biggest relevantIdx. It's guaranteed to have
                         // the greatest number of equality filters of any index in the list, and
                         // we know that every equality filter will be pulled from constraints and
                         // not residual.
                         //
                         // This also takes care of the case when the query has no equality filters,
                         // in which case relevantIdxs will actually only contain one index anyway
                         // :)
                         bestIdx = &relevantIdxs[len(relevantIdxs)-1]
                         if bestIdx.coll == nil {
-                                return nil, errQueryDone
+                                return nil, ds.ErrNullQuery
                         }
                 } else {
                         // If ret's not empty, then we need to find the best index we can. The
                         // best index will be the one with the most matching equality columns.
                         // Since relevantIdxs is sorted primarially by the number of equality
                         // columns, we walk down the list until the number of possible columns is
                         // worse than our best-so-far.
                         //
                         // Traversing the list backwards goes from more filters -> less filters,
                         // but also allows us to remove items from the list as we iterate over it.
@@ skipping 22 matching lines @@
                 if bestIdx == nil {
                         // something is really wrong here... if relevantIdxs is !nil, then we
                         // should always be able to make progress in this loop.
                         impossible(fmt.Errorf("deadlock: cannot fulfil query?"))
                 }
                 ret = append(ret, generate(q, bestIdx, constraints))
         }
 
         return ret, nil
 }