include/punk_observe/po_scan.h

filter: Statementstmt 100% 142 / 142 Branchbran 72.9% 105 / 144 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 86.3% 247 / 286 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« include/punk_observe/po_sgraph.h ↑ Summary xs/decode.xs »
1 /* po_scan.h - the pushdown: deciding what a query does NOT have to read.
2 *
3 * THE JOIN PHASE 9 COULD NOT MAKE.
4 *
5 * Phase 9's executor ran over rows somebody else had materialised, and its
6 * `blocks_skipped` was always zero - not because nothing could be skipped,
7 * but because there were no blocks yet to skip. Phase 10 gave the segment a
8 * region table and phase 12 shipped without closing the gap. This is the
9 * closure: the plan's predicates, turned into the question "can this segment,
10 * this chunk, this block possibly hold a matching row", asked BEFORE anything
11 * is mapped, decompressed or decoded.
12 *
13 * That ordering is the whole value. A bloom filter consulted after
14 * decompressing the block has cost more than it saved, and phase 6's filter
15 * has been sitting unconsulted since it was built.
16 *
17 * THE ASYMMETRY THAT GOVERNS EVERY TEST HERE.
18 *
19 * Skipping something that could have matched LOSES DATA, silently, and the
20 * answer still looks complete. Reading something that turns out not to match
21 * costs time and nothing else. So every predicate below is conservative:
22 * when it cannot prove a block is irrelevant it reads it, and an expression
23 * shape this file does not understand narrows nothing at all rather than
24 * narrowing by guess.
25 *
26 * In particular an OR narrows NOTHING. `t > noon or service = "api"` still
27 * admits every row outside the range, and treating either branch as a bound
28 * would drop rows the query asked for.
29 */
30 #ifndef PO_SCAN_H
31 #define PO_SCAN_H
32  
33 #include "punk_observe/po_compat.h"
34 #include "punk_observe/po_query.h"
35 #include "punk_observe/po_expr.h"
36 #include "punk_observe/po_result.h"
37 #include "punk_observe/po_qexec.h"
38 #include "punk_observe/po_seg.h"
39 #include "punk_observe/po_segio.h"
40 #include "punk_observe/po_logidx.h"
41 #include "punk_observe/po_bloom.h"
42  
43 /* ---- what the plan pushes down -------------------------------------------- */
44  
45 typedef struct {
46 po_u64 from, to; /* the closed time range, in nanoseconds */
47 int time_bounded; /* did anything actually narrow it? */
48  
49 const char *search; size_t search_len; /* for the trigram filter */
50  
51 /* the first equality on a label, which a stream or series directory can
52 * answer without opening the payload */
53 const char *eq_field; size_t eq_field_len;
54 const char *eq_val; size_t eq_val_len;
55 int have_eq;
56  
57 po_u64 min_dur; /* `duration > ...` on traces */
58 int have_min_dur;
59 } po_pushdown;
60  
61 97 static int po_field_is_time(const po_expr *e) {
62 29 ▶ return (e->field_len == 1 && e->field[0] == 't')
Branch: 1 branch
BranchTrueFalseTotal
return (e->field_len == 1 && e->field[0] == 't') 0 29 29
63 126 ▶ || (e->field_len == 4 && memcmp(e->field, "time", 4) == 0);
Branch: 3 branches
BranchTrueFalseTotal
|| (e->field_len == 4 && memcmp(e->field, "time", 4) == 0); 29 68 97
|| (e->field_len == 4 && memcmp(e->field, "time", 4) == 0); 6 62 68
|| (e->field_len == 4 && memcmp(e->field, "time", 4) == 0); 1 5 6
64 }
65  
66 67 static int po_field_is_duration(const po_expr *e) {
67 67 ▶ return e->field_len == 8 && memcmp(e->field, "duration", 8) == 0;
Branch: 2 branches
BranchTrueFalseTotal
return e->field_len == 8 && memcmp(e->field, "duration", 8) == 0; 21 46 67
return e->field_len == 8 && memcmp(e->field, "duration", 8) == 0; 6 15 21
68 }
69  
70 /* The numeric value of a comparison, as nanoseconds.
71 *
72 * A NUMBER arrives as a double and a DURATION as an exact po_u64. Rounding a
73 * nanosecond timestamp through a double loses the low bits, so the exact one
74 * is used exactly and only a genuine PO_V_NUMBER goes through the NV. */
75 36 static int po_expr_u64_value(const po_expr *e, po_u64 *out) {
76 36 ▶ if (e->vkind == PO_V_DURATION || e->vkind == PO_V_SEVERITY) {
Branch: 2 branches
BranchTrueFalseTotal
if (e->vkind == PO_V_DURATION || e->vkind == PO_V_SEVERITY) { 31 5 36
if (e->vkind == PO_V_DURATION || e->vkind == PO_V_SEVERITY) { 0 31 31
77 5 *out = e->uval;
78 5 return 1;
79 }
80 31 ▶ if (e->vkind == PO_V_NUMBER) {
Branch: 1 branch
BranchTrueFalseTotal
if (e->vkind == PO_V_NUMBER) { 29 2 31
81 /* Clamped BEFORE the cast, both ends. Converting a double that does
82 * not fit the destination integer type is undefined behaviour, not a
83 * wrap, so a query saying `t > 1e30` must not be allowed to reach the
84 * cast at all. */
85 29 ▶ if (!(e->nval == e->nval)) return 0; /* NaN narrows nothing */
Branch: 1 branch
BranchTrueFalseTotal
if (!(e->nval == e->nval)) return 0; /* NaN narrows nothing */ 0 29 29
86 29 ▶ if (e->nval < 0) { *out = 0; return 1; }
Branch: 1 branch
BranchTrueFalseTotal
if (e->nval < 0) { *out = 0; return 1; } 0 29 29
87 29 ▶ if (e->nval >= 1.8446744073709550e19) { *out = PO_U64_MAX; return 1; }
Branch: 1 branch
BranchTrueFalseTotal
if (e->nval >= 1.8446744073709550e19) { *out = PO_U64_MAX; return 1; } 0 29 29
88 29 *out = (po_u64)e->nval;
89 29 return 1;
90 }
91 2 return 0;
92 }
93  
94 29 static void po_range_narrow(po_pushdown *pd, int op, po_u64 v) {
95 29 switch (op) {
96 8 case PO_OP_GT:
97 8 ▶ if (v == PO_U64_MAX) { pd->from = PO_U64_MAX; pd->to = 0; }
Branch: 1 branch
BranchTrueFalseTotal
if (v == PO_U64_MAX) { pd->from = PO_U64_MAX; pd->to = 0; } 0 8 8
98 8 ▶ else if (v + 1 > pd->from) pd->from = v + 1;
Branch: 1 branch
BranchTrueFalseTotal
else if (v + 1 > pd->from) pd->from = v + 1; 8 0 8
99 8 pd->time_bounded = 1;
100 8 break;
101 10 case PO_OP_GE:
102 10 ▶ if (v > pd->from) pd->from = v;
Branch: 1 branch
BranchTrueFalseTotal
if (v > pd->from) pd->from = v; 10 0 10
103 10 pd->time_bounded = 1;
104 10 break;
105 3 case PO_OP_LT:
106 3 ▶ if (v == 0) { pd->from = PO_U64_MAX; pd->to = 0; }
Branch: 1 branch
BranchTrueFalseTotal
if (v == 0) { pd->from = PO_U64_MAX; pd->to = 0; } 1 2 3
107 2 ▶ else if (v - 1 < pd->to) pd->to = v - 1;
Branch: 1 branch
BranchTrueFalseTotal
else if (v - 1 < pd->to) pd->to = v - 1; 2 0 2
108 3 pd->time_bounded = 1;
109 3 break;
110 6 case PO_OP_LE:
111 6 ▶ if (v < pd->to) pd->to = v;
Branch: 1 branch
BranchTrueFalseTotal
if (v < pd->to) pd->to = v; 6 0 6
112 6 pd->time_bounded = 1;
113 6 break;
114 1 case PO_OP_EQ:
115 1 ▶ if (v > pd->from) pd->from = v;
Branch: 1 branch
BranchTrueFalseTotal
if (v > pd->from) pd->from = v; 1 0 1
116 1 ▶ if (v < pd->to) pd->to = v;
Branch: 1 branch
BranchTrueFalseTotal
if (v < pd->to) pd->to = v; 1 0 1
117 1 pd->time_bounded = 1;
118 1 break;
119 1 default:
120 /* !=, =~, !~ narrow nothing: every one of them admits rows on
121 * both sides of the value. */
122 1 break;
123 }
124 29 }
125  
126 109 static void po_pushdown_walk(po_pushdown *pd, const po_expr *e) {
127 109 ▶ if (!e) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!e) return; 0 109 109
128  
129 /* Only a conjunction narrows. An OR or a NOT is walked no further: see
130 * the header comment - a bound taken from one arm of an OR would drop
131 * rows the other arm asked for. */
132 109 ▶ if (e->kind == PO_E_AND) {
Branch: 1 branch
BranchTrueFalseTotal
if (e->kind == PO_E_AND) { 10 99 109
133 10 po_pushdown_walk(pd, e->a);
134 10 po_pushdown_walk(pd, e->b);
135 10 return;
136 }
137 99 ▶ if (e->kind != PO_E_CMP) return;
Branch: 1 branch
BranchTrueFalseTotal
if (e->kind != PO_E_CMP) return; 2 97 99
138  
139 97 ▶ if (po_field_is_time(e)) {
Branch: 1 branch
BranchTrueFalseTotal
if (po_field_is_time(e)) { 30 67 97
140 po_u64 v;
141 30 ▶ if (po_expr_u64_value(e, &v)) po_range_narrow(pd, e->op, v);
Branch: 1 branch
BranchTrueFalseTotal
if (po_expr_u64_value(e, &v)) po_range_narrow(pd, e->op, v); 29 1 30
142 30 return;
143 }
144  
145 67 ▶ if (po_field_is_duration(e)) {
Branch: 1 branch
BranchTrueFalseTotal
if (po_field_is_duration(e)) { 6 61 67
146 po_u64 v;
147 6 ▶ if ((e->op == PO_OP_GT || e->op == PO_OP_GE)
Branch: 2 branches
BranchTrueFalseTotal
if ((e->op == PO_OP_GT || e->op == PO_OP_GE) 2 4 6
if ((e->op == PO_OP_GT || e->op == PO_OP_GE) 2 0 2
148 6 ▶ && po_expr_u64_value(e, &v)) {
Branch: 1 branch
BranchTrueFalseTotal
&& po_expr_u64_value(e, &v)) { 5 1 6
149 5 ▶ if (!pd->have_min_dur || v > pd->min_dur) {
Branch: 2 branches
BranchTrueFalseTotal
if (!pd->have_min_dur || v > pd->min_dur) { 0 5 5
if (!pd->have_min_dur || v > pd->min_dur) { 0 0 0
150 5 ▶ pd->min_dur = (e->op == PO_OP_GT && v != PO_U64_MAX) ? v + 1 : v;
Branch: 2 branches
BranchTrueFalseTotal
pd->min_dur = (e->op == PO_OP_GT && v != PO_U64_MAX) ? v + 1 : v; 4 1 5
pd->min_dur = (e->op == PO_OP_GT && v != PO_U64_MAX) ? v + 1 : v; 4 0 4
151 5 pd->have_min_dur = 1;
152 }
153 }
154 6 return;
155 }
156  
157 61 ▶ if (e->op == PO_OP_EQ && e->vkind == PO_V_STRING && !pd->have_eq) {
Branch: 3 branches
BranchTrueFalseTotal
if (e->op == PO_OP_EQ && e->vkind == PO_V_STRING && !pd->have_eq) { 44 17 61
if (e->op == PO_OP_EQ && e->vkind == PO_V_STRING && !pd->have_eq) { 34 10 44
if (e->op == PO_OP_EQ && e->vkind == PO_V_STRING && !pd->have_eq) { 34 0 34
158 34 pd->eq_field = e->field;
159 34 pd->eq_field_len = e->field_len;
160 34 pd->eq_val = e->sval;
161 34 pd->eq_val_len = e->sval_len;
162 34 pd->have_eq = 1;
163 }
164 }
165  
166 987 static void po_pushdown_build(po_pushdown *pd, const po_plan *p) {
167 987 memset(pd, 0, sizeof(*pd));
168 987 pd->from = 0;
169 987 pd->to = PO_U64_MAX;
170 987 ▶ if (!p) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!p) return; 0 987 987
171 { /* Each where is a conjunct, so a bound proven by ANY of them
172 * narrows the read for all of them. */
173 int i;
174 1076 ▶ for (i = 0; i < p->nwhere; i++) po_pushdown_walk(pd, p->wheres[i]);
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < p->nwhere; i++) po_pushdown_walk(pd, p->wheres[i]); 89 987 1076
175 }
176 987 pd->search = p->search;
177 987 pd->search_len = p->search_len;
178 }
179  
180 /* An empty range is a range no row can be in: `t > 100 and t < 50`. Answering
181 * it by reading nothing is correct, and saying so here keeps every caller
182 * below from having to notice. */
183 4695 static int po_pushdown_empty(const po_pushdown *pd) {
184 4695 return pd->from > pd->to;
185 }
186  
187 /* ---- segment-level pruning ------------------------------------------------- */
188  
189 /* Worth opening at all? The footer carries t_min/t_max, so this is answered
190 * from 32 bytes rather than from the payload. */
191 619 static int po_scan_segment_wanted(const po_seg_r *s, const po_pushdown *pd,
192 po_result *res) {
193 int want;
194 619 ▶ if (po_pushdown_empty(pd)) want = 0;
Branch: 1 branch
BranchTrueFalseTotal
if (po_pushdown_empty(pd)) want = 0; 0 619 619
195 619 else want = po_seg_overlaps(s, pd->from, pd->to);
196 619 ▶ if (res) {
Branch: 1 branch
BranchTrueFalseTotal
if (res) { 619 0 619
197 619 res->blocks++;
198 619 ▶ if (!want) res->blocks_skipped++;
Branch: 1 branch
BranchTrueFalseTotal
if (!want) res->blocks_skipped++; 1 618 619
199 }
200 619 return want;
201 }
202  
203 /* ---- metrics ---------------------------------------------------------------
204 *
205 * A chunk carries its own first and last timestamp, so a range query reads
206 * only the chunks that overlap it and never touches the bit streams of the
207 * rest. */
208 618 static int po_scan_metric_chunks(const po_seg_r *s, const po_pushdown *pd,
209 po_mchunk_ref *into, uint32_t max,
210 po_result *res) {
211 618 size_t len = 0;
212 618 const char *p = po_seg_region_ptr(s, PO_RGN_MCHUNKS, &len);
213 po_mchunk_ref *all;
214 618 int n, i, keep = 0;
215  
216 618 ▶ if (!p) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!p) return 0; 0 618 618
217 618 ▶ all = (po_mchunk_ref *)malloc(sizeof(po_mchunk_ref) * (max ? max : 1));
Branch: 1 branch
BranchTrueFalseTotal
all = (po_mchunk_ref *)malloc(sizeof(po_mchunk_ref) * (max ? max : 1)); 618 0 618
218 618 ▶ if (!all) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if (!all) return -1; 0 618 618
219 618 n = po_metric_open(p, len, all, max);
220 618 ▶ if (n < 0) { free(all); return -1; }
Branch: 1 branch
BranchTrueFalseTotal
if (n < 0) { free(all); return -1; } 0 618 618
221  
222 1854 ▶ for (i = 0; i < n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n; i++) { 1236 618 1854
223 1236 int want = !po_pushdown_empty(pd)
224 1236 ▶ && all[i].h.t_first <= pd->to
Branch: 1 branch
BranchTrueFalseTotal
&& all[i].h.t_first <= pd->to 1232 4 1236
225 2472 ▶ && all[i].h.t_last >= pd->from;
Branch: 2 branches
BranchTrueFalseTotal
&& all[i].h.t_last >= pd->from; 1236 0 1236
&& all[i].h.t_last >= pd->from; 1230 2 1232
226 1236 ▶ if (res) {
Branch: 1 branch
BranchTrueFalseTotal
if (res) { 1236 0 1236
227 1236 res->blocks++;
228 1236 ▶ if (!want) res->blocks_skipped++;
Branch: 1 branch
BranchTrueFalseTotal
if (!want) res->blocks_skipped++; 6 1230 1236
229 }
230 1236 ▶ if (want) into[keep++] = all[i];
Branch: 1 branch
BranchTrueFalseTotal
if (want) into[keep++] = all[i]; 1230 6 1236
231 }
232 618 free(all);
233 618 return keep;
234 }
235  
236 /* ---- logs ------------------------------------------------------------------
237 *
238 * Three filters in increasing cost order, and the order is the point: a
239 * stream mismatch is a comparison, a time mismatch is two, and the bloom is
240 * a handful of hashes - all of them before the block is inflated.
241 *
242 * A query shorter than a trigram cannot use the filter and MUST fall through
243 * to reading the block. Answering "no match" from a filter that cannot see
244 * the term is the one failure mode that loses log lines. */
245 618 static int po_scan_log_blocks(const po_seg_r *s, const po_pushdown *pd,
246 int have_stream, po_u64 stream,
247 po_lblock_ref *into, uint32_t max,
248 po_result *res, po_prune_stats *st) {
249 618 size_t len = 0;
250 618 const char *p = po_seg_region_ptr(s, PO_RGN_LOGBLOCKS, &len);
251 po_lblock_ref *all;
252 618 int n, i, keep = 0;
253  
254 618 ▶ if (!p) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!p) return 0; 0 618 618
255 618 ▶ all = (po_lblock_ref *)malloc(sizeof(po_lblock_ref) * (max ? max : 1));
Branch: 1 branch
BranchTrueFalseTotal
all = (po_lblock_ref *)malloc(sizeof(po_lblock_ref) * (max ? max : 1)); 618 0 618
256 618 ▶ if (!all) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if (!all) return -1; 0 618 618
257 618 n = po_log_open(p, len, all, max);
258 618 ▶ if (n < 0) { free(all); return -1; }
Branch: 1 branch
BranchTrueFalseTotal
if (n < 0) { free(all); return -1; } 0 618 618
259  
260 1854 ▶ for (i = 0; i < n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n; i++) { 1236 618 1854
261 po_dir_ent e;
262 int want;
263 1236 memset(&e, 0, sizeof(e));
264 1236 e.h = all[i].h;
265 1236 want = !po_pushdown_empty(pd)
266 2472 && po_block_candidate(&e, have_stream, stream, pd->from, pd->to,
267 1236 all[i].bloom, pd->search, pd->search_len, st);
268 1236 ▶ if (res) {
Branch: 1 branch
BranchTrueFalseTotal
if (res) { 1236 0 1236
269 1236 res->blocks++;
270 1236 ▶ if (!want) res->blocks_skipped++;
Branch: 1 branch
BranchTrueFalseTotal
if (!want) res->blocks_skipped++; 620 616 1236
271 }
272 1236 ▶ if (want) into[keep++] = all[i];
Branch: 1 branch
BranchTrueFalseTotal
if (want) into[keep++] = all[i]; 616 620 1236
273 }
274 618 free(all);
275 618 return keep;
276 }
277  
278 /* ---- traces ----------------------------------------------------------------
279 *
280 * Spans are one flat array rather than blocks, so the pruning that pays is at
281 * the summary level: a `duration >` or a time range answers from the trace
282 * summaries without touching a span. */
283 618 static int po_scan_trace_summaries(const po_seg_r *s, const po_pushdown *pd,
284 const po_tsummary **into, uint32_t max,
285 po_result *res) {
286 618 size_t len = 0;
287 618 const char *p = po_seg_region_ptr(s, PO_RGN_TRACESUM, &len);
288 const po_tsummary *t;
289 618 uint32_t n = 0, i;
290 618 int keep = 0;
291  
292 618 ▶ if (!p) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!p) return 0; 0 618 618
293 618 t = po_tsum_open(p, len, &n);
294 618 ▶ if (!t) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if (!t) return -1; 0 618 618
295  
296 1854 ▶ for (i = 0; i < n && (uint32_t)keep < max; i++) {
Branch: 2 branches
BranchTrueFalseTotal
for (i = 0; i < n && (uint32_t)keep < max; i++) { 1236 618 1854
for (i = 0; i < n && (uint32_t)keep < max; i++) { 1236 0 1236
297 /* A trace OVERLAPS the range when it starts before the end of it and
298 * ends after the beginning: a slow request straddling the boundary is
299 * exactly the one being looked for, and keying on start_ns alone
300 * would drop it. */
301 1236 po_u64 end = t[i].start_ns + t[i].dur_ns;
302 1236 int want = !po_pushdown_empty(pd)
303 1236 ▶ && t[i].start_ns <= pd->to && end >= pd->from
Branch: 2 branches
BranchTrueFalseTotal
&& t[i].start_ns <= pd->to && end >= pd->from 1236 0 1236
&& t[i].start_ns <= pd->to && end >= pd->from 1223 13 1236
304 2472 ▶ && (!pd->have_min_dur || t[i].dur_ns >= pd->min_dur);
Branch: 3 branches
BranchTrueFalseTotal
&& (!pd->have_min_dur || t[i].dur_ns >= pd->min_dur); 1236 0 1236
&& (!pd->have_min_dur || t[i].dur_ns >= pd->min_dur); 4 1219 1223
&& (!pd->have_min_dur || t[i].dur_ns >= pd->min_dur); 3 1 4
305 1236 ▶ if (res) {
Branch: 1 branch
BranchTrueFalseTotal
if (res) { 1236 0 1236
306 1236 res->blocks++;
307 1236 ▶ if (!want) res->blocks_skipped++;
Branch: 1 branch
BranchTrueFalseTotal
if (!want) res->blocks_skipped++; 14 1222 1236
308 }
309 1236 ▶ if (want) into[keep++] = &t[i];
Branch: 1 branch
BranchTrueFalseTotal
if (want) into[keep++] = &t[i]; 1222 14 1236
310 }
311 618 return keep;
312 }
313  
314 #endif /* PO_SCAN_H */
« include/punk_observe/po_sgraph.h ↑ Summary xs/decode.xs »