Changeset: 4720c5def5d1 for MonetDB
URL: https://dev.monetdb.org/hg/MonetDB/rev/4720c5def5d1
Added Files:
gdk/gdk_rtree.c
gdk/gdk_rtree.h
Modified Files:
gdk/gdk.h
Branch: geo-update-dev
Log Message:
First version of rtree index (using librtree). BATrtree builds the index on a
geometry BAT and RTREEsearch searches for intersecting geometries to the input
mbr. Added variable in gdk.h that was not correctly set by the librtree.
diffs (180 lines):
diff --git a/gdk/gdk.h b/gdk/gdk.h
--- a/gdk/gdk.h
+++ b/gdk/gdk.h
@@ -351,6 +351,11 @@ gdk_export _Noreturn void GDKfatal(_In_z
#include "stream.h"
#include "mstring.h"
+#ifndef SIZEOF_RTREE_COORD_T
+#define SIZEOF_RTREE_COORD_T 4
+#endif
+#include <rtree.h>
+
#undef MIN
#undef MAX
#define MAX(A,B) ((A)<(B)?(B):(A))
@@ -740,6 +745,8 @@ typedef struct {
BUN baseoff; /* offset in heap->base (in whole items) */
Heap *vheap; /* space for the varsized data. */
Hash *hash; /* hash table */
+ rtree_t *rtree;
+
Imprints *imprints; /* column imprints index */
Heap *orderidx; /* order oid index */
Strimps *strimps; /* string imprint index */
diff --git a/gdk/gdk_rtree.c b/gdk/gdk_rtree.c
new file mode 100644
--- /dev/null
+++ b/gdk/gdk_rtree.c
@@ -0,0 +1,128 @@
+#include "monetdb_config.h"
+#include "gdk.h"
+#include "gdk_private.h"
+#include "gdk_rtree.h"
+
+//TODO The check for hasrtree should look into the parent BAT, not just
compare the BAT->rtree to NULL
+
+// Persist rtree to disk if the conditions are right
+/*static void
+persistRtree (BAT *b)
+{*/
+ /* Conditions to persist the RTree:
+ * - BAT has to be persistent
+ * - No deleted rows (when does batInserted update?)
+ * - The heap is not dirty -> no new values
+ * - DB Farm is persistent i.e. not in memory
+ */
+/* if ((BBP_status(b->batCacheid) & BBPEXISTING)
+ && b->batInserted == b->batCount
+ && !b->theap->dirty
+ && !GDKinmemory(b->theap->farmid)) {
+ BBPfix(b->batCacheid);
+ //char name[MT_NAME_LEN];
+ //snprintf(name, sizeof(name), "rtreesync%d", b->batCacheid);
+ }
+}*/
+
+//TODO Make this multi-thread safe? -> Only allow one thread to do rtree_new
and persist the BAT, but multiple threads can add new rects to the tree
+//MBR bat
+gdk_return
+BATrtree_wkb(BAT *wkb, BAT *mbr)
+{
+ BAT *pb;
+ BATiter bi;
+ rtree_t *rtree = NULL;
+ struct canditer ci;
+
+ //TODO check for MBR type
+
+ //Check for a parent BAT of wkb, load if exists
+ if (VIEWtparent(wkb)) {
+ pb = BBP_cache(VIEWtparent(wkb));
+ assert(pb);
+ } else {
+ pb = wkb;
+ }
+
+ //Check if rtree already exists
+ //TODO Check if it is on disk
+ if (pb->T.rtree == NULL) {
+ //If it doesn't exist, take the lock to create/get the rtree
+ MT_lock_set(&pb->batIdxLock);
+
+ //Try to load it from disk
+ //TODO BATcheckrtree
+
+ //First arg are dimensions: we only allow x, y
+ //Second arg are flags: split strategy and nodes-per-page
+ if ((rtree = rtree_new(2, RTREE_DEFAULT)) == NULL) {
+ GDKerror("rtree_new failed\n");
+ return GDK_FAIL;
+ }
+ bi = bat_iterator(mbr);
+ canditer_init(&ci, mbr,NULL);
+
+ for (BUN i = 0; i < ci.ncand; i++) {
+ oid p = canditer_next(&ci) - mbr->hseqbase;
+ mbr_t *inMBR = (mbr_t *)BUNtail(bi, p);
+
+ rtree_id_t rtree_id = i;
+ rtree_coord_t rect[4];
+ rect[0] = inMBR->xmin;
+ rect[1] = inMBR->ymin;
+ rect[2] = inMBR->xmax;
+ rect[3] = inMBR->ymax;
+ rtree_add_rect(rtree,rtree_id,rect);
+ }
+ bat_iterator_end(&bi);
+ pb->T.rtree = rtree;
+ //TODO persist rtree
+ MT_lock_unset(&pb->batIdxLock);
+ }
+ //TODO Check if the rtree is complete in case of already existing rtree
(not NULL)
+ return GDK_SUCCEED;
+}
+
+struct results_rtree {
+ int results_next;
+ int results_left;
+ BUN* candidates;
+};
+
+static int
+f (rtree_id_t id, void *context) {
+ struct results_rtree *results_rtree = (struct results_rtree *) context;
+ results_rtree->candidates[results_rtree->results_next++] = (BUN) id;
+ results_rtree->results_left -= 1;
+ return results_rtree->results_left <= 0;
+}
+
+BUN*
+RTREEsearch(BAT *b, mbr_t *inMBR, int result_limit) {
+ BAT *pb;
+ if (VIEWtparent(b)) {
+ pb = BBP_cache(VIEWtparent(b));
+ assert(pb);
+ } else {
+ pb = b;
+ }
+ rtree_t *rtree = pb->T.rtree;
+ if (rtree != NULL) {
+ BUN *candidates = GDKmalloc(result_limit*sizeof(BUN));
+ memset(candidates,BUN_NONE,result_limit*sizeof(BUN));
+
+ rtree_coord_t rect[4];
+ rect[0] = inMBR->xmin;
+ rect[1] = inMBR->ymin;
+ rect[2] = inMBR->xmax;
+ rect[3] = inMBR->ymax;
+ struct results_rtree results;
+ results.results_next = 0;
+ results.results_left = result_limit;
+ results.candidates = candidates;
+ rtree_search(rtree, (const rtree_coord_t*) rect, f, &results);
+ return candidates;
+ } else
+ return NULL;
+}
diff --git a/gdk/gdk_rtree.h b/gdk/gdk_rtree.h
new file mode 100644
--- /dev/null
+++ b/gdk/gdk_rtree.h
@@ -0,0 +1,18 @@
+#ifndef SIZEOF_RTREE_COORD_T
+#define SIZEOF_RTREE_COORD_T 4
+#endif
+#include <rtree.h>
+
+typedef struct mbr_t {
+ float xmin;
+ float ymin;
+ float xmax;
+ float ymax;
+
+} mbr_t;
+//TODO REMOVE
+
+gdk_export gdk_return BATrtree(BAT *b);
+gdk_export gdk_return BATrtree_wkb(BAT *wkb, BAT* mbr);
+gdk_export void RTREEdestroy(BAT *b);
+gdk_export BUN* RTREEsearch(BAT *b, mbr_t *inMBR, int result_limit);
_______________________________________________
checkin-list mailing list -- [email protected]
To unsubscribe send an email to [email protected]
