3

这似乎是一个常见的问题，但我一直在网上搜索并找不到答案。

我想保留一些东西几天（没有部分天），所以我想我需要一张类似的桌子：

CREATE TABLE reservations 
    (
     item int, 
     customer int, 
     startDate date, 
     endDate date
    );

（嗯，我的主键是什么？item 和 startDate？我还需要 PK 吗？）

但我的主要问题是如何在给定开始和结束日期的情况下找到免费物品。我的SELECT ...长相如何？

对于奖励分数，我们是否可以假设所有项目都是相同的，并且我想让它尽可能高效，所以如果我想从星期五开始预订，我希望找到一个保留到星期四的项目（因此是周五免费）。

对于双倍奖励分数，如果我需要 X 天的商品，我想在尽可能接近 X 天的时候找到预订有漏洞的商品。

我认为问题在于我试图找到不存在的东西（现有预订）。我发现的所有其他解决方案似乎都有一个带有项目 ID 的可预订日期表（值为 NULL、0 或 -1 表示“尚未预订”）。这对我来说似乎效率低下。这张桌子会延伸到多远的未来？

注意：有些人在询问读取与写入的比率。显然，每个预订只进行一次，所以这是一次写入（可能每天一次，具体取决于实现），我希望在用户搜索未预订的插槽时进行多次读取。

4

6 回答 6

6 
SELECT item FROM reservations WHERE 
(endDate BETWEEN start AND end) OR (startDate BETWEEN start AND end) OR (startDate<start AND endDate>end)

由@Strawberry 建议一个更好的查询看起来像这样

SELECT item FROM reservations WHERE
start<endDate AND end>startDate

这将为您提供在您正在寻找的日期拍摄的物品。现在您需要查找不在此列表中的项目。所以如果你有一张桌子，你可以这样写

SELECT * FROM items WHERE item NOT IN 
SELECT item FROM reservations WHERE
start<endDate AND end>startDate)

并且您会获得在您搜索期间免费的项目。

start，end 是日期您查找 startDate，endDate 是列。

SELECT item, start-r.startDate as diff FROM items as i 
LEFT JOIN reservations as r USING(item) 
WHERE i.item NOT IN 
(SELECT item FROM reservations WHERE
start<endDate AND end>startDate
) ORDER BY diff

没有模式来测试它，但这个查询应该是你的第一个奖金的答案

至于第二个，这需要在一张表的行之间做一些数学运算，如果可能的话，我现在不知道如何在纯 MySQL 中做。

//编辑

当现有预订在搜索期之前和之后结束时，我用另一种情况更新了查询。

对于第二个奖金问题，这应该有效

SELECT item, r1.startDate-r2.endDate as diff FROM reservations as r1 JOIN (SELECT * FROM reservations) as r2 USING (item)
WHERE r1.startDate-r2endDate>=x AND item NOT IN
(SELECT item FROM reservations WHERE
r1.startDate<endDate AND r2.endDate>startDate)
ORDER BY diff ASC

但这将是非常昂贵的查询。可能需要从子查询中的日期中添加/减去一天。

正如您在所有这些中看到的那样，我从帖子开头使用查询作为子查询，对于第一个和第二个查询，这不会是一个大问题，因为它只会执行一次。在第二个奖励的最后一个查询中，它必须分别为每一行执行（因为每个项目都有一个连接，给定项目的保留数量是 2 的幂），这可能是一个瓶颈。

我不知道您要保留的那些项目是什么，但如果它们不是很多 <1000 它可能足够快（每年最多 365000 行）但是如果项目数量真的很大，也许您可以使额外的条件在未来看起来最多一年，并且仅在必要时增加它加上分区它可以工作得非常快。

于 2013-04-14T05:29:25.047 回答
4

这对我的方法并不重要，但我假设你有一张items桌子。我还将提供一个不需要项目表的查询。单独的项目表的优点是您可以随着时间的推移轻松添加或淘汰项目。它们会自动显示在预订查询结果中，您可以稍后添加条件，例如WHERE retireDate IS NULL or retireDate > @reservationWindowEnd排除已停用的项目（而不是添加虚拟预订来实现相同的目标）。

举个例子，

CREATE TABLE items (
    item int, 
    description varchar(255),
    purchaseDate date,
    retireDate date
);

让我们还为我们想要匹配的预订窗口设置一些示例值。

mysql> set @newReservationStart='2013-06-01';
Query OK, 0 rows affected (0.00 sec)

mysql> set @newReservationEnd='2013-06-04';
Query OK, 0 rows affected (0.00 sec)

