1

Situation: I've got a table users and a table preferences along with some others. The table users is aligned horizontally (id, username,...) whereas the table preferences is aligned vertically (user_id, preference_key).

Table users has about 300K rows, preferences about 60M (about 20 out of 100 preferences per user)

Task: Find me all users that have a given combination of preferences (and/or pattern)

My first approach is this, run by a subquery

SELECT users.id FROM users LEFT JOIN ..other tables .. WHERE .. AND users.id IN (
   SELECT t1.id FROM 
  (
     SELECT user_id as id, count(*) as total 
     FROM preferences 
     WHERE pref_key IN (key1, key2, key3, etc..)
     GROUP BY id
     HAVING total > 3 
  )
)

having > 3: number of keys to match in an and-pattern, >0 for or-pattern

This approach is rather slow and I don't know if this approach is any good at all, as it looks complex with the subquery and IN () arguments.

For the performance - way more reads than writes - is the vertical alignment of the table structure optimal?

1 Answer 1

1

You might find this answer a little adventurous, so here it goes...

First some sample data

DROP DATABASE IF EXISTS beercan;
CREATE DATABASE beercan;
USE beercan
CREATE TABLE users
(id INT NOT NULL AUTO_INCREMENT PRIMARY KEY,
username VARCHAR(25));
CREATE TABLE preferences
(user_id INT NOT NULL,pref INT NOT NULL, PRIMARY KEY (user_id,pref));
INSERT INTO users (username) VALUES
('rolando'),('pamela'),('dominique'),('beercan'),('diamond');
INSERT INTO preferences VALUES
(1,10), (1,20), (1,30), (1,41), (1,50), (1,61), (1,70), (1,80), (1,94),
(2,10), (2,22), (2,31), (2,41), (2,50), (2,60), (2,70), (2,81), (2,93),
(3,10), (3,22), (3,30), (3,42), (3,50), (3,60), (3,71), (3,80), (3,92),
(4,18), (4,28), (4,38), (4,48), (4,58), (4,68), (4,78), (4,88), (4,98),
(5,10), (5,20), (5,31), (5,40), (5,50), (5,60), (5,70), (5,80), (5,91);

When you load this data, you get this:

mysql> SELECT * FROM users;
+----+-----------+
| id | username  |
+----+-----------+
|  1 | rolando   |
|  2 | pamela    |
|  3 | dominique |
|  4 | beercan   |
|  5 | diamond   |
+----+-----------+
5 rows in set (0.00 sec)

mysql> SELECT user_id,GROUP_CONCAT(pref)
    -> FROM preferences GROUP BY user_id;
+---------+----------------------------+
| user_id | GROUP_CONCAT(pref)         |
+---------+----------------------------+
|       1 | 10,20,30,41,50,61,70,80,94 |
|       2 | 10,22,31,41,50,60,70,81,93 |
|       3 | 10,22,30,42,50,60,71,80,92 |
|       4 | 18,28,38,48,58,68,78,88,98 |
|       5 | 10,20,31,40,50,60,70,80,91 |
+---------+----------------------------+
5 rows in set (0.00 sec)

mysql>

OK, that was the data. Now, suppose you are looking for (10,30,50,70,80,90)

Use this query

SELECT U.username,IFNULL(P.prefs,'') PrefList,
IF(
  LENGTH(IFNULL(P.prefs,''))=0,
  0,
  LENGTH(P.prefs) -
  LENGTH(REPLACE(P.prefs,',','')) + 1
) PrefCount
FROM users U LEFT JOIN
(
    SELECT user_id,
    GROUP_CONCAT(pref ORDER BY pref) prefs
    FROM preferences
    INNER JOIN
    (
        SELECT 10 pref UNION
        SELECT 30      UNION
        SELECT 50      UNION
        SELECT 70      UNION
        SELECT 80      UNION
        SELECT 90
    ) LookupPrefs
    USING (pref) GROUP BY user_id
) P
ON U.id = P.user_id;

Note the output

mysql> SELECT U.username,IFNULL(P.prefs,'') PrefList
    -> IF(
    ->   LENGTH(IFNULL(P.prefs,''))=0,
    ->   0,
    ->   LENGTH(P.prefs) -
    ->   LENGTH(REPLACE(P.prefs,',','')) + 1
    -> ) PrefCount
    -> FROM users U LEFT JOIN
    -> (
    ->     SELECT user_id,
    ->     GROUP_CONCAT(pref ORDER BY pref) prefs
    ->     FROM preferences
    ->     INNER JOIN
    ->     (
    ->         SELECT 10 pref UNION
    ->         SELECT 30      UNION
    ->         SELECT 50      UNION
    ->         SELECT 70      UNION
    ->         SELECT 80      UNION
    ->         SELECT 90
    ->     ) LookupPrefs
    ->     USING (pref) GROUP BY user_id
    -> ) P
    -> ON U.id = P.user_id;
+-----------+----------------+-----------+
| username  | PrefList       | PrefCount |
+-----------+----------------+-----------+
| rolando   | 10,30,50,70,80 |         5 |
| pamela    | 10,50,70       |         3 |
| dominique | 10,30,50,80    |         4 |
| beercan   |                |         0 |
| diamond   | 10,50,70,80    |         4 |
+-----------+----------------+-----------+
5 rows in set (0.01 sec)

mysql>

OK, fine. You return a list of preferences that satisfy the innermost subquery LookupPrefs Now, how did I compare the number of matches? If the length of prefs > 0, count the commas in prefs and add 1.

FINAL QUERY

SELECT U.username,IFNULL(P.prefs,'') PrefList,
IF(
  LENGTH(IFNULL(P.prefs,''))=0,
  0,
  LENGTH(P.prefs) -
  LENGTH(REPLACE(P.prefs,',','')) + 1
) PrefCount
FROM users U LEFT JOIN
(
    SELECT user_id,
    GROUP_CONCAT(pref ORDER BY pref) prefs
    FROM preferences
    INNER JOIN
    (
        SELECT 10 pref UNION
        SELECT 30      UNION
        SELECT 50      UNION
        SELECT 70      UNION
        SELECT 80      UNION
        SELECT 90
    ) LookupPrefs
    USING (pref) GROUP BY user_id
) P
ON U.id = P.user_id;

I will leave it to you to compare the PrefCount to your liking.

I will also leave it to you to build the LookupPrefs subquery for the Preferences you want.

Give it a Try !!!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.