[Location Hierarchy] Add location hierarchy lineage ids to each location.

[dubdabasoduba]

Context

• Location hierarchies are defined by the partOf relationship in Location resources.
• The gateway server leverages these hierarchies for several operations i.e
  • Including retrieving hierarchical data from the location hierarchy endpoint
  • Downloading resources via the Related Entity Location (REL) sync strategy.
• However, the recursive nature of hierarchy generation imposes high computational and memory overhead on both servers and mobile clients, leading to performance bottlenecks such as slow response times or complete request failures.
• To mitigate these issues, this proposal suggests augmenting each Location resource’s meta.tags with the IDs of all parent locations, up to the root.
  • By storing the entire lineage in meta.tags, search queries for a given location ID can be handled natively by HAPI or other SDK search libraries, removing the need for expensive custom recursion logic.
  • This approach should reduce resource consumption, improve performance, and streamline location-based queries.
• The proposal is to have the codes look something like this
  • system - This is an OpenSRP defined system. We can change it to anything.
  • code - This is the location id for the parent location
  • display - This can be the Location Name. We can also add the location level here e.g Level 2

{
  "system": "http://smartregister.org/CodeSystem/location-hierarchy",
  "code": "4ddd4157-921b-4c65-820c-161b6e845011",
  "display": "Location Name"
}

Implementation

Web client & Tooling

• The OpenSRP web client will be updated to:
  • Record the Location Hierarchy IDs: When a new location is created, the client will store the IDs of all parent locations (up to the root) in the location’s metadata. If the parent location changes, this list of IDs will be regenerated to maintain an accurate hierarchy reference.
  • Simplify Updates: To keep the process straightforward, the entire list of hierarchy-related location IDs will be cleared and then rebuilt whenever a location’s parent changes. This ensures consistency and avoids partial or outdated entries.

Server side

• The FHIR Info Gateway will be modified to eliminate the recursive lookup used to retrieve location hierarchies. Instead, it will rely on the precomputed hierarchy IDs now stored in location.meta.tags.
  • This change reduces the computational overhead and memory usage for both the Related Entity Location (REL) sync strategy and the Location Hierarchy endpoint, significantly improving response times and overall performance.

Mobile Client

• The mobile application will be updated to remove the recursive logic currently used to fetch child locations when a specific parent location is selected (e.g., retrieving service points for map display in a given region within EUSM).
  • Instead, it will leverage the prepopulated hierarchy data in location.meta.tags, thereby reducing memory usage and improving performance.

Sample Location Resources

{
  "resourceType": "Location",
  "id": "aa5ac053-d8aa-4f42-b326-bae32e5944e1",
  "meta": {
    "versionId": "2",
    "lastUpdated": "2024-07-22T15:13:53.014+00:00",
    "source": "#1b7d28fd21bf0b63",
    "tag": [
      {
        "system" : "http://smartregister.org/CodeSystem/location-hierarchy",
        "code"   : "03176924-6b3c-4b74-bccd-32afcceebabd"                  ,
        "display": "Madagascar (Level 1)"
      },
      {
        "system" : "http://smartregister.org/CodeSystem/location-hierarchy",
        "code"   : "bf116fdd-6617-4302-88e4-72fd1af2851c"                  ,
        "display": "ALAOTRA MANGORO (Level 2)"
      },
      {
        "system" : "http://smartregister.org/CodeSystem/location-hierarchy",
        "code"   : "696b532f-15b1-4422-a0ab-3525587260cd"                  ,
        "display": "Ambatondrazaka (Level 3)"
      }
    ]
  },
  "identifier": [
    {"use": "official", "value": "aa5ac053-d8aa-4f42-b326-bae32e5944e1"}
  ],
  "status": "active",
  "name": "Ambandrika",
  "type": [
    {
      "coding": [
        {
          "system" : "http://terminology.hl7.org/CodeSystem/location-type",
          "code"   : "jdn"                                                ,
          "display": "jurisdiction"
        }
      ]
    },
    {
      "coding": [
        {
          "system" : "https://smartregister.org/codes/administrative-level",
          "code"   : "4"                                                   ,
          "display": "Level 4"
        }
      ]
    },
    {
      "coding": [
        {
          "system": "http://terminology.hl7.org/CodeSystem/location-physical-type",
          "code": "jdn",
          "display": "Jurisdiction"
        }
      ]
    }
  ],
  "physicalType": {
    "coding": [
      {
        "system": "http://terminology.hl7.org/CodeSystem/location-physical-type",
        "code": "jdn",
        "display": "Jurisdiction"
      }
    ]
  },
  "partOf": {
    "reference": "Location/696b532f-15b1-4422-a0ab-3525587260cd",
    "display"  : "Ambatondrazaka"
  }
}

