0

I am working on a giveaway algorithm to select a customer based on what they purchased:

  • If they purchase item 1, they gain 1 point.
  • If they purchase item 2, they gain 2 points.
  • If they purchase item 3, they gain 3 points.

Each purchase in the database has an item_id, which I can use to figure out which item they have purchased.

I'm trying to make the minimum number of queries to the database to prevent memory usage from going up (e.g. I can't retrieve all records and calculate points all in memory), and I'm trying to put the minimum weight on MySQL. Here is what I've come up with:

Step 1: Get Total Points

I make three count queries to the database, multiply the count by the score multiplier for each item, add the multiplied scores together, and put the results in an array. For example, if there are 10 purchases for item 1, 10 for item 2, and 10 for item 3, the results array would look like this:

[
    1 => 10,
    2 => 30,
    3 => 60
];

As you can probably tell, the first item is just itself (10), the second item is (10 * 2) + 10 (10 * 2 is the count of purchases multiplied by the score multiplier, and then added up to the previous item). Likewise, the third item in the array is (10 * 3) + 30.

Step 2: Select a random number

At this stage, I simply choose a random number between 1 and 60 (1 and the value of the last item in the array).

Step 3: Retrieving the Winner

At this stage, I do almost the reverse of step 1. Imagine that the random number is 33. I find out what value is less than this random number (it is the item at index 2), then I deduct the value of that index from my random number (33 - 30 = 3), then I divide the remainder by the score multiplier for index + 1. In this case, the score multiplier for 2 + 1 (item number 3) is 3, so I divide 3 by 3, which gives me 1. Then I retrieve the very first purchase for item 3.

It's complicated!

It took me a lot of time just to write this here. Now imagine someone being faced with a piece of code that adds and multiplies and subtracts and divides all the time! Is there a way to make this simpler?

I don't mind some performance loss if it gains me better readability; I prefer my code to be as readable as possible, rather than performing well but being hard to understand.

2
  • 2
    I understand your algorithm, but I don't understand what it actually does. Can you describe the criteria of a "winner" record? As I can guess, you're trying to implement something similar to Fitness proportionate selection (fitness = purchase score) to select a single record, but it's hard to tell from your algorithm.
    – scriptin
    Oct 11, 2015 at 9:48
  • Yes. It's like each purchase gives you one (or more) tickets in a lottery. The more tickets you have, the more the chance of you winning. To simulate tickets, I try and calculate the number of total tickets by multiplication. For example, if you buy 10 of item 1, it's like you have 10 tickets, and if you buy 10 of item 3, it's like you have 30. So if 2 people buy some items, and the first person buys 10 of item 1, while the second person buys 10 of item 3, the chance of the second person is three times as much, and this should be taken into account in the final selection. Does that make sense? Oct 11, 2015 at 12:48

2 Answers 2

2

You need to use the running total to perform the same summation you described, but in SQL.

Assuming you have tables like this:

CREATE TABLE items(
  id int(10) auto_increment,
  score int(10),
  PRIMARY KEY(id)
);

CREATE TABLE purchases(
  id int(10) auto_increment,
  item_id int(10),
  PRIMARY KEY(id),
  FOREIGN KEY (item_id) REFERENCES items(id) ON DELETE CASCADE
);

The query you're looking for is something like this:

SELECT a.id, SUM(i.score) as running_total
FROM purchases a,
     purchases b JOIN items i ON i.id = b.item_id
WHERE b.id <= a.id
GROUP BY a.id
HAVING SUM(i.score) >= (SELECT ROUND(RAND() * (SELECT SUM(i.score) from purchases a JOIN items i ON i.id = a.item_id)))
ORDER BY a.id
LIMIT 1;

I create the running total by joining the table on itself, using ID for ordering. b.id <= a.id makes sure that running total only takes previous purchases.

Then I apply a filter SUM(i.score) >= (SELECT ROUND(RAND() * (SELECT SUM(i.score) from purchases a JOIN items i ON i.id = a.item_id))) and LIMIT 1 to get just one result.

