Complex query to count votes with a redistribution system

Question

I've spent the last couple of evenings trying to build a system for redistribution of votes in a ranked voting system. I've finally come up with the model for redistributing surpluses from a candidate whose number of votes exceeds the threshold.

I'm at the beginning of my learning curve and I've used Stack Overflow extensively during this process to gain knowledge about how to produce each and every query within this system.

Finally I've reached the result I want as can be seen below on the expense of a really confusing set of queries:

 +-----------+-------+----------------+----------------------------+
 | CANDIDATE | VOTES | REDISTRIBUTION | VOTES_AFTER_REDISTRIBUTION |
 +-----------+-------+----------------+----------------------------+
 |         1 |     8 |             -1 |                          7 |
 |         2 |     1 |          0.125 |                      1.125 |
 |         3 |     2 |           0.25 |                       2.25 |
 |         4 |     4 |            0.5 |                        4.5 |
 |         5 |     2 |           0.25 |                       2.25 |
 |         6 |     3 |              0 |                          3 |
 +-----------+-------+----------------+----------------------------+

As mentioned - these queries are horrible. Absolutely and utterly HORRIBLE. Now I need to understand how this could be simplified and at the same time as effective or even more effective than this mess of queries.

Could anyone explain how to optimize this in a way that I can learn more about writing good queries?

This is my (awful) query:

SELECT vote_candidate candidate, original_votes votes, surplus_redistribution redistribution, (original_votes + surplus_redistribution) votes_after_redistribution
FROM (
    SELECT c.vote_candidate, (
        SELECT (
            (MAX(votes_above_the_threshold) - (
                SELECT FLOOR((COUNT(*) / (2 + 1)) + 1) threshold
                FROM votes
            )) / MAX(votes_above_the_threshold)
        ) ratio
        FROM (
            SELECT vote_candidate vote_candidate, COUNT(*) votes_above_the_threshold
            FROM vote_orders
            WHERE vote_order = 1
            GROUP BY vote_candidate
            HAVING votes_above_the_threshold >= (
                SELECT FLOOR((COUNT(*) / (2 + 1)) + 1) threshold
                FROM votes
            )
        ) t
        WHERE votes_above_the_threshold = (
            SELECT MAX(votes_above_the_threshold)
            FROM vote_orders
        )
    ) surplus_ratio, c.original_votes, LEAST(0,t.threshold - c.original_votes) surplus_redistribution
    FROM (
        SELECT o.vote_candidate, COUNT(*) original_votes
        FROM vote_orders o
        WHERE o.vote_order = 1
        GROUP BY o.vote_candidate
    ) c
    CROSS JOIN (
        SELECT FLOOR((COUNT(*) / (2 + 1)) + 1) AS threshold
        FROM votes
    ) t
    GROUP BY c.vote_candidate
    UNION
    SELECT vote_candidate, (
        SELECT (
            (MAX(votes_above_the_threshold) - (
                SELECT FLOOR((COUNT(*) / (2 + 1)) + 1) threshold
                FROM votes
            )) / MAX(votes_above_the_threshold)
        ) ratio
        FROM (
            SELECT vote_candidate vote_candidate, COUNT(*) votes_above_the_threshold
            FROM vote_orders
            WHERE vote_order = 1
            GROUP BY vote_candidate
            HAVING votes_above_the_threshold >= (
                SELECT FLOOR((COUNT(*) / (2 + 1)) + 1) threshold
                FROM votes
            )
        ) t
        WHERE votes_above_the_threshold = (
            SELECT MAX(votes_above_the_threshold)
            FROM vote_orders
        )
    ) surplus_ratio, COUNT(*) original_votes, (
        ROUND((COUNT(*) * (
            SELECT (
                (MAX(votes_above_the_threshold) - (
                    SELECT FLOOR((COUNT(*) / (2 + 1)) + 1) threshold
                    FROM votes
                )) / MAX(votes_above_the_threshold)
            ) ratio
            FROM (
                SELECT vote_candidate vote_candidate, COUNT(*) votes_above_the_threshold
                FROM vote_orders
                WHERE vote_order = 1
                GROUP BY vote_candidate
                HAVING votes_above_the_threshold >= (
                    SELECT FLOOR((COUNT(*) / (2 + 1)) + 1) threshold
                    FROM votes
                )
            ) t
            WHERE votes_above_the_threshold = (
                SELECT MAX(votes_above_the_threshold)
                FROM vote_orders
            )
        )), 3)
    ) surplus_redistribution
    FROM vote_orders
    WHERE vote_order = 1
    AND vote_candidate IN ((
        SELECT vote_candidate
        FROM vote_orders a
        INNER JOIN (
            SELECT vote_id, MIN(vote_order) AS min_vote_order
            FROM vote_orders
            WHERE vote_candidate NOT IN ((
                SELECT vote_candidate
                FROM (
                    SELECT vote_candidate vote_candidate, COUNT(*) votes_above_the_threshold
                    FROM vote_orders
                    WHERE vote_order = 1
                    GROUP BY vote_candidate
                    HAVING (
                        votes_above_the_threshold >= (
                            SELECT FLOOR((COUNT(*) / (2 + 1)) + 1) threshold
                            FROM votes
                        )
                        OR (
                            votes_above_the_threshold >= (
                                SELECT FLOOR((COUNT(*) / (2 + 1)) + 1) threshold
                                FROM votes
                            )
                            AND votes_above_the_threshold = 0
                        )
                        OR (
                            votes_above_the_threshold = 0
                        )
                    )
                ) t
            ))
            GROUP BY vote_id
        ) b
        ON a.vote_id = b.vote_id
        AND a.vote_order = b.min_vote_order
        INNER JOIN (
            SELECT vote_id
            FROM vote_orders
            WHERE vote_candidate = (
                SELECT vote_candidate
                FROM (
                    SELECT vote_candidate vote_candidate, COUNT(*) votes_above_the_threshold
                    FROM vote_orders
                    WHERE vote_order = 1
                    GROUP BY vote_candidate
                    HAVING votes_above_the_threshold >= (
                        SELECT FLOOR((COUNT(*) / (2 + 1)) + 1) threshold
                        FROM votes
                    )
                ) t
                WHERE votes_above_the_threshold >= (
                    SELECT MAX(votes_above_the_threshold)
                    FROM vote_orders
                )
            )
            AND vote_order = 1
        ) c
        ON a.vote_id = c.vote_id
        GROUP BY vote_candidate
    ))
    GROUP BY vote_candidate
    ORDER BY vote_candidate ASC
) y
GROUP BY vote_candidate;

