| 1 |
|
| /* po_tsidx.h - the inverted index: label pair to series. |
| 2 |
|
| * |
| 3 |
|
| * "service=api" -> [12, 15, 16, 17, 88, 91, ...] |
| 4 |
|
| * "http.route=/x" -> [15, 91, ...] |
| 5 |
|
| * |
| 6 |
|
| * `where service = "api" and http.route = "/x"` is an INTERSECTION of two |
| 7 |
|
| * sorted lists, smallest first, which is a linear merge needing no allocation |
| 8 |
|
| * beyond the output. That is the whole design. |
| 9 |
|
| * |
| 10 |
|
| * Stored gap-encoded: the gaps between consecutive ids are small, so varints |
| 11 |
|
| * make the list a fraction of its raw size, with a skip table every 128 |
| 12 |
|
| * entries so an intersection can SEEK rather than scan. |
| 13 |
|
| * |
| 14 |
|
| * A roaring bitmap would beat this on very dense postings. It is not used, |
| 15 |
|
| * because postings here are sparse by construction - most label pairs belong |
| 16 |
|
| * to a small fraction of series - and a second compressed-set implementation |
| 17 |
|
| * is a second thing to get wrong. If profiling in phase 9 shows a dense case |
| 18 |
|
| * dominating, that is the moment to add it, with the number that justified it. |
| 19 |
|
| */ |
| 20 |
|
| #ifndef PO_TSIDX_H |
| 21 |
|
| #define PO_TSIDX_H |
| 22 |
|
| |
| 23 |
|
| #include "punk_observe/po_compat.h" |
| 24 |
|
| #include "punk_observe/po_rec.h" |
| 25 |
|
| |
| 26 |
|
| #define PO_SKIP_EVERY 128 |
| 27 |
|
| |
| 28 |
|
| /* ---- building ------------------------------------------------------------ */ |
| 29 |
|
| |
| 30 |
|
| typedef struct { |
| 31 |
|
| uint32_t *id; |
| 32 |
|
| uint32_t n, cap; |
| 33 |
|
| int sorted; |
| 34 |
|
| } po_postings; |
| 35 |
|
| |
| 36 |
106 |
| static int po_postings_init(po_postings *p) { |
| 37 |
106 |
| memset(p, 0, sizeof(*p)); |
| 38 |
106 |
| p->cap = 16; |
| 39 |
106 |
| p->id = (uint32_t *)malloc(p->cap * sizeof(uint32_t)); |
| 40 |
106 |
| p->sorted = 1; |
| 41 |
106 |
| return p->id != NULL; |
| 42 |
|
| } |
| 43 |
|
| |
| 44 |
106 |
| static void po_postings_free(po_postings *p) { |
| 45 |
106 |
| free(p->id); p->id = NULL; p->n = p->cap = 0; |
| 46 |
106 |
| } |
| 47 |
|
| |
| 48 |
78825 |
| static int po_postings_add(po_postings *p, uint32_t id) { |
| 49 |
78825 |
▶ | if (p->n == p->cap) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (p->n == p->cap) { |
466 |
78359 |
78825 |
|
| 50 |
466 |
| uint32_t want = p->cap * 2; |
| 51 |
466 |
| uint32_t *ni = (uint32_t *)realloc(p->id, want * sizeof(uint32_t)); |
| 52 |
466 |
▶ | if (!ni) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!ni) return 0; |
0 |
466 |
466 |
|
| 53 |
466 |
| p->id = ni; p->cap = want; |
| 54 |
|
| } |
| 55 |
78825 |
▶ | if (p->n && id <= p->id[p->n - 1]) p->sorted = 0; |
Branch: 2 branches
| Branch | True | False | Total |
| if (p->n && id <= p->id[p->n - 1]) p->sorted = 0; |
78719 |
106 |
78825 |
| if (p->n && id <= p->id[p->n - 1]) p->sorted = 0; |
5 |
78714 |
78719 |
|
| 56 |
78825 |
| p->id[p->n++] = id; |
| 57 |
78825 |
| return 1; |
| 58 |
|
| } |
| 59 |
|
| |
| 60 |
21 |
| static int po_u32cmp(const void *a, const void *b) { |
| 61 |
21 |
| uint32_t x = *(const uint32_t *)a, y = *(const uint32_t *)b; |
| 62 |
21 |
▶ | return x < y ? -1 : (x > y ? 1 : 0); |
Branch: 1 branch
| Branch | True | False | Total |
| return x < y ? -1 : (x > y ? 1 : 0); |
17 |
4 |
21 |
|
| 63 |
|
| } |
| 64 |
|
| |
| 65 |
|
| /* Sort and dedupe. A series can carry the same label pair only once, but a |
| 66 |
|
| * caller feeding one record per point would add it repeatedly, so the list is |
| 67 |
|
| * made a set here rather than trusting every caller to. */ |
| 68 |
106 |
| static void po_postings_finish(po_postings *p) { |
| 69 |
106 |
| uint32_t i, w = 0; |
| 70 |
106 |
▶ | if (!p->sorted) qsort(p->id, p->n, sizeof(uint32_t), po_u32cmp); |
Branch: 1 branch
| Branch | True | False | Total |
| if (!p->sorted) qsort(p->id, p->n, sizeof(uint32_t), po_u32cmp); |
1 |
105 |
106 |
|
| 71 |
78931 |
▶ | for (i = 0; i < p->n; i++) |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < p->n; i++) |
78825 |
106 |
78931 |
|
| 72 |
78825 |
▶ | if (i == 0 || p->id[i] != p->id[i - 1]) p->id[w++] = p->id[i]; |
Branch: 2 branches
| Branch | True | False | Total |
| if (i == 0 || p->id[i] != p->id[i - 1]) p->id[w++] = p->id[i]; |
78719 |
106 |
78825 |
| if (i == 0 || p->id[i] != p->id[i - 1]) p->id[w++] = p->id[i]; |
78716 |
3 |
78719 |
|
| 73 |
106 |
| p->n = w; |
| 74 |
106 |
| p->sorted = 1; |
| 75 |
106 |
| } |
| 76 |
|
| |
| 77 |
|
| /* Encode gap-varints plus a skip table. |
| 78 |
|
| * |
| 79 |
|
| * [varint count][skip count][ (u32 id, u32 bitoff) * skips ][gap varints] |
| 80 |
|
| */ |
| 81 |
106 |
| static size_t po_postings_encode(const po_postings *p, char **out) { |
| 82 |
106 |
| size_t cap = 16 + (size_t)p->n * 5 + ((size_t)p->n / PO_SKIP_EVERY + 1) * 8; |
| 83 |
106 |
| char *b = (char *)malloc(cap); |
| 84 |
106 |
| size_t o = 0; |
| 85 |
106 |
| uint32_t i, prev = 0, skips = (p->n + PO_SKIP_EVERY - 1) / PO_SKIP_EVERY; |
| 86 |
|
| size_t skip_at; |
| 87 |
|
| |
| 88 |
106 |
▶ | if (!b) { *out = NULL; return 0; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (!b) { *out = NULL; return 0; } |
0 |
106 |
106 |
|
| 89 |
|
| |
| 90 |
|
| #define PUTV(v) do { po_u64 _v = (v); \ |
| 91 |
|
| do { unsigned char _c = (unsigned char)(_v & 0x7F); _v >>= 7; \ |
| 92 |
|
| if (_v) _c |= 0x80; b[o++] = (char)_c; } while (_v); } while (0) |
| 93 |
|
| |
| 94 |
195 |
▶ | PUTV((po_u64)p->n); |
Branch: 2 branches
| Branch | True | False | Total |
| PUTV((po_u64)p->n); |
89 |
106 |
195 |
| PUTV((po_u64)p->n); |
89 |
106 |
195 |
|
| 95 |
108 |
▶ | PUTV((po_u64)skips); |
Branch: 2 branches
| Branch | True | False | Total |
| PUTV((po_u64)skips); |
2 |
106 |
108 |
| PUTV((po_u64)skips); |
2 |
106 |
108 |
|
| 96 |
106 |
| skip_at = o; |
| 97 |
106 |
| o += (size_t)skips * 8; /* filled in as we go */ |
| 98 |
|
| |
| 99 |
78928 |
▶ | for (i = 0; i < p->n; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < p->n; i++) { |
78822 |
106 |
78928 |
|
| 100 |
78822 |
▶ | if (i % PO_SKIP_EVERY == 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (i % PO_SKIP_EVERY == 0) { |
673 |
78149 |
78822 |
|
| 101 |
673 |
| uint32_t s = i / PO_SKIP_EVERY; |
| 102 |
673 |
| uint32_t v = po_le32(p->id[i]); |
| 103 |
673 |
| uint32_t f = po_le32((uint32_t)o); |
| 104 |
673 |
| memcpy(b + skip_at + (size_t)s * 8, &v, 4); |
| 105 |
673 |
| memcpy(b + skip_at + (size_t)s * 8 + 4, &f, 4); |
| 106 |
1438 |
▶ | PUTV((po_u64)p->id[i]); /* skip entries store the id whole */ |
Branch: 2 branches
| Branch | True | False | Total |
| PUTV((po_u64)p->id[i]); /* skip entries store the id whole */ |
765 |
673 |
1438 |
| PUTV((po_u64)p->id[i]); /* skip entries store the id whole */ |
765 |
673 |
1438 |
|
| 107 |
|
| } |
| 108 |
79187 |
▶ | else PUTV((po_u64)(p->id[i] - prev)); |
Branch: 2 branches
| Branch | True | False | Total |
| else PUTV((po_u64)(p->id[i] - prev)); |
1038 |
78149 |
79187 |
| else PUTV((po_u64)(p->id[i] - prev)); |
1038 |
78149 |
79187 |
|
| 109 |
78822 |
| prev = p->id[i]; |
| 110 |
|
| } |
| 111 |
|
| #undef PUTV |
| 112 |
106 |
| *out = b; |
| 113 |
106 |
| return o; |
| 114 |
|
| } |
| 115 |
|
| |
| 116 |
|
| /* ---- reading ------------------------------------------------------------- */ |
| 117 |
|
| |
| 118 |
|
| typedef struct { |
| 119 |
|
| const unsigned char *b; |
| 120 |
|
| size_t len, pos; |
| 121 |
|
| uint32_t n, i, prev; |
| 122 |
|
| const unsigned char *skip; |
| 123 |
|
| uint32_t skips; |
| 124 |
|
| } po_post_r; |
| 125 |
|
| |
| 126 |
78764 |
| static po_u64 po_getv(const unsigned char *b, size_t len, size_t *pos) { |
| 127 |
78764 |
| po_u64 v = 0; int sh = 0; |
| 128 |
80610 |
▶ | while (*pos < len) { |
Branch: 1 branch
| Branch | True | False | Total |
| while (*pos < len) { |
80610 |
0 |
80610 |
|
| 129 |
80610 |
| unsigned char c = b[(*pos)++]; |
| 130 |
80610 |
| v |= (po_u64)(c & 0x7F) << sh; |
| 131 |
80610 |
▶ | if (!(c & 0x80)) return v; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!(c & 0x80)) return v; |
78764 |
1846 |
80610 |
|
| 132 |
1846 |
| sh += 7; |
| 133 |
1846 |
▶ | if (sh > 63) break; |
Branch: 1 branch
| Branch | True | False | Total |
| if (sh > 63) break; |
0 |
1846 |
1846 |
|
| 134 |
|
| } |
| 135 |
0 |
| return v; |
| 136 |
|
| } |
| 137 |
|
| |
| 138 |
156 |
| static int po_post_open(po_post_r *r, const void *buf, size_t len) { |
| 139 |
156 |
| size_t pos = 0; |
| 140 |
156 |
| const unsigned char *b = (const unsigned char *)buf; |
| 141 |
156 |
| memset(r, 0, sizeof(*r)); |
| 142 |
156 |
| r->b = b; r->len = len; |
| 143 |
156 |
| r->n = (uint32_t)po_getv(b, len, &pos); |
| 144 |
156 |
| r->skips = (uint32_t)po_getv(b, len, &pos); |
| 145 |
156 |
▶ | if (pos + (size_t)r->skips * 8 > len) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (pos + (size_t)r->skips * 8 > len) return 0; |
0 |
156 |
156 |
|
| 146 |
156 |
| r->skip = b + pos; |
| 147 |
156 |
| r->pos = pos + (size_t)r->skips * 8; |
| 148 |
156 |
| return 1; |
| 149 |
|
| } |
| 150 |
|
| |
| 151 |
78558 |
| static int po_post_next(po_post_r *r, uint32_t *id) { |
| 152 |
78558 |
▶ | if (r->i >= r->n || r->pos >= r->len) return 0; |
Branch: 2 branches
| Branch | True | False | Total |
| if (r->i >= r->n || r->pos >= r->len) return 0; |
78452 |
106 |
78558 |
| if (r->i >= r->n || r->pos >= r->len) return 0; |
0 |
78452 |
78452 |
|
| 153 |
|
| { |
| 154 |
78452 |
| po_u64 v = po_getv(r->b, r->len, &r->pos); |
| 155 |
78452 |
▶ | if (r->i % PO_SKIP_EVERY == 0) r->prev = (uint32_t)v; |
Branch: 1 branch
| Branch | True | False | Total |
| if (r->i % PO_SKIP_EVERY == 0) r->prev = (uint32_t)v; |
703 |
77749 |
78452 |
|
| 156 |
77749 |
| else r->prev = r->prev + (uint32_t)v; |
| 157 |
|
| } |
| 158 |
78452 |
| *id = r->prev; |
| 159 |
78452 |
| r->i++; |
| 160 |
78452 |
| return 1; |
| 161 |
|
| } |
| 162 |
|
| |
| 163 |
|
| /* Seek to the first id >= target, using the skip table to avoid decoding |
| 164 |
|
| * every gap. This is what makes an intersection sublinear on the larger list. */ |
| 165 |
15302 |
| static int po_post_seek(po_post_r *r, uint32_t target, uint32_t *id) { |
| 166 |
|
| uint32_t s; |
| 167 |
44166 |
▶ | for (s = r->skips; s > 0; s--) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (s = r->skips; s > 0; s--) { |
44166 |
0 |
44166 |
|
| 168 |
|
| uint32_t sid, soff; |
| 169 |
44166 |
| memcpy(&sid, r->skip + (size_t)(s - 1) * 8, 4); sid = po_le32(sid); |
| 170 |
44166 |
| memcpy(&soff, r->skip + (size_t)(s - 1) * 8 + 4, 4); soff = po_le32(soff); |
| 171 |
44166 |
▶ | if (sid <= target) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (sid <= target) { |
15302 |
28864 |
44166 |
|
| 172 |
15302 |
| uint32_t block = s - 1; |
| 173 |
15302 |
▶ | if (block * PO_SKIP_EVERY >= r->i) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (block * PO_SKIP_EVERY >= r->i) { |
113 |
15189 |
15302 |
|
| 174 |
113 |
| r->i = block * PO_SKIP_EVERY; |
| 175 |
113 |
| r->pos = soff; |
| 176 |
|
| } |
| 177 |
15302 |
| break; |
| 178 |
|
| } |
| 179 |
|
| } |
| 180 |
30417 |
▶ | while (po_post_next(r, id)) if (*id >= target) return 1; |
Branch: 2 branches
| Branch | True | False | Total |
| while (po_post_next(r, id)) if (*id >= target) return 1; |
15265 |
15115 |
30380 |
| while (po_post_next(r, id)) if (*id >= target) return 1; |
30380 |
37 |
30417 |
|
| 181 |
37 |
| return 0; |
| 182 |
|
| } |
| 183 |
|
| |
| 184 |
|
| /* Intersect two encoded lists. SMALLEST FIRST is the caller's job and it is |
| 185 |
|
| * the difference between a merge and a scan. */ |
| 186 |
50 |
| static uint32_t po_post_intersect(const void *a, size_t alen, |
| 187 |
|
| const void *b, size_t blen, |
| 188 |
|
| uint32_t *out, uint32_t outmax) { |
| 189 |
|
| po_post_r ra, rb; |
| 190 |
50 |
| uint32_t ia, ib, n = 0; |
| 191 |
50 |
▶ | if (!po_post_open(&ra, a, alen) || !po_post_open(&rb, b, blen)) return 0; |
Branch: 2 branches
| Branch | True | False | Total |
| if (!po_post_open(&ra, a, alen) || !po_post_open(&rb, b, blen)) return 0; |
50 |
0 |
50 |
| if (!po_post_open(&ra, a, alen) || !po_post_open(&rb, b, blen)) return 0; |
0 |
50 |
50 |
|
| 192 |
50 |
▶ | if (!po_post_next(&ra, &ia)) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!po_post_next(&ra, &ia)) return 0; |
0 |
50 |
50 |
|
| 193 |
50 |
▶ | if (!po_post_next(&rb, &ib)) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!po_post_next(&rb, &ib)) return 0; |
50 |
0 |
50 |
|
| 194 |
|
| for (;;) { |
| 195 |
16920 |
▶ | if (ia == ib) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (ia == ib) { |
1618 |
15302 |
16920 |
|
| 196 |
1618 |
▶ | if (n < outmax) out[n] = ia; |
Branch: 1 branch
| Branch | True | False | Total |
| if (n < outmax) out[n] = ia; |
1618 |
0 |
1618 |
|
| 197 |
1618 |
| n++; |
| 198 |
1618 |
▶ | if (!po_post_next(&ra, &ia)) break; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!po_post_next(&ra, &ia)) break; |
6 |
1612 |
1618 |
|
| 199 |
1612 |
▶ | if (!po_post_next(&rb, &ib)) break; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!po_post_next(&rb, &ib)) break; |
7 |
1605 |
1612 |
|
| 200 |
|
| } |
| 201 |
15302 |
▶ | else if (ia < ib) { if (!po_post_seek(&ra, ib, &ia)) break; } |
Branch: 2 branches
| Branch | True | False | Total |
| else if (ia < ib) { if (!po_post_seek(&ra, ib, &ia)) break; } |
7804 |
7498 |
15302 |
| else if (ia < ib) { if (!po_post_seek(&ra, ib, &ia)) break; } |
18 |
7786 |
7804 |
|
| 202 |
7498 |
▶ | else { if (!po_post_seek(&rb, ia, &ib)) break; } |
Branch: 1 branch
| Branch | True | False | Total |
| else { if (!po_post_seek(&rb, ia, &ib)) break; } |
19 |
7479 |
7498 |
|
| 203 |
|
| } |
| 204 |
50 |
| return n; |
| 205 |
|
| } |
| 206 |
|
| |
| 207 |
|
| #endif /* PO_TSIDX_H */ |