更好的方法或数据库来存储 5000 万个范围数据和快速搜索操作

Better approach or database to store 50 million of range data and fast search operation

提问人:Pacemaker 753 提问时间:11/17/2023 最后编辑:Pacemaker 753 更新时间:11/19/2023 访问量:89

问:

问题陈述:我们将收到一个数字(11 位数字)的请求,并且必须在数据库中有效地查找并根据其适合的范围返回一行(上次更新)。 此外,我已经使用过 mysql 并使用适当的索引进行了负载测试,但是这需要更多时间。

当前数据库结构:

使用 MySQL

目前,我们有一个表,它有 2 列,即 low_range 和 high_range,用于存储数据范围,还有另外 2 列用于存储相应的数据,即 is_active(值可以是 0 和 1)和代码(int 值,它是另一个表的 id,即 code_mapping)。

表1名称:range_mapping

数据库架构:

create table range_mapping (
`id` int(11) unsigned NOT NULL AUTO_INCREMENT,
`low_range` decimal(11,0) NOT NULL,
`high_range` decimal(11,0) NOT NULL,
`is_active` tinyint(1) NOT NULL DEFAULT 1,
`code` int(8) DEFAULT NULL,
PRIMARY KEY (`id`),
KEY `idx_comp_is_active_low_high_range` (`is_active`, `low_range`, `high_range`)
) ENGINE=InnoDB AUTO_INCREMENT=26891234 DEFAULT CHARSET=utf8
Table 2 name: code_mapping

数据库架构:

create table code_mapping (
`id` int(11) unsigned NOT NULL AUTO_INCREMENT,
`name` varchar(100) NOT NULL,
PRIMARY KEY (`id`),
UNIQUE KEY `nameIdx` (`name`)
) ENGINE=InnoDB AUTO_INCREMENT=4410 DEFAULT CHARSET=utf8

要优化的查询:我需要重新设计或优化查询,以便高效、快速地执行。

select a.low_range, a.high_range, b.name from range_mapping AS a 
LEFT JOIN code_mapping AS b ON a.code = b.id 
WHERE a.is_active = 1 and 12345678912 BETWEEN a.low_range AND a.high_range 
ORDER BY a.id DESC 
limit 1;

解释查询:

explain select a.low_range, a.high_range, b.name 
from range_mapping AS a force index(idx_comp_is_active_low_high_range) 
LEFT JOIN code_mapping AS b ON a.code = b.id 
WHERE a.is_active = 1 and 12345678912 BETWEEN a.low_range AND a.high_range 
ORDER BY a.id DESC limit 1; 

输出:

id: 1
select_type: SIMPLE
table: a
type: range
possible_keys: idx_comp_is_active_low_high_range
key: idx_comp_is_active_low_high_range
key_len: 11
ref: NULL
rows: 227190
Extra: Using index condition; Using filesort

***************************
id: 1
select_type: SIMPLE
table: b
type: eq_ref
possible_keys: PRIMARY
key: PRIMARY
key_len: 4
ref: testbackup.a.code
rows: 1
Extra: Using where

解释查询的分析:

'-> Limit: 1 row(s)  (cost=65515 rows=0.104) (actual time=529..529 rows=1 loops=1)\n    -> Nested loop left join  (cost=65515 rows=0.104) (actual time=529..529 rows=1 loops=1)\n -> Filter: ((a.is_active = 1) and (535387481 between a.low_range and a.high_range))  (cost=0.21 rows=0.104) (actual time=529..529 rows=1 loops=1)\n            -> Index scan on a using PRIMARY (reverse)  (cost=0.21 rows=2) (actual time=1.25..490 rows=531614 loops=1)\n        -> Filter: (a.code = b.id)  (cost=0.961 rows=1) (actual time=0.0347..0.0347 rows=1 loops=1)\n -> Single-row index lookup on b using PRIMARY (id=a.code)  (cost=0.961 rows=1) (actual time=0.0331..0.0331 rows=1 loops=1)\n'

要求:12345678912

表中可能的行:

low_range: 12345678901 high_range: 12345678913 
low_range: 12345678910 high_range: 12345678912
low_range: 12345678902 high_range: 12345678920

问题:

哪个数据库可用于存储数百万个范围数据,并具有高效的查找功能。如果可能的话,任何更好的 mysql 方法。

我已经使用过mysql并使用适当的索引进行了负载测试,但是这需要更多时间。 期望查找应该是快速高效的~500毫秒。

数据库 PostgreSQL 查询优化 日期范围

评论

1赞 Simon Goater 11/17/2023
来自 mytable 的 SELECT *,其中 num 介于 A 和 B 之间;键入 query 可能必须扫描整个表。为什么不发布你正在使用的 SQL,也许有人可以就如何改进它提供很好的建议。
0赞 Frank Heikens 11/17/2023
500 毫秒是永恒的,在我看来有些不对劲。请检查/分享您的查询计划。而且 5000 万条记录并不多,任何数据库都可以处理这一点。
0赞 P.Salmon 11/17/2023
低范围和高范围是表中的列吗?请以文本形式发布表定义、示例数据、所需结果和查询。
0赞 Simon Goater 11/17/2023
您拥有的有关数据的更多信息都可能真正有所帮助。示例范围很短。这是典型的吗?
1赞 O. Jones 11/18/2023
这个问题看起来像 stackoverflow.com/questions/77433106/...但它实际上要求使用DBMS的另一个品牌/模型。