[pld]

For the mobile client you mention remove the recursive logic currently used to fetch child locations, but the metadata is storing parents in the children, how will this help with fetching children?

Same question for the server side, what is the nature of the query now and how does this address that , please add more details there.

For the OpenSRP web client, that only addresses one way that the data can become stale. A client can make call directly against the API that would make the data stale. Please add a list of the edge cases that can make the data become stale.

For avoiding staleness for changes on the web, the approach is unclear, are you suggesting we regenerate the entire hierarchy with it's meta data whenever there is any change to any location? I agree, that would avoid staleness introduced through interactions on the fhir web, but it would be expensive, but only at write time, so that cost may be fine.

Also on the web when you say If the parent location changes, this list of IDs will be regenerated, are you referring to the list of IDs in the children? I assume so, but please be more specific. Whenever a location is removed or inserted we have to change every node in the sub-graph below that location.

On the specific metadata we are including, more detail on the use cases in the gateway and the mobile app will help with this. If we are only ever using this for further fetches or comparisons, storing a display seems unnecessary (it's duplicative of what we'll get when we do the ID search, and that will be authoritative). It's also not clear if it is important at what level the ancestors are at other than by either parsing display name (if we have it there like in your example), or fetching the resource referred to, if it stores it's level. If it's not important to know the levels of the ancestor, we only care about what are the ID's of the ancestors, putting them in a single string also seems reasonable.

The approach we could take is instead of storing this information in the nodes themselves, we could maintain a separate mapping from each node to it's list of ancestors, and update that mapping whenever a node is added, moved, or removed. It's not clear exactly where we would store that, but it might be much simpler, certainly in terms of update logic.

Please add more details on the client and gateway use cases and then we can refine the approach with that, thank you for the detailed write up, glad we are looking into this!

[dubdabasoduba]

For the mobile client you mention remove the recursive logic currently used to fetch child locations, but the metadata is storing parents in the children, how will this help with fetching children?

Same question for the server side, what is the nature of the query now and how does this address that , please add more details there.

• By storing all ancestor IDs in a location’s meta.tags, we eliminate the need for recursive, level-by-level searches. Instead of querying each hierarchy layer (district, then commune, then service point), a single query can retrieve all child locations by searching for those whose meta.tags contain the specified parent ID.
• For example, if all service points store the region ID in their meta.tags, you can directly query for any location tagged with that region ID—eliminating the need to step through each intermediate level.

[pld]

Yes of course, that's obvious, the question is what are those specific queries are and how does this address those queries?

[dubdabasoduba]

Example Query on Server

• Get the service points (Level 5) in region Androy for EUSM. Keep in mind that Androy is a Level 2 Location.

Current workflow

1. Step one - Fetch all the children of Androy https://unicef-mg-eusm-preview.smartregister.org/fhir/Location?partof=5876f357-cff5-4f03-ad97-fc79b7375bec. Check if the children are at Level 5
2. Step two - Fetch all the children of the Androy's Children https://unicef-mg-eusm-preview.smartregister.org/fhir/Location?partof=01eb6048-2a32-4556-85d9-519cb453aafb, bd6ec7c3-3896-4847-8485-19756f300fec, e.t.c.
   • Check if the Children are Level 5
   • Requests are batched as needed
3. Step three - Fetch all the children of the locations loaded on step 2 above https://unicef-mg-eusm-preview.smartregister.org/fhir/Location?partof=409bb851-c200-4643-b590-5f0b2005e8d2, 113a292b-209d-4f6d-b7a3-aa7f6eb56186, e.t.c.
   • Check if the Children are Level 5
   • Requests are batched as needed