This is the schema:

CREATE TABLE votes
(
    vote_id INT NOT NULL AUTO_INCREMENT,
    vote_candidate_a INT,
    vote_candidate_b INT,
    vote_candidate_c INT,
    vote_candidate_d INT,
    vote_candidate_e INT,
    vote_candidate_f INT,
    PRIMARY KEY vote_id(vote_id)
);

INSERT INTO votes
VALUES
(NULL, 1, 3, 2, 5, 4, 6),
(NULL, 1, 2, 4, 6, 3, 5),
(NULL, 5, 3, 2, 1, 4, 6),
(NULL, 6, 1, 5, 3, 4, 2),
(NULL, 2, 3, 5, 6, 1, 4),
(NULL, 4, 1, 6, 3, 2, 5),
(NULL, 3, 2, 6, 1, 5, 4),
(NULL, 4, 3, 1, 6, 2, 5),
(NULL, 1, 2, 4, 3, 6, 5),
(NULL, 1, 5, 3, 2, 4, 6),
(NULL, 4, 5, 6, 2, 3, 1),
(NULL, 1, 4, 2, 3, 5, 6),
(NULL, 1, 2, 3, 4, 5, 6),
(NULL, 3, 6, 5, 1, 4, 2),
(NULL, 1, 2, 3, 4, 5, 6),
(NULL, 6, 5, 4, 3, 2, 1),
(NULL, 4, 3, 1, 5, 6, 2),
(NULL, 6, 3, 1, 2, 5, 4),
(NULL, 1, 4, 6, 3, 2, 5),
(NULL, 5, 3, 6, 4, 2, 1);

CREATE TABLE vote_orders
(
    id INT NOT NULL AUTO_INCREMENT,
    vote_id INT,
    vote_order INT,
    vote_candidate INT,
    PRIMARY KEY id(id)
);