答:

3赞 Zegarek 11/17/2023 #1

PostgreSQL 内置了范围类型,这些类型提供了 GiST 和 SP-GiST 索引支持的 @> 包含运算符。问题是,索引查找的性能是由样本的分布驱动的。如果我有目的地将所有填充样本移出目标范围,我可以在 0.06 毫秒内从 50M 行中挑选出目标:demo1(这些演示是我所做的测试的缩小示例)

查询计划
仅索引 在 public.test 上使用test_r_idx扫描(成本 = 0.42..26414.98 行 = 457289 宽度 = 22)(实际时间 = 0.043..0.047 行 = 3 循环 = 1)
输出:r
索引 Cond:(test.r @> '12345678912'::bigint)
堆提取:0
规划时间:0.234 ms
执行时间:0.060 ms

如果我完全随机生成它们,情况是一样的,但将范围宽度缩小到 100(示例中的范围宽度是 12、2、18)——在 50M 的范围内,如此高的数字不太可能重叠,选择性高,索引扫描速度快。如果我将范围宽度限制提高到 100k,在目标范围内产生更多命中,它仍然只需要 0.16 毫秒,如果我进一步达到 10M 并有更多的匹配,则仍然需要 4.6 毫秒。演示2

查询计划
仅索引 在 public.test 上使用 test_r_idx 进行扫描(成本 = 0.42..648.35 行 = 11196 宽度 = 22)(实际时间 = 0.102..4.182 行 = 12722 循环 = 1)
输出:r
索引 Cond:(test.r @> '12345678912'::bigint)
堆提取:0
规划时间:0.056 ms
执行时间:4.584 ms

如果我生成 50M 完全随机的范围,它们中的大多数都会跨得很宽,不太可能重叠并抓住目标,这使得它全部跳到 7 秒,因为它经历了近一半的堆,因为索引在这样的情况下并没有真正的帮助

select setseed(0.1);
create table test (r int8range);
insert into test 
select int8range(least(a,b),greatest(a,b),'[]') from (
select (random()*2e10)::int8 a,(random()*2e10)::int8 b
from generate_series(1,(random()*15e6)::int))_;

insert into test values (int8range(12345678901,12345678913,'[]'));
insert into test 
select int8range(least(a,b),greatest(a,b),'[]') from (
select (random()*2e10)::int8 a,(random()*2e10)::int8 b
from generate_series(1,(random()*15e6)::int))_;

insert into test values (int8range(12345678910,12345678912,'[]'));
insert into test 
select int8range(least(a,b),greatest(a,b),'[]') from (
select (random()*2e10)::int8 a,(random()*2e10)::int8 b
from generate_series(1,(random()*15e6)::int))_;

insert into test values (int8range(12345678902 ,12345678920,'[]'));
insert into test 
select int8range(least(a,b),greatest(a,b),'[]') from (
select (random()*2e10)::int8 a,(random()*2e10)::int8 b
from generate_series(1,(select 5e7-count(*) from test)))_;

create index on test using gist(r);

vacuum analyze test;


explain analyze verbose
select * from test where r@>12345678912;
查询计划
在 public.test 上进行顺序扫描(成本=0.00..943473.30 rows=23519755 width=22)(实际时间=18.990..6629.042 rows=23618706 loops=1)
输出:r
过滤器:(test.r @> '12345678912'::bigint)
按筛选器删除的行数:26381294
计划时间:0.069 ms
JIT:
功能:2
选项:内联 true、优化 true、表达式 true、变形 true
定时:生成 0.355 ms,内联 3.575 ms,优化 11.550 ms,发射 3.765 ms,总计 19.244 ms
执行时间:7608.159 ms

评论

0赞 Pacemaker 753 11/17/2023
谢谢@Zegarek。让我尝试使用具有范围数据类型的 PostgreSQL 并确认。
0赞 deroby 11/20/2023
您确实遗漏了查询的一部分,但我认为这可以通过使用过滤索引来处理(阅读:使用is_activeWHERE is_active = 1)
0赞 Zegarek 11/20/2023
@deroby 此答案早于 OP 添加其架构的编辑。但是,是的,您可以将其设置为部分索引,并且可以将该列设置为适当的而不是冒名顶替者。booleansmallinttinyint
0赞 Rick James 11/19/2023 #2

https://mysql.rjweb.org/doc.php/ipranges 中的代码显示了如何改进 IP 地址的查找。它使MySQL的性能与Postgres一样快(基本上是为简单查找获取1行)。你有;这应该同样有效。DECIMAL(11,0)

它确实涉及将结构更改为每行只有一个数字。如果存在间隙,则通过具有 [大概] is_active=false 的额外虚拟行来处理它们。

评论

0赞 Zegarek 11/20/2023
关于间隙:每个 PostgreSQL 类型都有一个对应项,该对应项仍然适合单行的单个字段,并支持来自索引支持的运算符类的相同包含运算符。rangemultirange
0赞 Rick James 11/20/2023
看看我的代码。这取决于实现速度。没有MySQL可以优化非重叠范围搜索,至少它本身不是。ORDER BY...LIMIT 1INDEX