SP-GiST implementation of 4-dimensional quad-tree and kd-tree over temporal integers and temporal floats. More...

#include "pg_temporal/tnumber_spgist.h"
#include <assert.h>
#include <float.h>
#include <limits.h>
#include <postgres.h>
#include <access/spgist.h>
#include <utils/timestamp.h>
#include <meos.h>
#include <meos_internal.h>
#include "temporal/span.h"
#include "temporal/stratnum.h"
#include "temporal/tbox.h"
#include "temporal/tbox_index.h"
#include "temporal/type_util.h"
#include "cbuffer/cbuffer.h"
#include "pg_temporal/meos_catalog.h"
#include "pg_temporal/temporal.h"
#include "pg_temporal/tnumber_gist.h"

Data Structures
struct	SortedTbox
	Structure to sort the temporal boxes of an inner node. More...

struct	TboxNode
	Structure to represent the bounding box of an inner node containing a set of temporal boxes. More...

Typedefs
typedef struct SortedTbox	SortedTbox
	Structure to sort the temporal boxes of an inner node. More...

Functions
static bool	after4D (const TboxNode nodebox, const TBox query)
	Can any box from nodebox be after the query? More...

static bool	before4D (const TboxNode nodebox, const TBox query)
	Can any box from nodebox be before the query? More...

int	compareFloat8 (const void a, const void b)
	Comparator for qsort for double values. More...

int	compareInt4 (const void a, const void b)
	Comparator for qsort for integer values. More...

int	compareTimestampTz (const void a, const void b)
	Comparator for qsort for timestamp values. More...

static bool	contain4D (const TboxNode nodebox, const TBox query)
	Can any box from nodebox contain the query? More...

static double	distance_tbox_nodebox (const TBox query, const TboxNode nodebox)
	Return the lower bound for the distance between query and nodebox. More...

static uint8	getQuadrant4D (const TBox centroid, const TBox inBox)
	Calculate the quadrant. More...

static bool	left4D (const TboxNode nodebox, const TBox query)
	Can any box from nodebox be to the left of the query? More...

static bool	overAfter4D (const TboxNode nodebox, const TBox query)
	Can any box from nodebox be not before the query? More...

static bool	overBefore4D (const TboxNode nodebox, const TBox query)
	Can any box from nodebox be not after the query? More...

static bool	overlap4D (const TboxNode nodebox, const TBox query)
	Can any box from nodebox overlap with the query? More...

static bool	overLeft4D (const TboxNode nodebox, const TBox query)
	Can any box from nodebox does not extend to the right of this query? More...

static bool	overRight4D (const TboxNode nodebox, const TBox query)
	Can any box from nodebox does not extend to the left of the query? More...

static bool	right4D (const TboxNode nodebox, const TBox query)
	Can any box from nodebox be right of the query? More...

Datum	Tbox_kdtree_choose (PG_FUNCTION_ARGS)
	Determine which half a 4D-mapped temporal box falls into, relative to the centroid and the level number. More...

Datum	Tbox_kdtree_inner_consistent (PG_FUNCTION_ARGS)
	Kd-tree inner consistent function for temporal numbers. More...

Datum	Tbox_kdtree_picksplit (PG_FUNCTION_ARGS)
	K-d tree pick-split function for temporal number. More...

static int	tbox_level_cmp (TBox centroid, TBox query, int level)

Datum	Tbox_quadtree_choose (PG_FUNCTION_ARGS)
	SP-GiST choose function for temporal numbers. More...

Datum	Tbox_quadtree_inner_consistent (PG_FUNCTION_ARGS)
	Quad-tree inner consistent function for temporal numbers. More...

Datum	Tbox_quadtree_picksplit (PG_FUNCTION_ARGS)
	SP-GiST pick-split function for temporal numbers. More...

Datum	Tbox_spgist_config (PG_FUNCTION_ARGS)
	SP-GiST config function for temporal numbers. More...