现在让我们找到至少在目标持续时间的一部分期间保留的项目列表：

SELECT
    DISTINCT item
FROM reservations
WHERE
    @newReservationStart BETWEEN startDate AND endDate
    OR startDate BETWEEN @newReservationStart and @newReservationEnd

我们想要未反转的项目列表，因此我们找到不在此列表中的项目列表：

SELECT
    item
FROM
    items
WHERE
    item NOT IN (
        SELECT
            DISTINCT item
        FROM reservations
        WHERE
            @newReservationStart BETWEEN startDate AND endDate
            OR startDate BETWEEN @newReservationStart and @newReservationEnd
    )

请注意，如果您没有单独的 items 表，则可以替换SELECT item FROM items为SELECT DISTINCT item FROM reservations.

现在我们有了一个已知可用项目的列表，让我们决定我们想要哪一个。

对于每个项目，我们需要知道它的哪个保留是在目标窗口之前最后结束的：

SELECT item, MAX(endDate) AS endDate
FROM reservations
WHERE endDate < @newReservationStart
GROUP BY item

我们想知道它的哪个保留是在目标保留期之后首先开始的：

SELECT item, MIN(startDate) AS startDate
FROM reservations
WHERE @newReservationEnd < startDate
GROUP BY item

在进一步讨论之前，让我们将其放在一起以一次获取相关项目的所有这些信息：

SELECT
    items.item AS item,
    priorReservation.endDate AS priorEnd,
    nextReservation.startDate AS nextStart
FROM
    items
    LEFT JOIN
        (
            SELECT item, MAX(endDate) AS endDate
            FROM reservations
            WHERE endDate < @newReservationStart
            GROUP BY item
        ) priorReservation ON priorReservation.item = items.item
    LEFT JOIN
        (
            SELECT item, MIN(startDate) AS startDate
            FROM reservations
            WHERE @newReservationEnd < startDate
            GROUP BY item
        ) nextReservation ON nextReservation.item = items.item
WHERE
    items.item NOT IN (
        SELECT
            DISTINCT item
        FROM reservations
        WHERE
            @newReservationStart BETWEEN startDate AND endDate
            OR startDate BETWEEN @newReservationStart and @newReservationEnd
    )

不是太寒酸。我们还知道上一个预订何时结束以及下一个预订何时开始。如果没有先前或下一个预留，则 LEFT JOIN 确保相应的值为空。因为我们知道所有列出的项目都是可用的，所以我们可以按照我们想要的条件进行排序。

我们可以通过最“舒适”的窗口订购：

ORDER BY DATEDIFF(nextStart, priorEnd)

或者最小化上一次预订结束和这次预订开始之间的时间：

ORDER BY DATEDIFF(@newReservationStart, priorEnd)

或者更喜欢从未保留的新项目：

ORDER BY ISNULL(priorEnd) DESC

或者我们可以组合多个选项，以偏爱新项目，然后选择最接近预订窗口开始日期返回的项目，然后选择可用性最符合目标窗口的项目：

ORDER BY
    ISNULL(priorEnd) DESC,
    DATEDIFF(nextStart, priorEnd),
    DATEDIFF(nextStart, priorEnd)

LIMIT关键字甚至可以用来选择最合适的。把这一切放在一起，

SELECT
    items.item AS item,
    priorReservation.endDate AS priorEnd,
    nextReservation.startDate AS nextStart
FROM
    items
    LEFT JOIN
        (
            SELECT item, MAX(endDate) AS endDate
            FROM reservations
            WHERE endDate < @newReservationStart
            GROUP BY item
        ) priorReservation ON priorReservation.item = items.item
    LEFT JOIN
        (
            SELECT item, MIN(startDate) AS startDate
            FROM reservations
            WHERE @newReservationEnd < startDate
            GROUP BY item
        ) nextReservation ON nextReservation.item = items.item
WHERE
    items.item NOT IN (
        SELECT
            DISTINCT item
        FROM reservations
        WHERE
            @newReservationStart BETWEEN startDate AND endDate
            OR startDate BETWEEN @newReservationStart and @newReservationEnd
    )
ORDER BY
    ISNULL(priorEnd) DESC,
    DATEDIFF(nextStart, priorEnd),
    DATEDIFF(nextStart, priorEnd)
LIMIT 1

在合理的数据集上运行查询需要很长时间，令人失望。使用包含 155 个项目的样本数据集，每个项目大约有 30 个预订，大约需要 15 秒，这对于交互式应用程序来说太慢了。

