ETS中select和match查询效率测试
Erlang内置了一个key-value内存数据库叫ets,除了支持通常key-value存储支持的按key查询数据以外,还支持两种更灵活的查询方式,分别是match和select。
灵活是要付出性能代价的,文档上有明确说明match和select是要遍历表中所有数据的,查询算法就不再是按key读取的n(1)复杂度了。但是如果在match和select的条件中明确指定了key的时候,ets的内部实现是否会对这样的查询优化成n(1)复杂度呢?
我做了一个对比实验,插入一批数据,然后分别按key和按普通字段match和select查询数据,下面是实验结果的shell输出:
1> ets_labs:match_vs_select(10000, 10). select by key : {87,ok} match by key : {74,ok} select all : {435180,ok} match all : {422559,ok} lookup : {17,ok} true 2> ets_labs:match_vs_select(10000, 10). select by key : {85,ok} match by key : {106,ok} select all : {431907,ok} match all : {429098,ok} lookup : {18,ok} true 3> ets_labs:match_vs_select(100000, 10). select by key : {76,ok} match by key : {73,ok} select all : {10770564,ok} match all : {10831494,ok} lookup : {22,ok} true
实验输出的数值是查询时间,以微秒为单位。实验分别试了两次1w玩家,每个玩家10条数据的查询(共10w条数据),以及10w玩家,每个玩家10条数据的查询(共100w条数据)。
可以从实验结果看出:
- 有用到key的select和match一样是n(1)复杂度,查询时间几乎不受数据条数影响
- 按key进行select和match的时间消耗,大约是lookup查询的4倍左右
- 没有用到key的select和match查询,耗时严重受数据条数影响
下面是实验代码:
-module(ets_labs). -export([match_vs_select/2, loop/2]). -record(player_item, {id, xd, player_id, item_id, grid}). %% %% Match和Select性能对比 %% match_vs_select (PlayerNum, RowsPerPlayer) -> Tab = ets:new(player_item, [{keypos, #player_item.id}]), init_test_data(PlayerNum, RowsPerPlayer, Tab, 1), %% 主键select R1 = timer:tc(?MODULE, loop, [100, fun() -> ets:select(Tab, [{#player_item { id = PlayerNum * RowsPerPlayer div 2, _='_' },[],['$_']}]) end]), io:format("select by key : ~p~n", [R1]), %% 主键match R2 = timer:tc(?MODULE, loop, [100, fun() -> ets:match_object(Tab, #player_item { id = PlayerNum * RowsPerPlayer div 2, _='_' }) end]), io:format("match by key : ~p~n", [R2]), %% 非主键select R3 = timer:tc(?MODULE, loop, [100, fun() -> ets:select(Tab, [{#player_item { xd = PlayerNum * RowsPerPlayer div 2, _='_' },[],['$_']}]) end]), io:format("select all : ~p~n", [R3]), %% 非主键match R4 = timer:tc(?MODULE, loop, [100, fun() -> ets:match_object(Tab, #player_item { xd = PlayerNum * RowsPerPlayer div 2, _='_' }) end]), io:format("match all : ~p~n", [R4]), %% 主键lookup R5 = timer:tc(?MODULE, loop, [100, fun() -> ets:lookup(Tab, PlayerNum * RowsPerPlayer div 2) end]), io:format("lookup : ~p~n", [R5]), ets:delete(Tab). loop (0, _) -> ok; loop (Times, Fun) -> Fun(), loop(Times - 1, Fun). %% %% 初始化测试数据 %% init_test_data (0, _, _, _) -> ok; init_test_data (PlayerNum, RowsPerPlayer, Tab, Id) -> Id2 = init_player_data(RowsPerPlayer, Tab, Id, PlayerNum), init_test_data(PlayerNum - 1, RowsPerPlayer, Tab, Id2). init_player_data (0, _, Id, _) -> Id; init_player_data (Rows, Tab, Id, PlayerId) -> true = ets:insert(Tab, #player_item { id = Id, xd = Id, player_id = PlayerId, item_id = Rows, grid = Rows }), init_player_data(Rows - 1, Tab, Id + 1, PlayerId).