www.espertech.comDocumentation

Chapter 20. EPL Reference: Spatial Methods and Indexes

20.1. Overview
20.2. Spatial Methods
20.2.1. Point-Inside-Rectangle
20.2.2. Rectangle-Intersects-Rectangle
20.3. Spatial Index - Quadtree
20.3.1. Overview
20.3.2. Declaring a Point-Region Quadtree Index
20.3.3. Using a Point-Region Quadtree as a Filter Index
20.3.4. Using a Point-Region Quadtree as an Event Index
20.3.5. Declaring a MX-CIF Quadtree Index
20.3.6. Using a MX-CIF Quadtree as a Filter Index
20.3.7. Using a MX-CIF Quadtree as an Event Index
20.4. Spatial Types, Functions and Methods from External Libraries

EPL provides spatial methods and spatial indexes.

The compiler 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 runtime 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 2.18.2, “Filter Indexes”. As there could be many point(...).inside(rectangle) filters active, having a filter index allows the runtime to efficiently match incoming events to 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 statement 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 runtime 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 runtime does not build a point-region quadtree filter index.

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

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

The runtime shares point-region quadtree filter indexes across the runtime 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 2.18.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 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 runtime 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 2.18.2, “Filter Indexes”. As there could be many rectangle(...).intersects(rectangle) filters active, having a filter index allows the runtime to efficiently match incoming events to 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 statement 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 compiler 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 runtime does not build a MX-CIF quadtree filter index.

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

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

The runtime shares MX-CIF quadtree filter indexes across the runtime 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 2.18.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 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 runtime does not instantiate rectangle objects at all but instead optimizes the expression to comparison between double-type values.

The scope of the compiler and runtime does not include addressing all geographical, topological or spatial processing. We encourage using external libraries for library calls. EPL makes 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, the compiler and runtime allow 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. The compiler and runtime also allow the use of such class anywhere within EPL expressions.

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 22.2, “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