INSERT INTO vote_orders (id, vote_id, vote_order, vote_candidate)
SELECT NULL, vote_id, 1, vote_candidate_a FROM votes
UNION
SELECT NULL, vote_id, 2, vote_candidate_b FROM votes
UNION
SELECT NULL, vote_id, 3, vote_candidate_c FROM votes
UNION
SELECT NULL, vote_id, 4, vote_candidate_d FROM votes
UNION
SELECT NULL, vote_id, 5, vote_candidate_e FROM votes
UNION
SELECT NULL, vote_id, 6, vote_candidate_f FROM votes;

The rules for redistributing works like this:

If a candidate exceeds the threshold in the first round, his/hers surplus is redistributed proportionally to the candidate ranked as number two on the winners ballots.

The ratio is calculated like this:

The surplus of the winner is divided by the total max votes rounded down to the nearest full integer. Then the redistributed value is added to the candidates.

Answer 1

Your query is simultaneously awful and awesome. It is truly impressive, especially if you are self-taught.

Unfortunately, I don't believe it is correct. (Or, I may have misunderstood how you intended for the vote redistribution scheme to work.) For example, it reports that the redistribution in favour of Candidate 2 should be +0.125. Of the 8 ballots that have Candidate 1 as the first choice, 4 of them have Candidate 2 as the second choice. Shouldn't the redistribution be +0.5 then?

As further evidence, the redistribution column should sum to 0. However, -1 + 0.125 + 0.25 + 0.5 + 0.25 + 0 = 0.125, which isn't neutral.

Schema

I would have changed the terminology of your votes table as

CREATE TABLE ballots
( id INT NOT NULL AUTO_INCREMENT PRIMARY KEY
, choice1 INT
, choice2 INT
, choice3 INT
, choice4 INT
, choice5 INT
, choice6 INT
);

However, it may have been better to do away with that table altogether, and go straight to the vote_orders table, because it's a bad idea to design your schema to support a fixed number of candidates. (As the saying goes, there are only three numbers in computer science: zero, one, and many. You want to support many.) Consider the ballots table to be more of a data entry tool (possibly a TEMPORARY TABLE) than a storage format.

I would have used the name "votes" for what you called the vote_orders table:

CREATE TABLE votes
( ballot INT NOT NULL
, rank INT NOT NULL
, candidate INT NOT NULL
, UNIQUE (ballot, rank)
, UNIQUE (ballot, candidate)
);

For the rest of the review, I'll stick with your original names, so as to avoid confusion.

Choice of RDBMS

For a complex query like this, I recommend using a more capable database than MySQL. For example, PostgreSQL (and others) offers several advantages:

• Support for Common Table Expressions (WITH clauses), which help tremendously with managing the complexity. MySQL does not support CTEs. As a workaround, you can create views instead. However, it's harder to edit all of your views at once as easily as a single query with CTEs, so development is more cumbersome. Also, CTEs don't pollute the global namespace, and it's easier to see how subsequent CTEs depend on earlier CTEs.

  I've written my solution below using CTEs, but it's trivial to rewrite each CTE as a CREATE VIEW statement instead, and I've verified that it does work with MySQL that way.

• Support for recursive queries. Using recursive CTEs, you should be able to write one query that processes multiple rounds of vote transfers. With MySQL, your alternative would be to write a stored procedure that manipulates a temporary table, which is less elegant.

• Stricter interpretation of SQL. I often find that MySQL adheres loosely to the SQL standard, and makes sense of queries that shouldn't make sense. For example, you have some rather suspect SQL such as

  WHERE votes_above_the_threshold = (
      SELECT MAX(votes_above_the_threshold)
      FROM vote_orders
  )
  

  that PostgreSQL would have rejected (see discussion about this excerpt below). You'll end up acquiring better habits developing on PostgreSQL than MySQL.

Overall impression

Unfortunately, your query is too complex for me to try to understand, especially since it yields wrong results. However, I can say that you did some things well:

• Indentation is consistent and logical (though using subqueries to select attributes results in messy indentation; see below).
• Keywords are capitalized according to common practice.
• Column names are pretty clear and meaningful.

Some problems are:

• Repetition, such as the threshold calculation.
• Cryptic table aliases, such as t, c, and y.
• Many of your subqueries are to select an attribute (SELECT (SELECT …) AS attribute). Try to formulate your subselects to appear in the FROM clause (SELECT subsel.attr FROM (SELECT attr FROM …)), which will make your indentation saner and the query generally more readable.

