-
Notifications
You must be signed in to change notification settings - Fork 1.2k
/
table_search.go
208 lines (173 loc) · 4.27 KB
/
table_search.go
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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
package storage
import (
"container/heap"
"fmt"
"io"
"github.com/VictoriaMetrics/VictoriaMetrics/lib/fasttime"
"github.com/VictoriaMetrics/VictoriaMetrics/lib/logger"
)
// tableSearch performs searches in the table.
type tableSearch struct {
BlockRef *BlockRef
tb *table
// ptws hold paritions snapshot for the given table during Init call.
// This snapshot is used for calling table.PutPartitions on tableSearch.MustClose.
ptws []*partitionWrapper
ptsPool []partitionSearch
ptsHeap partitionSearchHeap
err error
nextBlockNoop bool
needClosing bool
}
func (ts *tableSearch) reset() {
ts.BlockRef = nil
ts.tb = nil
for i := range ts.ptws {
ts.ptws[i] = nil
}
ts.ptws = ts.ptws[:0]
for i := range ts.ptsPool {
ts.ptsPool[i].reset()
}
ts.ptsPool = ts.ptsPool[:0]
for i := range ts.ptsHeap {
ts.ptsHeap[i] = nil
}
ts.ptsHeap = ts.ptsHeap[:0]
ts.err = nil
ts.nextBlockNoop = false
ts.needClosing = false
}
// Init initializes the ts.
//
// tsids must be sorted.
// tsids cannot be modified after the Init call, since it is owned by ts.
//
// MustClose must be called then the tableSearch is done.
func (ts *tableSearch) Init(tb *table, tsids []TSID, tr TimeRange) {
if ts.needClosing {
logger.Panicf("BUG: missing MustClose call before the next call to Init")
}
// Adjust tr.MinTimestamp, so it doesn't obtain data older
// than the tb retention.
now := int64(fasttime.UnixTimestamp() * 1000)
minTimestamp := now - tb.s.retentionMsecs
if tr.MinTimestamp < minTimestamp {
tr.MinTimestamp = minTimestamp
}
ts.reset()
ts.tb = tb
ts.needClosing = true
if len(tsids) == 0 {
// Fast path - zero tsids.
ts.err = io.EOF
return
}
ts.ptws = tb.GetPartitions(ts.ptws[:0])
// Initialize the ptsPool.
if n := len(ts.ptws) - cap(ts.ptsPool); n > 0 {
ts.ptsPool = append(ts.ptsPool[:cap(ts.ptsPool)], make([]partitionSearch, n)...)
}
ts.ptsPool = ts.ptsPool[:len(ts.ptws)]
for i, ptw := range ts.ptws {
ts.ptsPool[i].Init(ptw.pt, tsids, tr)
}
// Initialize the ptsHeap.
ts.ptsHeap = ts.ptsHeap[:0]
for i := range ts.ptsPool {
pts := &ts.ptsPool[i]
if !pts.NextBlock() {
if err := pts.Error(); err != nil {
// Return only the first error, since it has no sense in returning all errors.
ts.err = fmt.Errorf("cannot initialize table search: %w", err)
return
}
continue
}
ts.ptsHeap = append(ts.ptsHeap, pts)
}
if len(ts.ptsHeap) == 0 {
ts.err = io.EOF
return
}
heap.Init(&ts.ptsHeap)
ts.BlockRef = ts.ptsHeap[0].BlockRef
ts.nextBlockNoop = true
}
// NextBlock advances to the next block.
//
// The blocks are sorted by (TSID, MinTimestamp). Two subsequent blocks
// for the same TSID may contain overlapped time ranges.
func (ts *tableSearch) NextBlock() bool {
if ts.err != nil {
return false
}
if ts.nextBlockNoop {
ts.nextBlockNoop = false
return true
}
ts.err = ts.nextBlock()
if ts.err != nil {
if ts.err != io.EOF {
ts.err = fmt.Errorf("cannot obtain the next block to search in the table: %w", ts.err)
}
return false
}
return true
}
func (ts *tableSearch) nextBlock() error {
ptsMin := ts.ptsHeap[0]
if ptsMin.NextBlock() {
heap.Fix(&ts.ptsHeap, 0)
ts.BlockRef = ts.ptsHeap[0].BlockRef
return nil
}
if err := ptsMin.Error(); err != nil {
return err
}
heap.Pop(&ts.ptsHeap)
if len(ts.ptsHeap) == 0 {
return io.EOF
}
ts.BlockRef = ts.ptsHeap[0].BlockRef
return nil
}
// Error returns the last error in the ts.
func (ts *tableSearch) Error() error {
if ts.err == io.EOF {
return nil
}
return ts.err
}
// MustClose closes the ts.
func (ts *tableSearch) MustClose() {
if !ts.needClosing {
logger.Panicf("BUG: missing Init call before MustClose call")
}
for i := range ts.ptsPool {
ts.ptsPool[i].MustClose()
}
ts.tb.PutPartitions(ts.ptws)
ts.reset()
}
type partitionSearchHeap []*partitionSearch
func (ptsh *partitionSearchHeap) Len() int {
return len(*ptsh)
}
func (ptsh *partitionSearchHeap) Less(i, j int) bool {
x := *ptsh
return x[i].BlockRef.bh.Less(&x[j].BlockRef.bh)
}
func (ptsh *partitionSearchHeap) Swap(i, j int) {
x := *ptsh
x[i], x[j] = x[j], x[i]
}
func (ptsh *partitionSearchHeap) Push(x interface{}) {
*ptsh = append(*ptsh, x.(*partitionSearch))
}
func (ptsh *partitionSearchHeap) Pop() interface{} {
a := *ptsh
v := a[len(a)-1]
*ptsh = a[:len(a)-1]
return v
}