Visitar URL original
fix(#10247,#10245,#10210,#10206): schema changes scale with the types… · ArcadeData/arcadedb@1e4c388 · GitHub
Skip to content

Commit 1e4c388

Browse files
lvcalvca
authored
fix(#10247,#10245,#10210,#10206): schema changes scale with the types, lazy polyglot languages, planar geo shapes, strict SQL dates (#10259)
* fix(#10247,#10245,#10210,#10206): schema changes scale with the types, lazy polyglot languages, planar geo shapes, strict SQL dates #10247 - schema changes no longer cost O(N) in the number of types - The bucket-to-type and involved-bucket maps follow the additive changes in place (a bucket attached, an external or edge-list bucket paired) instead of being rebuilt over every type at the end of every frame; a detach, a drop, a rename or a stripe pool still rebuilds them. Under -ea every refresh compares them with a full rebuild. - The "bucket already associated" check is one lookup instead of a walk of every type, which also made opening a schema of N types O(N^2). - The schema file is streamed type by type into the same Gson writer, byte-identical to toJSON().toString(), without the 20k-entry root tree. - 20,000 types: bulkChange creation 212 s -> 1.6 s, open 24 s -> 1 s. #10245 - the first SQL/Cypher statement no longer builds the GraalVM polyglot Engine - QueryEngineManager registers the polyglot languages on first demand (a language no built-in engine answers, or the complete list), never displacing a built-in engine. #10210 - geo - DatelineRule.none: a polygon wider than 180 degrees and a polar cap are read as written (OGC/RFC 7946); longitudes past +/-180 are split at the antimeridian. - geo.dWithin and geo.distance measure between the shapes (0 when they intersect), not between centres, the short way across the antimeridian. - A GEOSPATIAL index refuses an invalid geometry on write (an index build still skips one written before, with a warning), and shares the parser of the geo.* functions. #10206 - SQL dates - Formats resolve STRICTly: 2021-02-30 and 24:00:00 are refused, not moved. - yyyy reads as the proleptic year unless the era is named, so year 0 parses; a 12-hour pattern (hh ... a) parses at all. - A DATE compares as midnight against a DATETIME on either side of the operator, BETWEEN and through an index (IntegralKeyBound maps the datetime bound to days). - A time pattern formats a DATE as midnight; date - datetime is an exact Duration. * fix(#10210,#10247): legacy GEOSPATIAL indexes are bypassed until rebuilt, antimeridian overlay failures are not geometries, aliased types are written once * fix(#10247,#10210,#10206): a failed schema change rebuilds the bucket maps, DATE index and scan agree on zoned datetimes, more regression tests * fix(#10247,#10210): rebuild the bucket maps at once when a schema change fails, one haversine for geo.distance * test(#10247,#10210): concurrent schema changes, a write refused while the geo index is built; log a swallowed antimeridian overlay failure * fix(#10247): log a failed bucket map rebuild, state the reader guarantee, test a change failing after it attached a bucket * fix(#10245,#10210): polyglot resolution does not hold the registry monitor nor retry a failing enumeration, per-thread marker for the geo index build * test(#10245): concurrent lookups and registrations resolve the polyglot languages once * test(#10206): exercise the zoned <= bound on a DATE
1 parent a830b21 commit 1e4c388

26 files changed

Lines changed: 1846 additions & 168 deletions

‎engine/src/main/java/com/arcadedb/function/sql/geo/GeoUtils.java‎

Lines changed: 121 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -18,37 +18,65 @@
1818
*/
1919
package com.arcadedb.function.sql.geo;
2020

21+
import com.arcadedb.log.LogManager;
22+
import org.locationtech.jts.geom.Coordinate;
23+
import org.locationtech.jts.geom.Envelope;
2124
import org.locationtech.jts.geom.Geometry;
25+
import org.locationtech.jts.geom.GeometryFactory;
26+
import org.locationtech.jts.geom.util.AffineTransformation;
2227
import org.locationtech.jts.io.ParseException;
2328
import org.locationtech.jts.io.WKTReader;
2429
import org.locationtech.jts.io.WKTWriter;
30+
import org.locationtech.jts.operation.distance.DistanceOp;
2531
import org.locationtech.spatial4j.context.SpatialContext;
2632
import org.locationtech.spatial4j.context.SpatialContextFactory;
33+
import org.locationtech.spatial4j.context.jts.DatelineRule;
2734
import org.locationtech.spatial4j.context.jts.JtsSpatialContext;
2835
import org.locationtech.spatial4j.context.jts.JtsSpatialContextFactory;
2936
import org.locationtech.spatial4j.io.ShapeIO;
37+
import org.locationtech.spatial4j.shape.Circle;
3038
import org.locationtech.spatial4j.shape.Point;
3139
import org.locationtech.spatial4j.shape.Rectangle;
3240
import org.locationtech.spatial4j.shape.Shape;
3341
import org.locationtech.spatial4j.shape.jts.JtsGeometry;
42+
import org.locationtech.spatial4j.shape.jts.JtsShapeFactory;
3443

3544
import java.util.List;
3645
import java.util.Locale;
3746
import java.util.Map;
47+
import java.util.logging.Level;
3848

3949
/**
4050
* Geospatial utility class.
4151
*
4252
* @author Luca Garulli (l.garulli--(at)--arcadedata.com)
4353
*/
4454
public class GeoUtils {
45-
static final JtsSpatialContextFactory FACTORY = new JtsSpatialContextFactory();
55+
static final JtsSpatialContextFactory FACTORY = newFactory();
4656
static final JtsSpatialContext SPATIAL_CONTEXT = new JtsSpatialContext(FACTORY);
57+
/** Mean Earth radius of the haversine formula {@code geo.distance()} answers with, in kilometres. */
58+
public static final double EARTH_RADIUS_KM = 6371.0;
4759

4860
// WKTReader/WKTWriter are not thread-safe; use ThreadLocal to avoid per-call allocation
4961
private static final ThreadLocal<WKTReader> WKT_READER = ThreadLocal.withInitial(WKTReader::new);
5062
private static final ThreadLocal<WKTWriter> WKT_WRITER = ThreadLocal.withInitial(WKTWriter::new);
5163

64+
/**
65+
* Geodetic (lon/lat), with {@link DatelineRule#none}: a polygon means the area its coordinates enclose, read on the
66+
* longitude/latitude plane as OGC WKT, PostGIS {@code geometry}, Shapely and GeoJSON (RFC 7946) read it.
67+
* <p>
68+
* Spatial4j's default, {@link DatelineRule#width180}, assumed no polygon is wider than 180 degrees and read a wider
69+
* one as crossing the antimeridian: a band from -100 to 100 of longitude was taken for the 160 degrees around the
70+
* back of the globe, a polar cap from -180 to 180 collapsed to nothing, and a wide polygon that is not a rectangle
71+
* failed to parse at all (issue #10210). A shape crossing the antimeridian is written either as a MULTIPOLYGON split
72+
* at 180, or with longitudes past it ({@code 170 .. 190}), which {@link #parseGeometry} splits there.
73+
*/
74+
private static JtsSpatialContextFactory newFactory() {
75+
final JtsSpatialContextFactory factory = new JtsSpatialContextFactory();
76+
factory.datelineRule = DatelineRule.none;
77+
return factory;
78+
}
79+
5280
public static SpatialContextFactory getFactory() {
5381
return FACTORY;
5482
}
@@ -124,11 +152,101 @@ public static Shape parseGeometry(final Object value) {
124152
return null;
125153
try {
126154
return SPATIAL_CONTEXT.getFormats().getReader(ShapeIO.WKT).read(wkt);
127-
} catch (Exception e) {
128-
throw new IllegalArgumentException("Cannot parse geometry from: " + wkt, e);
155+
} catch (final Exception e) {
156+
final Shape wrapped = splitAtAntimeridian(wkt);
157+
if (wrapped != null)
158+
return wrapped;
159+
throw new IllegalArgumentException("Cannot parse geometry from: " + wkt + " (" + e.getMessage() + ")", e);
160+
}
161+
}
162+
163+
/**
164+
* Reads a WKT whose longitudes run past +/-180 (up to one turn of the globe either way) as the same shape cut at the
165+
* antimeridian, each part moved back into [-180, 180]: {@code POLYGON ((170 0, 190 0, 190 10, 170 10, 170 0))} is the
166+
* 20 degrees across the antimeridian, two polygons on either side of it. The way to write a crossing shape as one
167+
* polygon now that a wide polygon is read as written (issue #10210), as PostGIS's {@code ST_WrapX} does.
168+
*
169+
* @return null when the WKT is not such a shape: unreadable, a latitude out of range, a longitude past one turn
170+
*/
171+
private static Shape splitAtAntimeridian(final String wkt) {
172+
final Geometry geometry;
173+
try {
174+
geometry = WKT_READER.get().read(wkt);
175+
} catch (final ParseException e) {
176+
return null;
177+
}
178+
final Envelope envelope = geometry.getEnvelopeInternal();
179+
if (envelope.isNull() || (envelope.getMinX() >= -180 && envelope.getMaxX() <= 180) || envelope.getMinY() < -90
180+
|| envelope.getMaxY() > 90 || envelope.getMinX() < -540 || envelope.getMaxX() > 540)
181+
return null;
182+
183+
try {
184+
final GeometryFactory factory = geometry.getFactory();
185+
Geometry result = null;
186+
for (int shift = -360; shift <= 360; shift += 360) {
187+
// the part that lands inside [-180, 180] once moved by 'shift'
188+
final Geometry part = geometry.intersection(factory.toGeometry(new Envelope(-180 - shift, 180 - shift, -90, 90)));
189+
if (part.isEmpty())
190+
continue;
191+
final Geometry moved = AffineTransformation.translationInstance(shift, 0).transform(part);
192+
result = result == null ? moved : result.union(moved);
193+
}
194+
return result == null ? null : SPATIAL_CONTEXT.getShapeFactory().makeShapeFromGeometry(result);
195+
} catch (final RuntimeException e) {
196+
// an invalid shape (a self-intersecting polygon) fails in the overlay: not a geometry, like any other unreadable one
197+
LogManager.instance().log(GeoUtils.class, Level.FINE, "Cannot split the geometry '%s' at the antimeridian: %s", wkt,
198+
e.getMessage());
199+
return null;
129200
}
130201
}
131202

203+
/**
204+
* The great-circle distance between two shapes, in degrees of arc: 0 when they intersect, otherwise the distance
205+
* between their two closest points. {@code geo.dWithin} and {@code geo.distance} used to measure between the CENTRES
206+
* of the shapes, so a point inside a polygon was far from it and a point near its edge farther than it is (issue #10210).
207+
* <p>
208+
* The closest points are found on the longitude/latitude plane, the way the predicates read a shape, with the second
209+
* shape also tried one turn either way so that two shapes facing each other across the antimeridian are measured the
210+
* short way round. A circle is its centre less its radius. The distance between those two points is the great-circle
211+
* one, so it is exact for a point and, for a larger shape, close to the shortest distance on the sphere but not always
212+
* equal to it: the plane picks the nearest edge in degrees, and a degree of longitude is shorter the nearer the pole.
213+
*/
214+
public static double distanceDegrees(final Shape a, final Shape b) {
215+
if (a instanceof Circle circle)
216+
return Math.max(0.0, distanceDegrees(circle.getCenter(), b) - circle.getRadius());
217+
if (b instanceof Circle circle)
218+
return Math.max(0.0, distanceDegrees(a, circle.getCenter()) - circle.getRadius());
219+
if (a instanceof Point p1 && b instanceof Point p2)
220+
return haversineDegrees(p1.getX(), p1.getY(), p2.getX(), p2.getY());
221+
if (a.relate(b).intersects())
222+
return 0.0;
223+
224+
final JtsShapeFactory shapeFactory = SPATIAL_CONTEXT.getShapeFactory();
225+
final Geometry ga = shapeFactory.getGeometryFrom(a);
226+
final Geometry gb = shapeFactory.getGeometryFrom(b);
227+
double min = Double.MAX_VALUE;
228+
for (int shift = -360; shift <= 360; shift += 360) {
229+
final Geometry moved = shift == 0 ? gb : AffineTransformation.translationInstance(shift, 0).transform(gb);
230+
final Coordinate[] closest = DistanceOp.nearestPoints(ga, moved);
231+
min = Math.min(min, haversineDegrees(closest[0].x, closest[0].y, closest[1].x - shift, closest[1].y));
232+
}
233+
return min;
234+
}
235+
236+
/** The central angle between two lon/lat points, in degrees, by the haversine formula. */
237+
public static double haversineDegrees(final double lon1, final double lat1, final double lon2, final double lat2) {
238+
return Math.toDegrees(haversineRadians(lon1, lat1, lon2, lat2));
239+
}
240+
241+
/** The central angle between two lon/lat points, in radians, by the haversine formula. */
242+
public static double haversineRadians(final double lon1, final double lat1, final double lon2, final double lat2) {
243+
final double deltaLat = Math.toRadians(lat2 - lat1);
244+
final double deltaLon = Math.toRadians(lon2 - lon1);
245+
final double h = Math.pow(Math.sin(deltaLat / 2), 2)
246+
+ Math.cos(Math.toRadians(lat1)) * Math.cos(Math.toRadians(lat2)) * Math.pow(Math.sin(deltaLon / 2), 2);
247+
return 2 * Math.atan2(Math.sqrt(h), Math.sqrt(1 - h));
248+
}
249+
132250
/**
133251
* Reads one coordinate of a point map. A non-numeric entry is an unparseable geometry like any other, so it has to
134252
* leave as {@link IllegalArgumentException}: callers that skip a value they cannot parse - a WHERE clause dropping a

‎engine/src/main/java/com/arcadedb/function/sql/geo/SQLFunctionGeoDWithin.java‎

Lines changed: 3 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -53,7 +53,7 @@ public int getMaxArgs() {
5353
}
5454

5555
/**
56-
* geo.dWithin uses a radius distance check against the centers of the two geometries.
56+
* geo.dWithin compares the great-circle distance between the two geometries (0 when they intersect) with the radius.
5757
* The geospatial index returns records based on geohash intersection, which does not
5858
* directly correspond to the distance radius. To guarantee correctness, indexed
5959
* execution is disabled and the predicate is evaluated inline on all records.
@@ -69,9 +69,8 @@ protected Boolean evaluate(final Shape geom1, final Shape geom2, final Object[]
6969
if (params.length < 3 || params[2] == null)
7070
return null;
7171
final double distance = GeoUtils.getDoubleValue(params[2]);
72-
final double actualDistance = GeoUtils.getSpatialContext()
73-
.calcDistance(geom1.getCenter(), geom2.getCenter());
74-
return actualDistance <= distance;
72+
// the distance between the shapes, not between their centres (issue #10210)
73+
return GeoUtils.distanceDegrees(geom1, geom2) <= distance;
7574
}
7675

7776
@Override

‎engine/src/main/java/com/arcadedb/function/sql/geo/SQLFunctionGeoDistance.java‎

Lines changed: 14 additions & 27 deletions
Original file line numberDiff line numberDiff line change
@@ -37,8 +37,6 @@
3737
public class SQLFunctionGeoDistance extends SQLFunctionAbstract {
3838
public static final String NAME = "geo.distance";
3939

40-
private static final double EARTH_RADIUS_KM = 6371.0;
41-
4240
public SQLFunctionGeoDistance() {
4341
super(NAME);
4442
}
@@ -64,19 +62,18 @@ public Object execute(final Object iThis, final Identifiable iCurrentRecord, fin
6462
if (iParams == null || iParams.length < 2 || iParams[0] == null || iParams[1] == null)
6563
return null;
6664

67-
final double[] p1 = extractPointCoords(iParams[0]);
68-
final double[] p2 = extractPointCoords(iParams[1]);
65+
final Shape shape1 = toShape(iParams[0]);
66+
final Shape shape2 = toShape(iParams[1]);
6967

7068
final String unit = iParams.length >= 3 && iParams[2] != null ? iParams[2].toString() : "m";
7169

72-
final double deltaLat = Math.toRadians(p2[1] - p1[1]);
73-
final double deltaLon = Math.toRadians(p2[0] - p1[0]);
74-
75-
final double a = Math.pow(Math.sin(deltaLat / 2), 2)
76-
+ Math.cos(Math.toRadians(p1[1])) * Math.cos(Math.toRadians(p2[1]))
77-
* Math.pow(Math.sin(deltaLon / 2), 2);
78-
79-
double distance = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a)) * EARTH_RADIUS_KM;
70+
final double distance;
71+
if (shape1 instanceof Point p1 && shape2 instanceof Point p2)
72+
distance = GeoUtils.haversineRadians(p1.getX(), p1.getY(), p2.getX(), p2.getY()) * GeoUtils.EARTH_RADIUS_KM;
73+
else
74+
// between the closest points of the shapes, 0 when they intersect, rather than between the centres of their
75+
// bounding boxes (issue #10210)
76+
distance = Math.toRadians(GeoUtils.distanceDegrees(shape1, shape2)) * GeoUtils.EARTH_RADIUS_KM;
8077

8178
return switch (unit.toLowerCase(Locale.ROOT)) {
8279
case "km" -> distance;
@@ -89,23 +86,13 @@ public Object execute(final Object iThis, final Identifiable iCurrentRecord, fin
8986
}
9087

9188
/**
92-
* Extract [x, y] coordinates from a point given as WKT string, Shape, or Point.
89+
* The shape of an argument: a Shape, a WKT string or a Cypher point map.
9390
*/
94-
private double[] extractPointCoords(final Object param) {
95-
if (param instanceof Point p)
96-
return new double[] { p.getX(), p.getY() };
97-
98-
// Parse as geometry and get center point
91+
private static Shape toShape(final Object param) {
9992
final Shape shape = GeoUtils.parseGeometry(param);
100-
if (shape instanceof Point p)
101-
return new double[] { p.getX(), p.getY() };
102-
103-
// Fall back to bounding box center
104-
final var bbox = shape.getBoundingBox();
105-
return new double[] {
106-
(bbox.getMinX() + bbox.getMaxX()) / 2.0,
107-
(bbox.getMinY() + bbox.getMaxY()) / 2.0
108-
};
93+
if (shape == null)
94+
throw new IllegalArgumentException("Cannot parse geometry from: " + param);
95+
return shape;
10996
}
11097

11198
@Override

‎engine/src/main/java/com/arcadedb/function/sql/geo/SQLFunctionGeoPredicate.java‎

Lines changed: 22 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -23,6 +23,7 @@
2323
import com.arcadedb.function.sql.SQLFunctionAbstract;
2424
import com.arcadedb.index.Index;
2525
import com.arcadedb.index.IndexCursor;
26+
import com.arcadedb.index.IndexInternal;
2627
import com.arcadedb.index.TypeIndex;
2728
import com.arcadedb.index.geospatial.LSMTreeGeoIndex;
2829
import com.arcadedb.query.sql.executor.CommandContext;
@@ -126,14 +127,31 @@ public boolean allowsIndexedExecution(final FromClause target, final BinaryCompa
126127
final DocumentType docType = schema.getType(typeName);
127128

128129
// Look for a GEOSPATIAL index on the field
130+
return resolveGeoIndex(docType, fieldName) != null;
131+
}
132+
133+
/**
134+
* The GEOSPATIAL index on {@code fieldName} a query can use, or null. An index built before shapes were read as written
135+
* on the longitude/latitude plane is not one (issue #10210): it holds the complement of a polygon wider than 180 degrees,
136+
* so it could leave out a record the predicate matches, which the check after the search cannot bring back. The query
137+
* scans the type instead until the index is rebuilt.
138+
*/
139+
private static TypeIndex resolveGeoIndex(final DocumentType docType, final String fieldName) {
129140
for (final TypeIndex typeIndex : TypeIndex.filterReadyForQueries(docType.getAllIndexes(true))) {
130141
if (typeIndex.getType() == Schema.INDEX_TYPE.GEOSPATIAL) {
131142
final List<String> props = typeIndex.getPropertyNames();
132-
if (props != null && props.contains(fieldName))
133-
return true;
143+
if (props != null && props.contains(fieldName) && isPlanar(typeIndex))
144+
return typeIndex;
134145
}
135146
}
136-
return false;
147+
return null;
148+
}
149+
150+
private static boolean isPlanar(final TypeIndex typeIndex) {
151+
for (final IndexInternal bucketIndex : typeIndex.getIndexesOnBuckets())
152+
if (bucketIndex instanceof LSMTreeGeoIndex geoIndex && !geoIndex.isPlanar())
153+
return false;
154+
return true;
137155
}
138156

139157
@Override
@@ -176,16 +194,7 @@ public Iterable<Record> searchFromTarget(final FromClause target, final BinaryCo
176194
final DocumentType docType = schema.getType(typeName);
177195

178196
// Resolve the GEOSPATIAL index on this field
179-
TypeIndex geoTypeIndex = null;
180-
for (final TypeIndex typeIndex : TypeIndex.filterReadyForQueries(docType.getAllIndexes(true))) {
181-
if (typeIndex.getType() == Schema.INDEX_TYPE.GEOSPATIAL) {
182-
final List<String> props = typeIndex.getPropertyNames();
183-
if (props != null && props.contains(fieldName)) {
184-
geoTypeIndex = typeIndex;
185-
break;
186-
}
187-
}
188-
}
197+
final TypeIndex geoTypeIndex = resolveGeoIndex(docType, fieldName);
189198

190199
if (geoTypeIndex == null)
191200
return List.of();

0 commit comments

Comments
 (0)