10

考虑以下 2 个表:

Table A:
id
event_time

Table B
id
start_time
end_time

表 A 中的每条记录都映射到表 B 中的 1 条记录。这意味着表 B 没有重叠期间。表 A 中的许多记录可以映射到表 B 中的同一记录。

我需要一个返回所有 A.id、B.id 对的查询。就像是:

SELECT A.id, B.id 
FROM A, B 
WHERE A.event_time BETWEEN B.start_time AND B.end_time

我正在使用 MySQL,但无法优化此查询。表 A 中有约 980 条记录,表 B 中有 130.000 条记录,这需要很长时间。我知道这必须执行 980 次查询,但是在一台强大的机器上花费超过 15 分钟是很奇怪的。有什么建议么?

PS 我无法更改数据库架构,但我可以添加索引。但是,时间字段上的索引(具有 1 个或 2 个字段)没有帮助。

4

19 回答 19

4

您可能想尝试这样的事情

Select A.ID,
(SELECT B.ID FROM B
WHERE A.EventTime BETWEEN B.start_time AND B.end_time LIMIT 1) AS B_ID
FROM A

如果您在 B 的 Start_Time、End_Time 字段上有一个索引,那么这应该工作得很好。

于 2009-02-17T16:14:13.250 回答
3

我不确定这可以完全优化。我在 MySQL 5.1.30 上试过。{B.start_time, B.end_time}我还按照其他人的建议添加了一个索引。然后我得到了一份报告EXPLAIN,但我能得到的最好的是范围访问方法

EXPLAIN SELECT A.id, B.id FROM A JOIN B 
ON A.event_time BETWEEN B.start_time AND B.end_time;

+----+-------------+-------+------+---------------+------+---------+------+------+------------------------------------------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows | Extra                                          |
+----+-------------+-------+------+---------------+------+---------+------+------+------------------------------------------------+
|  1 | SIMPLE      | A     | ALL  | event_time    | NULL | NULL    | NULL |    8 |                                                | 
|  1 | SIMPLE      | B     | ALL  | start_time    | NULL | NULL    | NULL |   96 | Range checked for each record (index map: 0x4) | 
+----+-------------+-------+------+---------------+------+---------+------+------+------------------------------------------------+

请参阅最右侧的注释。优化器认为它可能能够使用索引,{B.start_time, B.end_time}但最终决定不使用该索引。您的结果可能会有所不同,因为您的数据分布更具代表性。

A.event_time如果与恒定范围进行比较,请与索引使用情况进行比较:

EXPLAIN SELECT A.id FROM A
WHERE A.event_time BETWEEN '2009-02-17 09:00' and '2009-02-17 10:00';

+----+-------------+-------+-------+---------------+------------+---------+------+------+-------------+
| id | select_type | table | type  | possible_keys | key        | key_len | ref  | rows | Extra       |
+----+-------------+-------+-------+---------------+------------+---------+------+------+-------------+
|  1 | SIMPLE      | A     | range | event_time    | event_time | 8       | NULL |    1 | Using where | 
+----+-------------+-------+-------+---------------+------------+---------+------+------+-------------+

并与@Luke 和@Kibbee 给出的依赖子查询形式进行比较,这似乎更有效地利用了索引:

EXPLAIN SELECT A.id AS id_from_a,
    (
        SELECT B.id
        FROM B
        WHERE A.id BETWEEN B.start_time AND B.end_time
        LIMIT 0, 1
    ) AS id_from_b
FROM A;

+----+--------------------+-------+-------+---------------+---------+---------+------+------+-------------+
| id | select_type        | table | type  | possible_keys | key     | key_len | ref  | rows | Extra       |
+----+--------------------+-------+-------+---------------+---------+---------+------+------+-------------+
|  1 | PRIMARY            | A     | index | NULL          | PRIMARY | 8       | NULL |    8 | Using index | 
|  2 | DEPENDENT SUBQUERY | B     | ALL   | start_time    | NULL    | NULL    | NULL |  384 | Using where | 
+----+--------------------+-------+-------+---------------+---------+---------+------+------+-------------+