MySQL 从“外向内”评估查询，使用最外层查询过滤传递给内部查询的行。因此，让我们将最外层的WHERE子句放在“测试工具”查询中，看看会EXPLAIN发现什么。

mysql>解释
    -> 选择
    -> items.item
    -> 从
    -> 项目
    -> 在哪里
    -> items.item 不在（
    -> 选择
    -> 不同的项目
    -> 从预订
    -> 在哪里
    -> @newReservationStart 在 startDate 和 endDate 之间
    -> OR startDate BETWEEN @newReservationStart 和 @newReservationEnd
    ->）
    ->;
+----+--------+--------------+------+- --------------+------+---------+------+------+---- --------------------------+
| 编号 | 选择类型 | 表| 类型 | 可能的键 | 关键 | key_len | 参考 | 行 | 额外 |
+----+--------+--------------+------+- --------------+------+---------+------+------+---- --------------------------+
| 1 | 初级 | 项目 | 全部 | 空 | 空 | 空 | 空 | 155 | 使用位置 |
| 2 | 依赖子查询 | 预订 | 全部 | 空 | 空 | 空 | 空 | 3871 | 使用哪里；使用临时 |
+----+--------+--------------+------+- --------------+------+---------+------+------+---- --------------------------+
2 行（0.00 秒）

那看起来不太好。MySQL 正在为 items 表中的每一行运行子选择（“从属子查询”）。每次运行内部查询时，它都会查看表中的每个条目reservations。（这令人失望，因为内部查询产生的一组不同的项目实际上并不依赖于item外部查询的值。但这就是 MySQL 的工作方式，最近来自 Oracle DBA 的评论给我的印象是这种行为并不孤单。）

根据可用项目的总数，内部查询可能会运行多次。在我对 155 个项目的测试中，其中大多数都有约 30 个现有预订，运行此查询大约需要 0.7 秒。

让我们尝试一个索引以避免reservations对每个可用项目进行全表扫描。直观地说，我们可以从索引日期列开始。我们不在乎最终得到哪个项目，但我们对查看正确的时间段非常感兴趣：

mysql> 创建索引 idx_startDate_endDate_item
    -> ON 预订（开始日期、结束日期、项目）；
查询正常，0 行受影响（0.03 秒）
记录：0 重复：0 警告：0

不幸的是，这不会像预期的那样有帮助。MySQL 很好地处理startDate BETWEEN @newReservationStart and @newReservationEnd，因为它知道startDate只能在一个狭窄的值范围内。但是@newReservationStart BETWEEN startDate and endDate，我们不是在搜索可以缩小到一个小范围的单个列。MySQL 必须找到之前开始的所有保留@newReservationStart，并决定其中哪些在之后结束@newReservationStart。

运行相同的 EXPLAIN 语句，我们得到：

+----+--------+--------------+-------+ ----------------------------------------+---------- --------+---------+------+------+------ -------------------------------------+
| 编号 | 选择类型 | 表| 类型 | 可能的键 | 关键 | key_len | 参考 | 行 | 额外 |
+----+--------+--------------+-------+ ----------------------------------------+---------- --------+---------+------+------+------ -------------------------------------+
| 1 | 初级 | 项目 | 全部 | 空 | 空 | 空 | 空 | 155 | 使用位置 |
| 2 | 依赖子查询 | 预订 | 范围 | idx_startDate_endDate_item | idx_startDate_endDate_item | 4 | 空 | 3572 | 使用哪里；使用索引；使用临时 |
+----+--------+--------------+-------+ ----------------------------------------+---------- --------+---------+------+------+------ -------------------------------------+

尽管有索引，但我们只查看了 3871 行到 3572 行。我们正在为items.item. 如果我们假设大多数预订都是过去的，我们可以通过索引（endDate、startDate、item）做得更好一些。这将从查看​​ endDate 在@newReservationStart 之后的项目开始，并且可能是一个较小的子集。但它仍然不理想。我们需要一个单独的索引startDate作为第一列，因为该OR子句的另一部分查找特定范围的开始日期。

所以现在怎么办？

我们知道 MySQL 将为items.item. 所以我们真的只需要寻找我们当前正在检查的项目的预订。这可能意味着将查询转换为 SQL 连接，但让我们再给优化器一个机会。

mysql> ALTER TABLE 保留 DROP INDEX idx_startDate_endDate_item;
查询正常，0 行受影响（0.01 秒）
记录：0 重复：0 警告：0

