Essa é uma pergunta com muitas respostas possíveis. Aqui estão os meus dois principais:

1. 
   Use o poder de Lua para evitar mover dados para o cliente e ter todo o trabalho feito no lado do servidor. Você pode contornar a falta de RANGESTORE dessa maneira.
   
2. 
   Mantenha um conjunto ordenado onde as pontuações são feitas de ambos os atributos, usando bit-interleaving. No Redis-verse existe um experimento de antirez chamado redimension que faz exatamente isso. Os links são https://www.reddit.com/r/redis/comments/3qjlkk/redimension_ruby_library_implementing/ e minha porta acima para Redis lua https://www.reddit.com/r/redis/comments/3s0h73/ luaredimension_redis_multidimensional_query/. Você pode ler mais sobre a abordagem em Índices multidimensionais.