Spatial join method and apparatus
AssigneeNCR Corporation
InventorsGang Luo, Curt J. Ellmann, Jeffrey F. Naughton
Life of this patent
Estimating the term…
Abstract
A non-blocking parallel spatial join algorithm generates the spatial join result tuples continuously even in the event of memory overflow. The algorithm employs duplicate avoidance techniques to avoid the blocking and time-consuming removal of duplicates. The algorithm also uses parallelism to improve performance.
Claims37
A method comprising:
- storing first tuples in a first table in a system;
- storing second tuples in a second table in the system;
- partitioning the first and second tuples into plural portions;
- wherein partitioning the first and second tuples comprises redistributing the first and second tuples among plural nodes of the system;
- performing a spatial join of the first and second tuples to create join result tuples based on the partitioned portions and using spatial attributes of the first and second tuples;
- and
- performing duplicate avoidance to avoid generating duplicate join result tuples;
- and
- wherein performing duplicate avoidance comprises identifying a pair of a first tuple and a second tuple that is replicated on plural nodes, and selecting one of the plural nodes to perform the spatial join of the pair of the first tuple and the second tuple, wherein the spatial join of the pair of the first tuple and second tuple is not performed on the plural nodes other than the selected node.
A system comprising:
- a processor;
- a storage;
- and
- instructions executable by the processor, for enabling the system to:
- store first tuples in a first table accessible by plural nodes in the system;
- store second tuples in a second table accessible by the plural nodes;
- redistribute the first and second tuples across the plural nodes;
- at each node, subdivide received redistributed tuples into plural buckets;
- and perform a spatial join operation between the first tuples and the second tuples based on the redistributing and subdividing and using spatial attributes of the first and second tuples;
- and
- wherein the instructions executable by the processor, further enable the system to:
- generate join result tuples from the spatial join:
- and perform duplicate avoidance to avoid generating duplicate join result tuples by:
- identifying a pair of a first tuple and a second tuple that is replicated on plural nodes;
- and
- selecting one of the plural nodes to perform the spatial join of the pair of the first tuple and the second tuple, wherein the spatial join of the pair of the first tuple and second tuple is not performed on the plural nodes other than the selected node.
An article comprising a medium storing instructions for enabling a processor-based, system that has non-persistent storage and persistent storage to:
- store first tuples in a first table in a system;
- store second tuples in a second table in the system;
- redistribute the first and second tuples across plural nodes of the system;
- and
- perform a spatial join of the redistributed first and second tuples using spatial attributes of the first and second tuples;
- wherein performing the spatial join comprises performing the spatial join in plural stages, the plural stages including at least a first stage in which the spatial join is performed on redistributed first and second tuples stored in non-persistent storage, and a second stage after the non-persistent storage has become full, wherein performing the spatial join in the second storage comprises performing the spatial join on first and second tuples stored in persistent storage;
- and
- wherein further storing instructions for enabling a processor-based system to:
- identifying a pair of a first tuple and a second tuple that is replicated on plural nodes;
- and
- selecting one of the plural nodes to perform the spatial join of the pair of the first tuple and the second tuple, wherein the spatial join of the pair of the first tuple and second tuple is not performed on the plural nodes other than the selected node.
A system comprising:
- a plurality of nodes;
- a storage containing first tuples and second tuples;
- and
- a controller adapted to partition the first and second tuples among the plurality of nodes, the controller adapted to further identify a pair of a first tuple and a second tuple that is replicated on multiple nodes, and to select one of the multiple nodes to perform a join of the pair of the first tuple and the second tuple;
- and
- wherein the controller is adapted to perform a spatial join of the pair of the first tuple and the second tuple using spatial attributes of the first and second tuples;
- and
- wherein the storage is divided into plural portions accessible by corresponding nodes.
An article comprising at least one storage medium containing instructions that, when executed, cause a system to:
- partition first tuples of a first table and second tuples of a second table among plural nodes of the system;
- during the partitioning, receive, in each node, first tuples into a first spatial index and second tuples into a second spatial index, the first and second spatial indices stored in a non persistent memory;
- perform a spatial join of the first and second tuples from the first and second spatial indices during the partitioning;
- determine that the non-persistent memory is overflowing;
- and in response to determining that the non-persistent memory is overflowing, perform a spatial join of first tuples not received in the first spatial index with second tuples from the second spatial index;
- and
- wherein the instructions, when executed, cause the system to further:
- identify a pair of a first tuple and a second tuple that is replicated on multiple nodes:
- and to select one of the multiple nodes to perform the spatial join of the pair of the first tuple and the second tuple, wherein the spatial join of the pair of the first tuple and second tuple is not performed on nodes other than the selected node.
Dependencies are inferred from the claim text.