www.espertech.comDocumentation

Chapter 13. EPL Reference: Spatial Methods and Indexes

13.1. Overview
13.2. Spatial Methods
13.2.1. Point-Inside-Rectangle
13.2.2. Rectangle-Intersects-Rectangle
13.3. Spatial Index - Quadtree
13.3.1. Overview
13.3.2. Declaring a Point-Region Quadtree Index
13.3.3. Using a Point-Region Quadtree as a Filter Index
13.3.4. Using a Point-Region Quadtree as an Event Index
13.3.5. Declaring a MX-CIF Quadtree Index
13.3.6. Using a MX-CIF Quadtree as a Filter Index
13.3.7. Using a MX-CIF Quadtree as an Event Index
13.4. Spatial Types, Functions and Methods from External Libraries

EPL provides spatial methods and spatial indexes.

The engine analyzes filter criteria and the where-clause and considers spatial methods, utilizing spatial filter indexes or spatial event indexes for efficient matching and lookup.

For general information on the dot-operator please consult Section 9.6, “Dot Operator”.

The below table summarizes the built-in spatial methods available:


The method compares a rectangle to a rectangle and returns true if the rectangles intersect.

The method takes a rectangle as input and a rectangle as a parameter:

rectangle(rect_x, rect_y, rect_width, rect_height [, filterindex:configexpression]).intersects(rectangle(other_x, other_y, other_width, other_height))

The left-hand side is the rectangle's rect_x, rects_y, rect_width and rect_height expressions that return the (x, y)-coordinates and the size of the rectangle. The filterindex named parameter is for use with filter indexes as described below. The left-hand side rectangle can be subject to MX-CIF quadtree indexing (point-region quadtrees do not apply).

For the compared-to rectangle on the right-hand side, the other_x, other_y, other_width and other_height expressions return the (x, y)-coordinates and size of the compared-to rectangle.

All expressions must return a number-type and the implementation compares the double-values returned by the expressions.

A rectangle is considered to intersect another rectangle if:


A quadtree is a tree data structure in which each branch node has exactly four children. Quadtrees are often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions (source:WikiPedia).

Quadtree indexes can be used for:

The point-region quadtree is a quadtree for the efficient finding of points that fall inside a given rectangle. Use this index with the point-inside-rectangle method described above.

The MX-CIF quadtree is a quadtree for the efficient finding of rectangles that intersect with a given rectangle. Use this index with the rectangle-intersects-rectangle method described above.

While point-region quadtree and MX-CIF quadtree are similar, they are not compatible and are not the same. In point-region quadtree, only leaf nodes have data. In MX-CIF quadtrees both branch and leaf nodes have data as branches hold rectangles that don't fit any given quadrant. The engine expands and shrinks both types of trees dynamically based on data by promoting or subdividing a leaf node to branch nodes when adding data and by demoting or merging branches to a leaf node when removing data.

The section that summarizes filter indexes is Section 3.9.2, “Filter Indexes”. As there could be many point(...).inside(rectangle) filters active, having a filter index allows the engine to efficiently match incoming events to EPL statements.

For use of a point-region quadtree index within filter criteria you must:

  • Define an expression that returns the point-region quadtree configuration, making sure it specifies pointregionquadtree.

  • Add the filterindex named parameter providing the expression name.

For defining a local or global expression, please consult Section 5.2.9, “Expression Declaration”.

This sample EPL query defines the point-region quadtree filter index to have a bounding box of (0,0,100,100):

expression myPointRegionQuadtreeSettings { pointregionquadtree(0, 0, 100, 100) } 
select * from RectangleEvent(point(0, 0, filterindex:myPointRegionQuadtreeSettings).inside(rectangle(x, y, width, height)))

The filterindex named parameter instructs the engine that the settings for the point-region quadtree filter index are provided by the expression myPointRegionQuadtreeSettings, a local expression in this example. For sharing point-region quadtree settings across statements you may use a global expression instead. Please see Section 5.18, “Declaring Global Expressions, Aliases And Scripts: Create Expression”.

