1 /*
2 * This file and its contents are licensed under the Apache License 2.0.
3 * Please see the included NOTICE for copyright information and
4 * LICENSE-APACHE for a copy of the license.
5 */
6 #include <postgres.h>
7 #include <utils/memutils.h>
8
9 #include "dimension.h"
10 #include "dimension_slice.h"
11 #include "dimension_vector.h"
12 #include "hypercube.h"
13 #include "subspace_store.h"
14
15 /*
16 * In terms of datastructures, the subspace store is actually a tree. At the
17 * root of a tree is a DimensionVec representing the different DimensionSlices
18 * for the first dimension. Each of the DimensionSlices of the
19 * first dimension point to a DimensionVec of the second dimension. This recurses
20 * for the N dimensions. The leaf DimensionSlice points to the data being stored.
21 *
22 * */
23
24 typedef struct SubspaceStoreInternalNode
25 {
26 DimensionVec *vector;
27 size_t descendants;
28 bool last_internal_node;
29 } SubspaceStoreInternalNode;
30
31 typedef struct SubspaceStore
32 {
33 MemoryContext mcxt;
34 int16 num_dimensions;
35 /* limit growth of store by limiting number of slices in first dimension, 0 for no limit */
36 int16 max_items;
37 SubspaceStoreInternalNode *origin; /* origin of the tree */
38 } SubspaceStore;
39
40 static inline SubspaceStoreInternalNode *
subspace_store_internal_node_create(bool last_internal_node)41 subspace_store_internal_node_create(bool last_internal_node)
42 {
43 SubspaceStoreInternalNode *node = palloc(sizeof(SubspaceStoreInternalNode));
44
45 node->vector = ts_dimension_vec_create(DIMENSION_VEC_DEFAULT_SIZE);
46 node->descendants = 0;
47 node->last_internal_node = last_internal_node;
48 return node;
49 }
50
51 static inline void
subspace_store_internal_node_free(void * node)52 subspace_store_internal_node_free(void *node)
53 {
54 ts_dimension_vec_free(((SubspaceStoreInternalNode *) node)->vector);
55 pfree(node);
56 }
57
58 static size_t
subspace_store_internal_node_descendants(SubspaceStoreInternalNode * node,int index)59 subspace_store_internal_node_descendants(SubspaceStoreInternalNode *node, int index)
60 {
61 const DimensionSlice *slice = ts_dimension_vec_get(node->vector, index);
62
63 if (slice == NULL)
64 return 0;
65
66 if (node->last_internal_node)
67 return 1;
68
69 return ((SubspaceStoreInternalNode *) slice->storage)->descendants;
70 }
71
72 SubspaceStore *
ts_subspace_store_init(const Hyperspace * space,MemoryContext mcxt,int16 max_items)73 ts_subspace_store_init(const Hyperspace *space, MemoryContext mcxt, int16 max_items)
74 {
75 MemoryContext old = MemoryContextSwitchTo(mcxt);
76 SubspaceStore *sst = palloc(sizeof(SubspaceStore));
77
78 /*
79 * make sure that the first dimension is a time dimension, otherwise the
80 * tree will grow in a way that makes pruning less effective.
81 */
82 Assert(space->num_dimensions < 1 || space->dimensions[0].type == DIMENSION_TYPE_OPEN);
83
84 sst->origin = subspace_store_internal_node_create(space->num_dimensions == 1);
85 sst->num_dimensions = space->num_dimensions;
86 /* max_items = 0 is treated as unlimited */
87 sst->max_items = max_items;
88 sst->mcxt = mcxt;
89 MemoryContextSwitchTo(old);
90 return sst;
91 }
92
93 void
ts_subspace_store_add(SubspaceStore * store,const Hypercube * hc,void * object,void (* object_free)(void *))94 ts_subspace_store_add(SubspaceStore *store, const Hypercube *hc, void *object,
95 void (*object_free)(void *))
96 {
97 SubspaceStoreInternalNode *node = store->origin;
98 DimensionSlice *last = NULL;
99 MemoryContext old = MemoryContextSwitchTo(store->mcxt);
100 int i;
101
102 Assert(hc->num_slices == store->num_dimensions);
103
104 for (i = 0; i < hc->num_slices; i++)
105 {
106 const DimensionSlice *target = hc->slices[i];
107 DimensionSlice *match;
108
109 Assert(target->storage == NULL);
110
111 if (node == NULL)
112 {
113 /*
114 * We should have one internal node per dimension in the
115 * hypertable. If we don't have one for the current dimension,
116 * create one now. (There will always be one for time)
117 */
118 Assert(last != NULL);
119 last->storage = subspace_store_internal_node_create(i == (hc->num_slices - 1));
120 last->storage_free = subspace_store_internal_node_free;
121 node = last->storage;
122 }
123
124 Assert(store->max_items == 0 || node->descendants <= (size_t) store->max_items);
125
126 /*
127 * We only call this function on a cache miss, so number of leaves
128 * will definitely increase see `Assert(last != NULL && last->storage
129 * == NULL);` at bottom.
130 */
131 node->descendants += 1;
132
133 Assert(0 == node->vector->num_slices ||
134 node->vector->slices[0]->fd.dimension_id == target->fd.dimension_id);
135
136 /* Do we have enough space to store the object? */
137 if (store->max_items > 0 && node->descendants > store->max_items)
138 {
139 /*
140 * Always delete the slice corresponding to the earliest time
141 * range. In the normal case that inserts are performed in
142 * time-order this is the one least likely to be reused. (Note
143 * that we made sure that the first dimension is a time dimension
144 * when creating the subspace_store). If out-of-order inserts are
145 * become significant we may wish to change this to something more
146 * sophisticated like LRU.
147 */
148 size_t items_removed = subspace_store_internal_node_descendants(node, i);
149
150 /*
151 * descendants at the root is inclusive of the descendants at the
152 * children, so if we have an overflow it must be in the time dim
153 */
154 Assert(i == 0);
155
156 Assert(store->max_items + 1 == node->descendants);
157
158 ts_dimension_vec_remove_slice(&node->vector, i);
159
160 /*
161 * Note we would have to do this to ancestors if this was not the
162 * root.
163 */
164 node->descendants -= items_removed;
165 }
166
167 match = ts_dimension_vec_find_slice(node->vector, target->fd.range_start);
168
169 /* Do we have a slot in this vector for the new object? */
170 if (match == NULL)
171 {
172 DimensionSlice *copy;
173
174 /*
175 * create a new copy of the range this slice covers, to store the
176 * object in
177 */
178 copy = ts_dimension_slice_copy(target);
179
180 ts_dimension_vec_add_slice_sort(&node->vector, copy);
181 match = copy;
182 }
183
184 Assert(store->max_items == 0 || node->descendants <= (size_t) store->max_items);
185
186 last = match;
187 /* internal slices point to the next SubspaceStoreInternalNode */
188 node = last->storage;
189 }
190
191 Assert(last != NULL && last->storage == NULL);
192 last->storage = object; /* at the end we store the object */
193 last->storage_free = object_free;
194 MemoryContextSwitchTo(old);
195 }
196
197 void *
ts_subspace_store_get(const SubspaceStore * store,const Point * target)198 ts_subspace_store_get(const SubspaceStore *store, const Point *target)
199 {
200 int i;
201 DimensionVec *vec = store->origin->vector;
202 DimensionSlice *match = NULL;
203
204 Assert(target->cardinality == store->num_dimensions);
205
206 for (i = 0; i < target->cardinality; i++)
207 {
208 match = ts_dimension_vec_find_slice(vec, target->coordinates[i]);
209
210 if (NULL == match)
211 return NULL;
212
213 vec = ((SubspaceStoreInternalNode *) match->storage)->vector;
214 }
215 Assert(match != NULL);
216 return match->storage;
217 }
218
219 void
ts_subspace_store_free(SubspaceStore * store)220 ts_subspace_store_free(SubspaceStore *store)
221 {
222 subspace_store_internal_node_free(store->origin);
223 pfree(store);
224 }
225
226 MemoryContext
ts_subspace_store_mcxt(const SubspaceStore * store)227 ts_subspace_store_mcxt(const SubspaceStore *store)
228 {
229 return store->mcxt;
230 }
231