title: Optimizing MySQL GROUP BY/ORDER BY for calculating set intersection
body: <p>This scenario is simplified somewhat to make the problem clearer.
  My situation involves a set of data records in MySQL.</p>
  
  <pre><code>CREATE TABLE `records` (                                          
    `id` bigint(20) NOT NULL,                                                       
    `property1` bigint(20) NOT NULL,
    `property2` bigint(20) NOT NULL,
    PRIMARY KEY  (`id`),
    KEY `property1` (`property1`),
    KEY `property2` (`property2`)
  );
  </code></pre>
  
  <p>From each record, we generate and store a variable number of keys (hashes) based on the record data.</p>
  
  <pre><code>CREATE TABLE `rkeys` (
    `rKey` bigint(20) NOT NULL,
    `rId` bigint(20) NOT NULL,
    KEY `rKey` (`rKey`),
    KEY `rId` (`rId`),
    FOREIGN KEY (`rId`) REFERENCES `records` (`id`)
  );
  </code></pre>
  
  <p>(The key values are hashes to distribute them over the keyspace more evenly.)</p>
  
  <p>There may be, for example, 5 million records and 50 million keys.</p>
  
  <p>What I'm attempting to do is a fuzzy search on the key set -- match a record against the records in the database with the most keys in common.  The results also need to be filtered against the properties in the records table.</p>
  
  <p>The query I've been working from looks like this:</p>
  
  <pre><code>SELECT rkeys.rId, records.property1, SUM(1) as score 
  FROM rkeys, records
  WHERE 
     (rKey = 10 OR rKey = 11 OR rKey = 13 OR rKey = 14) AND 
      rkeys.rId = records.id AND 
      records.property1 = 1 AND
      records.property2 = 2 
  GROUP BY rId ORDER BY score DESC;
  </code></pre>
  
  <p>The performance is ok if the number of records with any given key is fairly small; the problem is if I hit a key that appears in several thousand records (say 5000).  All of a sudden, the GROUP BY/ORDER BY performance falls off a cliff (15-20s per query).  Note that smoothing out the key distribution is not really an option -- the record data itself is unevenly distributed.</p>
  
  <p>The join against the records problem doesn't seem to be the core of the problem -- I'm just including it for context.  I still see the same problem if all I want to do is this:</p>
  
  <pre><code>SELECT rId, SUM(1) as score 
  FROM rkeys
  WHERE rKey = 10 OR rKey = 11 OR rKey = 13 OR rKey = 14
  GROUP BY rId ORDER BY score DESC;
  </code></pre>
  
  <p>EXPLAIN output:</p>
  
  <pre><code>*************************** 1. row ***************************
             id: 1
    select_type: SIMPLE
          table: rkeys
           type: index
  possible_keys: rKey
            key: rKey
        key_len: 8
            ref: NULL
           rows: 1
          Extra: Using where; Using temporary; Using filesort
  </code></pre>
  
  <p>Is there a way I can restructure this table or query in order to speed this operation up?</p>