impl/memory: Implement Queries

impl/memory/datastore_query.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"
         "encoding/base64"
         "errors"
         "fmt"
         "math"
         "strings"
 
         ds "github.com/luci/gae/service/datastore"
         "github.com/luci/gae/service/datastore/serialize"
+        "github.com/luci/luci-go/common/cmpbin"
 )
 
 // MaxQueryComponents was lifted from a hard-coded constant in dev_appserver.
 // No idea if it's a real limit or just a convenience in the current dev
 // appserver implementation.
 const MaxQueryComponents = 100
 
 var errQueryDone = errors.New("query is done")
 
 type queryOp int
@@ skipping 29 matching lines @@
                 op = queryOpMap[toks[1]]
                 if op == qInvalid {
                         err = fmt.Errorf("datastore: invalid operator %q in filter %q", toks[1], f)
                 } else {
                         prop = toks[0]
                 }
         }
         return
 }
 
-type queryCursor string
+// A queryCursor is:
+//   {#orders} ++ IndexColumn* ++ RawRowData
+//   IndexColumn will always contain __key__ as the last column, and so #orders

[dnj (Google), 2015/08/23 06:50:06]

Do we need to encode the key column, then, or can we implicitly add it to the
end when encoding/decoding the cursor and save a few bytes?

[iannucci, 2015/08/23 18:19:42]

Yeah, we do, because it may not have an ASCENDING order. We could customize it
to just store the ASCENDING/DESCENDING bit, but the irregularity of that would
be annoying I think.

+//     must always be >= 1
+type queryCursor []byte
+
+func newCursor(s string) (ds.Cursor, error) {
+        d, err := base64.URLEncoding.DecodeString(s)

[dnj (Google), 2015/08/23 06:50:06]

Ack - I suspect that the recent cursor change I committed will double-B64
encode/decode this. If I had to pick, though, I'd remove the second layer from
here instead of the interface.

[iannucci, 2015/08/23 18:19:42]

Nah, I think it's fine here. This is parsing a cursor from the outside world.
The 'decode' at the bottom is making sure it is a series of encoded IndexColumns

+        if err != nil {
+                return nil, fmt.Errorf("Failed to Base64-decode cursor: %s", err)
+        }
+        c := queryCursor(d)
+        if _, _, err := c.decode(); err != nil {
+                return nil, err
+        }
+        return c, nil
+}
 
 func (q queryCursor) String() string { return base64.URLEncoding.EncodeToString([]byte(q)) }
-func (q queryCursor) Valid() bool    { return q != "" }
+
+// decode returns the encoded IndexColumns, the raw row (cursor) data, or an
+// error.
+func (q queryCursor) decode() ([]ds.IndexColumn, []byte, error) {
+        buf := bytes.NewBuffer([]byte(q))
+        count, _, err := cmpbin.ReadUint(buf)
+        if err != nil {
+                return nil, nil, fmt.Errorf("invalid cursor")

[dnj (Google), 2015/08/23 06:50:06]

Since you're generating errors here, you should be more specific about which
condition was violated in the errors.

[iannucci, 2015/08/23 18:19:42]

Done.

+        }
+
+        if count > ds.MaxIndexColumns {

[dnj (Google), 2015/08/23 06:50:06]

if count <= 0 || count > ds.MaxIndexColumns {
  return nil, nil, fmt.Errorf("invalid cursor: bad column count (%d)", count)

[iannucci, 2015/08/23 18:19:42]

Done.

+                return nil, nil, fmt.Errorf("invalid cursor")
+        }
+
+        if count <= 0 {
+                return nil, nil, fmt.Errorf("invalid cursor")
+        }
+
+        cols := make([]ds.IndexColumn, count)
+        for i := range cols {
+                if cols[i], err = serialize.ReadIndexColumn(buf); err != nil {
+                        return nil, nil, fmt.Errorf("invalid cursor")

[dnj (Google), 2015/08/23 06:50:06]

Note which index failed and why in the returned error.

[iannucci, 2015/08/23 18:19:42]

Done.

+                }
+        }
+
+        if cols[len(cols)-1].Property != "__key__" {
+                return nil, nil, fmt.Errorf("invalid cursor")

[dnj (Google), 2015/08/23 06:50:06]

"column set must end with the key". If key is implicit, though, it's two fewer
possible failure conditions :)

[iannucci, 2015/08/23 18:19:42]

Acknowledged.

+        }
+
+        return cols, buf.Bytes(), nil
+}
 
 type queryIneqFilter struct {
         prop string
 
-        low  *string
-        high *string
-}
-
-func decodeCursor(s string) (ds.Cursor, error) {
-        d, err := base64.URLEncoding.DecodeString(s)
-        if err != nil {
-                return nil, fmt.Errorf("Failed to Base64-decode cursor: %s", err)
-        }
-        c := queryCursor(string(d))
-        if !c.Valid() {
-                return nil, errors.New("Decoded cursor is not valid.")
-        }
-        return c, nil
-}
-
-func increment(bstr string, positive bool) string {
-        lastIdx := len(bstr) - 1
-        last := bstr[lastIdx]
-        if positive {
-                if last == 0xFF {
-                        return bstr + "\x00"
-                }
-                return bstr[:lastIdx] + string([]byte{last + 1})
-        } else {
-                if last == 0 {
-                        return bstr[:lastIdx-1]
-                }
-                return bstr[:lastIdx] + string([]byte{last - 1})
-        }
+        start []byte
+        end   []byte
 }
 
 // constrain 'folds' a new inequality into the current inequality filter.
 //