If your EPL does not specify filterindex the engine does not build a point-region quadtree filter index.

If your EPL specifies filterindex the engine always builds and uses a point-region quadtree filter index. In the case the engine analyses filter criteria and determines that it cannot use the point-region quadtree filter index, the engine fails statement validation.

If your EPL specifies filterindex and the engine determines that it cannot use the point-region quadtree filter index it fails statement validation.

The engine shares point-region quadtree filter indexes across the engine within the same event type given that:

  1. Filters have the same rectangle expressions.

  2. Filters use the same filterindex parameter i.e. the text myPointRegionQuadtreeSettings in above example.

  3. Filters use the same point-region quadtree index configuration i.e. pointregionquadtree(0,0,100,100) in above example.

For use with the filterindex named parameter, the following requirements apply towards point expressions:

  1. Point expressions must be a constant, a context-provided built-in property or an event property provided by a previous pattern match within the same pattern.

For use with the filterindex named parameter, the following requirements apply towards rectangle expressions:

  1. Rectangle expressions must be event properties.

The section that summarizes event indexes is Section 3.9.3, “Event Indexes”. The create index clause is described in Section 6.9, “Explicitly Indexing Named Windows and Tables”.

Declare a point-region quadtree event index as follows:

create index ... on ... (
  (x_expression, y_expression) pointregionquadtree(pointregion_quadtree_configuration)
)

The x_expression and y_expression expressions form the index columns. The expressions return the (x, y)-coordinates and must return numeric values. Coordinates are represented as double-type values internally. See above for the pointregion_quadtree_configuration point-region quadtree configuration.

For example, assume we have a table that contains points:

create table PointTable(pointId string primary key, px double, py double)

This example EPL declares an index on the points, with px and py becoming index columns that determine (x, y)-coordinates:

create index PointIndex on PointTable((px, py) pointregionquadtree(0, 0, 100, 100))

The above sample quadtree index expects (x, y)-coordinates that are in the range 0 <= px <= 100 and 0 <= py <= 100.

The example schema for events providing rectangles is:

create schema RectangleEvent(rx double, ry double, w double, h double)

This EPL outputs, upon arrival of a RectangleEvent, all points that fall inside the rectangle:

on RectangleEvent
select pointId from PointTable
where point(px, py).inside(rectangle(rx, ry, w, h))

Internally the engine does not instantiate point or rectangle objects at all but instead optimizes the expression to comparison between double-type values.

The section that summarizes filter indexes is Section 3.9.2, “Filter Indexes”. As there could be many rectangle(...).intersects(rectangle) filters active, having a filter index allows the engine to efficiently match incoming events to EPL statements.

For use of a MX-CIF quadtree index within filter criteria you must:

  • Define an expression that returns the MX-CIF quadtree configuration, making sure it specifies mxcifquadtree.

  • Add the filterindex named parameter providing the expression name.

For defining a local or global expression, please consult Section 5.2.9, “Expression Declaration”.

This sample EPL query defines the MX-CIF quadtree filter index to have a bounding box of (0,0,100,100):

expression myMXCIFQuadtreeSettings { mxcifquadtree(0, 0, 100, 100) } 
select * from RectangleEvent(rectangle(10, 20, 5, 5, filterindex:myMXCIFQuadtreeSettings).intersects(rectangle(x, y, width, height)))

The filterindex named parameter instructs the engine that the settings for the MX-CIF quadtree filter index are provided by the expression myMXCIFQuadtreeSettings, a local expression in this example. For sharing MX-CIF quadtree settings across statements you may use a global expression instead. Please see Section 5.18, “Declaring Global Expressions, Aliases And Scripts: Create Expression”.

If your EPL does not specify filterindex the engine does not build a MX-CIF quadtree filter index.

If your EPL specifies filterindex the engine always builds and uses a MX-CIF quadtree filter index. In the case the engine analyses filter criteria and determines that it cannot use the MX-CIF quadtree filter index, the engine fails statement validation.

