Repository: ndsev/mapget (language: python)

Issue:
Switch from stx::format to fmt::format



Discussion / hints:

Fix patch:
diff --git a/.github/workflows/cmake.yaml b/.github/workflows/cmake.yaml
index 0945fcca..2c3101d5 100644
--- a/.github/workflows/cmake.yaml
+++ b/.github/workflows/cmake.yaml
@@ -43,7 +43,7 @@ jobs:
     runs-on: ${{ matrix.os }}
     strategy:
       matrix:
-        os: [macos-latest, windows-2019]
+        os: [macos-13, windows-2019]  # Currently, macos-latest is macos 12
         python-version: ["3.8", "3.9", "3.10", "3.11"]
     steps:
       - uses: actions/checkout@v2
@@ -56,7 +56,7 @@ jobs:
       - run: python -m pip install setuptools wheel
       - run: mkdir build
       - name: Build (macOS)
-        if: matrix.os == 'macos-latest' || matrix.os == 'macos-10.15'
+        if: matrix.os == 'macos-13'
         working-directory: build
         run: |
           python -m pip install delocate
diff --git a/.github/workflows/deploy.yaml b/.github/workflows/deploy.yaml
index db3aa074..2ed733d9 100644
--- a/.github/workflows/deploy.yaml
+++ b/.github/workflows/deploy.yaml
@@ -8,7 +8,7 @@ jobs:
     strategy:
       matrix:
         python-version: ["3.8", "3.9", "3.10", "3.11"]
-        os: [macos-latest, ubuntu-latest, windows-2019]
+        os: [macos-13, ubuntu-latest, windows-2019]
     runs-on: ubuntu-latest
     steps:
       - name: Fetch
