ETS中select和match查询效率测试

ErlangETS性能实验 by 达达 at 2012-03-17

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条数据)。

可以从实验结果看出:

  1. 有用到key的select和match一样是n(1)复杂度,查询时间几乎不受数据条数影响
  2. 按key进行select和match的时间消耗,大约是lookup查询的4倍左右
  3. 没有用到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).