mysql> 创建索引 idx_item_startDate
    -> ON 预订（项目，开始日期）；
查询正常，0 行受影响（0.02 秒）
记录：0 重复：0 警告：0

再次运行 EXPLAIN 语句，我们得到

+----+--------+--------------+-------- --------+--------------------------------+-------- +---------+------+------+------------- ------------+
| 编号 | 选择类型 | 表| 类型 | 可能的键 | 关键 | key_len | 参考 | 行 | 额外 |
+----+--------+--------------+-------- --------+--------------------------------+-------- +---------+------+------+------------- ------------+
| 1 | 初级 | 项目 | 全部 | 空 | 空 | 空 | 空 | 155 | 使用位置 |
| 2 | 依赖子查询 | 预订 | 索引子查询 | idx_item_startDate | idx_item_startDate | 5 | 功能 | 38 | 使用哪里；对 NULL 键进行全扫描 |
+----+--------+--------------+-------- --------+--------------------------------+-------- +---------+------+------+------------- ------------+

一点也不差！只是为了好玩，我们不妨通过创建items.item为NOT NULL. 我们忽略了查询中使用的事实endDate，但它不在索引中。MySQL 将使用索引来完成大部分工作。没有理由让它查询完整表来检查 endDate，所以让我们也替换索引：

mysql> ALTER TABLE items MODIFY item INT NOT NULL;
查询正常，155 行受影响（0.00 秒）
记录：155 重复：0 警告：0

mysql> ALTER TABLE 保留 DROP INDEX idx_item_startDate;
查询正常，0 行受影响（0.00 秒）
记录：0 重复：0 警告：0

mysql> CREATE INDEX idx_item_startDate_endDate ON 保留(item, startDate, endDate);
查询正常，0 行受影响（0.02 秒）
记录：0 重复：0 警告：0

EXPLAIN现在给我们：

+----+--------+--------------+-------- --------+----------------+------------ ----------------+---------+------+------+--------- -----------------+
| 编号 | 选择类型 | 表| 类型 | 可能的键 | 关键 | key_len | 参考 | 行 | 额外 |
+----+--------+--------------+-------- --------+----------------+------------ ----------------+---------+------+------+--------- -----------------+
| 1 | 初级 | 项目 | 全部 | 空 | 空 | 空 | 空 | 155 | 使用位置 |
| 2 | 依赖子查询 | 预订 | 索引子查询 | idx_item_startDate_endDate | idx_item_startDate_endDate | 5 | 功能 | 38 | 使用索引；使用位置 |
+----+--------+--------------+-------- --------+----------------+------------ ----------------+---------+------+------+--------- -----------------+

MySQL 现在使用索引来获取它需要的所有信息reservations。查询运行时间为 0.14 秒，这对于交互式应用程序来说似乎是合理的。

如果您不想要单独的项目表，您可以执行以下操作。

SELECT
    reservationItems.item AS item,
    priorReservation.endDate AS priorEnd,
    nextReservation.startDate AS nextStart
FROM
    (SELECT DISTINCT item FROM reservations) AS reservationItems
    LEFT JOIN
        (
            SELECT item, MAX(endDate) AS endDate
            FROM reservations
            WHERE endDate < @newReservationStart
            GROUP BY item
        ) priorReservation ON priorReservation.item = reservationItems.item
    LEFT JOIN
        (
            SELECT item, MIN(startDate) AS startDate
            FROM reservations
            WHERE @newReservationEnd < startDate
            GROUP BY item
        ) nextReservation ON nextReservation.item = reservationItems.item
WHERE
    reservationItems.item NOT IN (
        SELECT
            DISTINCT item
        FROM reservations
        WHERE
            @newReservationStart BETWEEN startDate AND endDate
            OR startDate BETWEEN @newReservationStart and @newReservationEnd
    )
ORDER BY
    ISNULL(priorEnd) DESC,
    DATEDIFF(nextStart, priorEnd),
    DATEDIFF(nextStart, priorEnd)
LIMIT 1

最后，使用Strawberry对有关在 SQL 中匹配日期范围的问题的回答将运行时间大约减少了我最初方法的一半。有趣的是，EXPLAIN输出完全相同。但是，如下所示的最终查询现在在 0.07 秒内运行。

SELECT
    items.item AS item,
    priorReservation.endDate AS priorEnd,
    nextReservation.startDate AS nextStart
