Use the sort.Search api correctly.

service/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 datastore
 
 import (
         "bytes"
         "fmt"
         "sort"
@@ skipping 252 matching lines @@
                         if q.eqFilts == nil {
                                 q.eqFilts = make(map[string]PropertySlice, 1)
                         }
                         s := q.eqFilts[field]
                         for _, value := range values {
                                 p := Property{}
                                 if q.err = p.SetValue(value, ShouldIndex); q.err != nil {
                                         return
                                 }
                                 idx := sort.Search(len(s), func(i int) bool {
-                                        return s[i].Equal(&p)
+                                        // s[i] >= p is the same as:
+                                        return s[i].Equal(&p) || p.Less(&s[i])
                                 })
-                                if idx == len(s) {
-                                        s = append(s, p)
-                                        sort.Sort(s)
+                                if idx == len(s) || !s[idx].Equal(&p) {
+                                        s = append(s, Property{})
+                                        copy(s[idx+1:], s[idx:])

[dnj, 2015/10/15 02:23:46]

nit: WDYT about making eqfilts a binheap?

+                                        s[idx] = p
                                 }
                         }
                         q.eqFilts[field] = s
                 }
         })
 }
 
 func (q *Query) reserved(field string) bool {
         if field == "__key__" {
                 return false
@@ skipping 437 matching lines @@
         if q.keysOnly {
                 p("KeysOnly")
         }
 
         if _, err := ret.WriteRune(')'); err != nil {
                 panic(err)
         }
 
         return ret.String()
 }