diff --git a/CMakeLists.txt b/CMakeLists.txt
index 0b37feab..2404008a 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -16,7 +16,7 @@ option(MAPGET_WITH_HTTPLIB "Enable mapget-http-datasource and mapget-http-servic
 project(mapget)
 include(FetchContent)
 
-set(MAPGET_VERSION 0.3.0)
+set(MAPGET_VERSION 2024.1)
 
 set(CMAKE_CXX_STANDARD 17)
 set(CMAKE_CXX_STANDARD_REQUIRED ON)
@@ -60,22 +60,6 @@ list(APPEND CMAKE_MODULE_PATH "${CMAKE_CURRENT_SOURCE_DIR}/cmake/cmake-modules")
 ##############
 # deps
 
-if (NOT TARGET stx)
-  FetchContent_Declare(stx
-    GIT_REPOSITORY "https://github.com/Klebert-Engineering/stx.git"
-    GIT_TAG        "main"
-    GIT_SHALLOW    ON)
-  FetchContent_MakeAvailable(stx)
-endif()
-
-if (NOT TARGET spdlog::spdlog)
-  FetchContent_Declare(spdlog
-    GIT_REPOSITORY "https://github.com/gabime/spdlog.git"
-    GIT_TAG        "v1.x"
-    GIT_SHALLOW    ON)
-  FetchContent_MakeAvailable(spdlog)
-endif()
-
 set(SIMFIL_WITH_MODEL_JSON YES)
 if (NOT TARGET simfil)
   FetchContent_Declare(simfil
@@ -85,12 +69,13 @@ if (NOT TARGET simfil)
   FetchContent_MakeAvailable(simfil)
 endif()
 
-if (NOT TARGET bitsery)
-  FetchContent_Declare(bitsery
-    GIT_REPOSITORY "https://github.com/fraillt/bitsery.git"
-    GIT_TAG        "master"
+if (NOT TARGET spdlog::spdlog)
+  set(SPDLOG_FMT_EXTERNAL TRUE CACHE BOOL "Ensure that spdlog uses fmt from conan." FORCE)
+  FetchContent_Declare(spdlog
+    GIT_REPOSITORY "https://github.com/gabime/spdlog.git"
+    GIT_TAG        "v1.x"
     GIT_SHALLOW    ON)
-  FetchContent_MakeAvailable(bitsery)
+  FetchContent_MakeAvailable(spdlog)
 endif()
 
 if (MAPGET_WITH_WHEEL OR MAPGET_WITH_HTTPLIB OR MAPGET_ENABLE_TESTING)
@@ -180,8 +165,8 @@ if (MAPGET_WITH_SERVICE OR MAPGET_WITH_HTTPLIB OR MAPGET_ENABLE_TESTING)
 
     FetchContent_Declare(rocksdb
       GIT_REPOSITORY "https://github.com/facebook/rocksdb.git"
-      GIT_TAG        dc87847e65449ef1cb6f787c5d753cbe8562bff1 # Use version greater than v8.6.7 once released.
-      GIT_SHALLOW    OFF)  # Turn ON when using released tag.
+      GIT_TAG        v8.11.3
+      GIT_SHALLOW    ON)
     FetchContent_MakeAvailable(rocksdb)
   endif()
 
diff --git a/README.md b/README.md
index c6f4c16e..b0231891 100644
--- a/README.md
+++ b/README.md
@@ -76,6 +76,10 @@ A feature consists of a unique ID, some attributes, and some geometry. *mapget*
 also allows features to have a list of child feature IDs. **Note:** Feature geometry
 in *mapget* may always be 3D.
 
+* TODO: Document JSON representation.
+* TODO: Document Feature ID schemes.
+* TODO: Document Geometry Types.
+
 ## Map Tiles
 
 For performance reasons, *mapget* features are always served in a set covering
@@ -174,7 +178,7 @@ This example shows how you can write a minimal networked data source service.
 This example shows, how you can write a data source service in Python.
 You can simply `pip install mapget` to get access to the mapget Python API.
 
-## Retrieval Interface
+## REST API
 
 The `mapget` library provides simple C++ and HTTP/REST interfaces, which may be
 used to satisfy the following use-cases:
@@ -188,46 +192,14 @@ used to satisfy the following use-cases:
 The HTTP interface implemented in `mapget::HttpService` is a view on the C++ interface,
 which is implemented in `mapget::Service`. Detailed endpoint descriptions:
 
-```c++
-// Describe the connected Data Sources
-+ GET /sources():  list<DataSourceInfo>
-
-// Get streamed features, according to hard constraints.
-// With Accept-Encoding text/jsonl or application/binary
-+ POST /tiles(list<{
-    mapId: string,
-    layerId: string,
-    tileIds: list<TileId>,
-       maxKnownFieldIds*
-  }>, filter: optional<string>):
-  bytes<TileLayerStream>
-
-// Server status page
-+ GET /status(): text/html
-
-// Obtain a list of tile-layer combinations which provide a
-// feature that satisfies the given ID field constraints.
-// TODO: Not implemented
-+ GET /locate(typeId, map<string, Scalar>)
-  list<pair<TileId, LayerId>>
-
-// Instruct the cache to *try* to fill itself with map data
-// according to the provided constraints. No guarantees are
-// made as to the timeliness or completeness of this task.
-// TODO: Not implemented
-+ POST /populate(
-    spatialConstraint*,
-    {mapId*, layerId*, featureType*, zoomLevel*}) 
-
-// Write GeoJSON features for a tile back to a map data source
-// which has supportedOperations&WRITE.
-// TODO: Not implemented
-+ POST /tile(
-    mapId: string,
-    layerId: string,
-    tileId: TileId,
-    features: list<object>): void
-```
+| Endpoint   | Method | Description                                                                                                       | Input                                                                                                                                               | Output                                                                                                                                                                            |
+|------------|--------|-------------------------------------------------------------------------------------------------------------------|-----------------------------------------------------------------------------------------------------------------------------------------------------|-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
+| `/sources` | GET    | Describe the connected Data Sources                                                                               | None                                                                                                                                                | `application/json`: List of DataSourceInfo objects.                                                                                                                               |
+| `/tiles`   | POST   | Get streamed features, according to hard constraints. Accepts encoding types `text/jsonl` or `application/binary` | List of objects containing `mapId`, `layerId`, `tileIds`, and optional `maxKnownFieldIds`.                                                          | `text/jsonl` or `application/binary`                                                                                                                                              |
+| `/status`  | GET    | Server status page                                                                                                | None                                                                                                                                                | text/html                                                                                                                                                                         |
+| `/locate`  | POST   | Obtain a list of tile-layer combinations providing a feature that satisfies given ID field constraints.           | `application/json`: List of external references, where each is a Request object with `mapId`, `typeId` and `featureId` (list of external ID parts). | `application/json`: List of lists of Resolution objects, where each corresponds to the Request object index. Each Resolution object includes `tileId`, `typeId`, and `featureId`. |
+
+### Curl Call Example
 
 For example, the following curl call could be used to stream GeoJSON feature objects
 from the `MyMap` data source defined previously:
@@ -248,6 +220,8 @@ curl -X POST \
 }' "http://localhost:8080/tiles"
 ```
 
+### C++ Call Example
+
 If we use `"Accept: application/binary"` instead, we get a binary stream of
 tile data which we can also parse in C++, Python or JS. Here is an example in C++, using
 the `mapget::HttpClient` class:
@@ -277,6 +251,25 @@ void main(int argc, char const *argv[])
 
 Keep in mind, that you can also run a `mapget` service without any RPCs in your application. Check out [`examples/cpp/local-datasource`](examples/cpp/local-datasource/main.cpp) on how to do that.
 
+### About `locate`
+
+The `/locate` endpoint allows clients to obtain a list of tile-layer combinations that provide a feature satisfying given ID field constraints. This is crucial for applications needing to find specific data points within the massive datasets typically associated with map services. The endpoint uses a POST method due to the complexity and length of the queries, which involve resolving external references to data.
+
+**Details:**
+
+- **Input:** The input is a list of requests, each corresponding to an external reference that needs to be resolved. Each request object includes:
+    - `typeId`: Specifies the type of feature to locate.
+    - `featureId`: An array representing the external ID parts, where each part consists of a field name and value. This array is used to identify the feature uniquely. The used id scheme may be a secondary scheme.
+
+- **Output:** The output is a nested list structure where each outer list corresponds to an input request object. Each of these lists contains resolution objects that provide details about where the requested feature can be found within the map data. Each resolution object includes:
+    - `tileId`: The key of the map tile containing the feature.
+    - `typeId`: The type of feature found, which should match the `typeId` specified in the request.
+    - `featureId`: An array of ID parts similar to the input but typically using the primary feature ID scheme of the data source.
+
+This design allows clients to batch queries for multiple features in a single request, improving efficiency and reducing the number of required HTTP requests. It also supports the use of different ID schemes, accommodating scenarios where the request and response might use different identifiers for the same data due to varying external reference standards.
+
+Note, that a locate resolution must be provided by a datasource for the specified map, which implements the `onLocateRequest` callback.
+
 ### erdblick-mapget-datasource communication pattern
 
 TODO: expand and polish this section stub.
diff --git a/docs/components.png b/docs/components.png
index c9acee03..0ba80a09 100644
Binary files a/docs/components.png and b/docs/components.png differ
diff --git a/libs/http-datasource/include/mapget/http-datasource/datasource-client.h b/libs/http-datasource/include/mapget/http-datasource/datasource-client.h
index 4c008502..a0d28d34 100644
--- a/libs/http-datasource/include/mapget/http-datasource/datasource-client.h
+++ b/libs/http-datasource/include/mapget/http-datasource/datasource-client.h
@@ -30,6 +30,7 @@ class RemoteDataSource : public DataSource
     DataSourceInfo info() override;
     void fill(TileFeatureLayer::Ptr const& featureTile) override;
     TileFeatureLayer::Ptr get(MapTileKey const& k, Cache::Ptr& cache, DataSourceInfo const& info) override;
+    std::optional<LocateResponse> locate(const mapget::LocateRequest &req) override;
 
 private:
     // DataSourceInfo is fetched in the constructor
@@ -64,6 +65,7 @@ class RemoteDataSourceProcess : public DataSource
     DataSourceInfo info() override;
     void fill(TileFeatureLayer::Ptr const& featureTile) override;
     TileFeatureLayer::Ptr get(MapTileKey const& k, Cache::Ptr& cache, DataSourceInfo const& info) override;
+    std::optional<LocateResponse> locate(const mapget::LocateRequest &req) override;
 
 private:
     std::unique_ptr<RemoteDataSource> remoteSource_;
diff --git a/libs/http-datasource/include/mapget/http-datasource/datasource-server.h b/libs/http-datasource/include/mapget/http-datasource/datasource-server.h
index afbe3c09..e77c573c 100644
--- a/libs/http-datasource/include/mapget/http-datasource/datasource-server.h
+++ b/libs/http-datasource/include/mapget/http-datasource/datasource-server.h
@@ -2,6 +2,7 @@
 
 #include "mapget/model/featurelayer.h"
 #include "mapget/detail/http-server.h"
+#include "mapget/service/locate.h"
 
 namespace mapget
 {
@@ -32,6 +33,14 @@ class DataSourceServer : public HttpServer
      */
     DataSourceServer& onTileRequest(std::function<void(TileFeatureLayer::Ptr)> const&);
 
+    /**
+     * Set the callback which will be invoked when a `/locate`-request is received.
+     * The callback argument is a LocateRequest, which the callback
+     * must process according to its available data.
+     */
+    DataSourceServer&
+    onLocateRequest(std::function<std::optional<LocateResponse>(LocateRequest const&)> const&);
+
     /**
      * Get the DataSourceInfo metadata which this instance was constructed with.
      */
diff --git a/libs/http-datasource/src/datasource-client.cpp b/libs/http-datasource/src/datasource-client.cpp
index 4431b60f..fa9daffd 100644
--- a/libs/http-datasource/src/datasource-client.cpp
+++ b/libs/http-datasource/src/datasource-client.cpp
@@ -19,7 +19,7 @@ RemoteDataSource::RemoteDataSource(const std::string& host, uint16_t port)
     if (info_.nodeId_.empty()) {
         // Unique node IDs are required for the field offsets.
         throw logRuntimeError(
-            stx::format("Remote data source is missing node ID! Source info: {}",
+            fmt::format("Remote data source is missing node ID! Source info: {}",
                 fetchedInfoJson->body));
     }
 
@@ -46,7 +46,7 @@ RemoteDataSource::get(const MapTileKey& k, Cache::Ptr& cache, const DataSourceIn
     auto& client = httpClients_[(nextClient_++) % httpClients_.size()];
 
     // Send a GET tile request.
-    auto tileResponse = client.Get(stx::format(
+    auto tileResponse = client.Get(fmt::format(
         "/tile?layer={}&tileId={}&fieldsOffset={}",
         k.layerId_,
         k.tileId_.value_,
@@ -72,6 +72,33 @@ RemoteDataSource::get(const MapTileKey& k, Cache::Ptr& cache, const DataSourceIn
     return result;
 }
 
+std::optional<LocateResponse> RemoteDataSource::locate(const LocateRequest& req)
+{
+    // Round-robin usage of http clients to facilitate parallel requests.
+    auto& client = httpClients_[(nextClient_++) % httpClients_.size()];
+
+    // Send a GET tile request.
+    auto locateResponse = client.Post(
+        fmt::format("/locate"), req.serialize().dump(), "application/json");
+
+    // Check that the response is OK.
+    if (!locateResponse || locateResponse->status >= 300) {
+        // Forward to base class get(). This will instantiate a
+        // default TileFeatureLayer and call fill(). In our implementation
+        // of fill, we set an error.
+        // TODO: Read HTTPLIB_ERROR header, more log output.
+        return {};
+    }
+
+    // Check the response body for expected content.
+    auto responseJson = nlohmann::json::parse(locateResponse->body);
+    if (responseJson.is_null()) {
+        return {};
+    }
+
+    return LocateResponse(responseJson);
+}
+
 RemoteDataSourceProcess::RemoteDataSourceProcess(std::string const& commandLine)
 {
     auto stderrCallback = [this](const char* bytes, size_t n)
@@ -155,4 +182,11 @@ RemoteDataSourceProcess::get(MapTileKey const& k, Cache::Ptr& cache, DataSourceI
     return remoteSource_->get(k, cache, info);
 }
 
+std::optional<LocateResponse> RemoteDataSourceProcess::locate(const LocateRequest& req)
+{
+    if (!remoteSource_)
+        throw logRuntimeError("Remote data source is not initialized.");
+    return remoteSource_->locate(req);
+}
+
 }
diff --git a/libs/http-datasource/src/datasource-server.cpp b/libs/http-datasource/src/datasource-server.cpp
index 5567b0b1..1200638f 100644
--- a/libs/http-datasource/src/datasource-server.cpp
+++ b/libs/http-datasource/src/datasource-server.cpp
@@ -12,6 +12,7 @@ struct DataSourceServer::Impl
 {
     DataSourceInfo info_;
     std::function<void(TileFeatureLayer::Ptr)> tileCallback_;
+    std::function<std::optional<LocateResponse>(const LocateRequest&)> locateCallback_;
     std::shared_ptr<Fields> fields_;
 
     explicit Impl(DataSourceInfo info)
@@ -29,11 +30,19 @@ DataSourceServer::DataSourceServer(DataSourceInfo const& info)
 DataSourceServer::~DataSourceServer() = default;
 
 DataSourceServer&
-DataSourceServer::onTileRequest(std::function<void(TileFeatureLayer::Ptr)> const& callback) {
+DataSourceServer::onTileRequest(std::function<void(TileFeatureLayer::Ptr)> const& callback)
+{
     impl_->tileCallback_ = callback;
     return *this;
 }
 
+DataSourceServer& DataSourceServer::onLocateRequest(
+    const std::function<std::optional<LocateResponse>(const LocateRequest&)>& callback)
+{
+    impl_->locateCallback_ = callback;
+    return *this;
+}
+
 DataSourceInfo const& DataSourceServer::info() {
     return impl_->info_;
 }
@@ -92,6 +101,22 @@ void DataSourceServer::setup(httplib::Server& server)
             nlohmann::json j = impl_->info_.toJson();
             res.set_content(j.dump(), "application/json");
         });
+
+    // Set up POST /locate endpoint
+    server.Post(
+        "/locate",
+        [this](const httplib::Request& req, httplib::Response& res) {
+            LocateRequest parsedReq(nlohmann::json::parse(req.body));
+            auto responseJson = nlohmann::json();
+
+            if (impl_->locateCallback_) {
+                if (auto response = impl_->locateCallback_(parsedReq)) {
+                    responseJson = response->serialize();
+                }
+            }
+
+            res.set_content(responseJson.dump(), "application/json");
+        });
 }
 
 }  // namespace mapget
diff --git a/libs/http-datasource/src/http-server.cpp b/libs/http-datasource/src/http-server.cpp
index 9d937c99..bc029d00 100644
--- a/libs/http-datasource/src/http-server.cpp
+++ b/libs/http-datasource/src/http-server.cpp
@@ -4,9 +4,9 @@
 #include "httplib.h"
 #include <csignal>
 #include <atomic>
+#include <ranges>
 
-#include "stx/format.h"
-#include "stx/string.h"
+#include "fmt/format.h"
 
 namespace mapget
 {
@@ -78,7 +78,7 @@ void HttpServer::go(
 
     std::this_thread::sleep_for(std::chrono::milliseconds(waitMs));
     if (!impl_->server_.is_running() || !impl_->server_.is_valid())
-        throw logRuntimeError(stx::format("Could not start HttpServer on {}:{}", interfaceAddr, port));
+        throw logRuntimeError(fmt::format("Could not start HttpServer on {}:{}", interfaceAddr, port));
 }
 
 bool HttpServer::isRunning() {
@@ -115,10 +115,13 @@ void HttpServer::waitForSignal() {
 
 bool HttpServer::mountFileSystem(const std::string& pathFromTo)
 {
-    auto parts = stx::split(pathFromTo, ":");
-    if (parts.size() == 1)
-        return impl_->server_.set_mount_point("/", parts[0]);
-    return impl_->server_.set_mount_point(parts[0], parts[1]);
+    using namespace std::ranges;
+    auto parts = pathFromTo | views::split(':') | views::transform([](auto&& s){return std::string(&*s.begin(), distance(s));});
+    auto partsVec = std::vector<std::string>(parts.begin(), parts.end());
+
+    if (partsVec.size() == 1)
+        return impl_->server_.set_mount_point("/", partsVec[0]);
+    return impl_->server_.set_mount_point(partsVec[0], partsVec[1]);
 }
 
 void HttpServer::printPortToStdOut(bool enabled) {
diff --git a/libs/http-service/src/cli.cpp b/libs/http-service/src/cli.cpp
index b4bec5ba..e5800d2b 100644
--- a/libs/http-service/src/cli.cpp
+++ b/libs/http-service/src/cli.cpp
@@ -73,7 +73,7 @@ struct ServeCommand
             cache = std::make_shared<MemCache>(cacheMaxTiles_);
         }
         else {
-            logRuntimeError(stx::format("Cache type {} not supported!", cacheType_));
+            logRuntimeError(fmt::format("Cache type {} not supported!", cacheType_));
         }
 
         HttpService srv(cache);
diff --git a/libs/http-service/src/http-client.cpp b/libs/http-service/src/http-client.cpp
index c9dc01d2..4d06e415 100644
--- a/libs/http-service/src/http-client.cpp
+++ b/libs/http-service/src/http-client.cpp
@@ -17,7 +17,7 @@ struct HttpClient::Impl {
         auto sourcesJson = client_.Get("/sources");
         if (!sourcesJson || sourcesJson->status != 200)
             throw logRuntimeError(
-                stx::format("Failed to fetch sources: [{}]", sourcesJson->status));
+                fmt::format("Failed to fetch sources: [{}]", sourcesJson->status));
         for (auto const& info : nlohmann::json::parse(sourcesJson->body)) {
             auto parsedInfo = DataSourceInfo::fromJson(info);
             sources_.emplace(parsedInfo.mapId_, parsedInfo);
diff --git a/libs/http-service/src/http-service.cpp b/libs/http-service/src/http-service.cpp
index 8254f036..efeb1e17 100644
--- a/libs/http-service/src/http-service.cpp
+++ b/libs/http-service/src/http-service.cpp
@@ -50,7 +50,7 @@ struct HttpService::Impl
                 responseType_ = binaryMimeType;
                 return;
             }
-            throw logRuntimeError(stx::format("Unknown Accept-Header value {}", responseType_));
+            throw logRuntimeError(fmt::format("Unknown Accept-Header value {}", responseType_));
         }
 
         void addResult(TileFeatureLayer::Ptr const& result)
@@ -211,6 +211,26 @@ struct HttpService::Impl
         oss << "</body></html>";
         res.set_content(oss.str(), "text/html");
     }
+
+    void handleLocateRequest(const httplib::Request& req, httplib::Response& res)
+    {
+        // Parse the JSON request.
+        nlohmann::json j = nlohmann::json::parse(req.body);
+        auto requestsJson = j["requests"];
+        auto allResponsesJson = nlohmann::json::array();
+
+        for (auto const& locateReqJson : requestsJson) {
+            LocateRequest locateReq{locateReqJson};
+            auto responsesJson = nlohmann::json::array();
+            for (auto const& resp : self_.locate(locateReq))
+                responsesJson.emplace_back(resp.serialize());
+            allResponsesJson.emplace_back(responsesJson);
+        }
+
+        res.set_content(
+            nlohmann::json::object({{"responses", allResponsesJson}}).dump(),
+            "application/json");
+    }
 };
 
 HttpService::HttpService(Cache::Ptr cache) : Service(std::move(cache)), impl_(std::make_unique<Impl>(*this))
@@ -240,6 +260,13 @@ void HttpService::setup(httplib::Server& server)
         {
             impl_->handleStatusRequest(req, res);
         });
+
+    server.Post(
+        "/locate",
+        [this](const httplib::Request& req, httplib::Response& res)
+        {
+            impl_->handleLocateRequest(req, res);
+        });
 }
 
 }  // namespace mapget
diff --git a/libs/logging/CMakeLists.txt b/libs/logging/CMakeLists.txt
index 73446493..e4e20928 100644
--- a/libs/logging/CMakeLists.txt
+++ b/libs/logging/CMakeLists.txt
@@ -9,7 +9,8 @@ add_library(mapget-log STATIC
 
 target_link_libraries(mapget-log
   PUBLIC
-    spdlog::spdlog)
+    spdlog::spdlog
+    fmt::fmt)
 
 target_include_directories(mapget-log
   PUBLIC
diff --git a/libs/model/CMakeLists.txt b/libs/model/CMakeLists.txt
index 6c47bf22..2ec31687 100644
--- a/libs/model/CMakeLists.txt
+++ b/libs/model/CMakeLists.txt
@@ -11,6 +11,7 @@ add_library(mapget-model STATIC
   include/mapget/model/tileid.h
   include/mapget/model/featureid.h
   include/mapget/model/stream.h
+  include/mapget/model/relation.h
 
   src/fields.cpp
   src/layer.cpp
@@ -21,7 +22,8 @@ add_library(mapget-model STATIC
   src/attrlayer.cpp
   src/tileid.cpp
   src/featureid.cpp
-  src/stream.cpp)
+  src/stream.cpp
+  src/relation.cpp)
 
 target_include_directories(mapget-model
   PUBLIC
@@ -33,7 +35,6 @@ target_link_libraries(mapget-model
   PUBLIC
     mapget-log
     sfl::sfl
-    stx::stx
     Bitsery::bitsery
     simfil::simfil
     nlohmann_json::nlohmann_json)
diff --git a/libs/model/include/mapget/model/attr.h b/libs/model/include/mapget/model/attr.h
index d8a1cb9a..c728e58c 100644
--- a/libs/model/include/mapget/model/attr.h
+++ b/libs/model/include/mapget/model/attr.h
@@ -13,6 +13,7 @@ namespace mapget
 class Attribute : public simfil::ProceduralObject<2, Attribute>
 {
     friend class TileFeatureLayer;
+    template<typename> friend struct simfil::shared_model_ptr;
 
 public:
     /**
@@ -56,16 +57,19 @@ class Attribute : public simfil::ProceduralObject<2, Attribute>
         template<typename S>
         void serialize(S& s) {
             s.value1b(direction_);
-            s.value4b(validity_.value_);
+            s.object(validity_);
             s.value4b(fields_);
             s.value2b(name_);
         }
     };
 
-    Attribute(Data& data, simfil::ModelConstPtr l, simfil::ModelNodeAddress a);
+    Attribute(Data* data, simfil::ModelConstPtr l, simfil::ModelNodeAddress a);
+    Attribute() = default;
 
-    /** Reference to the actual stored data for the attribute. */
-    Data& data_;
+    /**
+     * Pointer to the actual data stored for the attribute.
+     */
+    Data* data_ = nullptr;
 };
 
 }
\ No newline at end of file
diff --git a/libs/model/include/mapget/model/attrlayer.h b/libs/model/include/mapget/model/attrlayer.h
index 877a2e85..5afc57ee 100644
--- a/libs/model/include/mapget/model/attrlayer.h
+++ b/libs/model/include/mapget/model/attrlayer.h
@@ -13,12 +13,11 @@ class AttributeLayerList;
  * For example, all feature attributes which refer to road rules, such
  * as speed limits, might belong to the same attribute layer.
  */
-class AttributeLayer : protected simfil::Object
+class AttributeLayer : public simfil::Object
 {
     friend class TileFeatureLayer;
     friend class bitsery::Access;
-    friend struct simfil::shared_model_ptr<simfil::ModelNode>;
-    friend ModelNode::Ptr;
+    template<typename> friend struct simfil::shared_model_ptr;
 
 public:
     /**
@@ -35,18 +34,19 @@ class AttributeLayer : protected simfil::Object
 
 protected:
     AttributeLayer(simfil::ArrayIndex i, simfil::ModelConstPtr l, simfil::ModelNodeAddress a);
+    AttributeLayer() = default;
 };
 
 /**
  * Collection of attribute layers - this is merely a typed dict which
  * stores (layer-name, layer) pairs.
  */
-class AttributeLayerList : protected simfil::Object
+class AttributeLayerList : public simfil::Object
 {
     friend class TileFeatureLayer;
     friend class bitsery::Access;
     friend class Feature;
-    friend ModelNode::Ptr;
+    template<typename> friend struct simfil::shared_model_ptr;
 
 public:
     /**
@@ -62,6 +62,7 @@ class AttributeLayerList : protected simfil::Object
 
 protected:
     AttributeLayerList(simfil::ArrayIndex i, simfil::ModelConstPtr l, simfil::ModelNodeAddress a);
+    AttributeLayerList() = default;
 };
 
-}
\ No newline at end of file
+}
diff --git a/libs/model/include/mapget/model/feature.h b/libs/model/include/mapget/model/feature.h
index 13f3322f..f78b5a4f 100644
--- a/libs/model/include/mapget/model/feature.h
+++ b/libs/model/include/mapget/model/feature.h
@@ -4,6 +4,7 @@
 #include "attrlayer.h"
 #include "featureid.h"
 #include "tileid.h"
+#include "relation.h"
 
 #include "nlohmann/json.hpp"
 
@@ -35,14 +36,23 @@ namespace mapget
  *       },
  *       <non-layer-attr-name>: <non-layer-attr-value>, ...
  *     },
- *     children: [<child-id-list>]
+ *     relations: [
+ *       {
+ *         name: <relation-name>,
+ *         target: <target-feature-id>,
+ *         targetValidity: <geometry>,
+ *         sourceValidity: <geometry>
+ *       },
+ *       ...
+ *     ]
  *   }
  */
-class Feature : protected simfil::MandatoryDerivedModelNodeBase<TileFeatureLayer>
+class Feature : public simfil::MandatoryDerivedModelNodeBase<TileFeatureLayer>
 {
     friend class bitsery::Access;
     friend class TileFeatureLayer;
-    friend ModelNode::Ptr;
+    friend class BoundFeature;
+    template<typename> friend struct simfil::shared_model_ptr;
 
 public:
     /** Get the name of this feature's type. */
@@ -51,17 +61,27 @@ class Feature : protected simfil::MandatoryDerivedModelNodeBase<TileFeatureLayer
     /** Get this feature's ID. */
     [[nodiscard]] model_ptr<FeatureId> id() const;
 
-    /** Get this feature's GeometryCollection. */
+    /**
+     * Get this feature's GeometryCollection. The non-const version adds a
+     * GeometryCollection if the feature does not have one yet.
+     */
     model_ptr<GeometryCollection> geom();
+    [[nodiscard]] model_ptr<GeometryCollection> geom() const;
+    [[nodiscard]] model_ptr<Geometry> firstGeometry() const;
 
-    /** Get this feature's Attribute layers. */
-    [[nodiscard]] model_ptr<AttributeLayerList> attributeLayers();
+    /**
+     * Get this feature's Attribute layers. The non-const version adds a
+     * AttributeLayerList if the feature does not have one yet.
+     */
+    model_ptr<AttributeLayerList> attributeLayers();
+    [[nodiscard]] model_ptr<AttributeLayerList> attributeLayers() const;
 
-    /** Get this feature's un-layered attributes. */
+    /**
+     * Get this feature's un-layered attributes.The non-const version adds a
+     * generic attribute storage if the feature does not have one yet.
+     */
     model_ptr<Object> attributes();
-
-    /** Get this feature's child ID list. */
-    [[nodiscard]] model_ptr<Array> children();
+    [[nodiscard]] model_ptr<Object> attributes() const;
 
     /** Add a point to the feature. */
     void addPoint(Point const& p);
@@ -98,6 +118,30 @@ class Feature : protected simfil::MandatoryDerivedModelNodeBase<TileFeatureLayer
      */
     using simfil::MandatoryDerivedModelNodeBase<TileFeatureLayer>::model;
 
+    /**
+     * Create a new named relation and immediately insert it into the feature.
+     * Variants:
+     * (1) Creates a new feature id for the target, based on the given ID parts.
+     * (2) Use an existing feature id for the target.
+     * (3) Use an existing relation.
+     */
+    void addRelation(std::string_view const& name, std::string_view const& targetType,
+        KeyValueViewPairs const& targetIdParts);
+    void addRelation(std::string_view const& name, model_ptr<FeatureId> const& target);
+    void addRelation(model_ptr<Relation> const& relation);
+
+    /**
+     * Visit all added relations. Return false from the callback to abort.
+     * Returns false if aborted, true otherwise.
+     */
+    bool forEachRelation(std::function<bool(model_ptr<Relation> const&)> const& callback) const;
+
+    /** Get the number of added relations. */
+    [[nodiscard]] uint32_t numRelations() const;
+
+    /** Get a relation at a specific index. */
+    [[nodiscard]] model_ptr<Relation> getRelation(uint32_t index) const;
+
 protected:
     /**
      * Simfil Model-Node Functions
@@ -109,6 +153,15 @@ class Feature : protected simfil::MandatoryDerivedModelNodeBase<TileFeatureLayer
     [[nodiscard]] simfil::FieldId keyAt(int64_t) const override;
     [[nodiscard]] bool iterate(IterCallback const& cb) const override;
 
+    /**
+     * Get this feature's relation list.The non-const version adds a
+     * Relation list if the feature does not have one yet.
+     * Note: This accessor is private, to ensure that the relations
+     * array really only ever contains relations.
+     */
+    [[nodiscard]] model_ptr<Array> relations();
+    [[nodiscard]] model_ptr<Array> relations() const;
+
     /**
      * Feature Data
      */
@@ -118,22 +171,23 @@ class Feature : protected simfil::MandatoryDerivedModelNodeBase<TileFeatureLayer
         simfil::ModelNodeAddress geom_;
         simfil::ModelNodeAddress attrLayers_;
         simfil::ModelNodeAddress attrs_;
-        simfil::ModelNodeAddress children_;
+        simfil::ModelNodeAddress relations_;
 
         template <typename S>
         void serialize(S& s)
         {
-            s.value4b(id_.value_);
-            s.value4b(geom_.value_);
-            s.value4b(attrLayers_.value_);
-            s.value4b(attrs_.value_);
-            s.value4b(children_.value_);
+            s.object(id_);
+            s.object(geom_);
+            s.object(attrLayers_);
+            s.object(attrs_);
+            s.object(relations_);
         }
     };
 
     Feature(Data& d, simfil::ModelConstPtr l, simfil::ModelNodeAddress a);
+    Feature() = default;
 
-    Data& data_;
+    Data* data_ = nullptr;
 
     // We keep the fields in a tiny vector on the stack,
     // because their number is dynamic, as a variable number
@@ -153,9 +207,10 @@ class Feature : protected simfil::MandatoryDerivedModelNodeBase<TileFeatureLayer
         [[nodiscard]] bool iterate(IterCallback const& cb) const override;
 
         FeaturePropertyView(Data& d, simfil::ModelConstPtr l, simfil::ModelNodeAddress a);
+        FeaturePropertyView() = default;
 
-        Data& data_;
-        std::optional<model_ptr<Object>> attrs_;
+        Data* data_ = nullptr;
+        model_ptr<Object> attrs_;
     };
 };
 
diff --git a/libs/model/include/mapget/model/featureid.h b/libs/model/include/mapget/model/featureid.h
index 08c373f6..8d848417 100644
--- a/libs/model/include/mapget/model/featureid.h
+++ b/libs/model/include/mapget/model/featureid.h
@@ -2,6 +2,7 @@
 
 #include "simfil/model/nodes.h"
 #include <functional>
+#include "sfl/small_vector.hpp"
 
 namespace mapget
 {
@@ -18,15 +19,30 @@ using GeometryCollection = simfil::GeometryCollection;
 using Geometry = simfil::Geometry;
 using GeomType = simfil::Geometry::GeomType;
 
+/**
+ * The KeyValuePairsView type is a vector of pairs, where each pair
+ * consists of a string_view key and a variant value that can be
+ * either an int64_t or a string_view. It is used as the interface-
+ * type for feature id parts. By using sfl::small_vector instead of
+ * std::vector, it is kept on the stack.
+ */
+using KeyValueViewPairs = sfl::small_vector<std::pair<
+    std::string_view,
+    std::variant<int64_t, std::string_view>>, 16>;
+using KeyValuePairs = sfl::small_vector<std::pair<
+    std::string,
+    std::variant<int64_t, std::string>>, 16>;
+
 /**
  * Unique feature ID
  */
-class FeatureId : protected simfil::MandatoryDerivedModelNodeBase<TileFeatureLayer>
+class FeatureId : public simfil::MandatoryDerivedModelNodeBase<TileFeatureLayer>
 {
     friend class TileFeatureLayer;
     friend class Feature;
+    friend class Relation;
     friend class bitsery::Access;
-    friend ModelNode::Ptr;
+    template<typename> friend struct simfil::shared_model_ptr;
 
 public:
     /** Convert the FeatureId to a string like `<type-id>.<part-value-0>...<part-value-n>` */
@@ -35,6 +51,9 @@ class FeatureId : protected simfil::MandatoryDerivedModelNodeBase<TileFeatureLay
     /** Get the feature ID's type id. */
     [[nodiscard]] std::string_view typeId() const;
 
+    /** Get all id-part key-value-pairs (including the common prefix). */
+    [[nodiscard]] KeyValueViewPairs keyValuePairs() const;
+
 protected:
     /**
      * Internal Node Access APIs
@@ -56,13 +75,14 @@ class FeatureId : protected simfil::MandatoryDerivedModelNodeBase<TileFeatureLay
         void serialize(S& s) {
             s.value1b(useCommonTilePrefix_);
             s.value2b(typeId_);
-            s.value4b(idParts_.value_);
+            s.object(idParts_);
         }
     };
 
     FeatureId(Data& data, simfil::ModelConstPtr l, simfil::ModelNodeAddress a);
+    FeatureId() = default;
 
-    Data& data_;
+    Data* data_ = nullptr;
 
     // Optional because resolve must be called, in
     // the constructor body.
diff --git a/libs/model/include/mapget/model/featurelayer.h b/libs/model/include/mapget/model/featurelayer.h
index 058308f7..b9e9ddc8 100644
--- a/libs/model/include/mapget/model/featurelayer.h
+++ b/libs/model/include/mapget/model/featurelayer.h
@@ -9,19 +9,11 @@
 #include "layer.h"
 #include "feature.h"
 #include "attrlayer.h"
+#include "relation.h"
 
 namespace mapget
 {
 
-/**
- * The KeyValuePairs type is a vector of pairs, where each pair
- * consists of a string_view key and a variant value that can be
- * either an int64_t or a string_view.
- */
-using KeyValuePairs = std::vector<std::pair<
-    std::string_view,
-    std::variant<int64_t, std::string_view>>>;
-
 /**
  * Callback type for a function which returns a field name cache instance
  * for a given node identifier.
@@ -37,6 +29,7 @@ class TileFeatureLayer : public TileLayer, public simfil::ModelPool
 {
     friend class Feature;
     friend class FeatureId;
+    friend class Relation;
 
 public:
     /**
@@ -59,7 +52,7 @@ class TileFeatureLayer : public TileLayer, public simfil::ModelPool
         std::string const& nodeId,
         std::string const& mapId,
         std::shared_ptr<LayerInfo> const& layerInfo,
-        std::shared_ptr<Fields> const& fields
+        std::shared_ptr<simfil::Fields> const& fields
     );
 
     /**
@@ -78,8 +71,9 @@ class TileFeatureLayer : public TileLayer, public simfil::ModelPool
 
     /**
      * Set common id prefix for all features in this layer.
+     * Note: The prefix MUST be set before any feature is added to the tile.
      */
-    void setPrefix(KeyValuePairs const& prefix);
+    void setPrefix(KeyValueViewPairs const& prefix);
 
     /** Destructor for the TileFeatureLayer class. */
     ~TileFeatureLayer() override;
@@ -95,8 +89,7 @@ class TileFeatureLayer : public TileLayer, public simfil::ModelPool
      * prefix. If empty, an error will be thrown.
      */
     model_ptr<Feature> newFeature(
-        std::string_view const& typeId,
-        KeyValuePairs const& featureIdParts);
+        std::string_view const& typeId, KeyValueViewPairs const& featureIdParts);
 
     /**
      * Create a new feature id. Use this function to create a reference to another
@@ -105,8 +98,16 @@ class TileFeatureLayer : public TileLayer, public simfil::ModelPool
      * different tile.
      */
     model_ptr<FeatureId> newFeatureId(
-        std::string_view const& typeId,
-        KeyValuePairs const& featureIdParts);
+        std::string_view const& typeId, KeyValueViewPairs const& featureIdParts);
+
+    /**
+     * Create a new relation. Use this function to create a named reference to another
+     * feature, which may also have optional source/target validity geometry.
+     * Relations must be stored in the feature's special relations-list.
+     */
+    model_ptr<Relation> newRelation(
+        std::string_view const& name,
+        model_ptr<FeatureId> const& target);
 
     /**
      * Validate that a unique id composition exists that matches this feature id,
@@ -114,12 +115,12 @@ class TileFeatureLayer : public TileLayer, public simfil::ModelPool
      * The order of values in KeyValuePairs must be the same as in the composition!
      * @param typeId Feature type id, throws error if the type was not registered.
      * @param featureIdParts Uniquely identifying information for the feature.
-     * @param includeTilePrefix True if the id should be evaluated with this tile's prefix prepended.
+     * @param validateForNewFeature True if the id should be evaluated with this tile's prefix prepended.
      */
     bool validFeatureId(
         const std::string_view& typeId,
-        KeyValuePairs const& featureIdParts,
-        bool includeTilePrefix);
+        KeyValueViewPairs const& featureIdParts,
+        bool validateForNewFeature);
 
     /**
      * Create a new named attribute, which may be inserted into an attribute layer.
@@ -167,19 +168,40 @@ class TileFeatureLayer : public TileLayer, public simfil::ModelPool
     Iterator end() const;
 
     /** (De-)Serialization */
-   void write(std::ostream& outputStream) override;
+    void write(std::ostream& outputStream) override;
+
+    /** Convert to GeoJSON geometry collection. */
+    nlohmann::json toGeoJson() const;
+
+    /** Access number of stored features */
+    size_t size() const;
 
-   /** Convert to GeoJSON geometry collection. */
-   nlohmann::json toGeoJson() const;
+    /** Access feature at index i */
+    model_ptr<Feature> at(size_t i) const;
 
-   /** Access number of stored features */
-   size_t size() const;
+    /** Access feature through its id. */
+    model_ptr<Feature> find(std::string_view const& type, KeyValueViewPairs const& queryIdParts) const;
+    model_ptr<Feature> find(std::string_view const& type, KeyValuePairs const& queryIdParts) const;
 
-   /** Access feature at index i */
-   model_ptr<Feature> at(size_t i) const;
+    /** Shared pointer type */
+    using Ptr = std::shared_ptr<TileFeatureLayer>;
 
-   /** Shared pointer type */
-   using Ptr = std::shared_ptr<TileFeatureLayer>;
+    /**
+     * Get this pool's simfil evaluation environment.
+     */
+    simfil::Environment& evaluationEnvironment();
+
+    /**
+     * Get a potentially cached compiled simfil expression for a simfil string.
+     */
+    simfil::ExprPtr const& compiledExpression(std::string_view const& expr);
+
+    /**
+     * Change the fields dict of this model to a different one.
+     * Note: This will potentially create new field entries in the newDict,
+     * for field names which were not there before.
+     */
+    void setFieldNames(std::shared_ptr<simfil::Fields> const& newDict) override;
 
 protected:
     /**
@@ -193,14 +215,17 @@ class TileFeatureLayer : public TileLayer, public simfil::ModelPool
         Attributes,
         AttributeLayers,
         AttributeLayerLists,
-        Icons
+        Relations,
     };
 
     /**
      * The featureIdPrefix function returns common ID parts,
      * which are shared by all features in this layer.
      */
-    std::optional<model_ptr<Object>> featureIdPrefix();
+    model_ptr<Object> featureIdPrefix();
+
+    /** Get the primary id composition for the given feature type. */
+    std::vector<IdPart> const& getPrimaryIdComposition(std::string_view const& type) const;
 
     /**
      * Create a new attribute layer collection.
@@ -215,22 +240,13 @@ class TileFeatureLayer : public TileLayer, public simfil::ModelPool
     model_ptr<Attribute> resolveAttribute(simfil::ModelNode const& n) const;
     model_ptr<Feature> resolveFeature(simfil::ModelNode const& n) const;
     model_ptr<FeatureId> resolveFeatureId(simfil::ModelNode const& n) const;
+    model_ptr<Relation> resolveRelation(simfil::ModelNode const& n) const;
 
     /**
      * Generic node resolution overload.
      */
     void resolve(const simfil::ModelNode &n, const ResolveFn &cb) const override;
 
-    /**
-     * Get this pool's simfil evaluation environment.
-     */
-    simfil::Environment& evaluationEnvironment();
-
-    /**
-     * Get a potentially cached compiled simfil expression for a simfil string.
-     */
-    simfil::ExprPtr const& compiledExpression(std::string_view const& expr);
-
     struct Impl;
     std::unique_ptr<Impl> impl_;
 };
diff --git a/libs/model/include/mapget/model/fields.h b/libs/model/include/mapget/model/fields.h
index fe9e91c2..48d32f5a 100644
--- a/libs/model/include/mapget/model/fields.h
+++ b/libs/model/include/mapget/model/fields.h
@@ -25,10 +25,14 @@ struct Fields : public simfil::Fields
         IdStr = NextStaticId,
         TypeIdStr,
         LayerStr,
-        ChildrenStr,
+        RelationsStr,
         DirectionStr,
         ValidityStr,
         PropertiesStr,
+        NameStr,
+        TargetStr,
+        SourceValidityStr,
+        TargetValidityStr
     };
 
     explicit Fields(const std::string_view& nodeId);
diff --git a/libs/model/include/mapget/model/info.h b/libs/model/include/mapget/model/info.h
index cfa3d72e..71822f47 100644
--- a/libs/model/include/mapget/model/info.h
+++ b/libs/model/include/mapget/model/info.h
@@ -102,6 +102,8 @@ struct FeatureTypeInfo
     /**
      * List of allowed unique id compositions (each id composition is a list of id parts)
      * A single id composition must never have more than 16 parts.
+     * The first unique id composition in the list is the primary, which must be
+     * used by all features. Secondary compositions may only be used by references/relations.
      */
     std::vector<std::vector<IdPart>> uniqueIdCompositions_;
 
diff --git a/libs/model/include/mapget/model/relation.h b/libs/model/include/mapget/model/relation.h
new file mode 100644
index 00000000..97430b8a
--- /dev/null
+++ b/libs/model/include/mapget/model/relation.h
@@ -0,0 +1,78 @@
+#pragma once
+
+#include "featureid.h"
+
+namespace mapget
+{
+
+class TileFeatureLayer;
+
+/**
+ * Represents a feature relation which belongs to a
+ * source feature, and points to a destination feature
+ * by its id. It may also have a validity geometry on either side.
+ */
+class Relation : public simfil::MandatoryDerivedModelNodeBase<TileFeatureLayer>
+{
+    friend class TileFeatureLayer;
+    friend class Feature;
+    template<typename> friend struct simfil::shared_model_ptr;
+
+public:
+    /**
+     * Source validity accessors.
+     */
+    [[nodiscard]] bool hasSourceValidity() const;
+    [[nodiscard]] model_ptr<Geometry> sourceValidity() const;
+    void setSourceValidity(model_ptr<Geometry> const& validityGeom);
+
+    /**
+     * Target validity accessors.
+     */
+    [[nodiscard]] bool hasTargetValidity() const;
+    [[nodiscard]] model_ptr<Geometry> targetValidity() const;
+    void setTargetValidity(model_ptr<Geometry> const& validityGeom);
+
+    /**
+     * Read-only relation name accessor.
+     */
+    [[nodiscard]] std::string_view name() const;
+
+    /**
+     * Read-only target feature accessors.
+     */
+    [[nodiscard]] model_ptr<FeatureId> target() const;
+
+protected:
+    /** ModelNode interface. */
+    [[nodiscard]] simfil::ValueType type() const override;
+    [[nodiscard]] ModelNode::Ptr at(int64_t) const override;
+    [[nodiscard]] uint32_t size() const override;
+    [[nodiscard]] ModelNode::Ptr get(const simfil::FieldId &) const override;
+    [[nodiscard]] simfil::FieldId keyAt(int64_t) const override;
+    bool iterate(IterCallback const& cb) const override;  // NOLINT (allow discard)
+
+    /** Actual per-attribute data that is stored in the model's attributes-column. */
+    struct Data {
+        simfil::FieldId name_ = 0;
+        simfil::ModelNodeAddress targetFeatureId_;
+        simfil::ModelNodeAddress sourceValidity_;
+        simfil::ModelNodeAddress targetValidity_;
+
+        template<typename S>
+        void serialize(S& s) {
+            s.value2b(name_);
+            s.object(targetFeatureId_);
+            s.object(sourceValidity_);
+            s.object(targetValidity_);
+        }
+    };
+
+    Relation(Data* data, simfil::ModelConstPtr l, simfil::ModelNodeAddress a);
+    Relation() = default;
+
+    /** Reference to the actual data stored for the relation. */
+    Data* data_{};
+};
+
+}
\ No newline at end of file
diff --git a/libs/model/include/mapget/model/stream.h b/libs/model/include/mapget/model/stream.h
index d69ebfee..5401ccd0 100644
--- a/libs/model/include/mapget/model/stream.h
+++ b/libs/model/include/mapget/model/stream.h
@@ -32,7 +32,7 @@ class TileLayerStream
     struct CachedFieldsProvider;
 
     /** Protocol Version which parsed blobs must be compatible with. */
-    static constexpr Version CurrentProtocolVersion{0, 1, 0};
+    static constexpr Version CurrentProtocolVersion{0, 1, 1};
 
     /** Map to keep track of the highest sent field id per datasource node. */
     using FieldOffsetMap = std::map<std::string, simfil::FieldId>;
diff --git a/libs/model/src/attr.cpp b/libs/model/src/attr.cpp
index 93143349..88ed8ca3 100644
--- a/libs/model/src/attr.cpp
+++ b/libs/model/src/attr.cpp
@@ -18,22 +18,22 @@ std::string_view directionToString(Attribute::Direction const& d) {
 }
 }
 
-Attribute::Attribute(Attribute::Data& data, simfil::ModelConstPtr l, simfil::ModelNodeAddress a)
-    : simfil::ProceduralObject<2, Attribute>(data.fields_, std::move(l), a), data_(data)
+Attribute::Attribute(Attribute::Data* data, simfil::ModelConstPtr l, simfil::ModelNodeAddress a)
+    : simfil::ProceduralObject<2, Attribute>(data->fields_, std::move(l), a), data_(data)
 {
-    if (data_.direction_)
+    if (data_->direction_)
         fields_.emplace_back(
             Fields::DirectionStr,
             [](Attribute const& self) {
                 return model_ptr<simfil::ValueNode>::make(
-                    directionToString(self.data_.direction_),
+                    directionToString(self.data_->direction_),
                     self.model_);
             });
-    if (data_.validity_.value_)
+    if (data_->validity_)
         fields_.emplace_back(
             Fields::ValidityStr,
             [](Attribute const& self) {
-                return model_ptr<simfil::ModelNode>::make(self.model_, self.data_.validity_);
+                return model_ptr<simfil::ModelNode>::make(self.model_, self.data_->validity_);
             });
 }
 
@@ -41,32 +41,32 @@ model_ptr<Geometry> Attribute::validity() const
 {
     if (!hasValidity())
         throw std::runtime_error("Attempt to access null validity.");
-    return model().resolveGeometry(model_ptr<simfil::ModelNode>::make(model_, data_.validity_));
+    return model().resolveGeometry(model_ptr<simfil::ModelNode>::make(model_, data_->validity_));
 }
 
 bool Attribute::hasValidity() const
 {
-    return data_.validity_.value_ != 0;
+    return data_->validity_;
 }
 
 void Attribute::setValidity(const model_ptr<Geometry>& validityGeom)
 {
-    data_.validity_ = validityGeom->addr();
+    data_->validity_ = validityGeom->addr();
 }
 
 void Attribute::setDirection(const Attribute::Direction& v)
 {
-    data_.direction_ = v;
+    data_->direction_ = v;
 }
 
 Attribute::Direction Attribute::direction() const
 {
-    return data_.direction_;
+    return data_->direction_;
 }
 
 std::string_view Attribute::name()
 {
-    if (auto s = model().fieldNames()->resolve(data_.name_))
+    if (auto s = model().fieldNames()->resolve(data_->name_))
         return *s;
     throw logRuntimeError("Attribute name is not known to string pool.");
 }
diff --git a/libs/model/src/feature.cpp b/libs/model/src/feature.cpp
index 972c3d47..b10dc42d 100644
--- a/libs/model/src/feature.cpp
+++ b/libs/model/src/feature.cpp
@@ -5,63 +5,91 @@ namespace mapget
 {
 
 Feature::Feature(Feature::Data& d, simfil::ModelConstPtr l, simfil::ModelNodeAddress a)
-    : simfil::MandatoryDerivedModelNodeBase<TileFeatureLayer>(std::move(l), a), data_(d)
+    : simfil::MandatoryDerivedModelNodeBase<TileFeatureLayer>(std::move(l), a), data_(&d)
 {
     updateFields();
 }
 
 model_ptr<FeatureId> Feature::id() const
 {
-    return model().resolveFeatureId(*Ptr::make(model_, data_.id_));
+    return model().resolveFeatureId(*Ptr::make(model_, data_->id_));
 }
 
 std::string_view mapget::Feature::typeId() const
 {
-    return model().resolveFeatureId(*Ptr::make(model_, data_.id_))->typeId();
+    return model().resolveFeatureId(*Ptr::make(model_, data_->id_))->typeId();
 }
 
 model_ptr<simfil::GeometryCollection> Feature::geom()
 {
-    if (data_.geom_.value_ == 0) {
+    if (!data_->geom_) {
         auto result = model().newGeometryCollection();
-        data_.geom_ = result->addr();
+        data_->geom_ = result->addr();
         updateFields();
         return result;
     }
-    return model().resolveGeometryCollection(Ptr::make(model_, data_.geom_));
+    return const_cast<const Feature*>(this)->geom();
+}
+
+model_ptr<GeometryCollection> Feature::geom() const
+{
+    if (!data_->geom_)
+        return {};
+    return model().resolveGeometryCollection(Ptr::make(model_, data_->geom_));
 }
 
 model_ptr<AttributeLayerList> Feature::attributeLayers()
 {
-    if (data_.attrLayers_.value_ == 0) {
+    if (!data_->attrLayers_) {
         auto result = model().newAttributeLayers();
-        data_.attrLayers_ = result->addr();
+        data_->attrLayers_ = result->addr();
         updateFields();
         return result;
     }
-    return model().resolveAttributeLayerList(*Ptr::make(model_, data_.attrLayers_));
+    return const_cast<const Feature*>(this)->attributeLayers();
+}
+
+model_ptr<AttributeLayerList> Feature::attributeLayers() const
+{
+    if (!data_->attrLayers_)
+        return {};
+    return model().resolveAttributeLayerList(*Ptr::make(model_, data_->attrLayers_));
 }
 
 model_ptr<Object> Feature::attributes()
 {
-    if (data_.attrs_.value_ == 0) {
+    if (!data_->attrs_) {
         auto result = model().newObject(8);
-        data_.attrs_ = result->addr();
+        data_->attrs_ = result->addr();
         updateFields();
         return result;
     }
-    return model().resolveObject(Ptr::make(model_, data_.attrs_));
+    return const_cast<const Feature*>(this)->attributes();
 }
 
-model_ptr<Array> Feature::children()
+model_ptr<Object> Feature::attributes() const
 {
-    if (data_.children_.value_ == 0) {
+    if (!data_->attrs_)
+        return {};
+    return model().resolveObject(Ptr::make(model_, data_->attrs_));
+}
+
+model_ptr<Array> Feature::relations()
+{
+    if (!data_->relations_) {
         auto result = model().newArray(8);
-        data_.children_ = result->addr();
+        data_->relations_ = result->addr();
         updateFields();
         return result;
     }
-    return model().resolveArray(Ptr::make(model_, data_.children_));
+    return const_cast<const Feature*>(this)->relations();
+}
+
+model_ptr<Array> Feature::relations() const
+{
+    if (!data_->relations_)
+        return {};
+    return model().resolveArray(Ptr::make(model_, data_->relations_));
 }
 
 std::vector<simfil::Value> Feature::evaluateAll(const std::string_view& expression)
@@ -136,7 +164,7 @@ void Feature::updateFields() {
     fields_.emplace_back(Fields::Type, simfil::ValueNode(std::string_view("Feature"), model_));
 
     // Add id field
-    fields_.emplace_back(Fields::IdStr, Ptr::make(model_, data_.id_));
+    fields_.emplace_back(Fields::IdStr, Ptr::make(model_, data_->id_));
     auto idNode = model().resolveFeatureId(*fields_.back().second);
 
     // Add type id field
@@ -146,7 +174,7 @@ void Feature::updateFields() {
 
     // Add common id-part fields
     if (model().featureIdPrefix())
-        for (auto const& [idPartName, value] : (*model().featureIdPrefix())->fields()) {
+        for (auto const& [idPartName, value] : model().featureIdPrefix()->fields()) {
             fields_.emplace_back(idPartName, value);
         }
 
@@ -156,16 +184,16 @@ void Feature::updateFields() {
     }
 
     // Add other fields
-    if (data_.geom_.value_)
-        fields_.emplace_back(Fields::Geometry, Ptr::make(model_, data_.geom_));
-    if (data_.attrLayers_.value_ || data_.attrs_.value_)
+    if (data_->geom_)
+        fields_.emplace_back(Fields::Geometry, Ptr::make(model_, data_->geom_));
+    if (data_->attrLayers_ || data_->attrs_)
         fields_.emplace_back(
             Fields::PropertiesStr,
             Ptr::make(
                 model_,
                 simfil::ModelNodeAddress{TileFeatureLayer::FeatureProperties, addr().index()}));
-    if (data_.children_.value_)
-        fields_.emplace_back(Fields::ChildrenStr, Ptr::make(model_, data_.children_));
+    if (data_->relations_)
+        fields_.emplace_back(Fields::RelationsStr, Ptr::make(model_, data_->relations_));
 }
 
 nlohmann::json Feature::toGeoJson()
@@ -236,6 +264,64 @@ void Feature::addPoly(const std::vector<Point>& points) {
         newGeom->append(p);
 }
 
+void Feature::addRelation(
+    const std::string_view& name,
+    const std::string_view& targetType,
+    const KeyValueViewPairs& targetIdParts)
+{
+    addRelation(name, model().newFeatureId(targetType, targetIdParts));
+}
+
+void Feature::addRelation(const std::string_view& name, const model_ptr<FeatureId>& target)
+{
+    addRelation(model().newRelation(name, target));
+}
+
+void Feature::addRelation(const model_ptr<Relation>& relation)
+{
+    relations()->append(relation);
+}
+
+uint32_t Feature::numRelations() const
+{
+    if (data_->relations_)
+        return relations()->size();
+    return 0;
+}
+
+model_ptr<Relation> Feature::getRelation(uint32_t index) const
+{
+    if (data_->relations_)
+        return model().resolveRelation(*relations()->at(index));
+    return {};
+}
+
+bool Feature::forEachRelation(std::function<bool(const model_ptr<Relation>&)> const& callback) const
+{
+    auto relationsPtr = relations();
+    if (!relationsPtr || !callback)
+        return true;
+    for (auto const& relation : *relationsPtr) {
+        if (!callback(model().resolveRelation(*relation)))
+            return false;
+    }
+    return true;
+}
+
+model_ptr<Geometry> Feature::firstGeometry() const
+{
+    model_ptr<Geometry> result;
+    if (auto geometryCollection = geom()) {
+        geometryCollection->forEachGeometry(
+            [&result](auto&& geometry)
+            {
+                result = geometry;
+                return false;
+            });
+    }
+    return result;
+}
+
 //////////////////////////////////////////
 
 Feature::FeaturePropertyView::FeaturePropertyView(
@@ -243,10 +329,10 @@ Feature::FeaturePropertyView::FeaturePropertyView(
     simfil::ModelConstPtr l,
     simfil::ModelNodeAddress a
 )
-    : simfil::MandatoryDerivedModelNodeBase<TileFeatureLayer>(std::move(l), a), data_(d)
+    : simfil::MandatoryDerivedModelNodeBase<TileFeatureLayer>(std::move(l), a), data_(&d)
 {
-    if (data_.attrs_.value_)
-        attrs_ = model().resolveObject(Ptr::make(model_, data_.attrs_));
+    if (data_->attrs_)
+        attrs_ = model().resolveObject(Ptr::make(model_, data_->attrs_));
 }
 
 simfil::ValueType Feature::FeaturePropertyView::type() const
@@ -256,50 +342,50 @@ simfil::ValueType Feature::FeaturePropertyView::type() const
 
 simfil::ModelNode::Ptr Feature::FeaturePropertyView::at(int64_t i) const
 {
-    if (data_.attrLayers_.value_) {
+    if (data_->attrLayers_) {
         if (i == 0)
-            return Ptr::make(model_, data_.attrLayers_);
+            return Ptr::make(model_, data_->attrLayers_);
         i -= 1;
     }
     if (attrs_)
-        return (*attrs_)->at(i);
+        return attrs_->at(i);
     return {};
 }
 
 uint32_t Feature::FeaturePropertyView::size() const
 {
-    return (data_.attrLayers_.value_ ? 1 : 0) + (attrs_ ? (*attrs_)->size() : 0);
+    return (data_->attrLayers_ ? 1 : 0) + (attrs_ ? attrs_->size() : 0);
 }
 
 simfil::ModelNode::Ptr Feature::FeaturePropertyView::get(const simfil::FieldId& f) const
 {
-    if (data_.attrLayers_.value_ && f == Fields::LayerStr)
-        return Ptr::make(model_, data_.attrLayers_);
+    if (data_->attrLayers_ && f == Fields::LayerStr)
+        return Ptr::make(model_, data_->attrLayers_);
     if (attrs_)
-        return (*attrs_)->get(f);
+        return attrs_->get(f);
     return {};
 }
 
 simfil::FieldId Feature::FeaturePropertyView::keyAt(int64_t i) const
 {
-    if (data_.attrLayers_.value_) {
+    if (data_->attrLayers_) {
         if (i == 0)
             return Fields::LayerStr;
         i -= 1;
     }
     if (attrs_)
-        return (*attrs_)->keyAt(i);
+        return attrs_->keyAt(i);
     return {};
 }
 
 bool Feature::FeaturePropertyView::iterate(const simfil::ModelNode::IterCallback& cb) const
 {
-    if (data_.attrLayers_.value_) {
-        if (!cb(*model().resolveAttributeLayerList(*Ptr::make(model_, data_.attrLayers_))))
+    if (data_->attrLayers_) {
+        if (!cb(*model().resolveAttributeLayerList(*Ptr::make(model_, data_->attrLayers_))))
             return false;
     }
     if (attrs_)
-        return (*attrs_)->iterate(cb);
+        return attrs_->iterate(cb);
     return true;
 }
 
diff --git a/libs/model/src/featureid.cpp b/libs/model/src/featureid.cpp
index 82628c5c..c81b1e61 100644
--- a/libs/model/src/featureid.cpp
+++ b/libs/model/src/featureid.cpp
@@ -8,14 +8,14 @@ namespace mapget
 
 FeatureId::FeatureId(FeatureId::Data& data, simfil::ModelConstPtr l, simfil::ModelNodeAddress a)
     : simfil::MandatoryDerivedModelNodeBase<TileFeatureLayer>(std::move(l), a),
-      data_(data),
-      fields_(model().resolveObject(Ptr::make(l, data_.idParts_)))
+      data_(&data),
+      fields_(model().resolveObject(Ptr::make(l, data_->idParts_)))
 {
 }
 
 std::string_view FeatureId::typeId() const
 {
-    if (auto s = model().fieldNames()->resolve(data_.typeId_))
+    if (auto s = model().fieldNames()->resolve(data_->typeId_))
         return *s;
     return "err-unresolved-typename";
 }
@@ -32,8 +32,8 @@ std::string FeatureId::toString() const
     };
 
     // Add common id-part fields
-    if (data_.useCommonTilePrefix_ && model().featureIdPrefix())
-        for (auto const& [_, value] : (*model().featureIdPrefix())->fields())
+    if (data_->useCommonTilePrefix_ && model().featureIdPrefix())
+        for (auto const& [_, value] : model().featureIdPrefix()->fields())
             std::visit(addIdPart, value->value());
 
     // Add specific id-part fields
@@ -78,4 +78,32 @@ bool FeatureId::iterate(const simfil::ModelNode::IterCallback& cb) const
     return true;
 }
 
+KeyValueViewPairs FeatureId::keyValuePairs() const
+{
+    KeyValueViewPairs result;
+
+    auto objectFieldsToKeyValuePairs = [&result, this](simfil::ModelNode::FieldRange fields){
+        for (auto const& [key, value] : fields) {
+            auto keyStr = model().fieldNames()->resolve(key);
+            std::visit(
+                [&result, &keyStr](auto&& v)
+                {
+                    if constexpr (!std::is_same_v<std::decay_t<decltype(v)>, std::monostate> && !std::is_same_v<std::decay_t<decltype(v)>, double>) {
+                        result.emplace_back(*keyStr, v);
+                    }
+                },
+                value->value());
+        }
+    };
+
+    // Add common id-part fields.
+    if (data_->useCommonTilePrefix_ && model().featureIdPrefix())
+        objectFieldsToKeyValuePairs(model().featureIdPrefix()->fields());
+
+    // Add specific id-part fields.
+    objectFieldsToKeyValuePairs(fields());
+
+    return std::move(result);
+}
+
 }
diff --git a/libs/model/src/featurelayer.cpp b/libs/model/src/featurelayer.cpp
index 2def1e08..b2a539aa 100644
--- a/libs/model/src/featurelayer.cpp
+++ b/libs/model/src/featurelayer.cpp
@@ -22,12 +22,43 @@ struct TileFeatureLayer::Impl {
     sfl::segmented_vector<FeatureId::Data, simfil::detail::ColumnPageSize/2> featureIds_;
     sfl::segmented_vector<simfil::ArrayIndex, simfil::detail::ColumnPageSize/2> attrLayers_;
     sfl::segmented_vector<simfil::ArrayIndex, simfil::detail::ColumnPageSize/2> attrLayerLists_;
+    sfl::segmented_vector<Relation::Data, simfil::detail::ColumnPageSize/2> relations_;
+
+    /**
+     * Indexing of features by their id hash. The hash-feature pairs are kept
+     * in a vector, which is kept in a sorted state. This allows finding a
+     * feature by it's id in O(log(n)) time.
+     */
+    struct FeatureAddrWithIdHash
+    {
+        simfil::ModelNodeAddress featureAddr_;
+        uint64_t idHash_ = 0;
+
+        template<class S>
+        void serialize(S& s) {
+            s.object(featureAddr_);
+            s.value8b(idHash_);
+        }
+
+        bool operator< (FeatureAddrWithIdHash const& other) const {
+            return std::tie(idHash_, featureAddr_) < std::tie(other.idHash_, other.featureAddr_);
+        }
+    };
+    sfl::segmented_vector<FeatureAddrWithIdHash, simfil::detail::ColumnPageSize/4> featureHashIndex_;
+    bool featureHashIndexNeedsSorting_ = false;
+
+    void sortFeatureHashIndex() {
+        if (!featureHashIndexNeedsSorting_)
+            return;
+        featureHashIndexNeedsSorting_ = false;
+        std::sort(featureHashIndex_.begin(), featureHashIndex_.end());
+    }
 
     // Simfil execution Environment for this tile's string pool.
-    simfil::Environment simfilEnv_;
+    std::unique_ptr<simfil::Environment> simfilEnv_;
 
     // Compiled simfil expressions, by hash of expression string
-    std::map<std::string, simfil::ExprPtr> simfilExpressions_;
+    std::map<std::string, simfil::ExprPtr, std::less<>> simfilExpressions_;
 
     // Mutex to manage access to the expression cache
     std::shared_mutex expressionCacheLock_;
@@ -41,11 +72,14 @@ struct TileFeatureLayer::Impl {
         s.container(featureIds_, maxColumnSize);
         s.container(attrLayers_, maxColumnSize);
         s.container(attrLayerLists_, maxColumnSize);
-        s.value4b(featureIdPrefix_.value_);
+        s.object(featureIdPrefix_);
+        s.container(relations_, maxColumnSize);
+        sortFeatureHashIndex();
+        s.container(featureHashIndex_, maxColumnSize);
     }
 
-    explicit Impl(std::shared_ptr<Fields> fields)
-        : simfilEnv_(std::move(fields))
+    explicit Impl(std::shared_ptr<simfil::Fields> fieldDict)
+        : simfilEnv_(std::make_unique<simfil::Environment>(std::move(fieldDict)))
     {
     }
 };
@@ -55,7 +89,7 @@ TileFeatureLayer::TileFeatureLayer(
     std::string const& nodeId,
     std::string const& mapId,
     std::shared_ptr<LayerInfo> const& layerInfo,
-    std::shared_ptr<Fields> const& fields
+    std::shared_ptr<simfil::Fields> const& fields
 ) :
     simfil::ModelPool(fields),
     impl_(std::make_unique<Impl>(fields)),
@@ -75,7 +109,7 @@ TileFeatureLayer::TileFeatureLayer(
     bitsery::Deserializer<bitsery::InputStreamAdapter> s(inputStream);
     impl_->readWrite(s);
     if (s.adapter().error() != bitsery::ReaderError::NoError) {
-        throw logRuntimeError(stx::format(
+        throw logRuntimeError(fmt::format(
             "Failed to read TileFeatureLayer: Error {}",
             static_cast<std::underlying_type_t<bitsery::ReaderError>>(s.adapter().error())));
     }
@@ -94,7 +128,7 @@ namespace
 bool idPartsMatchComposition(
     std::vector<IdPart> const& candidateComposition,
     uint32_t compositionMatchStartIdx,
-    KeyValuePairs const& featureIdParts,
+    KeyValueViewPairs const& featureIdParts,
     unsigned long matchLength)
 {
     auto featureIdIter = featureIdParts.begin();
@@ -163,7 +197,10 @@ bool idPartsMatchComposition(
     return matchLength == 0;
 }
 
-std::string idPartsToString(KeyValuePairs const& idParts) {
+/**
+ * Create a string representation of the given id parts.
+ */
+std::string idPartsToString(KeyValueViewPairs const& idParts) {
     std::stringstream result;
     result << "{";
     for (auto i = 0; i < idParts.size(); ++i) {
@@ -178,13 +215,99 @@ std::string idPartsToString(KeyValuePairs const& idParts) {
     return result.str();
 }
 
+/**
+ * Remove id parts from a keysAndValues list which are optional under
+ * the given composition. Note: The ordering of keys in the keysAndValues
+ * list must match the ordering in the composition. E.g., if `areaId` comes
+ * before `featureId`, it will only be recognized if this order is also
+ * maintained in the keysAndValues list.
+ */
+KeyValueViewPairs
+stripOptionalIdParts(KeyValueViewPairs const& keysAndValues, std::vector<IdPart> const& composition)
+{
+    KeyValueViewPairs result;
+    result.reserve(keysAndValues.size());
+    auto idPartIt = composition.begin();
+
+    for (auto const& [key, value] : keysAndValues) {
+        bool isOptional = true;
+        while (idPartIt != composition.end()) {
+            if (key == idPartIt->idPartLabel_) {
+                isOptional = idPartIt->isOptional_;
+                ++idPartIt;
+                break;
+            }
+            ++idPartIt;
+        }
+        if (!isOptional)
+            result.emplace_back(key, value);
+    }
+
+    return result;
+}
+
+/**
+ * Create a hash of the given feature-type-name + idParts combination.
+ * We do not use std::hash, as it has different implementations on different
+ * compilers. This hash must be stable across Emscripten/GCC/MSVC/etc.
+ */
+uint64_t hashFeatureId(const std::string_view& type, const KeyValueViewPairs& idParts)
+{
+    // Constants for the FNV-1a hash algorithm
+    constexpr uint64_t FNV_prime = 1099511628211ULL;
+    constexpr uint64_t offset_basis = 14695981039346656037ULL;
+
+    // Lambda function for FNV-1a hash of a string view
+    auto fnv1a_hash = [](std::string_view str) -> uint64_t {
+        uint64_t hash = offset_basis;
+        for (char c : str) {
+            hash ^= static_cast<uint64_t>(c);
+            hash *= FNV_prime;
+        }
+        return hash;
+    };
+
+    // Lambda function to hash int64_t values
+    auto hash_int64 = [](int64_t value) -> uint64_t {
+        uint64_t hash = offset_basis;
+        for (size_t i = 0; i < sizeof(int64_t); ++i) {
+            hash ^= (value & 0xff);
+            hash *= FNV_prime;
+            value >>= 8;
+        }
+        return hash;
+    };
+
+    // Begin hashFeatureId implementation
+    uint64_t hash = fnv1a_hash(type);
+
+    for (const auto& [key, value] : idParts) {
+        // Combine the hash of the key
+        hash ^= fnv1a_hash(key);
+        hash *= FNV_prime;
+
+        // Combine the hash of the value
+        hash ^= std::visit([&](const auto& val) -> uint64_t {
+            using T = std::decay_t<decltype(val)>;
+            if constexpr (std::is_same_v<T, int64_t>) {
+                return hash_int64(val);
+            } else {
+                return fnv1a_hash(val);
+            }
+        }, value);
+        hash *= FNV_prime;
+    }
+
+    return hash;
+}
+
 }  // namespace
 
 bool TileFeatureLayer::validFeatureId(
     const std::string_view& typeId,
-    KeyValuePairs const& featureIdParts,
-    bool includeTilePrefix) {
-
+    KeyValueViewPairs const& featureIdParts,
+    bool validateForNewFeature)
+{
     auto typeIt = this->layerInfo_->featureTypes_.begin();
     while (typeIt != this->layerInfo_->featureTypes_.end()) {
         if (typeIt->name_ == typeId)
@@ -192,14 +315,14 @@ bool TileFeatureLayer::validFeatureId(
         ++typeIt;
     }
     if (typeIt == this->layerInfo_->featureTypes_.end()) {
-        throw logRuntimeError(stx::format("Could not find feature type {}", typeId));
+        throw logRuntimeError(fmt::format("Could not find feature type {}", typeId));
     }
 
     for (auto& candidateComposition : typeIt->uniqueIdCompositions_) {
         uint32_t compositionMatchStartIndex = 0;
-        if (includeTilePrefix && this->featureIdPrefix().has_value()) {
+        if (validateForNewFeature && this->featureIdPrefix()) {
             // Iterate past the prefix in the unique id composition.
-            compositionMatchStartIndex = this->featureIdPrefix().value()->size();
+            compositionMatchStartIndex = this->featureIdPrefix()->size();
         }
 
         if (idPartsMatchComposition(
@@ -210,6 +333,11 @@ bool TileFeatureLayer::validFeatureId(
         {
             return true;
         }
+
+        // References may use alternative ID compositions,
+        // but the feature itself must always use the first one.
+        if (validateForNewFeature)
+            return false;
     }
 
     return false;
@@ -217,14 +345,14 @@ bool TileFeatureLayer::validFeatureId(
 
 simfil::shared_model_ptr<Feature> TileFeatureLayer::newFeature(
     const std::string_view& typeId,
-    const KeyValuePairs& featureIdParts)
+    const KeyValueViewPairs& featureIdParts)
 {
     if (featureIdParts.empty()) {
         throw logRuntimeError("Tried to create an empty feature ID.");
     }
 
     if (!validFeatureId(typeId, featureIdParts, true)) {
-        throw logRuntimeError(stx::format(
+        throw logRuntimeError(fmt::format(
             "Could not find a matching ID composition of type {} with parts {}.",
             typeId,
             idPartsToString(featureIdParts)));
@@ -257,6 +385,13 @@ simfil::shared_model_ptr<Feature> TileFeatureLayer::newFeature(
         shared_from_this(),
         simfil::ModelNodeAddress{Features, (uint32_t)featureIndex});
 
+    // Add feature hash index entry.
+    auto const& primaryIdComposition = getPrimaryIdComposition(typeId);
+    auto fullStrippedFeatureId = stripOptionalIdParts(result.id()->keyValuePairs(), primaryIdComposition);
+    auto hash = hashFeatureId(typeId, fullStrippedFeatureId);
+    impl_->featureHashIndex_.emplace_back(TileFeatureLayer::Impl::FeatureAddrWithIdHash{result.addr(), hash});
+    impl_->featureHashIndexNeedsSorting_ = true;
+
     // Note: Here we rely on the assertion that the root_ collection
     // contains only references to feature nodes, in the order
     // of the feature node column.
@@ -268,10 +403,10 @@ simfil::shared_model_ptr<Feature> TileFeatureLayer::newFeature(
 model_ptr<FeatureId>
 TileFeatureLayer::newFeatureId(
     const std::string_view& typeId,
-    const KeyValuePairs& featureIdParts)
+    const KeyValueViewPairs& featureIdParts)
 {
     if (!validFeatureId(typeId, featureIdParts, false)) {
-        throw logRuntimeError(stx::format(
+        throw logRuntimeError(fmt::format(
             "Could not find a matching ID composition of type {} with parts {}.",
             typeId,
             idPartsToString(featureIdParts)));
@@ -293,9 +428,20 @@ TileFeatureLayer::newFeatureId(
     return FeatureId(impl_->featureIds_.back(), shared_from_this(), {FeatureIds, (uint32_t)featureIdIndex});
 }
 
-std::optional<model_ptr<Object>> TileFeatureLayer::featureIdPrefix()
+model_ptr<Relation>
+TileFeatureLayer::newRelation(const std::string_view& name, const model_ptr<FeatureId>& target)
+{
+    auto relationIndex = impl_->relations_.size();
+    impl_->relations_.emplace_back(Relation::Data{
+        fieldNames()->emplace(name),
+        target->addr()
+    });
+    return Relation(&impl_->relations_.back(), shared_from_this(), {Relations, (uint32_t)relationIndex});
+}
+
+model_ptr<Object> TileFeatureLayer::featureIdPrefix()
 {
-    if (impl_->featureIdPrefix_.value_)
+    if (impl_->featureIdPrefix_)
         return resolveObject(simfil::ModelNode::Ptr::make(shared_from_this(), impl_->featureIdPrefix_));
     return {};
 }
@@ -311,7 +457,7 @@ TileFeatureLayer::newAttribute(const std::string_view& name, size_t initialCapac
         fieldNames()->emplace(name)
     });
     return Attribute(
-        impl_->attributes_.back(),
+        &impl_->attributes_.back(),
         shared_from_this(),
         {Attributes, (uint32_t)attrIndex});
 }
@@ -355,7 +501,7 @@ model_ptr<AttributeLayerList> TileFeatureLayer::resolveAttributeLayerList(simfil
 model_ptr<Attribute> TileFeatureLayer::resolveAttribute(simfil::ModelNode const& n) const
 {
     return Attribute(
-        impl_->attributes_[n.addr().index()],
+        &impl_->attributes_[n.addr().index()],
         shared_from_this(),
         n.addr());
 }
@@ -376,6 +522,14 @@ model_ptr<FeatureId> TileFeatureLayer::resolveFeatureId(simfil::ModelNode const&
         n.addr());
 }
 
+model_ptr<Relation> TileFeatureLayer::resolveRelation(const simfil::ModelNode& n) const
+{
+    return Relation(
+        &impl_->relations_[n.addr().index()],
+        shared_from_this(),
+        n.addr());
+}
+
 void TileFeatureLayer::resolve(const simfil::ModelNode& n, const simfil::Model::ResolveFn& cb) const
 {
     switch (n.addr().column())
@@ -408,6 +562,10 @@ void TileFeatureLayer::resolve(const simfil::ModelNode& n, const simfil::Model::
         cb(*resolveAttributeLayerList(n));
         return;
     }
+    case Relations: {
+        cb(*resolveRelation(n));
+        return;
+    }
     }
 
     simfil::ModelPool::resolve(n, cb);
@@ -415,36 +573,41 @@ void TileFeatureLayer::resolve(const simfil::ModelNode& n, const simfil::Model::
 
 simfil::Environment& TileFeatureLayer::evaluationEnvironment()
 {
-    return impl_->simfilEnv_;
+    return *impl_->simfilEnv_;
 }
 
 simfil::ExprPtr const& TileFeatureLayer::compiledExpression(const std::string_view& expr)
 {
     std::shared_lock sharedLock(impl_->expressionCacheLock_);
-    std::string exprString{expr};
-    auto it = impl_->simfilExpressions_.find(exprString);
+    auto it = impl_->simfilExpressions_.find(expr);
     if (it != impl_->simfilExpressions_.end()) {
         return it->second;
     }
     sharedLock.unlock();
     std::unique_lock uniqueLock(impl_->expressionCacheLock_);
     auto [newIt, _] = impl_->simfilExpressions_.emplace(
-        std::move(exprString),
-        simfil::compile(impl_->simfilEnv_, expr, false)
+        std::string(expr),
+        simfil::compile(*impl_->simfilEnv_, expr, false)
     );
     return newIt->second;
 }
 
-void TileFeatureLayer::setPrefix(const KeyValuePairs& prefix)
+void TileFeatureLayer::setPrefix(const KeyValueViewPairs& prefix)
 {
-    // Check that the prefix is compatible with all existing id composites.
+    // The prefix must be set, before any feature is added.
+    if (!impl_->features_.empty())
+        throw std::runtime_error("Cannot set feature id prefix after a feature was added.");
+
+    // Check that the prefix is compatible with all primary id composites.
+    // The primary id composition is the first one in the list.
     for (auto& featureType : this->layerInfo_->featureTypes_) {
         for (auto& candidateComposition : featureType.uniqueIdCompositions_) {
             if (!idPartsMatchComposition(candidateComposition, 0, prefix, prefix.size())) {
-                throw logRuntimeError(stx::format(
+                throw logRuntimeError(fmt::format(
                     "Prefix not compatible with an id composite in type: {}",
                     featureType.name_));
             }
+            break;
         }
     }
 
@@ -497,4 +660,108 @@ model_ptr<Feature> TileFeatureLayer::at(size_t i) const
     return resolveFeature(*root(i));
 }
 
+model_ptr<Feature>
+TileFeatureLayer::find(const std::string_view& type, const KeyValueViewPairs& queryIdParts) const
+{
+    auto const& primaryIdComposition = getPrimaryIdComposition(type);
+    auto queryIdPartsStripped = stripOptionalIdParts(queryIdParts, primaryIdComposition);
+    auto hash = hashFeatureId(type, queryIdPartsStripped);
+
+    impl_->sortFeatureHashIndex();
+    auto it = std::lower_bound(
+        impl_->featureHashIndex_.begin(),
+        impl_->featureHashIndex_.end(),
+        Impl::FeatureAddrWithIdHash{0, hash},
+        [](auto&& l, auto&& r) { return l.idHash_ < r.idHash_; });
+
+    // Iterate through potential matches to handle hash collisions.
+    while (it != impl_->featureHashIndex_.end() && it->idHash_ == hash)
+    {
+        auto feature = resolveFeature(*simfil::ModelNode::Ptr::make(shared_from_this(), it->featureAddr_));
+        if (feature->id()->typeId() == type) {
+            auto featureIdParts = stripOptionalIdParts(feature->id()->keyValuePairs(), primaryIdComposition);
+            // Ensure that ID parts match exactly, not just the hash.
+            if (featureIdParts.size() != queryIdPartsStripped.size()) {
+                ++it;
+                continue;
+            }
+            bool exactMatch = true;
+            for (auto i = 0; i < featureIdParts.size(); ++i) {
+                if (featureIdParts[i] != queryIdPartsStripped[i]) {
+                    exactMatch = false;
+                    break;
+                }
+            }
+            if (exactMatch)
+                return feature;
+        }
+        // Move to the next potential match.
+        ++it;
+    }
+
+    return {};
+}
+
+model_ptr<Feature>
+TileFeatureLayer::find(const std::string_view& type, const KeyValuePairs& queryIdParts) const
+{
+    // Convert KeyValuePairs to KeyValuePairsView
+    KeyValueViewPairs kvpView;
+    for (auto const& [k, v] : queryIdParts) {
+        std::visit([&kvpView, &k](auto&& vv){
+            if constexpr (std::is_same_v<std::decay_t<decltype(vv)>, std::string>)
+                kvpView.emplace_back(k, std::string_view(vv));
+            else
+                kvpView.emplace_back(k, vv);
+        }, v);
+    }
+    return find(type, kvpView);
+}
+
+std::vector<IdPart> const& TileFeatureLayer::getPrimaryIdComposition(const std::string_view& typeId) const
+{
+    auto typeIt = this->layerInfo_->featureTypes_.begin();
+    while (typeIt != this->layerInfo_->featureTypes_.end()) {
+        if (typeIt->name_ == typeId)
+            break;
+        ++typeIt;
+    }
+    if (typeIt == this->layerInfo_->featureTypes_.end()) {
+        throw logRuntimeError(fmt::format("Could not find feature type {}", typeId));
+    }
+    if (typeIt->uniqueIdCompositions_.empty()) {
+        throw logRuntimeError(fmt::format("No composition for feature type {}!", typeId));
+    }
+    return typeIt->uniqueIdCompositions_.front();
+}
+
+void TileFeatureLayer::setFieldNames(std::shared_ptr<simfil::Fields> const& newDict)
+{
+    // Re-map old field IDs to new field IDs
+    for (auto& attr : impl_->attributes_) {
+        if (auto resolvedName = fieldNames()->resolve(attr.name_)) {
+            attr.name_ = newDict->emplace(*resolvedName);
+        }
+    }
+    for (auto& fid : impl_->featureIds_) {
+        if (auto resolvedName = fieldNames()->resolve(fid.typeId_)) {
+            fid.typeId_ = newDict->emplace(*resolvedName);
+        }
+    }
+    for (auto& rel : impl_->relations_) {
+        if (auto resolvedName = fieldNames()->resolve(rel.name_)) {
+            rel.name_ = newDict->emplace(*resolvedName);
+        }
+    }
+
+    // Reset simfil environment and clear expression cache
+    {
+        std::unique_lock lock(impl_->expressionCacheLock_);
+        impl_->simfilExpressions_.clear();
+        impl_->simfilEnv_ = std::make_unique<simfil::Environment>(newDict);
+    }
+
+    ModelPool::setFieldNames(newDict);
+}
+
 }
diff --git a/libs/model/src/fields.cpp b/libs/model/src/fields.cpp
index e90b408f..8b6cbc4a 100644
--- a/libs/model/src/fields.cpp
+++ b/libs/model/src/fields.cpp
@@ -11,10 +11,14 @@ Fields::Fields(const std::string_view& nodeId) : nodeId_(nodeId) {
     addStaticKey(IdStr, "id");
     addStaticKey(TypeIdStr, "typeId");
     addStaticKey(LayerStr, "layer");
-    addStaticKey(ChildrenStr, "children");
+    addStaticKey(RelationsStr, "relations");
     addStaticKey(DirectionStr, "direction");
     addStaticKey(ValidityStr, "validity");
     addStaticKey(PropertiesStr, "properties");
+    addStaticKey(NameStr, "name");
+    addStaticKey(TargetStr, "target");
+    addStaticKey(SourceValidityStr, "sourceValidity");
+    addStaticKey(TargetValidityStr, "targetValidity");
 }
 
 void Fields::write(std::ostream& outputStream, simfil::FieldId offset) const
diff --git a/libs/model/src/info.cpp b/libs/model/src/info.cpp
index cee7906e..9c45d969 100644
--- a/libs/model/src/info.cpp
+++ b/libs/model/src/info.cpp
@@ -24,7 +24,7 @@ std::string generateUuid() {
 
 auto missing_field(std::string const& error, std::string const& context) {
     return std::runtime_error(
-        stx::format("{}::fromJson(): `{}`", context, error));
+        fmt::format("{}::fromJson(): `{}`", context, error));
 }
 
 }
@@ -36,7 +36,7 @@ bool Version::isCompatible(const Version& other) const
 
 std::string Version::toString() const
 {
-    return stx::format("{}.{}.{}", major_, minor_, patch_);
+    return fmt::format("{}.{}.{}", major_, minor_, patch_);
 }
 
 bool Version::operator==(const Version& other) const
@@ -214,7 +214,7 @@ std::shared_ptr<LayerInfo> DataSourceInfo::getLayer(std::string const& layerId)
     auto it = layers_.find(layerId);
     if (it == layers_.end()) {
         throw logRuntimeError(
-            stx::format("Could not find layer '{}' in map '{}'", layerId, mapId_)
+            fmt::format("Could not find layer '{}' in map '{}'", layerId, mapId_)
         );
     }
     return it->second;
diff --git a/libs/model/src/layer.cpp b/libs/model/src/layer.cpp
index 33cadb71..c6b9ebfe 100644
--- a/libs/model/src/layer.cpp
+++ b/libs/model/src/layer.cpp
@@ -8,6 +8,9 @@
 #include "simfil/model/bitsery-traits.h"
 
 #include <istream>
+#include <ranges>
+#include <string_view>
+#include <charconv>
 
 #include "nlohmann/json.hpp"
 
@@ -16,13 +19,19 @@ namespace mapget
 
 MapTileKey::MapTileKey(const std::string& str)
 {
-    auto parts = stx::split(str, ":", false);
-    if (parts.size() < 4)
-        throw logRuntimeError(stx::format("Invalid cache tile id: {}", str));
-    layer_ = nlohmann::json(parts[0]).get<LayerType>();
-    mapId_ = parts[1];
-    layerId_ = parts[2];
-    tileId_ = TileId(std::stoull(str, nullptr, 16));
+    // This will get simpler with C++ 23. Then we can just use ranges::to<std::vector>,
+    // and also the verbose conversion from a char range to a string_view
+    // will not be necessary anymore.
+    using namespace std::ranges;
+    auto parts = str | views::split(':');
+    auto partsVec = std::vector<decltype(*parts.begin())>(parts.begin(), parts.end());
+
+    if (partsVec.size() < 4)
+        throw logRuntimeError(fmt::format("Invalid cache tile id: {}", str));
+    layer_ = nlohmann::json(std::string_view(&*partsVec[1].begin(), distance(partsVec[1]))).get<LayerType>();
+    mapId_ = std::string_view(&*partsVec[1].begin(), distance(partsVec[1]));
+    layerId_ = std::string_view(&*partsVec[2].begin(), distance(partsVec[2]));
+    std::from_chars(&*partsVec[3].begin(), &*partsVec[3].begin() + distance(partsVec[3]), tileId_.value_, 16);
 }
 
 MapTileKey::MapTileKey(const TileLayer& data)
@@ -35,7 +44,7 @@ MapTileKey::MapTileKey(const TileLayer& data)
 
 std::string MapTileKey::toString() const
 {
-    return stx::format(
+    return fmt::format(
         "{}:{}:{}:{:0x}",
         nlohmann::json(layer_).get<std::string>(),
         mapId_,
@@ -80,7 +89,7 @@ TileLayer::TileLayer(
 
     s.object(mapVersion_);
     if (!mapVersion_.isCompatible(layerInfo_->version_)) {
-        throw logRuntimeError(stx::format(
+        throw logRuntimeError(fmt::format(
             "Read map layer '{}' version {} "
             "is incompatible with present version {}.",
             layerName,
diff --git a/libs/model/src/relation.cpp b/libs/model/src/relation.cpp
new file mode 100644
index 00000000..6a6e4f0d
--- /dev/null
+++ b/libs/model/src/relation.cpp
@@ -0,0 +1,118 @@
+#include "relation.h"
+#include "featurelayer.h"
+#include "mapget/log.h"
+
+namespace mapget
+{
+
+Relation::Relation(Relation::Data* data, simfil::ModelConstPtr l, simfil::ModelNodeAddress a)
+    : simfil::MandatoryDerivedModelNodeBase<TileFeatureLayer>(std::move(l), a), data_(data)
+{
+}
+
+model_ptr<Geometry> Relation::sourceValidity() const
+{
+    if (!hasSourceValidity())
+        throw std::runtime_error("Attempt to access null validity.");
+    return model().resolveGeometry(model_ptr<simfil::ModelNode>::make(model_, data_->sourceValidity_));
+}
+
+bool Relation::hasSourceValidity() const
+{
+    return data_->sourceValidity_;
+}
+
+void Relation::setSourceValidity(const model_ptr<Geometry>& validityGeom)
+{
+    data_->sourceValidity_ = validityGeom->addr();
+}
+
+model_ptr<Geometry> Relation::targetValidity() const
+{
+    if (!hasTargetValidity())
+        throw std::runtime_error("Attempt to access null validity.");
+    return model().resolveGeometry(model_ptr<simfil::ModelNode>::make(model_, data_->targetValidity_));
+}
+
+bool Relation::hasTargetValidity() const
+{
+    return data_->targetValidity_;
+}
+
+void Relation::setTargetValidity(const model_ptr<Geometry>& validityGeom)
+{
+    data_->targetValidity_ = validityGeom->addr();
+}
+
+std::string_view Relation::name() const
+{
+    if (auto s = model().fieldNames()->resolve(data_->name_))
+        return *s;
+    throw logRuntimeError("Relation name is not known to string pool.");
+}
+
+model_ptr<FeatureId> Relation::target() const
+{
+    return model().resolveFeatureId(*model_ptr<simfil::ModelNode>::make(model_, data_->targetFeatureId_));
+}
+
+simfil::ValueType Relation::type() const
+{
+    return simfil::ValueType::Object;
+}
+
+simfil::ModelNode::Ptr Relation::at(int64_t i) const
+{
+    switch (i) {
+    case 0: // name
+        return model_ptr<simfil::ValueNode>::make(name(), model().shared_from_this());
+    case 1: // target
+        return ModelNode::Ptr::make(model().shared_from_this(), data_->targetFeatureId_);
+    case 2: // source validity
+        return ModelNode::Ptr::make(model().shared_from_this(), data_->sourceValidity_);
+    case 3: // target validity
+        return ModelNode::Ptr::make(model().shared_from_this(), data_->targetValidity_);
+    default:
+        return {};
+    }
+}
+
+uint32_t Relation::size() const
+{
+    return 2 + (data_->sourceValidity_ || data_->targetValidity_ ? 2 : 0);
+}
+
+simfil::ModelNode::Ptr Relation::get(const simfil::FieldId& f) const
+{
+    switch (f) {
+    case Fields::NameStr: // name
+        return model_ptr<simfil::ValueNode>::make(name(), model().shared_from_this());
+    case Fields::TargetStr: // target
+        return ModelNode::Ptr::make(model().shared_from_this(), data_->targetFeatureId_);
+    case Fields::SourceValidityStr: // source validity
+        return ModelNode::Ptr::make(model().shared_from_this(), data_->sourceValidity_);
+    case Fields::TargetValidityStr: // target validity
+        return ModelNode::Ptr::make(model().shared_from_this(), data_->targetValidity_);
+    default:
+        return {};
+    }
+}
+
+simfil::FieldId Relation::keyAt(int64_t i) const
+{
+    switch (i) {
+    case 0: return Fields::NameStr;
+    case 1: return Fields::TargetStr;
+    case 2: return Fields::SourceValidityStr;
+    case 3: return Fields::TargetValidityStr;
+    default:
+        return {};
+    }
+}
+
+bool Relation::iterate(const simfil::ModelNode::IterCallback& cb) const
+{
+    return std::all_of(begin(), end(), [&cb](auto&& child){return cb(*child);});
+}
+
+}
\ No newline at end of file
diff --git a/libs/model/src/stream.cpp b/libs/model/src/stream.cpp
index 300ae50e..c3c6defc 100644
--- a/libs/model/src/stream.cpp
+++ b/libs/model/src/stream.cpp
@@ -89,7 +89,7 @@ bool TileLayerStream::Reader::readMessageHeader(std::stringstream & stream, Mess
     Version protocolVersion;
     s.object(protocolVersion);
     if (!protocolVersion.isCompatible(CurrentProtocolVersion)) {
-        throw logRuntimeError(stx::format(
+        throw logRuntimeError(fmt::format(
             "Unable to read message with version {} using version {}.",
             protocolVersion.toString(),
             CurrentProtocolVersion.toString()));
diff --git a/libs/pymapget/CMakeLists.txt b/libs/pymapget/CMakeLists.txt
index 13c33672..af8aa7a6 100644
--- a/libs/pymapget/CMakeLists.txt
+++ b/libs/pymapget/CMakeLists.txt
@@ -36,6 +36,7 @@ if (MSVC)
 else()
   set(DEPLOY_FILES "${CMAKE_CURRENT_LIST_DIR}/__main__.py")
 endif ()
+list(APPEND DEPLOY_FILES $<TARGET_FILE:simfil::simfil>)
 
 add_wheel(pymapget
   NAME mapget
diff --git a/libs/pymapget/binding/py-layer.h b/libs/pymapget/binding/py-layer.h
index 9ab3f9ed..de975e6e 100644
--- a/libs/pymapget/binding/py-layer.h
+++ b/libs/pymapget/binding/py-layer.h
@@ -95,14 +95,14 @@ void bindTileLayer(py::module_& m)
         )pbdoc")
         .def(
             "set_prefix",
-            [](TileFeatureLayer& self, KeyValuePairs const& v) {self.setPrefix(v); },
+            [](TileFeatureLayer& self, KeyValueViewPairs const& v) {self.setPrefix(v); },
             py::arg("prefix"),
             R"pbdoc(
             Set common id prefix for all features in this layer.
         )pbdoc")
         .def(
             "new_feature",
-            [](TileFeatureLayer& self, std::string const& typeId, KeyValuePairs const& idParts)
+            [](TileFeatureLayer& self, std::string const& typeId, KeyValueViewPairs const& idParts)
             { return BoundFeature(self.newFeature(typeId, idParts)); },
             py::arg("type_id"),
             py::arg("feature_id_parts"),
@@ -113,7 +113,7 @@ void bindTileLayer(py::module_& m)
         )pbdoc")
         .def(
             "new_feature_id",
-            [](TileFeatureLayer& self, std::string const& typeId, KeyValuePairs const& idParts)
+            [](TileFeatureLayer& self, std::string const& typeId, KeyValueViewPairs const& idParts)
             { return BoundFeatureId(self.newFeatureId(typeId, idParts)); },
             py::arg("type_id"),
             py::arg("feature_id_parts"),
diff --git a/libs/pymapget/binding/py-model.h b/libs/pymapget/binding/py-model.h
index e2c1724b..4ea8cd90 100644
--- a/libs/pymapget/binding/py-model.h
+++ b/libs/pymapget/binding/py-model.h
@@ -379,44 +379,44 @@ struct BoundFeature : public BoundModelNode
                 { return BoundAttributeLayerList(self.modelNodePtr_->attributeLayers()); },
                 "Access this feature's attribute layer collection.")
             .def(
-                "children",
-                [](BoundFeature& self) { return BoundArray(self.modelNodePtr_->children()); },
-                "Access this feature's child feature id list.")
-                .def(
-                    "add_point",
-                    [](BoundFeature& self, Point const& p) {
-                        self.modelNodePtr_->addPoint(p);
-                    },
-                    py::arg("p"),
-                    "Add a point to the feature.")
-                .def(
-                    "add_points",
-                    [](BoundFeature& self, std::vector<Point> const& points) {
-                        self.modelNodePtr_->addPoints(points);
-                    },
-                    py::arg("points"),
-                    "Add multiple points to the feature.")
-                .def(
-                    "add_line",
-                    [](BoundFeature& self, std::vector<Point> const& points) {
-                        self.modelNodePtr_->addLine(points);
-                    },
-                    py::arg("points"),
-                    "Add a line to the feature.")
-                .def(
-                    "add_mesh",
-                    [](BoundFeature& self, std::vector<Point> const& points) {
-                        self.modelNodePtr_->addMesh(points);
-                    },
-                    py::arg("points"),
-                    "Add a mesh to the feature, len(points) must be multiple of three.")
-                .def(
-                    "add_poly",
-                    [](BoundFeature& self, std::vector<Point> const& points) {
-                        self.modelNodePtr_->addPoly(points);
-                    },
-                    py::arg("points"),
-                    "Add a polygon to the feature.");
+                "relations",
+                [](BoundFeature& self) { return BoundArray(self.modelNodePtr_->relations()); },
+                "Access this feature's relation list.")
+            .def(
+                "add_point",
+                [](BoundFeature& self, Point const& p) {
+                    self.modelNodePtr_->addPoint(p);
+                },
+                py::arg("p"),
+                "Add a point to the feature.")
+            .def(
+                "add_points",
+                [](BoundFeature& self, std::vector<Point> const& points) {
+                    self.modelNodePtr_->addPoints(points);
+                },
+                py::arg("points"),
+                "Add multiple points to the feature.")
+            .def(
+                "add_line",
+                [](BoundFeature& self, std::vector<Point> const& points) {
+                    self.modelNodePtr_->addLine(points);
+                },
+                py::arg("points"),
+                "Add a line to the feature.")
+            .def(
+                "add_mesh",
+                [](BoundFeature& self, std::vector<Point> const& points) {
+                    self.modelNodePtr_->addMesh(points);
+                },
+                py::arg("points"),
+                "Add a mesh to the feature, len(points) must be multiple of three.")
+            .def(
+                "add_poly",
+                [](BoundFeature& self, std::vector<Point> const& points) {
+                    self.modelNodePtr_->addPoly(points);
+                },
+                py::arg("points"),
+                "Add a polygon to the feature.");
     }
 
     ModelNode::Ptr node() override { return modelNodePtr_; }
diff --git a/libs/pymapget/py-mapget.cpp b/libs/pymapget/py-mapget.cpp
index 09ab252a..d2e97515 100644
--- a/libs/pymapget/py-mapget.cpp
+++ b/libs/pymapget/py-mapget.cpp
@@ -2,7 +2,7 @@
 #include <pybind11/stl_bind.h>
 #include <pybind11/stl.h>
 #include <pybind11/functional.h>
-#include "stx/format.h"
+#include "fmt/format.h"
 
 namespace py = pybind11;
 using namespace py::literals;
diff --git a/libs/service/CMakeLists.txt b/libs/service/CMakeLists.txt
index 72ce3664..e9dbef42 100644
--- a/libs/service/CMakeLists.txt
+++ b/libs/service/CMakeLists.txt
@@ -6,12 +6,14 @@ add_library(mapget-service STATIC
   include/mapget/service/datasource.h
   include/mapget/service/memcache.h
   include/mapget/service/rocksdbcache.h
+  include/mapget/service/locate.h
 
   src/service.cpp
   src/cache.cpp
   src/datasource.cpp
   src/memcache.cpp
-  src/rocksdbcache.cpp)
+  src/rocksdbcache.cpp
+  src/locate.cpp)
 
 target_include_directories(mapget-service
   PUBLIC
@@ -21,7 +23,6 @@ target_include_directories(mapget-service
 
 target_link_libraries(mapget-service
   PUBLIC
-    stx::stx
     mapget-model
     mapget-log
     rocksdb)
diff --git a/libs/service/include/mapget/service/datasource.h b/libs/service/include/mapget/service/datasource.h
index 86716d1b..a99c0be9 100644
--- a/libs/service/include/mapget/service/datasource.h
+++ b/libs/service/include/mapget/service/datasource.h
@@ -1,6 +1,7 @@
 #pragma once
 
 #include "cache.h"
+#include "locate.h"
 
 namespace mapget
 {
@@ -34,6 +35,14 @@ class DataSource
      */
     virtual void fill(TileFeatureLayer::Ptr const& featureTile) = 0;
 
+    /**
+     * Obtain a map tile key, where the feature with the specified ID may be found.
+     * The implementation is completely datasource-specific. Note, that the returned
+     * resulting LocateResponse may have resolved to a different typeId and featureId
+     * than the requested one.
+     */
+    virtual std::optional<LocateResponse> locate(LocateRequest const& req);
+
     /** Called by mapget::Service worker. Dispatches to Cache or fill(...) on miss. */
     virtual TileFeatureLayer::Ptr get(MapTileKey const& k, Cache::Ptr& cache, DataSourceInfo const& info);
 
diff --git a/libs/service/include/mapget/service/locate.h b/libs/service/include/mapget/service/locate.h
new file mode 100644
index 00000000..98f25b77
--- /dev/null
+++ b/libs/service/include/mapget/service/locate.h
@@ -0,0 +1,47 @@
+#pragma once
+
+#pragma once
+
+#include "cache.h"
+
+namespace mapget
+{
+
+/**
+ * Class which models a request object that is passed into the
+ * Service::Locate function.
+ */
+class LocateRequest
+{
+public:
+    explicit LocateRequest(nlohmann::json const& j);
+    virtual ~LocateRequest() = default;
+
+    std::string mapId_;
+    std::string typeId_;
+    KeyValuePairs featureId_;
+
+    void setFeatureId(KeyValueViewPairs const& kvp);
+
+    [[nodiscard]] std::optional<int64_t> getIntIdPart(std::string_view const& idPart) const;
+    [[nodiscard]] std::optional<std::string_view> getStrIdPart(std::string_view const& idPart) const;
+
+    [[nodiscard]] virtual nlohmann::json serialize() const;
+};
+
+/**
+ * Class which models a response object that is returned from
+ * the Service::Locate function.
+ */
+class LocateResponse : public LocateRequest
+{
+public:
+    explicit LocateResponse(nlohmann::json const& j);
+    LocateResponse(LocateRequest const& req);
+
+    MapTileKey tileKey_;
+
+    [[nodiscard]] nlohmann::json serialize() const override;
+};
+
+}
diff --git a/libs/service/include/mapget/service/service.h b/libs/service/include/mapget/service/service.h
index 688f754c..f7574579 100644
--- a/libs/service/include/mapget/service/service.h
+++ b/libs/service/include/mapget/service/service.h
@@ -2,6 +2,7 @@
 
 #include "cache.h"
 #include "datasource.h"
+#include "mapget/model/layer.h"
 #include "memcache.h"
 
 #include <condition_variable>
@@ -30,7 +31,7 @@ class LayerTilesRequest
 public:
     using Ptr = std::shared_ptr<LayerTilesRequest>;
 
-    /** Construct a request with the relevant parameters. */
+    /** Construct a request for tiles with the relevant parameters. */
     LayerTilesRequest(
         std::string mapId,
         std::string layerId,
@@ -132,6 +133,13 @@ class Service
      */
     bool request(std::vector<LayerTilesRequest::Ptr> requests);
 
+    /**
+     * Trigger queries to all connected data sources to check
+     * for a feature matching the given typeId and idParts.
+     * Returns the list of MapTileKeys received from data sources.
+     */
+    std::vector<LocateResponse> locate(LocateRequest const& req);
+
     /**
      * Abort the given request. The request will be removed from
      * the processing queue, and forcefully marked as done.
diff --git a/libs/service/src/cache.cpp b/libs/service/src/cache.cpp
index 874d6095..fd13a141 100644
--- a/libs/service/src/cache.cpp
+++ b/libs/service/src/cache.cpp
@@ -1,7 +1,7 @@
 #include "cache.h"
 #include "mapget/log.h"
 
-#include "stx/format.h"
+#include "fmt/format.h"
 
 namespace mapget
 {
@@ -71,7 +71,7 @@ TileFeatureLayer::Ptr Cache::getTileFeatureLayer(const MapTileKey& tileKey, Data
     TileLayerStream::Reader tileReader(
         [&dataSource, &tileKey](auto&& mapId, auto&& layerId){
             if (dataSource.mapId_ != mapId) {
-                throw logRuntimeError(stx::format(
+                throw logRuntimeError(fmt::format(
                     "Encountered unexpected map id '{}' in cache for tile {:0x}, expected '{}'",
                     mapId,
                     tileKey.tileId_.value_,
diff --git a/libs/service/src/datasource.cpp b/libs/service/src/datasource.cpp
index 3e0c1dae..51709fdd 100644
--- a/libs/service/src/datasource.cpp
+++ b/libs/service/src/datasource.cpp
@@ -20,4 +20,9 @@ simfil::FieldId DataSource::cachedFieldsOffset(const std::string& nodeId, Cache:
     return cache->cachedFieldsOffset(nodeId);
 }
 
+std::optional<LocateResponse> DataSource::locate(const LocateRequest& req)
+{
+    return {};
+}
+
 }
\ No newline at end of file
diff --git a/libs/service/src/locate.cpp b/libs/service/src/locate.cpp
new file mode 100644
index 00000000..e91f106f
--- /dev/null
+++ b/libs/service/src/locate.cpp
@@ -0,0 +1,100 @@
+#include "locate.h"
+
+namespace mapget
+{
+
+LocateRequest::LocateRequest(const nlohmann::json& j)
+{
+    if (j.contains("mapId"))
+        mapId_ = j["mapId"].get<std::string>();
+    if (j.contains("typeId"))
+        typeId_ = j["typeId"].get<std::string>();
+    if (j.contains("featureId")) {
+        auto featureIdParts = j["featureId"];
+        auto numFeatureIdParts = featureIdParts.size();
+        for (auto kvIndex = 0; kvIndex < numFeatureIdParts; kvIndex += 2) {
+            auto key = featureIdParts.at(kvIndex).get<std::string>();
+            auto value = featureIdParts.at(kvIndex + 1);
+            if (value.is_number())
+                featureId_.emplace_back(key, value.get<int64_t>());
+            else
+                featureId_.emplace_back(key, value.get<std::string>());
+        }
+    }
+}
+
+nlohmann::json LocateRequest::serialize() const
+{
+    nlohmann::json featureId = nlohmann::json::array();
+    for (auto const& [k, v] : featureId_) {
+        featureId.emplace_back(k);
+        std::visit([&featureId](auto&& vv){
+            featureId.emplace_back(vv);
+        }, v);
+    }
+    return nlohmann::json::object({
+        {"mapId", mapId_},
+        {"typeId", typeId_},
+        {"featureId", featureId},
+    });
+}
+
+LocateResponse::LocateResponse(const LocateRequest& req) : LocateRequest(req)
+{
+    tileKey_.mapId_ = req.mapId_;
+    tileKey_.layer_ = LayerType::Features;
+}
+
+LocateResponse::LocateResponse(const nlohmann::json& j) : LocateRequest(j)
+{
+    if (j.contains("tileId")) {
+        tileKey_ = MapTileKey(j["tileId"].get<std::string>());
+    }
+}
+
+nlohmann::json LocateResponse::serialize() const
+{
+    auto result = LocateRequest::serialize();
+    result["tileId"] = tileKey_.toString();
+    return result;
+}
+
+std::optional<int64_t> LocateRequest::getIntIdPart(const std::string_view& idPart) const
+{
+    for (auto const& [key, value] : featureId_) {
+        if (key == idPart) {
+            if (std::holds_alternative<int64_t>(value)) {
+                return std::get<int64_t>(value);
+            }
+        }
+    }
+    return {};
+}
+
+std::optional<std::string_view> LocateRequest::getStrIdPart(const std::string_view& idPart) const
+{
+    for (auto const& [key, value] : featureId_) {
+        if (key == idPart) {
+            if (std::holds_alternative<std::string>(value)) {
+                return std::get<std::string>(value);
+            }
+        }
+    }
+    return {};
+}
+
+void LocateRequest::setFeatureId(const KeyValueViewPairs& kvp)
+{
+    // Convert KeyValueViewPairs to KeyValuePairs
+    featureId_.clear();
+    for (auto const& [k, v] : kvp) {
+        std::visit([this, &k](auto&& vv){
+            if constexpr (std::is_same_v<std::decay_t<decltype(vv)>, std::string_view>)
+                featureId_.emplace_back(k, std::string(vv));
+            else
+                featureId_.emplace_back(k, vv);
+        }, v);
+    }
+}
+
+}  // namespace mapget
diff --git a/libs/service/src/rocksdbcache.cpp b/libs/service/src/rocksdbcache.cpp
index 9b4f8f65..e8af4206 100644
--- a/libs/service/src/rocksdbcache.cpp
+++ b/libs/service/src/rocksdbcache.cpp
@@ -48,10 +48,10 @@ RocksDBCache::RocksDBCache(uint32_t cacheMaxTiles, std::string cachePath, bool c
     if (fs::path(cachePath).is_relative()) {
         absoluteCachePath = fs::current_path() / cachePath;
     }
-    log().debug(stx::format("Initializing RocksDB cache under: {}", absoluteCachePath.string()));
+    log().debug(fmt::format("Initializing RocksDB cache under: {}", absoluteCachePath.string()));
 
     if (!fs::exists(absoluteCachePath.parent_path())) {
-        throw logRuntimeError(stx::format(
+        throw logRuntimeError(fmt::format(
             "Error initializing rocksDB cache: parent directory {} does not exist!",
             absoluteCachePath.parent_path().string()));
     }
@@ -69,7 +69,7 @@ RocksDBCache::RocksDBCache(uint32_t cacheMaxTiles, std::string cachePath, bool c
             "RocksDB cache is corrupted, restart with '--clear-cache 1'!");
     }
     else if (!status.ok()) {
-        throw logRuntimeError(stx::format(
+        throw logRuntimeError(fmt::format(
             "Error opening database at {}: {}",
             absoluteCachePath.string(),
             status.ToString()));
@@ -113,7 +113,7 @@ RocksDBCache::RocksDBCache(uint32_t cacheMaxTiles, std::string cachePath, bool c
         key_count_ = max_key_count_;
     }
 
-    log().debug(stx::format("Initialized RocksDB cache with {} existing tile entries.",key_count_));
+    log().debug(fmt::format("Initialized RocksDB cache with {} existing tile entries.",key_count_));
 }
 
 RocksDBCache::~RocksDBCache()
@@ -131,7 +131,7 @@ std::optional<std::string> RocksDBCache::getTileLayer(MapTileKey const& k)
         db_->Get(read_options_, column_family_handles_[COL_TILES], k.toString(), &read_value);
 
     if (status.ok()) {
-        log().trace(stx::format("Key: {} | Layer size: {}", k.toString(), read_value.size()));
+        log().trace(fmt::format("Key: {} | Layer size: {}", k.toString(), read_value.size()));
         log().debug("Cache hits: {}, cache misses: {}", cacheHits_, cacheMisses_);
         return read_value;
     }
@@ -139,7 +139,7 @@ std::optional<std::string> RocksDBCache::getTileLayer(MapTileKey const& k)
         return {};
     }
 
-    throw logRuntimeError(stx::format("Error reading from database: {}", status.ToString()));
+    throw logRuntimeError(fmt::format("Error reading from database: {}", status.ToString()));
 }
 
 void RocksDBCache::putTileLayer(MapTileKey const& k, std::string const& v)
@@ -172,7 +172,7 @@ void RocksDBCache::putTileLayer(MapTileKey const& k, std::string const& v)
     auto status = db_->Write(write_options_, &newTileBatch);
 
     if (!status.ok()) {
-        throw logRuntimeError(stx::format("Error writing to database: {}", status.ToString()));
+        throw logRuntimeError(fmt::format("Error writing to database: {}", status.ToString()));
     }
 
     ++key_count_;
@@ -195,7 +195,7 @@ void RocksDBCache::putTileLayer(MapTileKey const& k, std::string const& v)
 
         if (!purgeStatus.ok()) {
             throw logRuntimeError(
-                stx::format("Could not delete oldest cache entry: {}", purgeStatus.ToString()));
+                fmt::format("Could not delete oldest cache entry: {}", purgeStatus.ToString()));
         }
         --key_count_;
     }
@@ -208,14 +208,14 @@ std::optional<std::string> RocksDBCache::getFields(std::string_view const& sourc
         db_->Get(read_options_, column_family_handles_[COL_FIELD_DICTS], sourceNodeId, &read_value);
 
     if (status.ok()) {
-        log().trace(stx::format("Node: {} | Field dict size: {}", sourceNodeId, read_value.size()));
+        log().trace(fmt::format("Node: {} | Field dict size: {}", sourceNodeId, read_value.size()));
         return read_value;
     }
     else if (status.IsNotFound()) {
         return {};
     }
 
-    throw logRuntimeError(stx::format("Error reading from database: {}", status.ToString()));
+    throw logRuntimeError(fmt::format("Error reading from database: {}", status.ToString()));
 }
 
 void RocksDBCache::putFields(std::string_view const& sourceNodeId, std::string const& v)
@@ -224,7 +224,7 @@ void RocksDBCache::putFields(std::string_view const& sourceNodeId, std::string c
         db_->Put(write_options_, column_family_handles_[COL_FIELD_DICTS], sourceNodeId, v);
 
     if (!status.ok()) {
-        throw logRuntimeError(stx::format("Error writing to database: {}", status.ToString()));
+        throw logRuntimeError(fmt::format("Error writing to database: {}", status.ToString()));
     }
 }
 
diff --git a/libs/service/src/service.cpp b/libs/service/src/service.cpp
index f1b860c1..a8153c31 100644
--- a/libs/service/src/service.cpp
+++ b/libs/service/src/service.cpp
@@ -282,7 +282,7 @@ struct Service::Impl : public Service::Controller
             if (existingSource.second.nodeId_ == dataSource->info().nodeId_) {
                 // Unique node IDs are required for the field offsets.
                 throw logRuntimeError(
-                    stx::format("Data source with node ID '{}' already registered!",
+                    fmt::format("Data source with node ID '{}' already registered!",
                                 dataSource->info().nodeId_));
             }
         }
@@ -402,6 +402,16 @@ bool Service::request(std::vector<LayerTilesRequest::Ptr> requests)
     return dataSourcesAvailable;
 }
 
+std::vector<LocateResponse> Service::locate(LocateRequest const& req)
+{
+    std::vector<LocateResponse> results;
+    for (auto const& [ds, info] : impl_->dataSourceInfo_)
+        if (info.mapId_ == req.mapId_)
+            if (auto location = ds->locate(req))
+                results.emplace_back(*location);
+    return results;
+}
+
 void Service::abort(const LayerTilesRequest::Ptr& r)
 {
     impl_->abortRequest(r);
@@ -421,8 +431,7 @@ bool Service::hasLayer(std::string const& mapId, std::string const& layerId)
 {
     std::unique_lock lock(impl_->jobsMutex_);
     // Check that one of the data sources can fulfill the request.
-    for (auto& dataSourceAndInfo : impl_->dataSourceInfo_) {
-        auto& info = dataSourceAndInfo.second;
+    for (auto& [ds, info] : impl_->dataSourceInfo_) {
         if (mapId != info.mapId_)
             continue;
         if (info.layers_.find(layerId) != info.layers_.end()) {


Test patch:
diff --git a/test/unit/test-cache.cpp b/test/unit/test-cache.cpp
index 56286268..53e96a3a 100644
--- a/test/unit/test-cache.cpp
+++ b/test/unit/test-cache.cpp
@@ -1,8 +1,10 @@
+#include <cstdint>
 #include <bitsery/bitsery.h>
 #include <bitsery/adapter/stream.h>
 
 #include <catch2/catch_test_macros.hpp>
 #include <chrono>
+
 #include "mapget/http-service/cli.h"
 #include "mapget/log.h"
 #include "mapget/service/rocksdbcache.h"
@@ -224,7 +226,7 @@ TEST_CASE("RocksDBCache", "[Cache]")
 
         std::filesystem::path test_cache = std::filesystem::temp_directory_path() /
             ("rocksdb-unit-test-" + std::to_string(epoch_time));
-        log().info(stx::format("Test creating cache: {}", test_cache.string()));
+        log().info(fmt::format("Test creating cache: {}", test_cache.string()));
 
         // Delete cache if it already exists, e.g. from a broken test case.
         if (std::filesystem::exists(test_cache)) {
diff --git a/test/unit/test-http-datasource.cpp b/test/unit/test-http-datasource.cpp
index 0e17301f..147a5f45 100644
--- a/test/unit/test-http-datasource.cpp
+++ b/test/unit/test-http-datasource.cpp
@@ -56,6 +56,18 @@ TEST_CASE("HttpDataSource", "[HttpDataSource]")
             g->append({42., 12});
             ++dataSourceRequestCount;
         });
+    ds.onLocateRequest(
+        [&](mapget::LocateRequest const& request) -> std::optional<mapget::LocateResponse>
+        {
+            REQUIRE(request.mapId_ == "Tropico");
+            REQUIRE(request.typeId_ == "Way");
+            REQUIRE(request.featureId_ == mapget::KeyValuePairs{{"wayId", 0}});
+
+            mapget::LocateResponse response(request);
+            response.tileKey_.layerId_ = "WayLayer";
+            response.tileKey_.tileId_.value_ = 1;
+            return response;
+        });
 
     // Launch the DataSource on a separate thread.
     ds.go();
@@ -101,6 +113,30 @@ TEST_CASE("HttpDataSource", "[HttpDataSource]")
         REQUIRE(receivedTileCount == 1);
     }
 
+    SECTION("Fetch /locate")
+    {
+        // Initialize an httplib client.
+        httplib::Client cli("localhost", ds.port());
+
+        // Send a POST locate request.
+        auto response = cli.Post("/locate", R"({
+            "mapId": "Tropico",
+            "typeId": "Way",
+            "featureId": ["wayId", 0]
+        })", "application/json");
+
+        // Check that the response is OK.
+        REQUIRE(response != nullptr);
+        REQUIRE(response->status == 200);
+
+        // Check the response body for expected content.
+        mapget::LocateResponse responseParsed(nlohmann::json::parse(response->body));
+        REQUIRE(responseParsed.tileKey_.mapId_ == "Tropico");
+        REQUIRE(responseParsed.tileKey_.layer_ == mapget::LayerType::Features);
+        REQUIRE(responseParsed.tileKey_.layerId_ == "WayLayer");
+        REQUIRE(responseParsed.tileKey_.tileId_.value_ == 1);
+    }
+
     SECTION("Query mapget HTTP service")
     {
         mapget::HttpService service;
@@ -149,6 +185,35 @@ TEST_CASE("HttpDataSource", "[HttpDataSource]")
             REQUIRE(receivedTileCount == 0);
         }
 
+        SECTION("Run /locate through service")
+        {
+            httplib::Client client("localhost", service.port());
+
+            // Send a POST locate request.
+            auto response = client.Post("/locate", R"({
+                "requests": [{
+                    "mapId": "Tropico",
+                    "typeId": "Way",
+                    "featureId": ["wayId", 0]
+                }]
+            })", "application/json");
+
+            // Check that the response is OK.
+            REQUIRE(response != nullptr);
+            REQUIRE(response->status == 200);
+
+            // Check the response body for expected content.
+            auto responseJsonLists = nlohmann::json::parse(response->body)["responses"];
+            REQUIRE(responseJsonLists.size() == 1);
+            auto responseJsonList = responseJsonLists[0];
+            REQUIRE(responseJsonList.size() == 1);
+            mapget::LocateResponse responseParsed(responseJsonList[0]);
+            REQUIRE(responseParsed.tileKey_.mapId_ == "Tropico");
+            REQUIRE(responseParsed.tileKey_.layer_ == mapget::LayerType::Features);
+            REQUIRE(responseParsed.tileKey_.layerId_ == "WayLayer");
+            REQUIRE(responseParsed.tileKey_.tileId_.value_ == 1);
+        }
+
         service.stop();
         REQUIRE(service.isRunning() == false);
     }
diff --git a/test/unit/test-model.cpp b/test/unit/test-model.cpp
index 1e59d506..b540dc93 100644
--- a/test/unit/test-model.cpp
+++ b/test/unit/test-model.cpp
@@ -35,11 +35,6 @@ TEST_CASE("FeatureLayer", "[test.featurelayer]")
                         }
                     ],
                     [
-                        {
-                            "partId": "areaId",
-                            "description": "String which identifies the map area.",
-                            "datatype": "STR"
-                        },
                         {
                             "partId": "wayIdU32",
                             "description": "A 32b uinteger.",
@@ -57,11 +52,6 @@ TEST_CASE("FeatureLayer", "[test.featurelayer]")
                         }
                     ],
                     [
-                        {
-                            "partId": "areaId",
-                            "description": "String which identifies the map area.",
-                            "datatype": "STR"
-                        },
                         {
                             "partId": "wayIdI32",
                             "description": "A 32b integer.",
@@ -94,12 +84,16 @@ TEST_CASE("FeatureLayer", "[test.featurelayer]")
         layerInfo,
         fieldNames);
 
-    // Test creating a feature while tile prefix is not set
-    auto feature0 = tile->newFeature("Way", {{"areaId", "MediocreArea"}, {"wayId", 24}});
-
-    // Set the tile feature id prefix
+    // Set the tile's feature id prefix.
     tile->setPrefix({{"areaId", "TheBestArea"}});
 
+    // Test creating a feature while tile prefix is not set.
+    auto feature0 = tile->newFeature("Way", {{"wayId", 24}});
+
+    // Setting the tile feature id prefix after a feature was added
+    // must lead to a runtime error.
+    REQUIRE_THROWS(tile->setPrefix({{"areaId", "TheBestArea"}}));
+
     // Create a feature with line geometry
     auto feature1 = tile->newFeature("Way", {{"wayId", 42}});
     auto line = feature1->geom()->newGeometry(Geometry::GeomType::Line, 2);
@@ -122,14 +116,20 @@ TEST_CASE("FeatureLayer", "[test.featurelayer]")
     attr->setDirection(Attribute::Direction::Positive);
     attr->addField("smell", "neutral");
 
-    // Add other features using different ID compositions
-    auto featureForId1 = tile->newFeature(
+    // Add feature ids using secondary ID compositions
+    auto featureForId1 = tile->newFeatureId(
         "Way",
         {{"wayIdU32", 42}, {"wayIdU64", 84}, {"wayIdUUID128", "0123456789abcdef"}});
-    auto featureForId2 = tile->newFeature(
+    auto featureForId2 = tile->newFeatureId(
         "Way",
         {{"wayIdI32", -42}, {"wayIdI64", -84}, {"wayIdUUID128", "0123456789abcdef"}});
 
+    SECTION("firstGeometry")
+    {
+        auto firstGeom = feature1->firstGeometry();
+        REQUIRE(firstGeom->geomType() == GeomType::Line);
+    }
+
     SECTION("toGeoJSON")
     {
         constexpr auto expected = R"({"areaId":"TheBestArea","geometry":{"geometries":[{"coordinates":[[41.0,10.0,0.0],[43.0,11.0,0.0]],"type":"LineString"},{"coordinates":[[41.5,10.5,0.0]],"type":"MultiPoint"},{"coordinates":[[41.5,10.5,0.0],[41.600000001490116,10.700000002980232,0.0]],"type":"MultiPoint"},{"coordinates":[[41.5,10.5,0.0],[41.600000001490116,10.700000002980232,0.0]],"type":"LineString"},{"coordinates":[[41.5,10.5,0.0],[41.600000001490116,10.700000002980232,0.0],[41.5,10.299999997019768,0.0]],"type":"MultiPolygon"},{"coordinates":[[41.5,10.5,0.0],[41.600000001490116,10.700000002980232,0.0],[41.5,10.299999997019768,0.0],[41.80000001192093,10.900000005960464,0.0]],"type":"Polygon"}],"type":"GeometryCollection"},"id":"Way.TheBestArea.42","properties":{"layer":{"cheese":{"mozzarella":{"direction":"POSITIVE","smell":"neutral"}}},"main_ingredient":"Pepper"},"type":"Feature","typeId":"Way","wayId":42})";
@@ -162,7 +162,7 @@ TEST_CASE("FeatureLayer", "[test.featurelayer]")
     }
 
     SECTION("Create feature ID with negative value in uint") {
-        CHECK_THROWS(tile->newFeature(
+        CHECK_THROWS(tile->newFeatureId(
             "Way",
             {{"wayIdU32", -4},
              {"wayIdU64", -2},
@@ -170,7 +170,7 @@ TEST_CASE("FeatureLayer", "[test.featurelayer]")
     }
 
     SECTION("Create feature ID with non-16-byte UUID128") {
-        CHECK_THROWS(tile->newFeature(
+        CHECK_THROWS(tile->newFeatureId(
             "Way",
             {{"wayIdU32", 4},
              {"wayIdU64", 2},
@@ -178,7 +178,7 @@ TEST_CASE("FeatureLayer", "[test.featurelayer]")
     }
 
     SECTION("Create feature ID with no matching composition") {
-        CHECK_THROWS(tile->newFeature(
+        CHECK_THROWS(tile->newFeatureId(
             "Way",
             {{"wayIdI32", -4},
              {"wayIdU64", 2},
@@ -270,9 +270,26 @@ TEST_CASE("FeatureLayer", "[test.featurelayer]")
         REQUIRE(readTiles.size() == 3);
         REQUIRE(readTiles[0]->fieldNames() == readTiles[1]->fieldNames());
         REQUIRE(readTiles[1]->fieldNames() == readTiles[2]->fieldNames());
-        REQUIRE(readTiles[0]->numRoots() == 4);
-        REQUIRE(readTiles[1]->numRoots() == 4);
-        REQUIRE(readTiles[2]->numRoots() == 5);
+        REQUIRE(readTiles[0]->numRoots() == 2);
+        REQUIRE(readTiles[1]->numRoots() == 2);
+        REQUIRE(readTiles[2]->numRoots() == 3);
+    }
+
+    SECTION("Find")
+    {
+        auto foundFeature01 = tile->find("Way", KeyValueViewPairs{{"areaId", "TheBestArea"}, {"wayId", 24}});
+        REQUIRE(foundFeature01);
+        REQUIRE(foundFeature01->addr() == feature0->addr());
+
+        auto foundFeature11 = tile->find("Way", KeyValueViewPairs{{"areaId", "TheBestArea"}, {"wayId", 42}});
+        REQUIRE(foundFeature11);
+        REQUIRE(foundFeature11->addr() == feature1->addr());
+
+        auto foundFeature00 = tile->find("Way", KeyValueViewPairs{{"areaId", "MediocreArea"}, {"wayId", 24}});
+        REQUIRE(!foundFeature00);
+
+        auto foundFeature10 = tile->find("Way", KeyValueViewPairs{{"wayId", 42}});
+        REQUIRE(!foundFeature10);
     }
 }