OLD | NEW |
1 // Copyright 2015 The LUCI Authors. All rights reserved. | 1 // Copyright 2015 The LUCI Authors. All rights reserved. |
2 // Use of this source code is governed under the Apache License, Version 2.0 | 2 // Use of this source code is governed under the Apache License, Version 2.0 |
3 // that can be found in the LICENSE file. | 3 // that can be found in the LICENSE file. |
4 | 4 |
5 package memory | 5 package memory |
6 | 6 |
7 import ( | 7 import ( |
8 "bytes" | 8 "bytes" |
9 "fmt" | 9 "fmt" |
10 "sort" | 10 "sort" |
(...skipping 18 matching lines...) Expand all Loading... |
29 } | 29 } |
30 return fmt.Sprintf( | 30 return fmt.Sprintf( |
31 "Insufficient indexes. Consider adding:\n%s", yaml) | 31 "Insufficient indexes. Consider adding:\n%s", yaml) |
32 } | 32 } |
33 | 33 |
34 // reducedQuery contains only the pieces of the query necessary to iterate for | 34 // reducedQuery contains only the pieces of the query necessary to iterate for |
35 // results. | 35 // results. |
36 // deduplication is applied externally | 36 // deduplication is applied externally |
37 // projection / keysonly / entity retrieval is done externally | 37 // projection / keysonly / entity retrieval is done externally |
38 type reducedQuery struct { | 38 type reducedQuery struct { |
39 » aid string | 39 » kc ds.KeyContext |
40 » ns string | |
41 kind string | 40 kind string |
42 | 41 |
43 // eqFilters indicate the set of all prefix constraints which need to be | 42 // eqFilters indicate the set of all prefix constraints which need to be |
44 // fulfilled in the composite query. All of these will translate into pr
efix | 43 // fulfilled in the composite query. All of these will translate into pr
efix |
45 // bytes for SOME index. | 44 // bytes for SOME index. |
46 eqFilters map[string]stringset.Set | 45 eqFilters map[string]stringset.Set |
47 | 46 |
48 // suffixFormat is the PRECISE listing of the suffix columns that ALL in
dexes | 47 // suffixFormat is the PRECISE listing of the suffix columns that ALL in
dexes |
49 // in the multi query will have. | 48 // in the multi query will have. |
50 // | 49 // |
(...skipping 139 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
190 totalEqFilts++ | 189 totalEqFilts++ |
191 } | 190 } |
192 | 191 |
193 // ok, we can actually use this | 192 // ok, we can actually use this |
194 | 193 |
195 // Grab the collection for convenience later. We don't want to invalidat
e this | 194 // Grab the collection for convenience later. We don't want to invalidat
e this |
196 // index's potential just because the collection doesn't exist. If it's | 195 // index's potential just because the collection doesn't exist. If it's |
197 // a builtin and it doesn't exist, it still needs to be one of the 'poss
ible' | 196 // a builtin and it doesn't exist, it still needs to be one of the 'poss
ible' |
198 // indexes... it just means that the user's query will end up with no re
sults. | 197 // indexes... it just means that the user's query will end up with no re
sults. |
199 coll := s.GetCollection( | 198 coll := s.GetCollection( |
200 » » fmt.Sprintf("idx:%s:%s", q.ns, serialize.ToBytes(*id.PrepForIdxT
able()))) | 199 » » fmt.Sprintf("idx:%s:%s", q.kc.Namespace, serialize.ToBytes(*id.P
repForIdxTable()))) |
201 | 200 |
202 // First, see if it's a perfect match. If it is, then our search is over
. | 201 // First, see if it's a perfect match. If it is, then our search is over
. |
203 // | 202 // |
204 // A perfect match contains ALL the equality filter columns (or more, si
nce | 203 // A perfect match contains ALL the equality filter columns (or more, si
nce |
205 // we can use residuals to fill in the extras). | 204 // we can use residuals to fill in the extras). |
206 toAdd := indexDefinitionSortable{coll: coll} | 205 toAdd := indexDefinitionSortable{coll: coll} |
207 toAdd.eqFilts = eqFilts | 206 toAdd.eqFilts = eqFilts |
208 for _, sb := range toAdd.eqFilts { | 207 for _, sb := range toAdd.eqFilts { |
209 missingTerms.Del(sb.Property) | 208 missingTerms.Del(sb.Property) |
210 } | 209 } |
(...skipping 101 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
312 remains.SortBy = append(remains.SortBy, q.suffixFormat...) | 311 remains.SortBy = append(remains.SortBy, q.suffixFormat...) |
313 last := remains.SortBy[len(remains.SortBy)-1] | 312 last := remains.SortBy[len(remains.SortBy)-1] |
314 if !last.Descending { | 313 if !last.Descending { |
315 // this removes the __key__ column, since it's implicit. | 314 // this removes the __key__ column, since it's implicit. |
316 remains.SortBy = remains.SortBy[:len(remains.SortBy)-1] | 315 remains.SortBy = remains.SortBy[:len(remains.SortBy)-1] |
317 } | 316 } |
318 if remains.Builtin() { | 317 if remains.Builtin() { |
319 impossible( | 318 impossible( |
320 fmt.Errorf("recommended missing index would be a
builtin: %s", remains)) | 319 fmt.Errorf("recommended missing index would be a
builtin: %s", remains)) |
321 } | 320 } |
322 » » return nil, &ErrMissingIndex{q.ns, remains} | 321 » » return nil, &ErrMissingIndex{q.kc.Namespace, remains} |
323 } | 322 } |
324 | 323 |
325 return idxs, nil | 324 return idxs, nil |
326 } | 325 } |
327 | 326 |
328 // generate generates a single iterDefinition for the given index. | 327 // generate generates a single iterDefinition for the given index. |
329 func generate(q *reducedQuery, idx *indexDefinitionSortable, c *constraints) *it
erDefinition { | 328 func generate(q *reducedQuery, idx *indexDefinitionSortable, c *constraints) *it
erDefinition { |
330 def := &iterDefinition{ | 329 def := &iterDefinition{ |
331 c: idx.coll, | 330 c: idx.coll, |
332 start: q.start, | 331 start: q.start, |
(...skipping 131 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
464 ret.constraints[prop] = bvals | 463 ret.constraints[prop] = bvals |
465 } | 464 } |
466 return ret | 465 return ret |
467 } | 466 } |
468 | 467 |
469 // getIndexes returns a set of iterator definitions. Iterating over these | 468 // getIndexes returns a set of iterator definitions. Iterating over these |
470 // will result in matching suffixes. | 469 // will result in matching suffixes. |
471 func getIndexes(q *reducedQuery, s memStore) ([]*iterDefinition, error) { | 470 func getIndexes(q *reducedQuery, s memStore) ([]*iterDefinition, error) { |
472 relevantIdxs := indexDefinitionSortableSlice(nil) | 471 relevantIdxs := indexDefinitionSortableSlice(nil) |
473 if q.kind == "" { | 472 if q.kind == "" { |
474 » » if coll := s.GetCollection("ents:" + q.ns); coll != nil { | 473 » » if coll := s.GetCollection("ents:" + q.kc.Namespace); coll != ni
l { |
475 relevantIdxs = indexDefinitionSortableSlice{{coll: coll}
} | 474 relevantIdxs = indexDefinitionSortableSlice{{coll: coll}
} |
476 } | 475 } |
477 } else { | 476 } else { |
478 err := error(nil) | 477 err := error(nil) |
479 relevantIdxs, err = getRelevantIndexes(q, s) | 478 relevantIdxs, err = getRelevantIndexes(q, s) |
480 if err != nil { | 479 if err != nil { |
481 return nil, err | 480 return nil, err |
482 } | 481 } |
483 } | 482 } |
484 if len(relevantIdxs) == 0 { | 483 if len(relevantIdxs) == 0 { |
(...skipping 57 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
542 if bestIdx == nil { | 541 if bestIdx == nil { |
543 // something is really wrong here... if relevantIdxs is
!nil, then we | 542 // something is really wrong here... if relevantIdxs is
!nil, then we |
544 // should always be able to make progress in this loop. | 543 // should always be able to make progress in this loop. |
545 impossible(fmt.Errorf("deadlock: cannot fulfil query?")) | 544 impossible(fmt.Errorf("deadlock: cannot fulfil query?")) |
546 } | 545 } |
547 ret = append(ret, generate(q, bestIdx, constraints)) | 546 ret = append(ret, generate(q, bestIdx, constraints)) |
548 } | 547 } |
549 | 548 |
550 return ret, nil | 549 return ret, nil |
551 } | 550 } |
OLD | NEW |