Pattern Matching Redis keys

Question

I have a question regarding doing pattern matching in Redis keys. Currently, I am storing a set of subscriptions, where keys are composite of different events. For example, if a subscription comes in as

S1 - {event:created, userId:1234, stateId:xyz}

It's stored in cache for matching as (events are sorted before creating the key)

event:created#stateId:xyz#userId:1234 = {S1}

Now there can be other events that can subscribe to this exact combination. But if an event comes if any of the three attributes, it will be matched with all the keys to which they are a substring. Example

event:created#stateId:xyz#userId:1234 = {S1,S2,S3}
event:started#stateId:xyz#userId:1234 = {S4,S5,S6}
event:created#stateId:abc#userId:1234 = {S7,S8,S9}

The following will be the event and subscription chart.

event:created -> S1,S2,S3,S7,S8,S9
event:started -> S4,S5,S6
state:xyz -> S1,S2,S3,S4,S5,S6
userId:1234 -> S1,S2,S3,S4,S5,S6,S7,S8,S9
stateId:abc and userId:1234 -> S1,S2,S3,S4,S5,S6,S7,S8,S9

I tried using a SCAN on Redis with a pattern match, but it takes a long time as my cache can have a lot of entries, and SCAN takes O(N) time.

Any idea how I can do this efficiently? Maybe by using a secondary structure in Redis like a Tree or something? Or any other Redis data structure I should look at?

Thanks