See SQLFiddle for step-by-step explanation.

The only concern is performance, you have to try it on your actual data. If it's bad, I believe there is a way to optimize this. Replacing HAVING with another WHERE condition is probably a good way to start.

Related article: NoSQL? No, SQL! – How to Calculate Running Totals

1

Generally, the solution which has the RDBMS do everything for you usually ends up being the most lightweight on the database, because you end up hitting the database only once, instead of multiple times. This is also, by definition, the solution which taxes the web server the least, as it only brings to the server the final results, nothing more.

So, you need to do the whole thing using a single select statement, ideally only with joins, but with nested sub-selects if need be. Then, you can try to find more optimal ways by breaking it down into pieces, but I would be willing to bet that you will not find anything that performs better.

So:

(Edit: the following is not correct, see scriptin's comments and scriptin's answer.)

  • Select customers.
  • Left join items purchased.
  • Left join that with the table that lists points per item.
  • Use SUM() to calculate total points per customer. I do not remember the exact details, but you will need to also look up the SQL reference for GROUP BY and possibly also for HAVING.
  • Use ORDER BY with DESCENDING on the sum of points to get the top-scoring customers first.
  • Use LIMIT 60 if you want to select someone among the top 60.
  • Nest the above in a new query which adds a column containing a random number. (See https://stackoverflow.com/questions/14798640/creating-a-random-number-using-mysql)
  • Add ORDER BY on the random column.
  • Take LIMIT 1 of that if you want only one winner.

Do all of the above in a single query, nesting as much as necessary. Indent nicely, but keep in mind that no matter how nicely you indent, in the end it will be an ugly looking monster. However, SQL is a relatively simple language, so anyone who has enough experience with SQL should be able to understand what it does and how it does it after giving it enough diligent study. A major benefit of doing it all in a single SQL query is that it is all in one place for someone to read and understand. (Besides the fact that it will most probably be the best performing way to obtain a random customer among the top scorers.)

Hint: in order to test this, you need to use the RAND(N) syntax of MySQL, so as to obtain the exact same sequence of random numbers each time you run the query. If you also want to have control over the exact values of the "random" numbers, then create a separate table with customer ids and random numbers and LEFT JOIN it when testing your algorithm in order to make sure it works. Then, replace that with RAND().

6
  • I believe your approach is correct (doing everything in SQL), but you're describing another algorithm. Particularly, score is not even taken into account - you only filter top N records by score, but after that you just select randomly, i.e. with even distribution, which conflicts with question's intent.
    – scriptin
    Oct 11, 2015 at 13:24
  • @scriptin but I say "Use SUM() to calculate total points per customer", and then "Use ORDER BY on the sum of points" and then "Use `LIMIT 60 to select someone among the top 60". The sum of points is, you know, the score. No?
    – Mike Nakis
    Oct 11, 2015 at 13:46
  • Yes, it is. But still that's just random selection with a threshold filter: 1) items which are not in top N do not get a chance to be selected, 2) items among those top N are selected randomly, without considering the score. You're using the score only as a threshold. I asked a question about that in a comment, and author replied that indeed he wanted to implement fitness proportionate selection (with a single round of selection). I'm not saying your algorithm is wrong, but it's different, and it's not what the question is about.
    – scriptin
    Oct 11, 2015 at 15:39
  • 1
    As author explained, each score point is a ticket in a "lottery", and your algorithm makes that lottery unfair, since not all tickets participate. All tickets must have a chance, it's just a matter of which one is selected in the end. Since each purchase can have more than one score, you can imagine that as buying few tickets in a row, multiplying your chances to win by the number of tickets you buy.
    – scriptin
    Oct 11, 2015 at 15:43
  • 1
    I still learned a lot from your answer. Upvote for that. Thank you both; you're awesome. Oct 12, 2015 at 7:33

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.