奇怪的是,EXPLAIN 列出possible_keys为 NULL(即不能使用索引),但最终还是决定使用主键。可能是 MySQL 的 EXPLAIN 报告的一个特质吗?

于 2009-02-17T16:49:52.460 回答
2

我通常不会推荐这样的查询,但是......

由于您已指定表 A 只有大约 980 行,并且每一行都映射到表 B 中的一行,所以您可以执行以下操作,它很可能比笛卡尔连接快很多:

SELECT A.id AS id_from_a,
    (
        SELECT B.id
        FROM B
        WHERE A.event_time BETWEEN B.start_time AND B.end_time
        LIMIT 0, 1
    ) AS id_from_b
FROM A
于 2009-02-17T16:32:41.053 回答
2

我对类似的问题进行了一些测试 - 根据 IP 地址(以数字形式给出)计算国家。这是我的数据和结果:

  • 表 A(包含用户和 IP 地址)包含大约 20 条记录。
  • 表 B(包含每个国家/地区的 IP 范围)包含大约 100000 条记录。

使用“between”的 JOIN 查询大约需要 10 秒;SELECT 查询中的 SELECT 使用“between”,大约需要 5.5 秒;使用空间索引的 SELECT 查询中的 SELECT 大约需要 6.3 秒。使用空间索引的 JOIN 查询耗时 0 秒!

于 2010-10-27T12:07:02.817 回答
1

请注意,在运行此查询时,您实际上在应用条件之前在内存中创建了 980x130000 条记录。这样的 JOIN 不是很推荐,我可以理解为什么它会给你带来性能问题。

于 2009-02-17T15:46:27.620 回答
1

如果您无法更改架构——特别是,如果您无法在 a.event_time 上添加索引,我认为在 SQL 级别上没有太大的改进空间。

我更倾向于用代码来做。

  • 将所有 B 开始/结束/id 元组读入列表,按开始时间排序
  • 读取所有 A 事件
  • 对于每个 A 事件
    • 找到最大的开始时间 <= 事件时间(二分查找就可以了)
    • 如果事件时间 <= 结束时间,则将 A 添加到此 B 的事件列表中
    • 否则这个B没有家
于 2009-02-17T15:55:21.453 回答
1

不更改架构是否意味着您不能添加索引?在 start_time 和 end_time 上尝试多列索引。

于 2009-02-17T15:55:27.273 回答
0

尝试使用标准比较运算符(< 和 >)。

于 2009-02-17T15:45:00.230 回答
0

我看到您正在对两个表进行交叉连接。这不是很好,DBMS 将花费大量时间来执行该操作。交叉连接是 SQL 中最昂贵的操作。执行时间这么长的原因可能是这个。

照着做,就可以解决...

SELECT A.id, B.id FROM A, B WHERE A.id = B.id AND A.event_time BETWEEN B.start_time AND B.end_time

我希望这对你有帮助:)

于 2009-02-17T15:47:26.793 回答
0

B (start_time, end_time) 上是否有索引?如果不是,也许添加一个可能会加快 B 行与 A 行的匹配?

请注意,如果您无法更改架构,也许您也无法创建新索引?

于 2009-02-17T15:56:29.343 回答
0

您必须加快执行此查询的唯一方法是使用索引。

注意放入一个索引 yourA.event_time然后放入另一个索引B.start_timeand B.end_time

如果如您所说,这是将两个实体绑定在一起的唯一条件,我认为这是您可以采取的唯一解决方案。

费德

于 2009-02-17T16:11:57.297 回答
0

Daremon,这个答案是基于您的评论之一,您说表 A 中的每条记录都映射到表 B 中的一条记录,