FROM
    items
    LEFT JOIN
        (
            SELECT item, MAX(endDate) AS endDate
            FROM reservations
            WHERE endDate < @newReservationStart
            GROUP BY item
        ) priorReservation ON priorReservation.item = items.item
    LEFT JOIN
        (
            SELECT item, MIN(startDate) AS startDate
            FROM reservations
            WHERE @newReservationEnd < startDate
            GROUP BY item
        ) nextReservation ON nextReservation.item = items.item
WHERE
    items.item NOT IN (
        SELECT
            DISTINCT item
        FROM reservations
        WHERE
            @newReservationStart <= endDate
            AND startDate <= @newReservationEnd
    )
ORDER BY
    ISNULL(priorEnd) DESC,
    DATEDIFF(nextStart, priorEnd),
    DATEDIFF(nextStart, priorEnd)
LIMIT 1
于 2013-04-18T21:08:28.220 回答
1

这在数据库之外很容易做到 - 选择您愿意考虑在其中进行预订的时间段内的所有预订，使用结果填充一天为 1（已填充）或 0（未填充）的数组) 并扫描阵列以查找所需大小的间隙。O(n) 但一年只有 365 天，所以不会很慢。

于 2013-04-11T01:49:27.650 回答
1

正如其他人指出的那样，您可能不需要这样做太高效。也就是说，这是一种方法（取决于您的读写比率）：

一种方法是使用一张表格来跟踪未预订的时间段（在您感兴趣的任何时间范围内，例如从 2000 年到 2020 年）。最初，每个项目都有一段空闲时间。（我将以一种可读的方式列出这个；我将把模式留给你想象。）

FREE SLOTS
Item 1: January 1, 2000 - December 31, 2020
Item 2: January 1, 2000 - December 31, 2020

RESERVATIONS
(none)

当有人进行预订时，您创建一个预订，并将空闲槽分成两个较小的空闲槽（除非这会使它变空）。在此操作期间注意数据存储的锁定！

FREE SLOTS
Item 1: January 1, 2000 - May 4, 2012
Item 1: May 8, 2012 - December 31, 2020
Item 2: January 1, 2000 - December 31, 2020

RESERVATIONS
Item 1: May 5, 2012 - May 7, 2012, Barack Obama

删除预订后，您会立即检查前后的空闲时段。如果两者都存在，则将两个空闲槽和预留合并到一个空闲槽中。如果仅存在一个，则将其扩展以填充先前由预留占用的空间。

由于您可以轻松地在表格中保留空闲插槽的持续时间，因此您可以轻松找到所需持续时间的插槽（确切地说，大于某个数量，在一个范围内等）。您支付的成本是在修改数据存储时确保一致性所需的锁定。

于 2013-04-14T04:37:48.890 回答
1

如果您可以节省现金，Joe Celko 的 Smarties SQL可能会满足您的需求。

于 2013-04-17T22:53:32.647 回答
1

如果查找效率是最重要的，那么您最好使用更像...的模式

CREATE TABLE items
(
    id          INT             NOT NULL    AUTO_INCREMENT,
    name        VARCHAR(255)    NOT NULL,
    PRIMARY KEY (id)
);

CREATE TABLE reservations 
(
    item_id     INT     NOT NULL, 
    customer_id INT     NOT NULL, 
    reserved_on DATE    NOT NULL,
    PRIMARY KEY (item_id, reserved_on)
);

...并为每个保留项目的日期添加单独的行。

这样，数据库将确保您不能在同一日期多次预订同一个项目，并且查找哪些项目 ID 是免费的，比如说，2013-04-18变成......

SELECT
    i.id
FROM items i
    LEFT JOIN reservations r ON (r.item_id=i.id AND r.reserved_on='2013-04-18')
WHERE item_id IS NULL;

...EXPLAIN仅使用索引就可以满足一个节目...

+----+-------------+-------+--------+---------------+---------+---------+-----------------+------+--------------------------------------+
| id | select_type | table | type   | possible_keys | key     | key_len | ref             | rows | Extra                                |
+----+-------------+-------+--------+---------------+---------+---------+-----------------+------+--------------------------------------+
|  1 | SIMPLE      | i     | index  | NULL          | PRIMARY | 4       | NULL            |   10 | Using index                          |
|  1 | SIMPLE      | r     | eq_ref | PRIMARY       | PRIMARY | 7       | test.i.id,const |    1 | Using where; Using index; Not exists |
+----+-------------+-------+--------+---------------+---------+---------+-----------------+------+--------------------------------------+

这意味着在添加/修改保留时需要做更多的工作，但假设您将进行更多的读取而不是写入，这可能不是一个显着的开销。

于 2013-04-18T12:40:08.067 回答