• Convoluted reasoning that looks almost circular. For example, in the first two dozen lines…

  SELECT c.vote_candidate, (
      SELECT (
          (MAX(votes_above_the_threshold) - (
              SELECT FLOOR((COUNT(*) / (2 + 1)) + 1) threshold
              FROM votes
          )) / MAX(votes_above_the_threshold)
      ) ratio
      FROM (
          SELECT vote_candidate vote_candidate, COUNT(*) votes_above_the_threshold
          FROM vote_orders
          WHERE vote_order = 1
          GROUP BY vote_candidate
          HAVING votes_above_the_threshold >= (
              SELECT FLOOR((COUNT(*) / (2 + 1)) + 1) threshold
              FROM votes
          )
      ) t
      WHERE votes_above_the_threshold = (
          SELECT MAX(votes_above_the_threshold)
          FROM vote_orders
      )
  ) surplus_ratio,
  

  votes_above_the_threshold is defined as a column of t. t is filtered through a HAVING clause. It is further filtered by WHERE votes_about_the_threshold = (SELECT MAX(votes_above_the_threshold) FROM vote_orders), but there is no votes_above_the_threshold column in vote_orders! I'd also try removing the HAVING condition in t favour of the WHERE condition of the surplus_ratio subquery.

• What happens if there is a tie for first place after a round (multiple MAX(votes_above_the_threshold))? Does it still work?
• It's not obvious how to take your massive query apart for inspection and verification.

Solution

Here is my solution as SQL Fiddles for PostgreSQL and MS SQL Server, also ported to MySQL.

The second CTE, preferences, is worth explaining. I've devised it as a way to capture all the votes in a useful aggregated format.

The last two CTEs (raw_next_round and redistributed_next_round) are actually superfluous. I've left it in to show how you can do a SELECT * FROM redistributed_next_round ORDER BY 1, 2, 3 to produce a data set that is self-similar to the original preferences CTE, thus serving as a proof-of-concept for recursion.

Rather than explain the code line by line, I think it would be instructive to follow along yourself. Query each CTE in turn:

• SELECT * FROM quota;
• SELECT * FROM preferences ORDER BY 1, 2, 3;
• SELECT * FROM electees ORDER BY 1, 2, 3;
• etc.

The purpose of each CTE should be clear, and the intermediate results are all verifiable at each step.

