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]

Reply via email to