Использование Verified Permissions для реализации точной авторизации в высоконагруженных приложениях

Если проверяем каждую запись, то, вероятно, отработает за O(N) (возможно, существуют более эффективные решения, но мне о таких неизвестно).
Однако это не должно стать узким местом, так как в подавляющем большинстве случаев пользователь не будет работать с миллионом записей на одном экране.

Использование Verified Permissions для реализации точной авторизации в высоконагруженных приложениях

Всё равно не могу до конца понять чего вы хотите достичь...

Может ли PDP (внешний по отношению к БД, хранящей бизнес-объекты и/или их метаданные) выполнить "policy eavaluation" имея на руках всю необходимую для этого информацию (как правило профиль пользователя, запрос пользователя и его контекст, метаданные каждого объекта (либо класса объектов) к которым адресован запрос) - определённо да, он для этого и создан.
Можно ли это сделать не имея всех необходимых данных (например отсутствуют метаданные объекта, используемые в политике) - очевидно, что нет.

Использование Verified Permissions для реализации точной авторизации в высоконагруженных приложениях

Интересная задача, на вскидку я бы положил интересующие нас характеристики в индексируемые структуры и делегировал функцию фильрации на сторону БД. В случае, если проблемы с производительностью такого решения сделают его не приемлемым, посмотрел бы на применимость альтернативных подходов вплоть до "хранения всех записей одного владельца в отдельной таблице/области памяти" и "предвычисления результатов для конкретной роли".
И да, шагом 0, бы поставил получение полного и исчерпывающего описания решаемой бизнес-задачи включая все NFR'ы

Использование Verified Permissions для реализации точной авторизации в высоконагруженных приложениях

Если я правильно понял ваш вопрос, то решить обозначенную проблему поможет ABAC, то есть использование наборов свойств субъекта и объекта при описании политик доступа. На Cedar применение этой концепции можно показать на следующем примере:

Задача: Разрешить любое действие любому пользователю над любым ресурсом, если пользователю назначены права на работу со всеми сегментами, в которые включён ресурс. Действие "Удалить" разрешить только пользователю-владельцу ресурса.

Решение:

Характеристики наших сущностей (User/Принципал и Photo/Ресурс):

[
  {
    "uid": { "type": "User", "id": "alice"},
    "attrs": {"id": "alice","age": 18, "allowed_segments": ["b2o", "b2b", "b2c"]},
    "parents": []
  },
  {
    "uid": { "type": "Photo", "id": "VacationPhoto94.jpg"},
    "attrs": {"object_segment":["b2c","b2o"], "owner": "alice"},
    "parents": [{ "type": "Album", "id": "jane_vacation" }]
  }
]

Политика, решающая поставленную задачу:

permit (
    principal,
    action,
    resource
)
when {
    (principal.allowed_segments.containsAll(resource.object_segment)
        && action != Action::"delete") ||
    resource.owner == principal.id
};

Действие "удалить" над ресурсом "VacationPhoto94.jpg" будет доступно только для пользователя с id="alice", тогда как любые другие действия будут доступны для всех пользователей, сегменты которых совпадут с сегментами объектов, к которым пользователели будут обращаться