你可以在你的模式中添加一个额外的表吗?如果是,您可以预先计算此查询的结果并将其存储在另一个表中。您还必须使这个预先计算的表与表 A 和 B 的更改保持同步

于 2009-02-17T16:13:11.690 回答
0

根据您的评论,A 中的每个条目都对应于 B 中的一个条目,最简单的解决方案是AUTOINCREMENT从 B 的 id 列中删除,然后将 B 的所有 id 替换为 A 中的 id。

于 2009-02-17T16:15:20.220 回答
0

MySQL不允许您INDEX ORDER BY WITH RANGE在派生查询中使用。

这就是为什么您需要创建一个用户定义的函数。

请注意,如果您的范围确实重叠,则查询将只选择一个(最后开始)。

CREATE UNIQUE INDEX ux_b_start ON b (start_date);

CREATE FUNCTION `fn_get_last_b`(event_date TIMESTAMP) RETURNS int(11)
BEGIN
  DECLARE id INT;
  SELECT b.id
  INTO id
  FROM b
  FORCE INDEX (ux_b_start)
  WHERE b.start_time <= event_date
  ORDER BY
    b.start_time DESC
  LIMIT 1;
  RETURN id;
END;

SELECT COUNT(*) FROM a;

1000


SELECT COUNT(*) FROM b;

200000

SELECT *
FROM (
  SELECT fn_get_last_b(a.event_time) AS bid,
         a.*
  FROM a
) ao, b FORCE INDEX (PRIMARY)
WHERE b.id = ao.bid
  AND b.end_time >= ao.event_time

1000 rows fetched in 0,0143s (0,1279s)
于 2009-02-17T16:52:55.573 回答
0

在 B.start_time 降序放置索引,然后使用此查询:

 SELECT A.id AS idA,
 (SELECT B.id FROM B WHERE A.event_time > B.start_time LIMIT 0, 1
 ORDER BY B.start_time DESC) AS idB
 FROM A

由于 B 中的时间桶是不相交的,这将为您提供第一个匹配的时间桶,并且您摆脱了两者之间的时间,但仍然有子查询。也许在索引中包含 B.id 会给你一些额外的小的性能提升。(免责声明:不确定 MySQL 语法)

于 2009-02-17T17:01:34.383 回答
0

我想不出你有一个包含 130.000 行时间间隔的表的原因。无论如何,这样的设计必须有充分的理由,如果是这样,你必须避免每次都尝试计算这样的连接。所以这是我的建议。我会在表 A (A.B_ID) 中添加对 B.id 的引用,并使用触发器来保持一致性。每当您添加新记录(插入触发器)或 even_time 列更改(更新触发器)时,您都将重新计算该时间对应的对 B 的引用。您的 select 语句将简化为一个 select * from A。

于 2009-02-17T17:05:23.283 回答
0

就个人而言,如果您有一对多关系并且表 a 中的每条记录仅与表 b 中的一条记录相关,我会将表 b id 存储在表 a 中,然后进行常规连接以获取数据。你目前拥有的是一个糟糕的设计,永远不会真正有效。

于 2009-02-17T21:48:01.060 回答
0

我的解决方案有两个警告:

1)您说您可以添加索引但不能更改架构,所以我不确定这是否适合您,因为您不能在 MySQL 中拥有基于函数的索引,您需要在 Table 上创建一个额外的列B. 2) 此解决方案的另一个警告是您必须为表 B 使用 MyISAM 引擎。如果您不能使用 MyISAM,那么此解决方案将不起作用,因为空间索引仅支持 MyISAM。

因此,假设上述两个对您来说不是问题,以下应该可以工作并为您提供良好的性能:

此解决方案利用 MySQL 对空间数据的支持(请参阅此处的文档)。虽然可以将空间数据类型添加到各种存储引擎中,但为了获得所需的性能,空间 R-Tree 索引(请参阅此处的文档)仅支持 MyISAM。另一个限制是空间数据类型仅适用于数字数据,因此您不能将此技术用于基于字符串的范围查询。