4. Bundle the results up and add pagination.

Propose workflow

1. Step one - Fetch all the Level 5 locations that are part of Androy https://unicef-mg-eusm-preview.smartregister.org/fhir/Location?_tag=5876f357-cff5-4f03-ad97-fc79b7375bec&type=5
   • We then utilize pagination from HAPI

[peterMuriuki]

• If the parent location changes, this list of IDs will be regenerated to maintain an accurate hierarchy reference.

An edge case on the cost of the write operation; If a parent location's level on the hierarchy changes then we are looking at at-least as many api write requests as there are descendants to the modified location.

[dubdabasoduba]

For the OpenSRP web client, that only addresses one way that the data can become stale. A client can make a call directly against the API that would make the data stale. Please add a list of the edge cases that can make the data stale.

For avoiding staleness for changes on the web, the approach is unclear, are you suggesting we regenerate the entire hierarchy with its meta.tags whenever there is any change to any location? I agree, that would avoid staleness introduced through interactions on the fhir web, but it would be expensive, but only at write time, so that cost may be fine.

An edge case on the cost of the write operation; If a parent location's level on the hierarchy changes then we are looking at at least as many api write requests as there are descendants to the modified location.

• Based on a fresh review that considered various edge cases, the recommendation is to move the meta.tags generation to the FHIR Info Gateway.
  • This way, the server is responsible for updating Location resources, eliminating the need for changes in OpenSRP Web.
  • Concretely, the Gateway would handle regenerating meta.tags for the targeted Location resource and all its child locations whenever updates occur.
• Although this process could introduce performance overhead, we can mitigate the risk by leveraging the tag-based search to identify only the relevant locations and update them accordingly.

[dubdabasoduba]

Also on the web when you say If the parent location changes, this list of IDs will be regenerated, are you referring to the list of IDs in the children? I assume so, but please be more specific. Whenever a location is removed or inserted we have to change every node in the sub-graph below that location.

• @pld Yes the idea is to update the list of IDS in the children.

[pld]

This means on insert/delete you will need to walk from the inserted node to all descendants and update each node, is inserting non-leaf nodes infrequent?

You could also store both parents and descendants, this would make the updates faster

[dubdabasoduba]

@pld that storing both would make the search easier, but it would make the " lineage cache" huge. This means the resources grow big if we use the FHIR resources to store the lineage.

[dubdabasoduba]

This might degrade performance in other areas e.g. when fetching the resources for the rules execution.

[pld]

yea agree, this is an argument for not storing it in the resources, but in a reference data structure

[dubdabasoduba]

On the specific metadata we are including, more detail on the use cases in the gateway and the mobile app will help with this. If we are only ever using this for further fetches or comparisons, storing a display seems unnecessary (it's duplicative of what we'll get when we do the ID search, and that will be authoritative). It's also not clear if it is important at what level the ancestors are at other than by either parsing display name (if we have it there like in your example), or fetching the resource referred to, if it stores it's level. If it's not important to know the levels of the ancestor, we only care about what are the ID's of the ancestors, putting them in a single string also seems reasonable.

• @pld Currently, meta.tags is intended solely for searches and comparisons. The display field is included to provide supplementary information when additional validation is required—e.g., using the location’s name and level as part of the validation process.
• Using a single code field to store all location IDs won’t meet the search requirement, since the API requires an exact match. Consequently, each location ID must be stored separately, ensuring the search mechanism can correctly identify individual IDs. e.g. "https://unicef-mg-eusm-preview.smartregister.org/fhir/Location?_tag=696b532f-15b1-4422-a0ab-3525587260cd" would not work if the resource in question has the tags added this way

