| 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 |