This is an automated email from the ASF dual-hosted git repository.
yiguolei pushed a commit to branch branch-4.1
in repository https://gitbox.apache.org/repos/asf/doris.git
The following commit(s) were added to refs/heads/branch-4.1 by this push:
new 31b20456c6d branch-4.1: [improvement](geo) Decode constant shapes once
in st_contains and other spatial relation functions #70302 (#70595)
31b20456c6d is described below
commit 31b20456c6d94b9402228e5d97f834ab51cca0cb
Author: github-actions[bot]
<41898282+github-actions[bot]@users.noreply.github.com>
AuthorDate: Mon Nov 16 11:09:44 2026 +0800
branch-4.1: [improvement](geo) Decode constant shapes once in st_contains
and other spatial relation functions #70302 (#70595)
Cherry-picked from #70302
Co-authored-by: guptashivam04
<[email protected]>
Co-authored-by: Shivam Gupta <[email protected]>
---
be/src/exprs/function/geo/functions_geo.cpp | 61 +++++++++--
be/src/exprs/function/geo/functions_geo.h | 31 +++++-
be/src/exprs/function/geo/geo_types.cpp | 55 ++++++++--
be/src/exprs/function/geo/geo_types.h | 6 +
be/test/exprs/function/function_geo_test.cpp | 151 ++++++++++++++++++++++++++
be/test/exprs/function/geo/geo_types_test.cpp | 41 +++++++
6 files changed, 319 insertions(+), 26 deletions(-)
diff --git a/be/src/exprs/function/geo/functions_geo.cpp
b/be/src/exprs/function/geo/functions_geo.cpp
index 6a191f133e5..515aac14428 100644
--- a/be/src/exprs/function/geo/functions_geo.cpp
+++ b/be/src/exprs/function/geo/functions_geo.cpp
@@ -501,7 +501,15 @@ struct StRelationFunction {
static const size_t NUM_ARGS = 2;
using Type = DataTypeUInt8;
- static Status execute(Block& block, const ColumnNumbers& arguments, size_t
result) {
+ static Status open(FunctionContext* context,
FunctionContext::FunctionStateScope scope) {
+ if (scope == FunctionContext::FunctionStateScope::THREAD_LOCAL) {
+ context->set_function_state(scope,
std::make_shared<StRelationState>());
+ }
+ return Status::OK();
+ }
+
+ static Status execute(FunctionContext* context, Block& block, const
ColumnNumbers& arguments,
+ size_t result) {
DCHECK_EQ(arguments.size(), 2);
auto return_type = block.get_data_type(result);
auto left_col =
ColumnView<TYPE_STRING>::create(block.get_by_position(arguments[0]).column);
@@ -514,26 +522,61 @@ struct StRelationFunction {
auto null_map = ColumnUInt8::create(size, 0);
auto& null_map_data = null_map->get_data();
- for (int row = 0; row < size; ++row) {
- auto lhs_value = left_col.value_at(row);
- auto rhs_value = right_col.value_at(row);
+ auto* state = reinterpret_cast<StRelationState*>(
+
context->get_function_state(FunctionContext::FunctionStateScope::THREAD_LOCAL));
+ std::shared_ptr<GeoShape> const_shape1;
+ std::shared_ptr<GeoShape> const_shape2;
+ if (left_col.is_const) {
+ const_shape1 = decode_const(state, 0, left_col.value_at(0));
+ }
+ if (right_col.is_const) {
+ const_shape2 = decode_const(state, 1, right_col.value_at(0));
+ }
- std::unique_ptr<GeoShape> shape1(
- GeoShape::from_encoded(lhs_value.data, lhs_value.size));
- std::unique_ptr<GeoShape> shape2(
- GeoShape::from_encoded(rhs_value.data, rhs_value.size));
+ for (int row = 0; row < size; ++row) {
+ std::unique_ptr<GeoShape> row_shape1;
+ std::unique_ptr<GeoShape> row_shape2;
+ GeoShape* shape1 = const_shape1.get();
+ GeoShape* shape2 = const_shape2.get();
+ if (!left_col.is_const) {
+ auto lhs_value = left_col.value_at(row);
+ row_shape1 = GeoShape::from_encoded(lhs_value.data,
lhs_value.size);
+ shape1 = row_shape1.get();
+ }
+ if (!right_col.is_const) {
+ auto rhs_value = right_col.value_at(row);
+ row_shape2 = GeoShape::from_encoded(rhs_value.data,
rhs_value.size);
+ shape2 = row_shape2.get();
+ }
if (!shape1 || !shape2) {
null_map_data[row] = 1;
continue;
}
- auto relation_value = Func::evaluate(shape1.get(), shape2.get());
+ auto relation_value = Func::evaluate(shape1, shape2);
res->get_data()[row] = relation_value;
}
block.replace_by_position(result,
ColumnNullable::create(std::move(res),
std::move(null_map)));
return Status::OK();
}
+
+private:
+ // Decodes a constant argument, reusing the shape decoded for an earlier
block when the value
+ // is unchanged. Returns nullptr if the value is not a valid shape.
+ static std::shared_ptr<GeoShape> decode_const(StRelationState* state, int
arg,
+ const StringRef& value) {
+ if (state == nullptr) {
+ return GeoShape::from_encoded(value.data, value.size);
+ }
+ auto& cached = state->args[arg];
+ if (!cached.decoded || StringRef(cached.encoded) != value) {
+ cached.encoded.assign(value.data, value.size);
+ cached.shape = GeoShape::from_encoded(cached.encoded.data(),
cached.encoded.size());
+ cached.decoded = true;
+ }
+ return cached.shape;
+ }
};
struct StContainsFunc {
diff --git a/be/src/exprs/function/geo/functions_geo.h
b/be/src/exprs/function/geo/functions_geo.h
index c75525641e6..d2dab939d89 100644
--- a/be/src/exprs/function/geo/functions_geo.h
+++ b/be/src/exprs/function/geo/functions_geo.h
@@ -46,11 +46,18 @@ struct StConstructState {
std::string encoded_buf;
};
-struct StContainsState {
- StContainsState() : is_null(false), shapes {nullptr, nullptr} {}
- ~StContainsState() {}
- bool is_null;
- std::vector<std::shared_ptr<GeoShape>> shapes;
+// Thread-local state of st_contains, st_within and the other relation
functions: the decoded
+// shape of each constant argument, keyed by its encoded value. Decoding a
polygon validates it,
+// which builds an index over all its edges, so a constant shape is decoded
once per thread
+// instead of once per row.
+struct StRelationState {
+ struct ConstShape {
+ bool decoded = false;
+ std::string encoded;
+ // nullptr if `encoded` is not a valid shape
+ std::shared_ptr<GeoShape> shape;
+ };
+ ConstShape args[2];
};
template <typename Impl>
@@ -67,9 +74,21 @@ public:
return make_nullable(std::make_shared<ReturnType>());
}
+ Status open(FunctionContext* context, FunctionContext::FunctionStateScope
scope) override {
+ if constexpr (requires { Impl::open(context, scope); }) {
+ return Impl::open(context, scope);
+ } else {
+ return Status::OK();
+ }
+ }
+
Status execute_impl(FunctionContext* context, Block& block, const
ColumnNumbers& arguments,
uint32_t result, size_t input_rows_count) const
override {
- return Impl::execute(block, arguments, result);
+ if constexpr (requires { Impl::execute(context, block, arguments,
result); }) {
+ return Impl::execute(context, block, arguments, result);
+ } else {
+ return Impl::execute(block, arguments, result);
+ }
}
};
diff --git a/be/src/exprs/function/geo/geo_types.cpp
b/be/src/exprs/function/geo/geo_types.cpp
index 03dd5c080c3..4b3958bd5d9 100644
--- a/be/src/exprs/function/geo/geo_types.cpp
+++ b/be/src/exprs/function/geo/geo_types.cpp
@@ -37,6 +37,7 @@
#include "core/assert_cast.h"
// IWYU pragma: no_include <bits/std_abs.h>
+#include <algorithm>
#include <cmath>
#include <iomanip>
#include <limits>
@@ -788,6 +789,7 @@ const S2Point* GeoLine::getPoint(int i) const {
}
GeoParseStatus GeoPolygon::from_coords(const GeoCoordinateListList& list) {
+ _loop_lat_lngs.clear();
return to_s2polygon(list, &_polygon);
}
@@ -800,6 +802,7 @@ void GeoPolygon::encode(std::string* buf) {
bool GeoPolygon::decode(const void* data, size_t size) {
Decoder decoder(data, size);
_polygon.reset(new S2Polygon());
+ _loop_lat_lngs.clear();
return _polygon->Decode(&decoder) && _polygon->IsValid();
}
@@ -1043,17 +1046,7 @@ bool GeoPolygon::contains(const GeoShape* rhs) const {
}
// Point on the edge of polygon doesn't count as "Contians"
- for (int i = 0; i < _polygon->num_loops(); ++i) {
- const S2Loop* loop = _polygon->loop(i);
- for (int j = 0; j < loop->num_vertices(); ++j) {
- const S2Point& p1 = loop->vertex(j);
- const S2Point& p2 = loop->vertex((j + 1) %
loop->num_vertices());
- if (compute_distance_to_line(*point->point(), p1, p2) <
TOLERANCE) {
- return false;
- }
- }
- }
- return true;
+ return !point_on_edge(*point->point());
}
case GEO_SHAPE_LINE_STRING: {
const GeoLine* line = (const GeoLine*)rhs;
@@ -1097,6 +1090,46 @@ bool GeoPolygon::contains(const GeoShape* rhs) const {
}
}
+// Same check as compute_distance_to_line(point, p1, p2) < TOLERANCE over
every edge, with the
+// vertices converted to lat/lng once per polygon instead of once per edge and
call.
+bool GeoPolygon::point_on_edge(const S2Point& point) const {
+ if (_loop_lat_lngs.empty()) {
+ _loop_lat_lngs.resize(_polygon->num_loops());
+ for (int i = 0; i < _polygon->num_loops(); ++i) {
+ const S2Loop* loop = _polygon->loop(i);
+ auto& lat_lngs = _loop_lat_lngs[i];
+ lat_lngs.reserve(loop->num_vertices());
+ for (int j = 0; j < loop->num_vertices(); ++j) {
+ S2LatLng vertex(loop->vertex(j));
+ lat_lngs.emplace_back(vertex.lat().degrees(),
vertex.lng().degrees(), 0.0);
+ }
+ }
+ }
+
+ S2LatLng point_lat_lng(point);
+ const S2Point query(point_lat_lng.lat().degrees(),
point_lat_lng.lng().degrees(), 0.0);
+ // The point can only be within TOLERANCE of an edge if it lies in the
edge's bounding box
+ // grown by TOLERANCE. The margin is doubled to stay clear of rounding in
project_distance.
+ constexpr double margin = 2 * TOLERANCE;
+ for (const auto& lat_lngs : _loop_lat_lngs) {
+ const size_t num_vertices = lat_lngs.size();
+ for (size_t j = 0; j < num_vertices; ++j) {
+ const S2Point& p1 = lat_lngs[j];
+ const S2Point& p2 = lat_lngs[j + 1 == num_vertices ? 0 : j + 1];
+ if (query.x() < std::min(p1.x(), p2.x()) - margin ||
+ query.x() > std::max(p1.x(), p2.x()) + margin ||
+ query.y() < std::min(p1.y(), p2.y()) - margin ||
+ query.y() > std::max(p1.y(), p2.y()) + margin) {
+ continue;
+ }
+ if (project_distance(query, p1, p2) < TOLERANCE) {
+ return true;
+ }
+ }
+ }
+ return false;
+}
+
std::double_t GeoPolygon::getArea() const {
return _polygon->GetArea();
}
diff --git a/be/src/exprs/function/geo/geo_types.h
b/be/src/exprs/function/geo/geo_types.h
index f6d8e04e018..274710215ca 100644
--- a/be/src/exprs/function/geo/geo_types.h
+++ b/be/src/exprs/function/geo/geo_types.h
@@ -204,7 +204,13 @@ protected:
bool decode(const void* data, size_t size) override;
private:
+ bool point_on_edge(const S2Point& point) const;
+
std::unique_ptr<S2Polygon> _polygon;
+ // (lat, lng, 0) in degrees of every loop's vertices, for the
point-on-edge check in
+ // contains(). Built on first use, so a polygon that is checked against
many points converts
+ // its vertices only once.
+ mutable std::vector<std::vector<S2Point>> _loop_lat_lngs;
};
class GeoMultiPolygon : public GeoShape {
diff --git a/be/test/exprs/function/function_geo_test.cpp
b/be/test/exprs/function/function_geo_test.cpp
index b4993a231e8..282be6f9508 100644
--- a/be/test/exprs/function/function_geo_test.cpp
+++ b/be/test/exprs/function/function_geo_test.cpp
@@ -21,10 +21,17 @@
#include <iomanip>
#include <memory>
+#include <optional>
#include <string>
#include <vector>
#include "common/status.h"
+#include "core/assert_cast.h"
+#include "core/block/block.h"
+#include "core/column/column_const.h"
+#include "core/column/column_nullable.h"
+#include "core/column/column_string.h"
+#include "core/column/column_vector.h"
#include "core/data_type/data_type_nullable.h"
#include "core/data_type/data_type_number.h"
#include "core/data_type/data_type_string.h"
@@ -32,6 +39,7 @@
#include "exprs/function/function_test_util.h"
#include "exprs/function/geo/geo_common.h"
#include "exprs/function/geo/geo_types.h"
+#include "exprs/function/simple_function_factory.h"
#include "gtest/gtest_pred_impl.h"
#include "testutil/any_type.h"
@@ -317,6 +325,149 @@ TEST(VGeoFunctionsTest, function_geo_st_contains) {
}
}
+namespace {
+std::string encode_wkt(const std::string& wkt) {
+ GeoParseStatus status;
+ std::unique_ptr<GeoShape> shape(GeoShape::from_wkt(wkt.data(), wkt.size(),
status));
+ EXPECT_TRUE(status == GeoParseStatus::GEO_PARSE_OK);
+ std::string buf;
+ shape->encode_to(&buf);
+ return buf;
+}
+
+std::string encode_point(double x, double y) {
+ GeoPoint point;
+ EXPECT_TRUE(point.from_coord(x, y) == GeoParseStatus::GEO_PARSE_OK);
+ std::string buf;
+ point.encode_to(&buf);
+ return buf;
+}
+
+using RowResults = std::vector<std::optional<uint8_t>>;
+
+// Executes a spatial relation function the way a scan thread does: one
FunctionContext, opened
+// in both scopes, runs every block. Argument `const_arg` of each block is a
constant shape, a
+// ColumnConst over a one-row column.
+class ConstShapeRunner {
+public:
+ ConstShapeRunner(const std::string& func_name, size_t const_arg) :
_const_arg(const_arg) {
+ _arg_types[const_arg] = std::make_shared<DataTypeString>();
+ _arg_types[1 - const_arg] =
make_nullable(std::make_shared<DataTypeString>());
+ Block sample_block = make_block("", {std::string()});
+ _func = SimpleFunctionFactory::instance().get_function(
+ func_name, sample_block.get_columns_with_type_and_name(),
_return_type);
+ EXPECT_NE(nullptr, _func);
+ _fn_utils = std::make_unique<FunctionUtils>(
+ _return_type, std::vector<DataTypePtr> {_arg_types[0],
_arg_types[1]}, false);
+ EXPECT_TRUE(
+ _func->open(fn_ctx(),
FunctionContext::FunctionStateScope::FRAGMENT_LOCAL).ok());
+ EXPECT_TRUE(_func->open(fn_ctx(),
FunctionContext::FunctionStateScope::THREAD_LOCAL).ok());
+ }
+
+ ~ConstShapeRunner() {
+ static_cast<void>(
+ _func->close(fn_ctx(),
FunctionContext::FunctionStateScope::THREAD_LOCAL));
+ static_cast<void>(
+ _func->close(fn_ctx(),
FunctionContext::FunctionStateScope::FRAGMENT_LOCAL));
+ }
+
+ // Runs one block whose other argument holds `values`, std::nullopt for
NULL. Returns the
+ // result of each row, std::nullopt for NULL.
+ RowResults run(const std::string& const_value,
+ const std::vector<std::optional<std::string>>& values) {
+ Block block = make_block(const_value, values);
+ block.insert({nullptr, _return_type, "result"});
+ Status status = _func->execute(fn_ctx(), block, {0, 1}, 2,
values.size());
+ EXPECT_TRUE(status.ok()) << status;
+ if (!status.ok()) {
+ return {};
+ }
+ const auto& result = assert_cast<const
ColumnNullable&>(*block.get_by_position(2).column);
+ const auto& data = assert_cast<const
ColumnUInt8&>(result.get_nested_column()).get_data();
+ RowResults results;
+ for (size_t row = 0; row < values.size(); ++row) {
+ results.push_back(result.is_null_at(row) ? std::nullopt
+ :
std::optional<uint8_t>(data[row]));
+ }
+ return results;
+ }
+
+private:
+ FunctionContext* fn_ctx() { return _fn_utils->get_fn_ctx(); }
+
+ Block make_block(const std::string& const_value,
+ const std::vector<std::optional<std::string>>& values)
const {
+ auto const_column = ColumnString::create();
+ const_column->insert_data(const_value.data(), const_value.size());
+ auto value_column = ColumnString::create();
+ auto null_map = ColumnUInt8::create();
+ for (const auto& value : values) {
+ if (value) {
+ value_column->insert_data(value->data(), value->size());
+ } else {
+ value_column->insert_default();
+ }
+ null_map->insert_value(value ? 0 : 1);
+ }
+ ColumnWithTypeAndName columns[2];
+ columns[_const_arg] = {ColumnConst::create(std::move(const_column),
values.size()),
+ _arg_types[_const_arg], "const_shape"};
+ columns[1 - _const_arg] = {
+ ColumnNullable::create(std::move(value_column),
std::move(null_map)),
+ _arg_types[1 - _const_arg], "shape"};
+ Block block;
+ block.insert(columns[0]);
+ block.insert(columns[1]);
+ return block;
+ }
+
+ size_t _const_arg;
+ DataTypePtr _arg_types[2];
+ DataTypePtr _return_type =
make_nullable(std::make_shared<DataTypeUInt8>());
+ FunctionBasePtr _func;
+ std::unique_ptr<FunctionUtils> _fn_utils;
+};
+} // namespace
+
+// A constant polygon is decoded once and then checked against every row of
the block.
+TEST(VGeoFunctionsTest, function_geo_st_contains_const_polygon) {
+ std::string polygon = encode_wkt("POLYGON ((0 0, 10 0, 10 10, 0 10, 0
0))");
+ std::vector<std::optional<std::string>> points = {
+ encode_point(5, 5), encode_point(50, 50),
encode_point(10, 5),
+ encode_point(10 - 5e-7, 5), encode_point(10 - 2e-6, 5),
std::nullopt,
+ encode_point(1, 9)};
+ RowResults expected = {1, 0, 0, 0, 1, std::nullopt, 1};
+ {
+ ConstShapeRunner runner("st_contains", 0);
+ EXPECT_EQ(expected, runner.run(polygon, points));
+ }
+ // The polygon is the second argument of st_within.
+ {
+ ConstShapeRunner runner("st_within", 1);
+ EXPECT_EQ(expected, runner.run(polygon, points));
+ }
+ // An invalid constant makes every row NULL.
+ {
+ ConstShapeRunner runner("st_contains", 0);
+ EXPECT_EQ((RowResults {std::nullopt, std::nullopt}),
+ runner.run("invalid", {encode_point(5, 5), encode_point(50,
50)}));
+ }
+}
+
+// The decoded constant is kept in the thread-local state across blocks. A
block whose constant
+// differs from the previous one must not reuse the shape decoded for it.
+TEST(VGeoFunctionsTest, function_geo_st_contains_const_polygon_across_blocks) {
+ std::string small_polygon = encode_wkt("POLYGON ((0 0, 10 0, 10 10, 0 10,
0 0))");
+ std::string large_polygon = encode_wkt("POLYGON ((0 0, 30 0, 30 30, 0 30,
0 0))");
+ std::vector<std::optional<std::string>> points = {encode_point(5, 5),
encode_point(20, 20)};
+
+ ConstShapeRunner runner("st_contains", 0);
+ EXPECT_EQ((RowResults {1, 0}), runner.run(small_polygon, points));
+ EXPECT_EQ((RowResults {1, 0}), runner.run(small_polygon, points));
+ EXPECT_EQ((RowResults {1, 1}), runner.run(large_polygon, points));
+ EXPECT_EQ((RowResults {1, 0}), runner.run(small_polygon, points));
+}
+
TEST(VGeoFunctionsTest, function_geo_st_circle) {
std::string func_name = "st_circle";
{
diff --git a/be/test/exprs/function/geo/geo_types_test.cpp
b/be/test/exprs/function/geo/geo_types_test.cpp
index 580218f4058..134142b6dd2 100644
--- a/be/test/exprs/function/geo/geo_types_test.cpp
+++ b/be/test/exprs/function/geo/geo_types_test.cpp
@@ -1925,6 +1925,47 @@ TEST_F(GeoTypesTest, polygon_contains) {
}
}
+// A point within 1e-6 (in lat/lng degrees) of an edge is on the boundary and
not contained.
+// The same polygon is checked against all points, so later calls reuse the
vertices it converted
+// for the first one.
+TEST_F(GeoTypesTest, polygon_contains_point_near_edge) {
+ const char* wkt =
+ "POLYGON ((10 10, 50 10, 50 50, 10 50, 10 10), (20 20, 40 20, 40
40, 20 40, 20 "
+ "20))";
+ GeoParseStatus status;
+ auto polygon(GeoShape::from_wkt(wkt, strlen(wkt), status));
+ EXPECT_EQ(GeoParseStatus::GEO_PARSE_OK, status);
+ ASSERT_NE(nullptr, polygon);
+
+ auto contains = [&](double x, double y) {
+ GeoPoint point;
+ EXPECT_EQ(GeoParseStatus::GEO_PARSE_OK, point.from_coord(x, y));
+ return polygon->contains(&point);
+ };
+ for (int i = 0; i < 2; ++i) {
+ EXPECT_TRUE(contains(15, 30));
+ EXPECT_FALSE(contains(25, 30));
+ // outer loop edge on lng 50 and its vertex
+ EXPECT_FALSE(contains(50 - 5e-7, 30));
+ EXPECT_TRUE(contains(50 - 2e-6, 30));
+ EXPECT_FALSE(contains(50 - 5e-7, 50 - 5e-7));
+ // hole edge on lng 20
+ EXPECT_FALSE(contains(20 - 5e-7, 30));
+ EXPECT_TRUE(contains(20 - 2e-6, 30));
+ }
+
+ // A polygon decoded from its encoding checks the edges the same way.
+ std::string buf;
+ polygon->encode_to(&buf);
+ auto decoded(GeoShape::from_encoded(buf.data(), buf.size()));
+ ASSERT_NE(nullptr, decoded);
+ GeoPoint point;
+ EXPECT_EQ(GeoParseStatus::GEO_PARSE_OK, point.from_coord(50 - 5e-7, 30));
+ EXPECT_FALSE(decoded->contains(&point));
+ EXPECT_EQ(GeoParseStatus::GEO_PARSE_OK, point.from_coord(50 - 2e-6, 30));
+ EXPECT_TRUE(decoded->contains(&point));
+}
+
TEST_F(GeoTypesTest, polygon_parse_fail) {
{
const char* wkt = "POLYGON ((10 10, 50 10, 50 50, 10 50), (10 10 01))";
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]