{
  "resourceType": "Location",
  "id": "aa5ac053-d8aa-4f42-b326-bae32e5944e1",
  "meta": {
    "versionId": "4",
    "lastUpdated": "2025-01-15T11:06:04.655+00:00",
    "source": "#68b1bd0c9a81ad67",
    "tag": [
      {
        "system": "http://smartregister.org/CodeSystem/location-hierarchy",
        "code": "03176924-6b3c-4b74-bccd-32afcceebabd,bf116fdd-6617-4302-88e4-72fd1af2851c,696b532f-15b1-4422-a0ab-3525587260cd"
      }
    ]
  },
  "identifier": [
    {"use": "official", "value": "aa5ac053-d8aa-4f42-b326-bae32e5944e1"}
  ],
  "status": "active",
  "name": "Ambandrika",
  "type": [
    {
      "coding": [
        {
          "system" : "http://terminology.hl7.org/CodeSystem/location-type",
          "code"   : "jdn"                                                ,
          "display": "jurisdiction"
        }
      ]
    },
    {
      "coding": [
        {
          "system" : "https://smartregister.org/codes/administrative-level",
          "code"   : "4"                                                   ,
          "display": "Level 4"
        }
      ]
    },
    {
      "coding": [
        {
          "system": "http://terminology.hl7.org/CodeSystem/location-physical-type",
          "code": "jdn",
          "display": "Jurisdiction"
        }
      ]
    }
  ],
  "physicalType": {
    "coding": [
      {
        "system": "http://terminology.hl7.org/CodeSystem/location-physical-type",
        "code": "jdn",
        "display": "Jurisdiction"
      }
    ]
  },
  "partOf": {
    "reference": "Location/696b532f-15b1-4422-a0ab-3525587260cd",
    "display"  : "Ambatondrazaka"
  }
}

[dubdabasoduba]

The approach we could take is instead of storing this information in the nodes themselves, we could maintain a separate mapping from each node to its list of ancestors, and update that mapping whenever a node is added, moved, or removed. It's not clear exactly where we would store that, but it might be much simpler, certainly in terms of update logic.

• An alternative approach is to avoid modifying the resources directly and instead utilize Redis for managing location data.
  • This would eliminate concerns about affecting existing projects.
  • The existing Redis proposal includes a custom API for regenerating the Location Hierarchy cache, which can also be leveraged to rebuild Location Lineage ID links. Furthermore, new or updated lineage links can be maintained in Redis whenever location resources are created or modified.

[dubdabasoduba]

@ndegwamartin While adding the hierarchy type on the URL works doesn't it make it harder to query the data like on the example given above? i.e it means we have to know the Location level before writing the query e.g

https://unicef-mg-eusm-preview.smartregister.org/fhir/Location?_tag=http://smartregister.org/CodeSystem/location-hierarchy-3|5876f357-cff5-4f03-ad97-fc79b7375bec&type=5

instead of

https://unicef-mg-eusm-preview.smartregister.org/fhir/Location?_tag=http://smartregister.org/CodeSystem/location-hierarchy|5876f357-cff5-4f03-ad97-fc79b7375bec&type=5

[dubdabasoduba]

The levels are good for debugging but not necessarily needed for filtering. Adding it this way makes it necessary for filtering too.

[ndegwamartin]

Yeah I think you are right for the original approach

[ndegwamartin]

The main decision we need to make though is on whether we are going with the original approach vs the Redis approach

[dubdabasoduba]

@pld and I decided on the 1st approach to allow the use of the tags both on the app and the server. I need to create the tickets and start a PR documenting the approach. This documentation will be added to the docusite.

[dubdabasoduba]

Tickets

Server side

• [Location Hierarchy] Enable storing ancestor tags on all locations. onaio/fhir-gateway-extension#110
• https://github.com/onaio/fhir-gateway-extension/issues/111
• [Location Hierarchy] Update the hierarchy creation process to retrieve child locations using lineage location tags. onaio/fhir-gateway-extension#113
• [Location Hierarchy] Enhance the “Sync Locations by Sync Strategy” functionality to retrieve locations based on their lineage location tags. onaio/fhir-gateway-extension#112

Client side (Mobile)

• [Location Hierarchy] Update map data loading to fetch locations using lineage location tags. #3697
• [Location Hierarchy] Update the hierarchy creation process to retrieve child locations using lineage location tags. #3696
• [Location Hierarchy] Document the updated approach for location hierarchy creation and search. #3698