# US 2015/0178352 A1 · Parallelizable gridded geospatial join (pggj)

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2015/0178352 A1
- Document ID: US20150178352A1
- Status: Published application
- Kind: A1
- Application number: 14/579,697
- Filed: 2014-12-22
- Published: 2015-06-25
- Earliest claimed: 2013-12-23
- Assignees: Teradata US, Inc.
- Applicants: Teradata US, Inc.
- Inventors: Heng Yuan; Daniel Wong; Congnan Luo; Guilian Wang
- Web page: https://patentgrep.com/patent/US20150178352A1

## CPC

- G06F 16/2456: {Join operations}
- G06F 16/2246: {Trees, e.g. B+trees}
- G06F 16/29: Geographical information databases
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Statistics for a Relational Database Management System (RDBMS) set of tables are normalized and a grid computed. A particular grid cell having above threshold number of entries from the tables is determined and an R-Tree is dynamically constructed for that grid cell for use when performing a geospatial join operation against the tables.

## Claims

### Claim 1

A method, comprising:
normalizing statistics for a first table and a second table associated with a join operation;
generating a grid from the normalized statistics;
identifying a grid cell having more than a threshold number of entries from both the first table and the second table; and
dynamically constructing an R-tree for the grid cell to assist in performing the join operation.

### Claim 2 (depends on 1)

The method of claim 1, wherein normalizing further includes obtaining the statistics for the first table and the second table from a Relational Database Management System (RDBMS) that produced the statistics.

### Claim 3 (depends on 1)

The method of claim 1, wherein generating further includes providing a cost for processing the join operation and a cardinality of processing the join operation for each grid cell of the grid.

### Claim 4 (depends on 1)

The method of claim 1, wherein generating further includes producing the grid with at least some grid cells that overlap one another.

### Claim 5 (depends on 1)

The method of claim 1, wherein generating further includes producing the grid with uneven spacing between the grid cells.

### Claim 6 (depends on 1)

The method of claim 1, wherein generating further includes producing the grid with evenly spaced rectangular-shaped grid cells.

### Claim 7 (depends on 1)

The method of claim 1, wherein generating further includes providing an indication for the join operation to ensure uniqueness of rows following the processing of the join operation when some of the grid cells overlap within the grid.

### Claim 8 (depends on 1)

The method of claim 1, wherein generating further includes dividing the grid cells into groups of cells and sending at least one group to a distributed access module processor (AMP) across a network connection for processing that group when the join operation is processed, wherein the AMP processes in parallel with the method once receiving that group of cells.

### Claim 9 (depends on 1)

The method of claim 1, wherein identifying further includes associating a higher cost to the grid cell for processing the join operation based on the grid cell having more than the threshold number of entries.

### Claim 10 (depends on 1)

The method of claim 1, wherein dynamically constructing further includes selectively and dynamically constructing other R-Trees for some of the other grid cells based on a cardinality of the join operation or costs associated with those other grid cells, wherein a number of the grid cells for the grid lack a grid-specific R-Tree.

### Claim 11

A method, comprising:
dividing a grid representing normalized statistics for a first table and a second table into groups of grid cells;
distributing the groups to Access Module Processors (AMPs) across a distributed Relational Database Management System (RDBMS) over a network, each AMP having a different group or set of groups from remaining AMPs; and
processing each AMP in parallel to process a geospatial join operation over the network, wherein each AMP selectively, dynamically, and independently decides whether certain grid cells for that AMP's group of grid cells necessitates dynamic construction of grid cell-specific R-Trees to assist when processing the geospatial join operation.

### Claim 12 (depends on 11)

The method of claim 11, wherein dividing further includes obtaining statistics for the first table and the second table from the RDBMS.

### Claim 13 (depends on 12)

The method of claim 12, wherein obtaining further includes producing the normalized statistics from the statistics.

### Claim 14 (depends on 13)

The method of claim 13, wherein producing further includes computing the grid from the normalized statistics.

### Claim 15 (depends on 14)

The method of claim 14, wherein computing further includes producing the grid cells so that at least two grid cells overlap one another.

### Claim 16 (depends on 14)

The method of claim 14, wherein computing further includes producing the grid cells so that the grid cells are unevenly spaced.

### Claim 17 (depends on 14)

The method of claim 14, wherein computing further includes producing the grid cells so that the grid cells are evenly spaced in a regular geometric shape.

### Claim 18

A system, comprising:
a processor; and
a geospatial join manager configured to: i) execute on the processor, ii) compute a grid for normalized statistics associated with a first table and a second table associated with a geospatial join operation of a Relational Database Management System (RDBMS), and iii) selectively constructing a grid cell-specific R-Tree for selective grid cells of the grid to assist when processing the geospatial join from the grid.

### Claim 19 (depends on 18)

The system of claim 18, wherein the geospatial join manager is further configured to: iv) assign a cost and a cardinality of the geospatial join operation associated with each grid cell of the grid.

### Claim 20 (depends on 19)

The method of claim 19, wherein a particular grid cell having a highest cost in view of remaining grid cells for the grid has a grid cell-specific R-Tree constructed by the geospatial join manager.
