title: Efficient Redis SCAN of multiple key patterns
body: <p>I'm trying to power some multi-selection query &amp; filter operations with <code>SCAN</code> operations on my data and I'm not sure if I'm heading in the right direction.</p>
  <p>I am using AWS ElastiCache (Redis 5.0.6).</p>
  <p><strong>Key design</strong>: &lt;recipe id&gt;:&lt;recipe name&gt;:&lt;recipe type&gt;:&lt;country of origin&gt;</p>
  <p><strong>Example:</strong></p>
  <blockquote>
  <p>13434:Guacamole:Dip:Mexico<br />
  34244:Gazpacho:Soup:Spain<br />
  42344:Paella:Dish:Spain<br />
  23444:HotDog:StreetFood:USA<br />
  78687:CustardPie:Dessert:Portugal<br />
  75453:Churritos:Dessert:Spain</p>
  </blockquote>
  <p>If I want to power queries with complex multi-selection filters (example to return all keys matching five recipe types from two different countries) which the <code>SCAN</code> glob-style match pattern can't handle, what is the common way to go about it for a production scenario?</p>
  <p>Assuming the I will calculate all possible patterns by doing a cartesian product of all field alternating patterns and multi-field filters:</p>
  <blockquote>
  <p>[[Guacamole, Gazpacho], [Soup, Dish, Dessert], [Portugal]]<br />
  *:Guacamole:Soup:Portugal<br />
  *:Guacamole:Dish:Portugal<br />
  *:Guacamole:Dessert:Portugal<br />
  *:Gazpacho:Soup:Portugal<br />
  *:Gazpacho:Dish:Portugal<br />
  *:Gazpacho:Dessert:Portugal</p>
  </blockquote>
  <p>What mechanism should I use to implement this sort of pattern matching in Redis?</p>
  <ol>
  <li>Do multiple <code>SCAN</code> for each scannable pattern sequentially and merge the results?</li>
  <li>LUA script to use improved pattern matching for each pattern while scanning keys and get all matching keys in a single <code>SCAN</code>?</li>
  <li>An index built on top of sorted sets supporting fast lookups of keys matching single fields and solve matching alternation in the same field with <code>ZUNIONSTORE</code> and solve intersection of different fields with <code>ZINTERSTORE</code>?</li>
  </ol>
  <blockquote>
  <p>&lt;recipe name&gt;:: =&gt; key1, key2, keyN<br />
  :&lt;recipe type&gt;:  =&gt; key1, key2, keyN<br />
  ::&lt;country of origin&gt;  =&gt; key1, key2, keyN</p>
  </blockquote>
  <ol start="4">
  <li>An index built on top of sorted sets supporting fast lookups of keys matching all dimensional combinations and therefore avoiding Unions and Intersecions but wasting more storage and extend my index keyspace footprint?</li>
  </ol>
  <blockquote>
  <p>&lt;recipe name&gt;:: =&gt; key1, key2, keyN<br />
  &lt;recipe name&gt;:&lt;recipe type&gt;: =&gt; key1, key2, keyN<br />
  &lt;recipe name&gt;::&lt;country of origin&gt; =&gt; key1, key2, keyN<br />
  :&lt;recipe type&gt;: =&gt; key1, key2, keyN<br />
  :&lt;recipe type&gt;:&lt;country of origin&gt; =&gt; key1, key2, keyN<br />
  ::&lt;country of origin&gt; =&gt; key1, key2, keyN</p>
  </blockquote>
  <ol start="5">
  <li>Leverage RedisSearch? (while impossible for my use case, see Tug Grall answer which appears to be very nice solution.)</li>
  <li>Other?</li>
  </ol>
  <p>I've implemented 1) and performance is awful.</p>
  <pre><code>private static HashSet&lt;String&gt; redisScan(Jedis jedis, String pattern, int scanLimitSize) {
  
      ScanParams params = new ScanParams().count(scanLimitSize).match(pattern);
  
      ScanResult&lt;String&gt; scanResult;
      List&lt;String&gt; keys;
      String nextCursor = &quot;0&quot;;
      HashSet&lt;String&gt; allMatchedKeys = new HashSet&lt;&gt;();
  
      do {
          scanResult = jedis.scan(nextCursor, params);
          keys = scanResult.getResult();
          allMatchedKeys.addAll(keys);
          nextCursor = scanResult.getCursor();
      } while (!nextCursor.equals(&quot;0&quot;));
  
      return allMatchedKeys;
  
  }
  
  private static HashSet&lt;String&gt; redisMultiScan(Jedis jedis, ArrayList&lt;String&gt; patternList, int scanLimitSize) {
  
      HashSet&lt;String&gt; mergedHashSet = new HashSet&lt;&gt;();
      for (String pattern : patternList)
          mergedHashSet.addAll(redisScan(jedis, pattern, scanLimitSize));
  
      return mergedHashSet;
  }
  </code></pre>
  <p>For 2) I've created a Lua Script to help with the server-side <code>SCAN</code> and the performance is not brilliant but is much faster than 1) even taking into consideration that Lua doesn't support alternation matching patterns and I have to loop each key through a pattern list for validation:</p>
  <pre><code>local function MatchAny( str, pats )
      for pat in string.gmatch(pats, '([^|]+)') do
          local w = string.match( str, pat )
          if w then return w end
      end
  end
  
  -- ARGV[1]: Scan Count
  -- ARGV[2]: Scan Match Glob-Pattern
  -- ARGV[3]: Patterns
  
  local cur = 0
  local rep = {}
  local tmp
  
  repeat
    tmp = redis.call(&quot;SCAN&quot;, cur, &quot;MATCH&quot;, ARGV[2], &quot;count&quot;, ARGV[1])
    cur = tonumber(tmp[1])
    if tmp[2] then
      for k, v in pairs(tmp[2]) do
        local fi = MatchAny(v, ARGV[3])
        if (fi) then
          rep[#rep+1] = v
        end
      end
    end
  until cur == 0
  return rep
  </code></pre>
  <p>Called in such a fashion:</p>
  <pre><code>private static ArrayList&lt;String&gt; redisLuaMultiScan(Jedis jedis, String luaSha, List&lt;String&gt; KEYS, List&lt;String&gt; ARGV) {
      Object response = jedis.evalsha(luaSha, KEYS, ARGV);
      if(response instanceof List&lt;?&gt;)
          return (ArrayList&lt;String&gt;) response;
      else
          return new ArrayList&lt;&gt;();
  }  
  </code></pre>
  <p>For 3) I've implemented and maintained a secondary Index updated for each of the 3 fields using Sorted Sets and implemented querying with alternating matching patterns on single fields and multi-field matching patterns like this:</p>
  <pre><code>private static Set&lt;String&gt; redisIndexedMultiPatternQuery(Jedis jedis, ArrayList&lt;ArrayList&lt;String&gt;&gt; patternList) {
  
      ArrayList&lt;String&gt; unionedSets = new ArrayList&lt;&gt;();
      String keyName;
      Pipeline pipeline = jedis.pipelined();
  
      for (ArrayList&lt;String&gt; subPatternList : patternList) {
          if (subPatternList.isEmpty()) continue;
          keyName = &quot;un:&quot; + RandomStringUtils.random(KEY_CHAR_COUNT, true, true);
          pipeline.zunionstore(keyName, subPatternList.toArray(new String[0]));
          unionedSets.add(keyName);
      }
  
      String[] unionArray = unionedSets.toArray(new String[0]);
      keyName = &quot;in:&quot; + RandomStringUtils.random(KEY_CHAR_COUNT, true, true);
      pipeline.zinterstore(keyName, unionArray);
      Response&lt;Set&lt;String&gt;&gt; response = pipeline.zrange(keyName, 0, -1);
      pipeline.del(unionArray);
      pipeline.del(keyName);
      pipeline.sync();
  
      return response.get();
  }
  </code></pre>
  <p>The results of my stress test cases clearly favor 3) in terms of request latency:</p>
  <p><a href="https://i.stack.imgur.com/Hjwjy.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/Hjwjy.png" alt="enter image description here" /></a></p>