复杂的查询以重新分配系统计算票数

我花了最后两个晚上，尝试建立一个在分级投票系统中重新分配选票的系统。我最终提出了一种模型，用于从票数超过阈值的候选人中重新分配盈余。

我正处于学习曲线的起点，在此过程中，我广泛使用了Stack Overflow，以获取有关如何在此系统中生成每个查询的知识。

最后我达到了想要的结果，如下所示，这是以一组真正令人困惑的查询为代价的：

 +-----------+-------+----------------+----------------------------+
 | 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 |
 +-----------+-------+----------------+----------------------------+

如前所述-这些查询是可怕的。绝对可怕。现在，我需要了解如何简化这种方法，同时又比这种混乱的查询更有效。甚至更有效。

谁能解释一下如何以一种我可以学习更多的方式来优化它。关于编写好的查询？

这是我的（糟糕的）查询：

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;

这是架构：

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;

重新分配的规则如下：

如果候选人在第一轮中超过了门槛，他/她的盈余将按排名为数字的候选人按比例重新分配

比率计算如下：

胜利者的盈余除以总最大投票数，四舍五入到最接近的整数。然后将重新分配的值添加到候选项。

您是如何做到的？如果您得到正确的结果，我会非常感动（如果可以，我还没有检查过。）我会尽快检查一下。哇，好多嵌套。 =）

我分别尝试了每个子查询，以查明是否能够返回所需的值。完成后，我将其添加到外部查询中，然后重试。这很耗时，有时还很棘手，但是像SO这样的社区在帮助您方面发挥了最大的作用。 :)

听起来像是单一可转让投票，还是它的某些变体？

确实是。 :)这是它的剩余再分配。

OP对投票系统有误解。我们在聊天中将其清除。

#1 楼

您的查询同时非常糟糕。这确实令人印象深刻，尤其是如果您是自学成才的人。

不幸的是，我认为这是不正确的。（或者，我可能误会了您打算如何使用投票重新分配方案。）例如，报告显示，支持候选人2的重新分配应为+0.125。在以候选人1为第一选择的8张选票中，有4幅以候选人2为第二选择。再分配不应该是+0.5吗？

作为进一步的证据，redistribution列的总和应为0。但是，-1 + 0.125 + 0.25 + 0.5 + 0.25 + 0 = 0.125，这是“ t中性。

我会将votes表的术语更改为

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

，最好完全不使用该表，而直接进入vote_orders表，因为设计架构以支持固定数量的候选对象是一个坏主意。（俗话说，计算机科学中只有三个数字：零，一个和很多。您想要支持很多。）考虑到ballots表比存储格式更像是一种数据输入工具（可能是TEMPORARY TABLE）。

我会用“ votes”这个名字来称呼vote_orders表：

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

对于其余的评论，为了避免混淆，我会坚持使用您的原始名称。

选择RDBMS

对于像这样的复杂查询，我建议使用比MySQL更强大的数据库。例如，PostgreSQL（及其他）提供了几个优点：

支持公用表表达式（WITH子句），极大地帮助管理复杂性。 MySQL不支持CTE。解决方法是，您可以创建视图。但是，很难像使用CTE进行单个查询一样轻松地一次编辑所有视图，因此开发更加麻烦。此外，CTE不会污染全局名称空间，而且更容易了解后续CTE如何依赖较早的CTE。

我在下面使用CTE编写了解决方案，但将每个CTE重写为而是使用CREATE VIEW语句，并且我已经验证它可以与MySQL一起使用。

支持递归查询。使用递归CTE，您应该能够编写一个查询，以处理多轮投票转移。使用MySQL，您的替代方法是编写一个存储过程，该存储过程可以操纵临时表，这不太优雅。

对SQL的解释更严格。我经常发现MySQL松散地遵循SQL标准，并且使不应该使用的查询有意义。例如，您有一些相当可疑的SQL，例如

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

PostgreSQL会拒绝的（请参见下面有关此摘录的讨论）。与MySQL相比，您最终会在PostgreSQL上养成更好的习惯。

总体印象

不幸的是，您的查询太复杂了，我无法理解，特别是因为它会产生错误的结果。但是，我可以说您做得很好：

缩进是一致且合乎逻辑的（尽管使用子查询选择属性会导致混乱的缩进；请参见下文）。
关键字按惯例大写。
列名非常清楚和有意义。

一些问题是：