static Datum	tbox_spgist_inner_consistent (FunctionCallInfo fcinfo, SPGistIndexType idxtype)
	Generic SP-GiST inner consistent function for temporal numbers. More...

Datum	Tbox_spgist_leaf_consistent (PG_FUNCTION_ARGS)
	SP-GiST leaf consistency function for temporal numbers. More...

static int	tbox_tmax_cmp (const TBox box1, const TBox box2)
	Comparator of temporal boxes based on their tmax value. More...

static int	tbox_tmin_cmp (const TBox box1, const TBox box2)
	Comparator of temporal boxes based on their tmin value. More...

static int	tbox_xmax_cmp (const TBox box1, const TBox box2)
	Comparator of temporal boxes based on their xmax value. More...

static int	tbox_xmin_cmp (const TBox box1, const TBox box2)
	Comparator of temporal boxes based on their xmin value. More...

TboxNode *	tboxnode_copy (const TboxNode *box)
	Copy a traversal value. More...

static void	tboxnode_init (TBox centroid, TboxNode nodebox)
	Initialize the traversal value. More...

static void	tboxnode_kdtree_next (const TboxNode nodebox, const TBox centroid, uint8 node, int level, TboxNode *next_nodebox)
	Compute the next traversal value for a k-d tree given the bounding box and the centroid of the current node, the half number (0 or 1) and the level. More...

static void	tboxnode_quadtree_next (const TboxNode nodebox, const TBox centroid, uint8 quadrant, TboxNode *next_nodebox)
	Calculate the next traversal value. More...

Datum	Tnumber_spgist_compress (PG_FUNCTION_ARGS)
	SP-GiST compress function for temporal numbers. More...

static bool	tnumber_spgist_get_tbox (const ScanKeyData scankey, TBox result)
	Transform a query argument into a temporal box. More...

Detailed Description

SP-GiST implementation of 4-dimensional quad-tree and kd-tree over temporal integers and temporal floats.

Note: These functions are based on those in the file `geo_spgist.c.

This module provides an SP-GiST implementation for temporal number types using a quad tree analogy in 4-dimensional space. Since SP-GiST does not allow indexing of overlapping objects, we transform 2D objects in a 4D space to make them not overlap. This technique has some benefits compared to traditional R-Tree which is implemented as GiST. The performance tests reveal that this technique especially beneficial with too much overlapping objects, so called "spaghetti data".

Unlike the original quadtree, we are splitting the tree into 16 quadrants in 4D space. It is easier to imagine it as splitting space two times into 4:

             |      |
             |      |
             | -----+-----
             |      | c2
             |      |
-------------+-------------
             | c1
             |
             |
             |
             |

where c1 and c2 are the centroids of the node and the child quadrant.

We use centroids represented as a temporal box as the prefix, but we treat them as points in 4-dimensional space. Notice that 2D boxes are not enough to represent the quadrant boundaries in 4D space. However, they are sufficient to point out the additional boundaries of the next quadrant.

We use node boxes (see below) composed by a left and a right temporal boxes as traversal values to calculate and to store the bounds of the quadrants while traversing the tree. A traversal value has all the boundaries in 4D space, and is is capable of transferring the required boundaries to the following traversal values. In conclusion, three things are necessary to calculate the next traversal value:

the traversal value of the parent
the quadrant of the current node
the prefix of the current node

If we visualize them on the above drawing, transferred boundaries of (1) would be the relevant part of the outer axis, (2) would be the up right part of the other axis, and (3) would be the inner axis.

For example, consider the case of overlapping. When recursion descends deeper and deeper down the tree, all quadrants in the current node will be checked for overlapping. The boundaries will be re-calculated for all quadrants. Overlap check answers the question: can any box from this quadrant overlap with the given box? If yes, then this quadrant will be walked. If no, then this quadrant will be skipped.

This method provides restrictions for minimum and maximum values of every dimension of every corner of the box on every level of the tree except the root. For the root node, we are setting the boundaries that we don't yet have as infinity.

Data Structures

Typedefs

Functions

Detailed Description