我不会详细介绍空间类型如何工作以及空间索引如何有用的理论细节,但您应该查看Jeremy Cole 的解释,了解如何使用空间数据类型和索引进行 GeoIP 查找。如果您需要原始性能并且可以放弃一些准确性,还请查看评论,因为它们提出了一些有用的观点和替代方案。

基本前提是我们可以使用 start/end 并使用它们中的两个创建四个不同的点,一个用于在 xy 网格上以 0,0 为中心的矩形的每个角,然后快速查找空间index 来确定我们关心的特定时间点是否在矩形内。如前所述,请参阅 Jeremy Cole 的解释,以更全面地了解其工作原理。

在您的特定情况下,我们将需要执行以下操作:

1) 将表更改为 MyISAM 表(请注意,除非您完全了解此类更改的后果,例如缺少与 MyISAM 关联的事务和表锁定行为,否则不应这样做)。

alter table B engine = MyISAM;

2)接下来我们添加将保存空间数据的新列。我们将使用多边形数据类型,因为我们需要能够容纳一个完整的矩形。

alter table B add column time_poly polygon NOT NULL;

3) 接下来,我们用数据填充新列(请记住,任何更新或插入表 B 的进程都需要进行修改,以确保它们也填充新列)。由于开始和结束范围是时间,我们需要使用 unix_timestamp 函数将它们转换为数字(有关其工作原理,请参阅此处的文档)。

update B set time_poly := LINESTRINGFROMWKB(LINESTRING(
    POINT(unix_timestamp(start_time), -1),
    POINT(unix_timestamp(end_time), -1),
    POINT(unix_timestamp(end_time), 1),
    POINT(unix_timestamp(start_time), 1),
    POINT(unix_timestamp(start_time), -1)
  ));

4) 接下来我们将空间索引添加到表中(如前所述,这仅适用于 MyISAM 表,并且会产生错误“ERROR 1464 (HY000): The used table type doesn't support SPATIAL index”)。

alter table B add SPATIAL KEY `IXs_time_poly` (`time_poly`);

5)接下来,您将需要使用以下选择,以便在查询数据时使用空间索引。

SELECT A.id, B.id 
FROM A inner join B force index (IXs_time_poly)
ON MBRCONTAINS(B.time_poly, POINTFROMWKB(POINT(unix_timestamp(A.event_time), 0)));

强制索引可以 100% 确保 MySQL 将使用索引进行查找。如果一切顺利,在上述选择上运行解释应该显示类似于以下内容:

mysql> explain SELECT A.id, B.id
    -> FROM A inner join B force index (IXs_time_poly)
    -> on MBRCONTAINS(B.time_poly, POINTFROMWKB(POINT(unix_timestamp(A.event_time), 0)));
+----+-------------+-------+------+---------------+------+---------+------+---------+-------------------------------------------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows    | Extra                                           |
+----+-------------+-------+------+---------------+------+---------+------+---------+-------------------------------------------------+
|  1 | SIMPLE      | A     | ALL  | NULL          | NULL | NULL    | NULL |    1065 |                                                 | 
|  1 | SIMPLE      | B     | ALL  | IXs_time_poly | NULL | NULL    | NULL | 7969897 | Range checked for each record (index map: 0x10) | 
+----+-------------+-------+------+---------------+------+---------+------+---------+-------------------------------------------------+
2 rows in set (0.00 sec)

请参阅 Jeremy Cole 的分析,了解与 between 子句相比此方法的性能优势的详细信息。

如果您有任何问题,请告诉我。

谢谢,

-蘸

于 2009-02-19T20:01:46.190 回答
-1

像这样的东西?

SELECT A.id, B.id 
FROM A
JOIN B ON A.id =  B.id 
WHERE A.event_time BETWEEN B.start_time AND B.end_time
于 2009-02-17T15:45:25.127 回答