重复，例如阈值计算。
加密表别名，例如t，c和y。
您的许多子查询都将选择一个属性（SELECT (SELECT …) AS attribute）。尝试将子选择公式化为出现在FROM子句（SELECT subsel.attr FROM (SELECT attr 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,

votes_above_the_threshold被定义为t的列。 t通过HAVING子句进行过滤。它由WHERE votes_about_the_threshold = (SELECT MAX(votes_above_the_threshold) FROM vote_orders)进一步过滤，但votes_above_the_threshold中没有vote_orders列！我还会尝试从HAVING子查询的t条件中移走WHERE条件，从而取代surplus_ratio条件。它仍然有效吗？
如何将大量查询拆开以进行检查和验证并不明显。

解决方案

这是我作为PostgreSQL的SQL Fiddles解决方案以及也移植到MySQL的MS SQL Server。

第二个CTE MAX(votes_above_the_threshold)值得解释。我将其设计为一种以有用的汇总格式捕获所有投票的方法。

最后两个CTE（preferences和raw_next_round）实际上是多余的。我将其留给您展示如何使用redistributed_next_round生成与原始SELECT * FROM redistributed_next_round ORDER BY 1, 2, 3 CTE自相似的数据集，从而用作递归的概念验证。

我认为，与其逐行解释代码，不如继续学习。依次查询每个CTE：

preferences
SELECT * FROM quota;
SELECT * FROM preferences ORDER BY 1, 2, 3;
等。

每个CTE的目的应为清晰，并且在每个步骤中都可以验证中间结果。

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;

\ $ \ begingroup \ $
这绝对很棒。我将考虑所有这些建议。我需要坚持使用MySQL，因为我的主机仅支持MySQL和MSSQL。回到计算-正如我在前面的评论中提到的，该计算应该是正确的（我已经纠正了我的问题中的错字），因为据我了解，盈余和抵销是在单独的回合中计算的。我的这个丑陋查询只是赢家盈余的计算。为了获得消除再分配，我需要添加一个全新的查询（并且更漂亮）。 :)
\ $ \ endgroup \ $
–克里斯托弗·吉斯伦（KristoferGisslén）
2014年6月14日12:29在

\ $ \ begingroup \ $
在MS SQL Server上运行相同的查询。
\ $ \ endgroup \ $
– 200_success
2014年6月14日12:30

\ $ \ begingroup \ $
不过，重新分配列肯定会计算出错误的值。它与小数舍入的方式有关，我实际上不知道如何处理小数位。 :(
\ $ \ endgroup \ $
–克里斯托弗·吉斯伦（KristoferGisslén）
2014年6月14日12:31

#2 楼

免责声明：我是SQL Server专家。我可能会误解MySQL的特定语法。如果我这样做，我感到抱歉。

我注意到的第一件事是子查询在您的查询中一遍又一遍地显示。

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

您应该在查询开始时使用变量存储此结果，并在以后每次使用时调用它。像这样的东西：

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

这简化了以后的where语句。

此：
变为：

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

您可以在整个查询中应用它。（在SQL Server中，我不得不将其保留在您的交叉联接中。）

此子查询在您的代码中也显示了很多。

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

这是临时餐桌的不错选择。我不知道如何在MySQL中创建和填充表，因此您必须对其进行查找。查询应该是这样的。

声明@threshold变量。
设置@threshold变量。
创建一个临时表来存储vote_candidate和voice_above_the_threshold。
填充临时表。
在所有子查询所在的位置使用临时表代替子查询。

这应该为您提供一个不错的开始。在您真正拥有可管理的内容之前，可能需要进行几次迭代。一旦实现了临时表，您很有可能会发现完全不需要该变量。

\ $ \ begingroup \ $
MySQL非常复杂。我已经研究了您的建议，并且不得不使用它们。我试图在MySQL中实现声明语句（BEGIN DECLARE @threshold INT SET @threshold =（SELECT ...）END），但是我收到的只是一个语法错误。仅使用SET，我就可以调用一次@threshold。然后我得到一个错误，即字段中不存在@threshold列...我只是无法掌握它。
\ $ \ endgroup \ $
–克里斯托弗·吉斯伦（KristoferGisslén）
2014年6月13日在13:44

\ $ \ begingroup \ $
是的。对不起。就像我说的，我是SQL Server专家。我不知道什么是正确的MySQL语法。您必须查找文档。我尽力将其正确，但是我无法测试该声明。
\ $ \ endgroup \ $
–RubberDuck
2014年6月13日13:54

\ $ \ begingroup \ $
你给我这个主意。没有它，我会迷路。 :)当然，我将进一步探索变量的世界，以简化这些查询。 :)
\ $ \ endgroup \ $
–克里斯托弗·吉斯伦（KristoferGisslén）
2014年6月13日14:01

\ $ \ begingroup \ $
创建我提到的第二个查询的视图（您不能在视图中使用变量）也是另一个非常好的选择。 =）
\ $ \ endgroup \ $
–RubberDuck
14年6月13日在14:03

#3 楼

由于无法将悬赏赏赐给问题，因此，此“答案”将被授予2014年最佳代码回顾奖-昼夜奖。

\ $ \ begingroup \ $
非常感谢你们。这个“奖项”让我感到非常荣幸。我希望我能及时回到社区，这是过去一年给我的！
\ $ \ endgroup \ $
–克里斯托弗·吉斯伦（KristoferGisslén）
15年1月20日在12:17

编程黑洞网

复杂的查询以重新分配系统计算票数

评论

#1 楼

评论

#2 楼

评论

#3 楼

评论