How We Have Solved The Issue Of Searching Within Nested Nodes - API Platform

Imagine a system of libraries set up like this:

• there’s an organization that has several groups

• each group contains multiple individual libraries

• and each library is just a single unit

Here’s the big picture:

The hierarchy – organization, group, and library – resemble a tree structure, as shown here:

Now, keeping this structure in mind, your task is to create a new API endpoint using the API Platform framework. This endpoint should take a valid id or uuid of an organization or group and return all the libraries associated with it. You can use the id of an organization, a group, or even a library.

This means that every part of the structure has its own set of child elements. For reference, we’ve designed our schema to treat each library as a single entity, with an attribute that indicates whether it’s an organization, a group, or a library.

The Problem

When you think about a Group and its Location records, you might think it's simple to just use a getter function to pull its child records. But things get trickier when you add multiple levels of nodes. How can you know how deep you need to go without using recursion, and how can you avoid creating a solution that is too heavy on resources?

It’s not easy. One option is to change the entire database layout by adding some kind of record indexing. This would speed up search times but would slow down updates. The other choice is to use recursion to get the information you need.

Changing the database setup means adding more attributes to the entity, which can make things smoother if you don’t plan on changing the hierarchy much. However, if you have to update a record and move it within the hierarchy, it could be costly because you would need to renumber each node in the tree.

On the flip side, using recursion makes it easier to make changes later. It does require some initial work, but we believe it helps keep things flexible for the future without adding too much extra burden.

The Choice

Instead of just jumping straight into the solution, let’s first cover the steps required for each of the proposed ways to reach our end goal, starting with the nested data set model.

Nested Data Set overview

The solution is simple:

• Traverse across each record of a tree in a sequence.

• Visit each node twice.

• Assign a sequencing number on the way forward.

• Assign a sequencing number on the way back

This leaves the node with two numbers, acting as boundaries for retrieving any other record underneath it. Fetching child nodes now becomes easy - just pass the inner and outer bound of records you want fetch, and the resulting query will simply check for the passed conditions.

Additionally, if it’s known that we’ll be managing multiple organizations of libraries, a separate root key has to be added, which will mark be the origin for traversing through a multi-level tree.

Implementation steps overview

Below is a high-level outline of the actions you would take to set up the Nested Data Set model in an API Platform/Symfony project. These steps focus on the overall process—entity changes, migrations, and repository adjustments—without diving into specific code snippets.

• add two new attributes to your entity that require hierarchical traversal; left and right key (both int types)

• add a third attribute if there will be many multi-level trees with multiple organizations in mind (i.e. multiple library systems can be added and monitored); root_id

• add a migration that will apply the changes to your database, and execute the same

• implement multiple repository-level functions for fetching, removing, adding, and setting a root level nodes (examples)

Retrieving child units now becomes a breeze, but the added overhead of making sure each record is correctly defined upon adding/updating nodes can create a wormhole of consequences (like missing out on records if they’re not updated after marking a neighboring node).

If you’re working in a system where changes to structures do not occur often, but you’re required to fetch information about descendant nodes of a hierarchy tree, this solution is phenomenal and once implemented, ensures a linear time complexity for fetching nodes in a tree.

The API platform approach - with extensions!

The latter approach is a bit more configuration-heavy, requiring a raw SQL query to execute (DQL doesn’t support recursive queries at this time of writing), and allows for easier updates down the line.

Based on the two proposed solutions, for our scenario, where we want to have the experience of allowing expansion and modification, we’ve chosen this option.

Before delving into the implementation, here’s a broad overview of the execution workflow:

• a given ID is provided

• state provider intercepts the request, executes repository logic to fetch child uuids and save in context array

• doctrine extension is called which fetches all IDs provided from database

• the return collection contains needed data

With the above defined, the primary things we have to uncover is the implementation of the state provider and the mysterious doctrine extension.

Using the provider to fetch all descendant units for a provided id

A state provider is a code segment that handles data retrieval. In our case, it's used to get all the child units from a specific library (like an organization or group). Here’s a sample of what that code looks like:

Next, take a look at the repository function here:

Let’s break down how everything flows:

1. Start by fetching the request and checking it.

2. Get the $parentId provided and validate it, if it exists.

3. Set the attribute $context['filters']['childUuids'] to include an array of all descendant library units using a recursive function from the repository.

4. Finally, return the data.

The repository function looks as follows:

This works because the $context array includes the filters key. During processing, this key is scanned to determine which IDs the state provider should return.

But how does the Provider know to fetch and return each ID listed under $context['filters']['childUuids'] as an array?

Creating the Doctrine Extension

This is where the previously mentioned extension comes in. We create a Doctrine Extension that runs when we query a collection of items, ensuring it extends from the right interface.

You can check it out here:

This extension catches any calls made while searching a collection but only acts if the correct $operation is called, specifically get_descendant_collection in this case.

Filtering results with addWhere

Armed with this information, we can integrate into the retrieval process and use the addWhere function to grab each Library unit ID saved in the $context['filters']['childUuids'] key. This wraps up the retrieval process and gives us the option to enhance it further if we need to manipulate the data.

And there you have it—a seamless flow from fetching and validating the request to dynamically retrieving and filtering data using a well-orchestrated combination of repository functions and Doctrine extensions.

Benefits and future enhancements

By leveraging the power of recursive functions and context-aware filtering, we’ve built a system that not only fetches the necessary data but also ensures it’s precisely tailored to the requirements of the operation.

This approach not only streamlines the retrieval process but also opens the door to further enhancements and customizations down the line. Whether you’re looking to refine the data manipulation or expand the functionality, this setup provides a solid foundation to build upon. Happy coding!