Spaces:
Running
Running
File size: 3,151 Bytes
b110593 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 |
// _ _
// __ _____ __ ___ ___ __ _| |_ ___
// \ \ /\ / / _ \/ _` \ \ / / |/ _` | __/ _ \
// \ V V / __/ (_| |\ V /| | (_| | || __/
// \_/\_/ \___|\__,_| \_/ |_|\__,_|\__\___|
//
// Copyright © 2016 - 2024 Weaviate B.V. All rights reserved.
//
// CONTACT: [email protected]
//
package hnsw
import (
"context"
"github.com/pkg/errors"
"github.com/weaviate/weaviate/adapters/repos/db/helpers"
"github.com/weaviate/weaviate/adapters/repos/db/priorityqueue"
"github.com/weaviate/weaviate/entities/storobj"
)
func (h *hnsw) selectNeighborsHeuristic(input *priorityqueue.Queue[any],
max int, denyList helpers.AllowList,
) error {
if input.Len() < max {
return nil
}
// TODO, if this solution stays we might need something with fewer allocs
ids := make([]uint64, input.Len())
closestFirst := h.pools.pqHeuristic.GetMin(input.Len())
i := uint64(0)
for input.Len() > 0 {
elem := input.Pop()
closestFirst.InsertWithValue(elem.ID, elem.Dist, i)
ids[i] = elem.ID
i++
}
var returnList []priorityqueue.Item[uint64]
if h.compressed.Load() {
bag := h.compressor.NewBag()
for _, id := range ids {
err := bag.Load(context.Background(), id)
if err != nil {
return err
}
}
returnList = h.pools.pqItemSlice.Get().([]priorityqueue.Item[uint64])
for closestFirst.Len() > 0 && len(returnList) < max {
curr := closestFirst.Pop()
if denyList != nil && denyList.Contains(curr.ID) {
continue
}
distToQuery := curr.Dist
good := true
for _, item := range returnList {
peerDist, err := bag.Distance(curr.ID, item.ID)
if err != nil {
return err
}
if peerDist < distToQuery {
good = false
break
}
}
if good {
returnList = append(returnList, curr)
}
}
} else {
vecs, errs := h.multiVectorForID(context.TODO(), ids)
returnList = h.pools.pqItemSlice.Get().([]priorityqueue.Item[uint64])
for closestFirst.Len() > 0 && len(returnList) < max {
curr := closestFirst.Pop()
if denyList != nil && denyList.Contains(curr.ID) {
continue
}
distToQuery := curr.Dist
currVec := vecs[curr.Value]
if err := errs[curr.Value]; err != nil {
var e storobj.ErrNotFound
if errors.As(err, &e) {
h.handleDeletedNode(e.DocID)
continue
} else {
// not a typed error, we can recover from, return with err
return errors.Wrapf(err,
"unrecoverable error for docID %d", curr.ID)
}
}
good := true
for _, item := range returnList {
peerDist, _, _ := h.distancerProvider.SingleDist(currVec,
vecs[item.Value])
if peerDist < distToQuery {
good = false
break
}
}
if good {
returnList = append(returnList, curr)
}
}
}
h.pools.pqHeuristic.Put(closestFirst)
for _, retElem := range returnList {
input.Insert(retElem.ID, retElem.Dist)
}
// rewind and return to pool
returnList = returnList[:0]
//nolint:staticcheck
h.pools.pqItemSlice.Put(returnList)
return nil
}
|