WITH quota AS (
    SELECT FLOOR(COUNT(*) / (2 + 1)) + 1 AS threshold
        FROM votes
), preferences AS (
    SELECT 1 AS round
         , NULL AS preferred_candidate
         , vote_candidate AS candidate
         , COUNT(*) AS votes
         , CAST(NULL AS INTEGER) AS elected_in_round
        FROM vote_orders
        WHERE vote_order = 1
        GROUP BY vote_candidate
  UNION ALL
    SELECT fallback.vote_order AS round
         , preferred.vote_candidate AS preferred_candidate
         , fallback.vote_candidate AS candidate
         , COUNT(*) AS votes
         , NULL AS elected_in_round
        FROM vote_orders AS preferred
            JOIN vote_orders AS fallback
                ON preferred.vote_id = fallback.vote_id
                AND preferred.vote_order + 1 = fallback.vote_order
        GROUP BY fallback.vote_order, preferred.vote_candidate, fallback.vote_candidate
), electees AS (
    SELECT preferences.round
         , preferences.preferred_candidate
         , preferences.candidate
         , preferences.votes
         , round AS elected_in_round
         , votes - quota.threshold AS surplus
        FROM preferences, quota
        WHERE votes >= quota.threshold
            AND round = (SELECT MIN(round) FROM preferences)
), per_electee_redistribution AS (
    SELECT this_round.round AS round
         , this_round.candidate AS preferred_candidate
         , next_round.candidate AS candidate
         , this_round.votes AS preferred_votes
         , this_round.surplus AS surplus
         , next_round.votes AS fallback_votes
         , this_round.surplus * next_round.votes / (this_round.votes + 0.0) AS redistribution
        FROM electees AS this_round
            LEFT OUTER JOIN preferences AS next_round
                ON this_round.round + 1 = next_round.round
                AND this_round.candidate = next_round.preferred_candidate
        WHERE this_round.elected_in_round = this_round.round
), redistribution AS (
    SELECT round
         , candidate AS beneficiary
         , SUM(redistribution) AS redistribution
        FROM per_electee_redistribution
        GROUP BY round, candidate
  UNION ALL
    SELECT round
         , candidate AS beneficiary
         , -surplus
         FROM electees
         WHERE elected_in_round = round
), redistributed AS (
    SELECT preferences.round AS round
         , preferences.preferred_candidate
         , preferences.candidate
         , preferences.votes
         , COALESCE(redistribution.redistribution, 0) AS redistribution
         , preferences.votes + COALESCE(redistribution.redistribution, 0) AS votes_after_redistribution
        FROM preferences
            LEFT OUTER JOIN redistribution
                ON preferences.round = redistribution.round
                AND preferences.candidate = redistribution.beneficiary
), raw_next_round AS (
    SELECT round
         , NULL AS preferred_candidate
         , candidate
         , SUM(votes) AS votes
         , NULL AS elected_in_round
        FROM preferences
        WHERE round = 1 + (SELECT MIN(round) FROM redistributed)
            AND candidate NOT IN (SELECT candidate FROM electees)
        GROUP BY round, candidate
  UNION ALL
    SELECT *
        FROM preferences
        WHERE round > 1 + (SELECT MIN(round) FROM redistributed)
            AND preferred_candidate NOT IN (SELECT candidate FROM electees)
            AND candidate NOT IN (SELECT candidate FROM electees)
  UNION ALL
    SELECT 1 + (SELECT MIN(round) FROM redistributed) AS round
         , NULL
         , candidate
         , votes
         , elected_in_round
        FROM electees
), redistributed_next_round AS (
    SELECT raw_next_round.round
         , raw_next_round.preferred_candidate
         , raw_next_round.candidate
         , raw_next_round.votes + redistributed.redistribution AS votes
         , raw_next_round.elected_in_round
        FROM raw_next_round
            CROSS JOIN redistributed
        WHERE raw_next_round.round = redistributed.round + 1
            AND raw_next_round.candidate = redistributed.candidate
)
SELECT candidate
     , votes
     , redistribution
     , votes_after_redistribution
    FROM redistributed
    WHERE round = 1
    ORDER BY candidate;

Answer 2

Disclaimer: I'm a SQL Server guy. I might get the particular syntax of MySQL wrong. I apologize if I do.

The first thing I notice is this that subquery shows up over and over again in your query.

SELECT FLOOR((COUNT(*) / (2 + 1)) + 1) threshold
FROM votes

You should use a variable to store the result of this at the beginning of your query and call it each time you would use it later. Something like:

DECLARE @threshold INT 
SELECT @threshold := SELECT FLOOR((COUNT(*) / (2 + 1)) + 1) FROM votes

This simplifies your where statements later.

This:

    SELECT (
        (MAX(votes_above_the_threshold) - (
            SELECT FLOOR((COUNT(*) / (2 + 1)) + 1) threshold
            FROM votes
        )) / MAX(votes_above_the_threshold)
    ) ratio

Becomes this:

    SELECT (
        (MAX(votes_above_the_threshold) - threshold) / MAX(votes_above_the_threshold)
    ) ratio

You can apply that through out your query. (In SQL Server I had to leave it duplicated in your Cross Join.)

This subquery shows up a lot in your code too.

        SELECT vote_candidate vote_candidate, COUNT(*) votes_above_the_threshold
        FROM vote_orders
        WHERE vote_order = 1
        GROUP BY vote_candidate
        HAVING votes_above_the_threshold >= @threshold

This a good candidate for a temporary table. I don't know how to create and populate a table in MySQL, so you'll have to look it up. The query should flow something like this though.

1. Declare @threshold variable.
2. Set @threshold variable.
3. Create temporary table to store vote_candidate & votes_above_the_threshold.
4. Populate temporary table.
5. Use temporary table in place of subquery in all places the subquery is now.

That should give you a pretty good start. It might take a couple of iterations until you really have something manageable. It's completely possible that you'll find the variable is completely unnecessary once you've implemented the temporary table.

Answer 3

Since bounties cannot be awarded to questions, this "answer" is being awarded a bounty as a prize for Best of Code Review 2014 — Night and Day category.