Search with Permissions using Local Index

[velmohan]

I am starting to look at building an index as described here: https://openfga.dev/docs/interacting/search-with-permissions

Would not this index get huge easily though? Say for example we have x number of resources and y number of users. If we have z different permissions for these resources, then there will be x*y*z number of objects in the Local Index?.

So, if x=500 000, y = 1000 and z= 5, then we are talking about 2.5 billion objects in index. Or is there any better way to do this?

[jon-whit]

@velmohan you are correct. However, your described approach assumes that you index a single row per combination (x, y, z). This is an approach, but depending on the kinds of resource ids in the system you may be able to optimize using bitmaps. An alternative could be to store a single bitmap index per user. Since an index is typically serving queries for the end user (e.g. show me all of the objects that a specific user has access to), then it makes sense to index a bitmap representing the effective access a user has for a particular relationship.

For example, let's assume we have a len(objects)=3, len(users) =2, len(relations)=2, then the index would be of size len(users) * len(relations) == 4 instead of 12. We can reduce the cardinality of the index by shrinking the object space into a bitmap. If we had the following relationship tuples:

- document:1#viewer@user:jon
- document:1#editor@user:jon
- document:1#viewer@user:bob
- document:2#viewer@user:jon
- document:3#viewer@user:bob
- document:3#editor@user:bob

then a bitmap index would look like the following:

| user     | relation | bitmap | objects                      |
|----------|----------|--------|------------------------------|
| user:jon | viewer   | 110    | ["document:1", "document:2"] |
| user:bob | viewer   | 101    | ["document:1", "document:3"] |
| user:jon | editor   | 100    | ["document:1"]               |
| user:bob | editor   | 001    | ["document:3"]               |

The user | relation | bitmap would be the indexed columns. I added the objects column just to demonstrate the interpretation of the bitmap.

[velmohan]

@jon-whit Thanks for your answer. Yes, that is really a good idea. I will explore what would be possible with the ids we have.