Line data Source code
1 : /*
2 : * SPDX-License-Identifier: MPL-2.0
3 : *
4 : * This Source Code Form is subject to the terms of the Mozilla Public
5 : * License, v. 2.0. If a copy of the MPL was not distributed with this
6 : * file, You can obtain one at http://mozilla.org/MPL/2.0/.
7 : *
8 : * Copyright 2024 MonetDB Foundation;
9 : * Copyright August 2008 - 2023 MonetDB B.V.;
10 : * Copyright 1997 - July 2008 CWI.
11 : */
12 :
13 : #include "monetdb_config.h"
14 : #include "gdk.h"
15 : #include "gdk_private.h"
16 :
17 : //TODO Check if we need to input RTREEdestroy into drop_index func in sql_cat.c
18 : //TODO Should you check if the parent BAT is null?
19 :
20 : //TODO Re-check the conditions
21 : /* Conditions to persist the RTree:
22 : * - BAT has to be persistent
23 : * - No deleted rows (when does batInserted update?)
24 : * - The heap is not dirty -> no new values
25 : * - DB Farm is persistent i.e. not in memory
26 : */
27 : #ifdef HAVE_RTREE
28 : static bool
29 : RTREEpersistcheck (BAT *b) {
30 : return ((BBP_status(b->batCacheid) & BBPEXISTING)
31 : && b->batInserted == b->batCount
32 : && !b->theap->dirty
33 : && !GDKinmemory(b->theap->farmid));
34 : }
35 :
36 : void
37 : RTREEdecref(BAT *b)
38 : {
39 : ATOMIC_BASE_TYPE refs = ATOMIC_DEC(&b->trtree->refs);
40 : //If RTree is marked for destruction and there are no refs, destroy the RTree
41 : if (b->trtree->destroy && refs == 0) {
42 : ATOMIC_DESTROY(&b->trtree->refs);
43 : rtree_destroy(b->trtree->rtree);
44 : b->trtree->rtree = NULL;
45 : GDKfree(b->trtree);
46 : b->trtree = NULL;
47 : }
48 :
49 : }
50 :
51 : void
52 : RTREEincref(BAT *b)
53 : {
54 : (void) ATOMIC_INC(&b->trtree->refs);
55 : }
56 :
57 : // Persist rtree to disk if the conditions are right
58 : static gdk_return
59 : persistRtree (BAT *b)
60 : {
61 : if (RTREEpersistcheck(b)) {
62 : //TODO Necessary?
63 : BBPfix(b->batCacheid);
64 : rtree_t *rtree = b->trtree->rtree;
65 :
66 : if (rtree) {
67 : const char * filename = BBP_physical(b->batCacheid);
68 : int farmid = b->theap->farmid;
69 :
70 : int fd = GDKfdlocate(farmid, filename, "w", "bsrt");
71 : FILE *file_stream = fdopen(fd,"w");
72 :
73 : if (file_stream != NULL) {
74 : int err;
75 : if ((err = rtree_bsrt_write(rtree,file_stream)) != 0) {
76 : GDKerror("%s", rtree_strerror(err));
77 : fclose(file_stream);
78 : BBPunfix(b->batCacheid);
79 : return GDK_FAIL;
80 : }
81 :
82 : if (!(GDKdebug & NOSYNCMASK)) {
83 : #if defined(NATIVE_WIN32)
84 : _commit(fd);
85 : #elif defined(HAVE_FDATASYNC)
86 : fdatasync(fd);
87 : #elif defined(HAVE_FSYNC)
88 : fsync(fd);
89 : #endif
90 : }
91 : fclose(file_stream);
92 : }
93 : else {
94 : GDKerror("%s",strerror(errno));
95 : close(fd);
96 : return GDK_FAIL;
97 : }
98 : }
99 : BBPunfix(b->batCacheid);
100 : }
101 : //TODO Should we just return sucess if the rtree is not persisted?
102 : return GDK_SUCCEED;
103 : }
104 :
105 : static gdk_return
106 : BATcheckrtree(BAT *b) {
107 : const char * filename = BBP_physical(b->batCacheid);
108 : int farmid = b->theap->farmid;
109 : int fd = GDKfdlocate(farmid, filename, "r", "bsrt");
110 :
111 : //Do we have the rtree on file?
112 : if (fd == -1)
113 : return GDK_SUCCEED;
114 :
115 : FILE *file_stream = fdopen(fd,"r");
116 : if (file_stream != NULL) {
117 : rtree_t* rtree = rtree_bsrt_read(file_stream);
118 : if (!rtree) {
119 : GDKerror("%s", errno != 0 ? strerror(errno) : "Failed rtree_bsrt_read");
120 : fclose(file_stream);
121 : return GDK_FAIL;
122 : }
123 : b->trtree = GDKmalloc(sizeof(struct RTree));
124 : b->trtree->rtree = rtree;
125 : b->trtree->destroy = false;
126 : ATOMIC_INIT(&b->trtree->refs, 1);
127 : fclose(file_stream);
128 : return GDK_SUCCEED;
129 : }
130 : else {
131 : GDKerror("%s",strerror(errno));
132 : close(fd);
133 : return GDK_FAIL;
134 : }
135 : }
136 :
137 : //Check if RTree exists on file (previously created index)
138 : static bool
139 : RTREEexistsonfile(BAT *b) {
140 : const char * filename = BBP_physical(b->batCacheid);
141 :
142 : if (!b->theap) return false;
143 :
144 : int farmid = b->theap->farmid;
145 : int fd = GDKfdlocate(farmid, filename, "r", "bsrt");
146 :
147 : //Do we have the rtree on file?
148 : if (fd == -1) {
149 : return false;
150 : } else {
151 : close(fd);
152 : return true;
153 : }
154 : }
155 :
156 : //Check if RTree exists
157 : //We also check if it exists on file. If the index is not loaded, it will be
158 : //TODO Check for destroy -> it does not exist if destroy
159 : bool
160 : RTREEexists(BAT *b)
161 : {
162 : BAT *pb;
163 : bool ret;
164 : if (VIEWtparent(b)) {
165 : pb = BBP_cache(VIEWtparent(b));
166 : assert(pb);
167 : } else {
168 : pb = b;
169 : }
170 :
171 : MT_lock_set(&pb->batIdxLock);
172 : ret = (pb->trtree != NULL || RTREEexistsonfile(pb));
173 : MT_lock_unset(&pb->batIdxLock);
174 :
175 : return ret;
176 :
177 : }
178 :
179 : bool
180 : RTREEexists_bid(bat *bid)
181 : {
182 : BAT *b;
183 : bool ret;
184 : if ((b = BATdescriptor(*bid)) == NULL)
185 : return false;
186 : ret = RTREEexists(b);
187 : BBPunfix(b->batCacheid);
188 : return ret;
189 : }
190 :
191 : gdk_return
192 : BATrtree(BAT *wkb, BAT *mbr)
193 : {
194 : BAT *pb;
195 : BATiter bi;
196 : rtree_t *rtree = NULL;
197 : struct canditer ci;
198 :
199 : //Check for a parent BAT of wkb, load if exists
200 : if (VIEWtparent(wkb)) {
201 : pb = BBP_cache(VIEWtparent(wkb));
202 : assert(pb);
203 : } else {
204 : pb = wkb;
205 : }
206 :
207 : //Check if rtree already exists
208 : if (pb->trtree == NULL) {
209 : //If it doesn't exist, take the lock to create/get the rtree
210 : MT_lock_set(&pb->batIdxLock);
211 :
212 : //Try to load it from disk
213 : if (BATcheckrtree(pb) == GDK_SUCCEED && pb->trtree != NULL) {
214 : MT_lock_unset(&pb->batIdxLock);
215 : return GDK_SUCCEED;
216 : }
217 :
218 : //First arg are dimensions: we only allow x, y
219 : //Second arg are flags: split strategy and nodes-per-page
220 : if ((rtree = rtree_new(2, RTREE_DEFAULT)) == NULL) {
221 : GDKerror("rtree_new failed\n");
222 : return GDK_FAIL;
223 : }
224 : bi = bat_iterator(mbr);
225 : canditer_init(&ci, mbr,NULL);
226 :
227 : for (BUN i = 0; i < ci.ncand; i++) {
228 : oid p = canditer_next(&ci) - mbr->hseqbase;
229 : mbr_t *inMBR = (mbr_t *)BUNtail(bi, p);
230 :
231 : rtree_id_t rtree_id = i;
232 : rtree_coord_t rect[4];
233 : rect[0] = inMBR->xmin;
234 : rect[1] = inMBR->ymin;
235 : rect[2] = inMBR->xmax;
236 : rect[3] = inMBR->ymax;
237 : rtree_add_rect(rtree,rtree_id,rect);
238 : }
239 : bat_iterator_end(&bi);
240 : pb->trtree = GDKmalloc(sizeof(struct RTree));
241 : pb->trtree->rtree = rtree;
242 : pb->trtree->destroy = false;
243 : ATOMIC_INIT(&pb->trtree->refs, 1);
244 : persistRtree(pb);
245 : MT_lock_unset(&pb->batIdxLock);
246 : }
247 : //TODO What do we do when the conditions are not right for creating the index?
248 : return GDK_SUCCEED;
249 : }
250 :
251 : //Free the RTree from memory,
252 : void
253 : RTREEfree(BAT *b)
254 : {
255 : BAT *pb;
256 : if (VIEWtparent(b)) {
257 : pb = BBP_cache(VIEWtparent(b));
258 : assert(pb);
259 : } else {
260 : pb = b;
261 : }
262 :
263 : if (pb && pb->trtree) {
264 : MT_lock_set(&pb->batIdxLock);
265 : //Mark the RTree for destruction
266 : pb->trtree->destroy = true;
267 : RTREEdecref(pb);
268 : MT_lock_unset(&b->batIdxLock);
269 : }
270 : }
271 :
272 : //Free the RTree from memory, unlink the file associated with it
273 : void
274 : RTREEdestroy(BAT *b)
275 : {
276 : BAT *pb;
277 : if (VIEWtparent(b)) {
278 : pb = BBP_cache(VIEWtparent(b));
279 : assert(pb);
280 : } else {
281 : pb = b;
282 : }
283 :
284 : MT_lock_set(&pb->batIdxLock);
285 : if (pb->trtree) {
286 : //Mark the RTree for destruction
287 : pb->trtree->destroy = true;
288 : RTREEdecref(pb);
289 : //If the farm is in-memory, don't unlink the file (there is no file in that case)
290 : if (pb->theap && !GDKinmemory(pb->theap->farmid)) {
291 : GDKunlink(pb->theap->farmid,
292 : BATDIR,
293 : BBP_physical(b->batCacheid),
294 : "bsrt");
295 : }
296 : }
297 : //If the rtree is not loaded (pb->trtree is null), but there is a file with the index (from previous execution),
298 : //we should remove the file
299 : else if (RTREEexistsonfile(pb)) {
300 : GDKunlink(pb->theap->farmid,
301 : BATDIR,
302 : BBP_physical(b->batCacheid),
303 : "bsrt");
304 : }
305 : MT_lock_unset(&b->batIdxLock);
306 : }
307 :
308 : struct results_rtree {
309 : int results_next;
310 : int results_left;
311 : BUN* candidates;
312 : };
313 :
314 : static int
315 : f (rtree_id_t id, void *context) {
316 : struct results_rtree *results_rtree = (struct results_rtree *) context;
317 : results_rtree->candidates[results_rtree->results_next++] = (BUN) id;
318 : --results_rtree->results_left;
319 : return results_rtree->results_left <= 0;
320 : }
321 :
322 : BUN*
323 : RTREEsearch(BAT *b, mbr_t *inMBR, int result_limit) {
324 : BAT *pb;
325 : if (VIEWtparent(b)) {
326 : pb = BBP_cache(VIEWtparent(b));
327 : assert(pb);
328 : } else {
329 : pb = b;
330 : }
331 :
332 : //Try to load if there is an RTree index on file
333 : MT_lock_set(&pb->batIdxLock);
334 : if (pb->trtree == NULL) {
335 : if (BATcheckrtree(pb) != GDK_SUCCEED) {
336 : MT_lock_unset(&pb->batIdxLock);
337 : return NULL;
338 : }
339 : }
340 : MT_lock_unset(&pb->batIdxLock);
341 :
342 : rtree_t *rtree = pb->trtree->rtree;
343 : if (rtree != NULL) {
344 : //Increase ref, we're gonna use the index
345 : RTREEincref(pb);
346 : BUN *candidates = GDKmalloc((result_limit + 1) * SIZEOF_BUN);
347 : memset(candidates, 0, (result_limit + 1) * SIZEOF_BUN);
348 :
349 : rtree_coord_t rect[4];
350 : rect[0] = inMBR->xmin;
351 : rect[1] = inMBR->ymin;
352 : rect[2] = inMBR->xmax;
353 : rect[3] = inMBR->ymax;
354 :
355 : struct results_rtree results;
356 : results.results_next = 0;
357 : results.results_left = result_limit;
358 : results.candidates = candidates;
359 :
360 : rtree_search(rtree, (const rtree_coord_t*) rect, f, &results);
361 : candidates[result_limit - results.results_left] = BUN_NONE;
362 :
363 : //Finished using the index, decrease ref
364 : RTREEdecref(pb);
365 :
366 : return candidates;
367 : } else
368 : return NULL;
369 : }
370 : #else
371 : void
372 80728221 : RTREEdestroy(BAT *b) {
373 80728221 : (void) b;
374 80728221 : }
375 :
376 : void
377 450631 : RTREEfree(BAT *b) {
378 450631 : (void) b;
379 450631 : }
380 : #endif
|
