The precomputed Algorithm for Paginated Responses in Symfony
Today, I want to introduce an algorithm for paginated responses in Symfony that aims to minimize database usage and maximize performance. It’s called the “precomputed pagination algorithm”, and it was conceived to deal with a recurrent problem in my previous job.
Let’s say you have a paginated list whose query is very complicated to make, you have a lot of joins, case statements, filters, and your tables has millions of records, what are you going to do? I have worked in such scenario and the solution might seem like you’re overengineering but, when it comes to paginated results, the clients don’t want to keep waiting until the next page loads up.
When I worked at SENAI Digital Solutions, I was assigned to create a user reporting module, and the main issue was that the users were not real tables. Each person could have multiple email addresses, roles, and accounts, and if you wanted to find out what a real user was, you had to create a very complicated query like this:
SELECT
ap.id,
p.name,
e.email,
r.name AS role
FROM
person.person p
INNER JOIN public.application_person ap ON ap.person_id = p.id
AND ap.inactive = FALSE
AND ap.application_id = 2
INNER JOIN public.person_email pe ON pe.person_id = p.id
AND pe.type = 'CORPORATE'
INNER JOIN public.email e ON e.email_id = pe.email_id
INNER JOIN person.person_role pr ON p.id = pr.person_id
AND pr.role_id IN (1, 2, 3)
INNER JOIN person.role r ON r.id = pr.role_id
GROUP BY
ap.id,
p.name,
e.email,
r.name;
I know this query is not complicated at all, but this is just an example. I can’t show you the real code due to copyright restrictions.
As you can see the “user” is just an imaginary concept, it’s not a real registry
in the database. To fix this you can make a database view named user_app_name,
but views are not flexible and not supported by Doctrine, and besides, views
don’t make your queries faster nor let you optimize them with the precomputed
pagination algorithm.
Standard Doctrine pagination
The standard doctrine pagination algorithm is mostly limited to entities, so you cannot use it to fetch DTOs or scalar values from the database. If you try to do it, you’ll face this error:
The Paginator does not support Queries which only yield ScalarResults.
Therefore, bear in mind that whenever you need to fetch some data in a custom format, you have to implement the custom logic yourself. Third-party libraries don’t like to support this functionality due to fact this is a very grey area, it’s simply not easy to create a pagination library that supports every scenario.
The Precomputed Pagination Algorithm
Instead of fetching user data page by page with standard filters, you can reduce the load on your database by fetching records by their primary keys. Here’s how it works:
- Select all unique identifiers
- Store them in the cache layer
- Count the composite IDs to get the total number of results
- Slice the list of IDs according to the current page
- Fetch the corresponding users by those IDs
- Return the results
The first step only happens during the initial request. It puts minimal load on the database because you’re only selecting primary keys. Pagination then happens in application code. Whenever the user requests a new page, the heavy filtering step is skipped, making subsequent queries significantly faster.
The unique identifier
Of course, you won’t be using a single primary key as a unique identifier. Instead, you’ll generate a composite identifier that includes all the relevant primary keys from the joined tables. This composite value acts as a virtual identifier, which you can later reverse-engineer to retrieve the original record. For example:
unique_identifier = application_person_id + person_email_id + person_role_id
This unique identifier is the most important part of the algorithm. It must include the primary keys from every intermediate table involved in the query. By doing so, you avoid duplicated results (which is something that ReactJS developers will especially appreciate when rendering lists).
The unique identifier can be any string format, typically with a separator character. For example:
<?php
$uniqId = '333_555_111';
However, you should not treat this identifier as a plain string. Since it’s a core part of the algorithm, it should be modeled as a Value Object. Here’s a simple implementation:
<?php
readonly class CompositeId {
private const SEPARATOR = '_';
public function __construct(
public int $applicationPersonId,
public int $personEmailId,
public int $personRoleId,
) {
}
public static function fromString(string $s) {
return new self(
...explode(
self::SEPARATOR,
$s,
3
)
);
}
public function __toString() {
return implode(self::SEPARATOR, [
$this->applicationPersonId,
$this->personEmailId,
$this->personRoleId,
]
);
}
}
The class needs to be serializable because it will be persisted in the cache layer and reused across multiple requests. The cache stores an array of unique identifiers, which are then used both to count the total number of results and to slice the list of IDs according to the current page.
Fetching unique identifiers
When the user makes the initial request, you have to select all unique identifiers. For example, let’s say the user wants to see a list of all users whose name is Carlos, a normal query would look like this:
SELECT
ap.id,
p.name,
e.email,
r.name AS role
FROM
person.person p
INNER JOIN public.application_person ap ON ap.person_id = p.id
AND ap.inactive = FALSE
AND ap.application_id = 2
INNER JOIN public.person_email pe ON pe.person_id = p.id
AND pe.type = 'CORPORATE'
INNER JOIN public.email e ON e.email_id = pe.email_id
INNER JOIN person.person_role pr ON p.id = pr.person_id
AND pr.role_id IN (1, 2, 3)
INNER JOIN person.role r ON r.id = pr.role_id
WHERE p.name ILIKE '%Carlos%'
GROUP BY
ap.id,
p.name,
e.email,
r.name
LIMIT 20
OFFSET 0;
For a database with millions of users, this query costs a lot of time and processing. When you go to the second page, the same filtering has to be done again making the application feel sluggish and slow.
Therefore, instead of applying the heavy filtering over and over, you just do it in the first time, and then continue fetching from the cache layer later on. To generate the values in cache layer, you have to make the same query, but instead of selecting the values that the user wants to see, you select the primary keys that identify those values.
SELECT
ap.id as application_person_id,
pe.id as person_email_id,
pr.id as person_role_id
FROM
person.person p
INNER JOIN public.application_person ap ON ap.person_id = p.id
AND ap.inactive = FALSE
AND ap.application_id = 2
INNER JOIN public.person_email pe ON pe.person_id = p.id
AND pe.type = 'CORPORATE'
INNER JOIN person.person_role pr ON p.id = pr.person_id
AND pr.role_id IN (1, 2, 3)
WHERE p.name ILIKE '%Carlos%'
GROUP BY
ap.id,
pe.id,
pr.id;
You SHALL NOT put any limit or offset in the unique identifiers’ query
As you probably noticed, there are fewer joins than the normal query and the reason is that we are just selecting intermediate tables and not tables with values themselves. This query can be considered an ‘abstraction’ that shows all users’ unique identifiers in our application, and it can have custom filters like:
- Account activation status
- Person name
- Email address
- Role name
All heavy filtering happens during the query for unique identifiers. Once you have the results, you should get them in the same format as described early by the value object which is beautifully supported by Doctrine:
<?php
$query = $em->createQuery('SELECT NEW CompositeId(ap.id, pe.id, pr.id) FROM Entity\Person p JOIN ...');
$users = $query->getResult(); // array of CompositeId
Pro-tip: to make this query less complicated, read my other article where I
teach how to use the Builder pattern for doctrine queries1. For example:
<?php
declare(strict_types=1);
namespace App\Builder\Repository;
use App\DTO\UserReportModule\CompositeId;
use App\Entity\Person;
use Doctrine\ORM\QueryBuilder;
use function sprintf;
readonly class CompositeIdQueryBuilder
{
public function __construct(
private QueryBuilder $queryBuilder,
) {
$this->queryBuilder
->select(
sprintf(
'new %s(ap.id, pe.id, pr.id)',
CompositeId::class
)
)
->from(Person::class, 'p')
->innerJoin('p.applicationPersons', 'ap')
->innerJoin('p.personEmails', 'pe')
->innerJoin('p.personRoles', 'pr')
->distinct();
}
public static function new(QueryBuilder $queryBuilder): UserQueryBuilder
{
return new self($queryBuilder);
}
/**
* @return CompositeId[]
*/
public function getResult(): array
{
return $this->queryBuilder->getQuery()->getResult();
}
public function whereEmailEq(string $email): static
{
$this->queryBuilder
->innerJoin('pe.email', 'e')
->andWhere(
$this->queryBuilder->expr()->eq(
'e.email',
':email'
)
)
->setParameter(':email', $email);
return $this;
}
// TODO: implement remaining filters here...
}
Storing in the cache layer
To store the array of results in the cache layer, you have to create a service
class that uses Symfony’s CacheInterface under-the-hood. This class needs to
have a method that fetches the unique identifiers from the database and must
receive a “filters” object as a parameter.
<?php
namespace App\Service;
use App\DTO\Filters;
use App\Repository\UserApp;
use Psr\Cache\CacheItemInterface;
use Symfony\Contracts\Cache\CacheInterface;
class CompositeIdCacheLayer
{
public function __construct(
private CacheInterface $cache,
private UserAppRepository $repo,
) {
}
public function fetchByFilters(Filters $filters) {
return $this->cache->get(
$filters->getCacheKey(),
function (CacheItemInterface $item) use ($filters) {
$item->expiresAfter(600); // Choose between 5 to 10 minutes
return $this->repo->fetchByFilters($filters);
}
);
}
}
The “Filters” object contains all the filters in the request like:
- field names
- field operators
- values
The structure may vary depending on your application, but the rule of thumb is: the filters must have a way to uniquely identify them so that you can use it to retrieve the results from cache instead of the database. A common way of identifying the filters is by serializing them into any format and creating a checksum from the serialized value.
<?php
namespace App\DTO;
use function serialize;
use function crc32;
use function sprintf;
class Filters
{
// ... filters implementation
public function getCacheKey(): string {
return sprintf(
'uniq_id_filter_key_%d',
crc32(serialize($this))
);
}
}
An example value would be:
uniq_id_filter_key_641303417
You can choose any hashing algorithm you want, and you can choose any prefix you want for the cache key. Just make sure that this value is unique across the entire cache layer.
Pro-tip: if you’re unsure how to implement a filtering object, take a look at how Material UI implements its filters2.
Getting the total number of results
Now that you have the unique identifiers, getting the total number of results is as simple as counting the array.
<?php
/** @var CompositeId[] $uniqueIdentifiers */
$uniqueIdentifiers = [];
$response = [
'total' => count($uniqueIdentifiers)
];
Once you have the results, you can simply count them when generating the response.
Getting the current page
To determine which items belong to the current page, you need to slice the array
of unique identifiers based on the pagination parameters. In PHP, this is
typically done with the array_slice function, which takes an offset (where
to start) and a length (how many items to include). These parameters
correspond directly to a database query’s OFFSET and LIMIT.
<?php
/** @var CompositeId[] $uniqueIdentifiers */
$uniqueIdentifiers = [];
$offset = 0;
$itemsPerPage = 20;
$currentPage = array_slice($uniqueIdentifiers, $offset, $itemsPerPage);
This approach is called application-side pagination, because all the data is already loaded into memory and the slicing is performed by your code instead of the database.
If you are using the php-ds extension, you can achieve the same behavior with
the slice() method, which works on data structures like Set:
<?php
/** @var Set<CompositeId> $uniqueIdentifiers */
$uniqueIdentifiers = new \Ds\Set();
$offset = 0;
$itemsPerPage = 20;
$currentPage = $uniqueIdentifiers->slice($offset, $itemsPerPage);
// $currentPage is an instance of \Ds\Set
Once you have the identifiers for the current page, you can use them in a query to fetch the corresponding users from the database.
Get the corresponding users
The final part of the algorithm is fetching the full data from the database by its composite IDs. In order to do so, the application must unpack the composite IDs into multiple query parameters.
SELECT DISTINCT
CONCAT(ap.id, '_', pe.id, '_', pr.id) AS compositeId,
p.name,
e.email,
r.name AS role
FROM
person.person p
INNER JOIN public.application_person ap ON ap.person_id = p.id
INNER JOIN public.person_email pe ON pe.person_id = p.id
INNER JOIN public.email e ON e.email_id = pe.email_id
INNER JOIN person.person_role pr ON p.id = pr.person_id
INNER JOIN person.role r ON r.id = pr.role_id
WHERE
(ap.id, pe.id, pr.id) IN (
(:applicationPersonId_1, :personEmailId_1, :personRoleId_1),
(:applicationPersonId_2, :personEmailId_2, :personRoleId_2),
(:applicationPersonId_3, :personEmailId_3, :personRoleId_3),
(:applicationPersonId_4, :personEmailId_4, :personRoleId_4)
);
If your database doesn’t support the IN() syntax you can use multiple where
clauses with the OR operator.
SELECT DISTINCT
CONCAT(ap.id, '_', pe.id, '_', pr.id) AS compositeId,
p.name,
e.email,
r.name AS role
FROM
person.person p
INNER JOIN public.application_person ap ON ap.person_id = p.id
INNER JOIN public.person_email pe ON pe.person_id = p.id
INNER JOIN public.email e ON e.email_id = pe.email_id
INNER JOIN person.person_role pr ON p.id = pr.person_id
INNER JOIN person.role r ON r.id = pr.role_id
WHERE
(ap.id = :applicationPersonId_1 AND pe.id = :personEmailId_1 AND pr.id = :personRoleId_1)
OR (ap.id = :applicationPersonId_2 AND pe.id = :personEmailId_2 AND pr.id = :personRoleId_2)
OR (ap.id = :applicationPersonId_3 AND pe.id = :personEmailId_3 AND pr.id = :personRoleId_3)
OR (ap.id = :applicationPersonId_4 AND pe.id = :personEmailId_4 AND pr.id = :personRoleId_4)
Each set of conditions correspond to a unique result which in turn, corresponds
to a logical user. This is how you would implement this query by following the
Builder pattern in Doctrine.
<?php
declare(strict_types=1);
namespace App\Builder\Repository;
use App\DTO\UserReportModule\CompositeId;
use App\DTO\UserReportModule\UserDTO;
use Doctrine\ORM\QueryBuilder;
use App\Entity\Person;
use function sprintf;
readonly class UserQueryBuilder
{
public function __construct(
private QueryBuilder $queryBuilder,
) {
$this->queryBuilder
->select(
sprintf(
<<<'DQL'
new %s(
CONCAT(ap.id, '_', pe.id, '_', pr.id),
p.name,
e.email,
r.name
)
DQL,
UserDTO::class
)
)
->from(Person::class, 'p')
->innerJoin('p.applicationPersons', 'ap')
->innerJoin('p.personEmails', 'pe')
->innerJoin('pe.email', 'e')
->innerJoin('p.personRoles', 'pr')
->innerJoin('pr.role', 'r')
->distinct();
}
public static function new(QueryBuilder $queryBuilder): UserQueryBuilder
{
return new self($queryBuilder);
}
/**
* @param array<array-key,CompositeId> $compositeIDs
*/
public function whereCompositeIdIn(array $compositeIDs): UserQueryBuilder
{
$expr = $this->queryBuilder->expr();
foreach ($compositeIDs as $key => $id) {
$this->queryBuilder
->orWhere(
$expr->andX(
$expr->eq("ap.id", ":applicationPersonId_{$key}"),
$expr->eq("pe.id", ":personEmailId_{$key}"),
$expr->eq("pr.id", ":personRoleId_{$key}"),
)
)
->setParameter(":applicationPersonId_{$key}", $id->applicationPersonId)
->setParameter(":personEmailId_{$key}", $id->personEmailId)
->setParameter(":personRoleId_{$key}", $id->personRoleId);
}
return $this;
}
/**
* @return UserDTO[]
*/
public function getResult(): array
{
return $this->queryBuilder->getQuery()->getResult();
}
}
Algorithm Summary
The core idea is simple: instead of running expensive queries every time someone clicks “next page”, you fetch all the primary keys once and handle pagination in your application. The database only gets hit hard during the initial request, then subsequent pages load from your cache layer (Redis, file system, or whatever’s cheaper than database queries).
I recommend Redis since everything happens in memory and primary keys don’t take up much space anyway. Think about it: storing a few thousand integers is nothing compared to repeatedly executing complex joins on million-row tables.
When This Makes Sense
This approach works best when you’re dealing with:
- Complex reporting queries that take seconds to execute
- Users who actually browse through multiple pages (not just hit page 1 and leave)
- Data that doesn’t change every few seconds
- Scenarios where a 5-10 minute data delay is acceptable
Downsides
Let’s be real, this isn’t a magic solution for every pagination problem. If your current setup is already fast enough, don’t overcomplicate things.
The biggest pain point is implementation complexity. There’s no plug-and-play library for this, so you’re writing everything from scratch: the unique identifier queries, the cache layer service, the final data fetching logic. It’s a lot of moving parts.
Then there’s cache invalidation, which is honestly one of the hardest problems in programming. When someone adds or deletes a record, your cached results become stale. My solution? Keep the cache TTL short, around 5 to 10 minutes. That’s usually enough time for users to browse through their search results, and short enough that outdated data doesn’t stick around too long.
You’ll also need to think about memory usage. While storing primary keys is cheap, if you’re dealing with filters that return millions of results, you might hit Redis memory limits.
Conclusion
There you have it, a practical solution for when standard pagination just isn’t cutting it. Remember, this technique isn’t tied to Symfony or even PHP. The concept works in any language or framework. I just used Symfony because that’s what I had at my previous company.
Use it when you need it, skip it when you don’t. Sometimes the simple solutions are the best ones, and sometimes you need to get creative with caching and composite identifiers.
Hope this helps someone out there dealing with slow pagination. I see you next time!