-// It will bump the high bound down, or the low bound up, assuming the incoming
+// It will bump the end bound down, or the start bound up, assuming the incoming
 // constraint does so.
 //
-// It returns true iff the filter is overconstrained (i.e.  low > high)
-func (q *queryIneqFilter) constrain(op queryOp, val string) bool {
+// It returns true iff the filter is overconstrained (i.e.  start > end)
+func (q *queryIneqFilter) constrain(op queryOp, val []byte) bool {
         switch op {
+        case qLessEq:
+                val = increment(val)
+                fallthrough
         case qLessThan:
-                val = increment(val, true)
-                fallthrough
-        case qLessEq:
                 // adjust upper bound downwards
-                if q.high == nil || *q.high > val {
-                        q.high = &val
+                if q.end == nil || bytes.Compare(q.end, val) > 0 {
+                        q.end = val
                 }
 
         case qGreaterThan:
-                val = increment(val, false)
+                val = increment(val)
                 fallthrough
         case qGreaterEq:
                 // adjust lower bound upwards
-                if q.low == nil || *q.low < val {
-                        q.low = &val
+                if q.start == nil || bytes.Compare(q.start, val) < 0 {
+                        q.start = val
                 }
 
         default:
-                panic(fmt.Errorf("constrain cannot handle filter op %d", op))
+                impossible(fmt.Errorf("constrain cannot handle filter op %d", op))
         }
 
-        if q.low != nil && q.high != nil {
-                return *q.low > *q.high
+        if q.start != nil && q.end != nil {
+                return bytes.Compare(q.start, q.end) >= 0
         }
         return false
 }
 
 type queryImpl struct {
         ns string
 
-        kind     string
-        ancestor ds.Key
+        kind string
 
-        // prop -> encoded values
-        eqFilters  map[string]map[string]struct{}
-        ineqFilter queryIneqFilter
-        order      []ds.IndexColumn
-        project    map[string]struct{}
+        // prop -> encoded values (which are ds.Property objects)
+        // "__ancestor__" is the key for Ancestor queries.
+        eqFilters          map[string]map[string]struct{}
+        ineqFilter         queryIneqFilter
+        order              []ds.IndexColumn
+        startCursor        []byte
+        startCursorColumns []ds.IndexColumn
+        endCursor          []byte
+        endCursorColumns   []ds.IndexColumn
 
+        // All of these are applied in post (e.g. not during the native index scan).
         distinct            bool
         eventualConsistency bool
         keysOnly            bool
         limit               int32
         offset              int32
-
-        start queryCursor
-        end   queryCursor
+        project             []string
 
         err error
 }
 
 var _ ds.Query = (*queryImpl)(nil)
 
-func (q *queryImpl) valid(ns string, isTxn bool) (done bool, err error) {
-        if q.err == errQueryDone {
-                done = true
-        } else if q.err != nil {
-                err = q.err
-        } else if ns != q.ns {
-                err = errors.New(
+func sortOrdersEqual(as, bs []ds.IndexColumn) bool {
+        if len(as) != len(bs) {
+                return false
+        }
+        for i, a := range as {
+                if a != bs[i] {
+                        return false
+                }
+        }
+        return true
+}
+
+func (q *queryImpl) reduce(ns string, isTxn bool) (*reducedQuery, error) {
+        if q.err != nil {
+                return nil, q.err
+        }
+        if ns != q.ns {
+                return nil, errors.New(
                         "gae/memory: Namespace mismatched. Query and Datastore don't agree " +
                                 "on the current namespace")
-        } else if isTxn && q.ancestor == nil {
-                err = errors.New(
+        } else if isTxn && q.eqFilters["__ancestor__"] == nil {

[dnj (Google), 2015/08/23 06:50:06]

IMO the "else" chaining here is ugly and unnecessary now that you're returning
the error in the conditional logic.

[iannucci, 2015/08/23 18:19:42]

Done.

+                return nil, errors.New(
                         "gae/memory: Only ancestor queries are allowed inside transactions")
         } else if q.numComponents() > MaxQueryComponents {
-                err = fmt.Errorf(
+                return nil, fmt.Errorf(
                         "gae/memory: query is too large. may not have more than "+
                                 "%d filters + sort orders + ancestor total: had %d",
                         MaxQueryComponents, q.numComponents())
         } else if len(q.project) == 0 && q.distinct {
                 // This must be delayed, because q.Distinct().Project("foo") is a valid
                 // construction. If we checked this in Distinct, it could be too early, and
                 // checking it in Project doesn't matter.
-                err = errors.New(
+                return nil, errors.New(
                         "gae/memory: Distinct() only makes sense on projection queries.")
+        } else if q.eqFilters["__ancestor__"] != nil && q.ineqFilter.prop == "__key__" {
+                anc := []byte(nil)
+                for k := range q.eqFilters["__ancestor__"] {
+                        anc = []byte(k)
+                        break
+                }
+                anc = anc[:len(anc)-1]
+                if q.ineqFilter.start != nil && !bytes.HasPrefix(q.ineqFilter.start, anc) {
+                        return nil, errors.New(
+                                "gae/memory: __key__ inequality filter has a value outside of Ancestor()")
+                }
+                if q.ineqFilter.end != nil && !bytes.HasPrefix(q.ineqFilter.end, anc) {
+                        return nil, errors.New(
+                                "gae/memory: __key__ inequality filter has a value outside of Ancestor()")
+                }
         }
-        return
+
+        ret := &reducedQuery{
+                ns:           q.ns,
+                kind:         q.kind,
+                eqFilters:    q.eqFilters,
+                suffixFormat: q.order,
+
+                start: q.startCursor,
+                end:   q.endCursor,
+        }
+
+        // if len(q.suffixFormat) > 0, queryImpl already enforces that the first order
+        // is the same as the inequality. Otherwise we need to add it.
+        if len(ret.suffixFormat) == 0 && q.ineqFilter.prop != "" {
+                ret.suffixFormat = []ds.IndexColumn{{Property: q.ineqFilter.prop}}
+        }
+
+        // The inequality is specified in natural (ascending) order in the query's
+        // Filter syntax, but the order information may indicate to use a descending
+        // index column for it. If that's the case, then we must invert, swap and
+        // increment the inequality endpoints.
+        //
+        // Invert so that the desired numbers are represented correctly in the index.
+        // Swap so that our iterators still go from >= start to < end.
+        // Increment so that >= and < get correctly bounded (since the iterator is
+        //   still using natrual bytes ordering)
+        if q.ineqFilter.prop != "" && ret.suffixFormat[0].Direction == ds.DESCENDING {
+                hi, lo := increment(invert(q.ineqFilter.end)), increment(invert(q.ineqFilter.start))
+                q.ineqFilter.end, q.ineqFilter.start = lo, hi
+        }
+
+        // Add any projection columns not mentioned in the user-defined order as
+        // ASCENDING orders. Technically we could be smart and automatically use
+        // a DESCENDING ordered index, if it fit, but the logic gets insane, since all
+        // suffixes of all used indexes need to be PRECISELY equal (and so you'd have
+        // to hunt/invalidate/something to find the combination of indexes that are
+        // compatible with each other as well as the query). If you want to use
+        // a DESCENDING column, just add it to the user sort order, and this loop will
+        // not synthesize a new suffix entry for it.
+        //
+        // NOTE: if you want to use an index that sorts by -__key__, you MUST
+        // include all of the projected fields for that index in the order explicitly.
+        // Otherwise the generated suffixFormat will be wacky. So:
+        //   Query("Foo").Project("A", "B").Order("A").Order("-__key__")
+        //
+        // will turn into a suffixFormat of:
+        //   A, ASCENDING
+        //   __key__, DESCENDING
+        //   B, ASCENDING
+        //   __key__, ASCENDING
+        //
+        // To prevent this, your query should have another Order("B") clause before
+        // the -__key__ clause.
+        originalStop := len(ret.suffixFormat)
+        for _, p := range q.project {
+                needAdd := true
+                // originalStop prevents this loop from getting longer every time we add
+                // a projected property.
+                for _, col := range ret.suffixFormat[:originalStop] {
+                        if col.Property == p {
+                                needAdd = false
+                                break
+                        }
+                }
+                if needAdd {
+                        ret.suffixFormat = append(ret.suffixFormat, ds.IndexColumn{Property: p})
+                }
+        }
+
+        // If the suffix format ends with __key__ already (e.g. .Order("__key__")),
+        // then we're good to go. Otherwise we need to add it as the last bit of the
+        // suffix, since all indexes implicitly have it as the last column.
+        if len(ret.suffixFormat) == 0 || ret.suffixFormat[len(ret.suffixFormat)-1].Property != "__key__" {
+                ret.suffixFormat = append(ret.suffixFormat, ds.IndexColumn{Property: "__key__"})
+        }
+
+        // Now we check the start and end cursors.
+        //
+        // Cursors are composed of a list of IndexColumns at the beginning, followed
+        // by the raw bytes to use for the suffix. The cursor is only valid if all of
+        // its IndexColumns match our proposed suffixFormat, as calculated above.
+        if ret.start != nil {

[dnj (Google), 2015/08/23 06:50:06]

How about:
(a) Don't assign "ret.start" or "ret.end" above.
(b) Rewrite this as:

ret.start = q.ineqFilter.start
if q.startCursor != nil {
  if !sortOrders...{}
  if ret.start == nil || bytes.Compare(ret.start, q.startCursor)  < 0 {
    ret.start = q.startCursor
  }
}

(Same for end).

Reads cleaner as: default is whatever the inequality filter is using, but if
there's a cursor bound and it's greater than the inequality filter's start,
start there.

[iannucci, 2015/08/23 18:19:42]

Much better! Thanks...

+                if !sortOrdersEqual(q.startCursorColumns, ret.suffixFormat) {
+                        return nil, errors.New("gae/memory: start cursor is invalid for this query.")
+                }
+                if q.ineqFilter.start != nil && bytes.Compare(ret.start, q.ineqFilter.start) < 0 {
+                        ret.start = q.ineqFilter.start
+                }
+        } else {
+                ret.start = q.ineqFilter.start
+        }
+
+        if ret.end != nil {
+                if !sortOrdersEqual(q.endCursorColumns, ret.suffixFormat) {
+                        return nil, errors.New("gae/memory: end cursor is invalid for this query.")
+                }
+                if q.ineqFilter.end != nil && bytes.Compare(ret.end, q.ineqFilter.end) > 0 {
+                        ret.end = q.ineqFilter.end
+                }
+        } else {
+                ret.end = q.ineqFilter.end
+        }
+
+        // Finally, verify that we could even /potentially/ do work. If we have
+        // overlapping range ends, then we don't have anything to do.
+        if ret.end != nil && bytes.Compare(ret.start, ret.end) >= 0 {
+                return nil, errQueryDone
+        }
+
+        return ret, nil
 }
 
 func (q *queryImpl) numComponents() int {
         numComponents := len(q.order)
         if q.ineqFilter.prop != "" {
-                if q.ineqFilter.low != nil {
+                if q.ineqFilter.start != nil {
                         numComponents++
                 }
-                if q.ineqFilter.high != nil {
+                if q.ineqFilter.end != nil {
                         numComponents++
                 }
         }
         for _, v := range q.eqFilters {
                 numComponents += len(v)
         }
-        if q.ancestor != nil {
-                numComponents++
-        }
         return numComponents
 }
 
-func (q *queryImpl) calculateIndex() *ds.IndexDefinition {
-        // as a nod to simplicity in this code, we'll require that a single index
-        // is able to service the entire query. E.g. no zigzag merge joins or
-        // multiqueries. This will mean that the user will need to rely on
-        // dev_appserver to tell them what indicies they need for real, and for thier
-        // tests they'll need to specify the missing composite indices manually.
-        //
-        // This COULD lead to an exploding indicies problem, but we can fix that when
-        // we get to it.
-
-        //sortOrders := []qSortBy{}
-
-        return nil
-}
-
 // checkMutateClone sees if the query has an error. If not, it clones the query,
 // and assigns the output of `check` to the query error slot. If check returns
 // nil, it calls `mutate` on the cloned query. The (possibly new) query is then
 // returned.
 func (q *queryImpl) checkMutateClone(check func() error, mutate func(*queryImpl)) *queryImpl {
         if q.err != nil {
                 return q
         }
         nq := *q
         nq.eqFilters = make(map[string]map[string]struct{}, len(q.eqFilters))
         for prop, vals := range q.eqFilters {
                 nq.eqFilters[prop] = make(map[string]struct{}, len(vals))
                 for v := range vals {
                         nq.eqFilters[prop][v] = struct{}{}
                 }
         }
         nq.order = make([]ds.IndexColumn, len(q.order))
         copy(nq.order, q.order)
-        nq.project = make(map[string]struct{}, len(q.project))
-        for f := range q.project {
-                nq.project[f] = struct{}{}
-        }
+        nq.project = make([]string, len(q.project))
+        copy(nq.project, q.project)
         if check != nil {
                 nq.err = check()
         }
         if nq.err == nil {
                 mutate(&nq)
         }
         return &nq
 }
 
 func (q *queryImpl) Ancestor(k ds.Key) ds.Query {
         return q.checkMutateClone(
                 func() error {
                         if k == nil {
                                 // SDK has an explicit nil-check
                                 return errors.New("datastore: nil query ancestor")
                         }
+                        if k.Namespace() != q.ns {
+                                return fmt.Errorf("bad namespace: %q (expected %q)", k.Namespace(), q.ns)
+                        }
                         if !k.Valid(false, globalAppID, q.ns) {
                                 // technically the SDK implementation does a Weird Thing (tm) if both the
                                 // stringID and intID are set on a key; it only serializes the stringID in
                                 // the proto. This means that if you set the Ancestor to an invalid key,
                                 // you'll never actually hear about it. Instead of doing that insanity, we
                                 // just swap to an error here.
                                 return ds.ErrInvalidKey
                         }
-                        if k.Namespace() != q.ns {
-                                return fmt.Errorf("bad namespace: %q (expected %q)", k.Namespace(), q.ns)
-                        }
-                        if q.ancestor != nil {
+                        if q.eqFilters["__ancestor__"] != nil {
                                 return errors.New("cannot have more than one ancestor")
                         }
                         return nil
                 },
                 func(q *queryImpl) {
-                        q.ancestor = k
+                        q.addEqFilt("__ancestor__", ds.MkProperty(k))
                 })
 }
 
 func (q *queryImpl) Distinct() ds.Query {
         return q.checkMutateClone(nil, func(q *queryImpl) {
                 q.distinct = true
         })
 }
 
+func (q *queryImpl) addEqFilt(prop string, p ds.Property) []byte {
+        binVal := serialize.ToBytes(p)
+        if _, ok := q.eqFilters[prop]; !ok {

[dnj (Google), 2015/08/23 06:50:06]

Retain the equality filter map from the initial lookup:
if eqFilter, ok := q.eqFilters[prop]; !ok {
  // Initialize/assign
} else {
  // assign
}

[iannucci, 2015/08/23 18:19:42]

Done.

+                q.eqFilters[prop] = map[string]struct{}{string(binVal): {}}
+        } else {
+                q.eqFilters[prop][string(binVal)] = struct{}{}
+        }
+        return binVal
+}
+
 func (q *queryImpl) Filter(fStr string, val interface{}) ds.Query {
         prop := ""
         op := qInvalid
-        binVal := ""
+        p := ds.Property{}
         return q.checkMutateClone(
                 func() error {
                         var err error
                         prop, op, err = parseFilter(fStr)
                         if err != nil {
                                 return err
                         }
 
                         if q.kind == "" && prop != "__key__" {
                                 // https://cloud.google.com/appengine/docs/go/datastore/queries#Go_Kindless_queries
                                 return fmt.Errorf(
                                         "kindless queries can only filter on __key__, got %q", fStr)
                         }
 
-                        p := ds.Property{}
-                        err = p.SetValue(val, ds.NoIndex)
+                        err = p.SetValue(val, ds.ShouldIndex)

[dnj (Google), 2015/08/23 06:50:06]

if err := p.SetValue(...); err != nil {

Why did this switch from NoIndex to ShouldIndex?

[iannucci, 2015/08/23 18:19:42]

Because we use this value directly as one of the values in the index key. The
index keys are a series of concatenated `ShouldIndex` Property []byte's.

                         if err != nil {
                                 return err
                         }
 
                         if p.Type() == ds.PTKey {
                                 if !p.Value().(ds.Key).Valid(false, globalAppID, q.ns) {
                                         return ds.ErrInvalidKey
                                 }
                         }
 
                         if prop == "__key__" {
                                 if op == qEqual {
                                         return fmt.Errorf(
                                                 "query equality filter on __key__ is silly: %q", fStr)
                                 }
                                 if p.Type() != ds.PTKey {
                                         return fmt.Errorf("__key__ filter value is not a key: %T", val)
                                 }
+                        } else if strings.HasPrefix(prop, "__") && strings.HasSuffix(prop, "__") {
+                                return fmt.Errorf("filter on reserved property: %q", prop)
                         }
 
                         if op != qEqual {
                                 if q.ineqFilter.prop != "" && q.ineqFilter.prop != prop {
                                         return fmt.Errorf(
                                                 "inequality filters on multiple properties: %q and %q",
                                                 q.ineqFilter.prop, prop)
                                 }
                                 if len(q.order) > 0 && q.order[0].Property != prop {
                                         return fmt.Errorf(
                                                 "first sort order must match inequality filter: %q v %q",
                                                 q.order[0].Property, prop)
                                 }
-                        } else if _, ok := q.project[prop]; ok {
-                                return fmt.Errorf(
-                                        "cannot project on field which is used in an equality filter: %q",
-                                        prop)
+                        } else {
+                                for _, p := range q.project {
+                                        if p == prop {
+                                                return fmt.Errorf(
+                                                        "cannot project on field which is used in an equality filter: %q",
+                                                        prop)
+                                        }
+                                }
                         }
-                        binVal = string(serialize.ToBytes(p))
                         return err
                 },
                 func(q *queryImpl) {
                         if op == qEqual {
                                 // add it to eq filters
-                                if _, ok := q.eqFilters[prop]; !ok {
-                                        q.eqFilters[prop] = map[string]struct{}{binVal: {}}
-                                } else {
-                                        q.eqFilters[prop][binVal] = struct{}{}
-                                }
+                                q.addEqFilt(prop, p)
 
                                 // remove it from sort orders.
                                 // https://cloud.google.com/appengine/docs/go/datastore/queries#sort_orders_are_ignored_on_properties_with_equality_filters
                                 toRm := -1
                                 for i, o := range q.order {
                                         if o.Property == prop {
                                                 toRm = i
                                                 break
                                         }
                                 }
                                 if toRm >= 0 {
                                         q.order = append(q.order[:toRm], q.order[toRm+1:]...)
                                 }
                         } else {
                                 q.ineqFilter.prop = prop
-                                if q.ineqFilter.constrain(op, binVal) {
+                                if q.ineqFilter.constrain(op, serialize.ToBytes(p)) {
                                         q.err = errQueryDone
                                 }
                         }
                 })
 }
 
 func (q *queryImpl) Order(prop string) ds.Query {
         col := ds.IndexColumn{}
         return q.checkMutateClone(
                 func() error {
@@ skipping 39 matching lines @@
                         }
                 })
 }
 
 func (q *queryImpl) Project(fieldName ...string) ds.Query {
         return q.checkMutateClone(
                 func() error {
                         if q.keysOnly {
                                 return errors.New("cannot project a keysOnly query")
                         }
+                        dupCheck := map[string]struct{}{}
                         for _, f := range fieldName {
+                                if _, ok := dupCheck[f]; ok {
+                                        return fmt.Errorf("cannot project on the same field twice: %q", f)
+                                }
+                                dupCheck[f] = struct{}{}
                                 if f == "" {
                                         return errors.New("cannot project on an empty field name")
                                 }
-                                if strings.HasPrefix(f, "__") && strings.HasSuffix(f, "__") {
-                                        return fmt.Errorf("cannot project on %q", f)
+                                if f == "__key__" {
+                                        return fmt.Errorf("cannot project on __key__")
                                 }
                                 if _, ok := q.eqFilters[f]; ok {
                                         return fmt.Errorf(
                                                 "cannot project on field which is used in an equality filter: %q", f)
                                 }
+                                for _, p := range q.project {
+                                        if p == f {
+                                                return fmt.Errorf("cannot project on the same field twice: %q", f)
+                                        }
+                                }
                         }
                         return nil
                 },
                 func(q *queryImpl) {
-                        for _, f := range fieldName {
-                                q.project[f] = struct{}{}
-                        }
+                        q.project = append(q.project, fieldName...)
                 })
 }
 
 func (q *queryImpl) KeysOnly() ds.Query {
         return q.checkMutateClone(
                 func() error {
                         if len(q.project) != 0 {
                                 return errors.New("cannot project a keysOnly query")
                         }
                         return nil
                 },
                 func(q *queryImpl) {
                         q.keysOnly = true
                 })
 }
 
 func (q *queryImpl) Limit(limit int) ds.Query {
         return q.checkMutateClone(
                 func() error {
+                        // nonsensically... ANY negative value means 'unlimited'. *shakes head*
                         if limit < math.MinInt32 || limit > math.MaxInt32 {
                                 return errors.New("datastore: query limit overflow")
                         }
                         return nil
                 },
                 func(q *queryImpl) {
                         q.limit = int32(limit)
                 })
 }
 
 func (q *queryImpl) Offset(offset int) ds.Query {
         return q.checkMutateClone(
                 func() error {
                         if offset < 0 {
                                 return errors.New("datastore: negative query offset")
                         }
                         if offset > math.MaxInt32 {
                                 return errors.New("datastore: query offset overflow")
                         }
                         return nil
                 },
                 func(q *queryImpl) {
                         q.offset = int32(offset)
                 })
 }
 
+func queryCursorCheck(ns, flavor string, current []byte, newCursor ds.Cursor) ([]ds.IndexColumn, []byte, error) {
+        if current != nil {
+                return nil, nil, fmt.Errorf("%s cursor is multiply defined", flavor)
+        }
+        curs, ok := newCursor.(queryCursor)
+        if !ok {
+                return nil, nil, fmt.Errorf("%s cursor is unknown type: %T", flavor, curs)
+        }
+        return curs.decode()
+}
+
 func (q *queryImpl) Start(c ds.Cursor) ds.Query {
-        curs := queryCursor("")
+        cols := []ds.IndexColumn(nil)
+        curs := []byte(nil)
         return q.checkMutateClone(
-                func() error {
-                        ok := false
-                        if curs, ok = c.(queryCursor); !ok {
-                                return fmt.Errorf("start cursor is unknown type: %T", c)
-                        }
-                        if !curs.Valid() {
-                                return errors.New("datastore: invalid cursor")
-                        }
-                        return nil
+                func() (err error) {
+                        cols, curs, err = queryCursorCheck(q.ns, "start", q.startCursor, c)
+                        return
                 },
                 func(q *queryImpl) {
-                        q.start = curs
+                        q.startCursorColumns = cols
+                        q.startCursor = curs
                 })
 }
 
 func (q *queryImpl) End(c ds.Cursor) ds.Query {
-        curs := queryCursor("")
+        cols := []ds.IndexColumn(nil)
+        curs := queryCursor(nil)
         return q.checkMutateClone(
-                func() error {
-                        ok := false
-                        if curs, ok = c.(queryCursor); !ok {
-                                return fmt.Errorf("end cursor is unknown type: %T", c)
-                        }
-                        if !curs.Valid() {
-                                return errors.New("datastore: invalid cursor")
-                        }
-                        return nil
+                func() (err error) {
+                        cols, curs, err = queryCursorCheck(q.ns, "end", q.endCursor, c)
+                        return
                 },
                 func(q *queryImpl) {
-                        q.end = curs
+                        q.endCursorColumns = cols
+                        q.endCursor = curs
                 })
 }
 
 func (q *queryImpl) EventualConsistency() ds.Query {
         return q.checkMutateClone(
                 nil, func(q *queryImpl) {
                         q.eventualConsistency = true
                 })
 }