If your EPL specifies filterindex and the engine determines that it cannot use the MX-CIF quadtree filter index it fails statement validation.

The engine shares MX-CIF quadtree filter indexes across the engine within the same event type given that:

  1. Filters have the same rectangle expressions.

  2. Filters use the same filterindex parameter i.e. the text myMXCIFQuadtreeSettings in above example.

  3. Filters use the same MX-CIF quadtree index configuration i.e. mxcifquadtree(0,0,100,100) in above example.

For use with the filterindex named parameter, the following requirements apply towards left-hand side rectangle expressions:

  1. Left-hand side rectangle expressions must be a constant, a context-provided built-in property or an event property provided by a previous pattern match within the same pattern.

For use with the filterindex named parameter, the following requirements apply towards right-hand side rectangle expressions:

  1. Right-hand side rectangle expressions must be event properties.

The section that summarizes event indexes is Section 3.9.3, “Event Indexes”. The create index clause is described in Section 6.9, “Explicitly Indexing Named Windows and Tables”.

Declare a MX-CIF quadtree event index as follows:

create index ... on ... (
  (x_expression, y_expression, width_expression, height_expression) mxcifquadtree(mxcif_quadtree_configuration)
)

The x_expression, y_expression, width_expression and height_expression expressions form the index columns. The expressions return the (x, y)-coordinates and rectangle size and must return numeric values. Coordinates and sizes are represented as double-type values internally. See above for the mxcif_quadtree_configuration MX-CIF quadtree configuration.

For example, assume we have a table that contains rectangles:

create table RectangleTable(rectangleId string primary key, rx double, ry double, rwidth double, rheight double)

This example EPL declares an index on the rectangles, with rx, ry, rwidth and rheight becoming index columns that determine the (x, y)-coordinates and the sizes:

create index RectangleIndex on RectangleTable((rx, ry, rwidth, rheight) mxcifquadtree(0, 0, 100, 100))

The above sample quadtree index expects rectangles to intersect the rectangle (0, 0, 100, 100).

The example schema for arriving events is:

create schema OtherRectangleEvent(otherX double, otherY double, otherWidth double, otherHeight double)

This EPL outputs, upon arrival of a OtherRectangleEvent, all rectangles stored in the table that intersect the arriving-events rectangle:

on OtherRectangleEvent
select rectangleId from RectangleTable
where rectangle(rx, ry, rwidth, rheight).intersects(rectangle(otherX, otherY, otherWidth, otherHeight))

Internally the engine does not instantiate rectangle objects at all but instead optimizes the expression to comparison between double-type values.

The scope of the Esper engine does not include addressing all geographical, topological or spatial processing. We encourage using external libraries with Esper and Esper. Esper and EPL make it easy to use and extend EPL, using functions, methods, data types and data structures provided by external libraries.

For example, assume you would like to use a geometric data type and the geographical distance function. Please consider using the Java Topology Suite (JTS) (https://www.locationtech.org) which provides a pretty complete set of geo computing functionality.

To pick an example data type, Esper allows any class such as the JTS Geometry class (org.locationtech.jts.geom.Geometry) to become an event type, an event property type or a column type in a named window, table. Esper also allows the use of such class anywhere within EPL expressions as well.

The EPL snippet below declares an event type that has a Geometry property:

create schema ShapeArrivalEvent(shapeId string, geometry org.locationtech.jts.geom.Geometry) // use imports to remove the need to have a package name

EPL can call methods and your application can declare its own functions. Registering an own EPL function is described in Section 19.3, “Single-Row Function”.

This sample EPL outputs events that have a distance of more than 100 comparing the current event's geometry to the last 1 minute of previous event's geometry:

select * from ShapeArrivalEvent as e1 unidirectional, ShapeArrivalEvent.time(1 minute) as e2
where e1.geometry.distance(e2.geometry) > 100