[Issue #405] RTree in memory index#563
Merged
mschoema merged 22 commits intoMobilityDB:masterfrom Aug 25, 2024
Merged
Conversation
There are two important structures. RTreeNode and RTree. There are 4 basic functions to interact with this structures: create and rtree, insert something to it, query and rtree and free the memory of an rtree.
We include a basic structure for the Rtree which is working for STBoxes. It allows to insert one by one. Queries are done with an STBox. A function to find each value as a double is required to be passed down to the RTree itself.
Since there is no tests for C code and only for sql code, this example is in some way also a test. It shows how you would normally use the Rtree, inserting and querying.
The largest axis was always choosing to split via the first element. Now it changes. Some thought should be done for the temporal axis since it is normally in a different scale. Maybe a mahalanobis distance would be better.
meos.h should only have information that the user would use. RTreeNode is no an structure that a user would use. Thus, is better to have it in tpoint_rtree.h and have a forward definition in meos.h for RTree node.
Keeping it consistent with the rest of the codebase
RtreeNode will allocate only once and there will be no need to allocate when inserting since it copying to an already allocated block of memory.
I have assumed meostype as an int since I meostype is defined in meos_catalog and I can't import it from meos.h, thus int was best option I had.
It was ambiguous that both #defines were related so they were refactored as RTREE_INNER_NODE and RTREE_INNER_NODE_NO
Adds missing documentation to newly add functions
To answer the query of rtree_search it is necessary to realloc memory, thus the code can become a little obscure. Added one extra function and some comments to make life easier for maintenance.
Included some time taking sinceit is important to know the difference between bruteforce and RTree search.
Matematikoi
commented
Aug 21, 2024
mschoema
requested changes
Aug 21, 2024
Change it so that when finding the minimum enclosing STBox there is no need to allocate new memory.
Use a simple STBox instead of a palloc.
mschoema
approved these changes
Aug 25, 2024
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Implementation of an RTree in memory index to solve issue 405.
The original code has been taken from Josh Baker rtree implementation and strip down to a more simple RTree.
This first version is only working with intersection but future versions should be able to work with any supported function that is already implemented for GIST.
The basic unit of inserting and querying is an STBox although the code has been done in a way that it allows an easy transition to other structures likes spans or boxes.
When querying the RTree returns an ID that identifies the STBox that was inserted.