<html><head><meta http-equiv="Content-Type" content="text/html; charset=utf-8"></head><body><div>The ordered_set optimization <i>traversal with partially bound key</i></div><div>does only trigger on the MatchHead tuple and not the MatchConditions list.</div><div><br></div><div>So both the select calls will have the same result, but the second one will traverse the entire search tree.</div><div><br></div><div><br></div><div>With a partially bound key like {Name, '_'} the total "lookup time" is roughly the same as doing one lookup per matching key.</div><div><br></div><div>With a partially bound key like {Name, '_', Other} the the total lookup time may be longer</div><div>as it have to visit all keys matching {Name, '_', '_'} and check if Other also matches.</div><div><br></div><div>/Sverker</div><div><br></div><div>On tis, 2019-12-10 at 20:26 +0100, Roberto Ostinelli wrote:</div><blockquote type="cite"><div dir="ltr">Related, is there any difference in terms of performance in this case (<font face="monospace">ordered_set</font>) between:<br><br><font face="monospace">ets:select(groups, [{<br> {{Name, '$2'}, '_', '_', '_'},<br> [],<br> ['$2']<br>}])</font><br><br>and<br><br><font face="monospace">ets:select(groups, [{<br> {{$1, '$2'}, '_', '_', '_'},<br> [{'=:=', '$1', Name}],<br> ['$2']<br>}])</font><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, Dec 10, 2019 at 12:34 PM Roberto Ostinelli <<a href="mailto:ostinelli@gmail.com">ostinelli@gmail.com</a>> wrote:<br></div><blockquote type="cite"><div dir="ltr">Sverker,<div>This looks very nice. I was considering using composite keys but I didn't know that partial lookups would work.</div><div><br></div><div>Seems definitely cleaner, and if I understand correctly the lookup time will be the same as with a single key, with the added benefit of the delete functionalities (please correct me if I'm wrong).</div><div><br></div><div>Thank you so much,</div><div>r.</div><div><br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Mon, Dec 9, 2019 at 8:15 PM Sverker Eriksson <<a href="mailto:sverker@erlang.org" target="_blank">sverker@erlang.org</a>> wrote:<br></div><blockquote type="cite"><div><div>Here is a variant of your second solution. But instead insert each element-group pair as a <b>key</b></div><div>and use ordered_set which has an optimization for <i>traversal with partially bound key</i>.</div><div><br></div><div><br></div><div>ets:new(elements,[ordered_set,named_table]).</div><div>ets:new(groups,[ordered_set,named_table]).</div><div><br></div><div>% Insert element</div><div>[ets:insert(elements, {{Element,G}}) || G <- Groups],</div><div>[ets:insert(groups, {{G,Element}}) || G <- Groups],</div><div><br></div><div><br></div><div>% Lookup groups from element</div><div>Groups = ets:select(elements, [{{{Element,'$1'}}, [], ['$1']}]),</div><div><br></div><div>% Lookup elements from group</div><div>Elements = ets:select(groups, [{{{Group,'$1'}}, [], ['$1']}]),</div><div><br></div><div>% Delete element</div><div>Groups = ets:select(elements, [{{{Element,'$1'}}, [], ['$1']}]),</div><div>ets:match_delete(elements, {{Element, '_'}}),</div><div>[ets:delete(groups, {G,Element}) || G <- Groups],</div><div><br></div><div><br></div><div>All select and match traversals use a partially bound key and will</div><div>only search the part of the ordered_set (tree) that may contain such keys.</div><div><br></div><div><br></div><div>/Sverker</div><div><br></div><div>On lör, 2019-12-07 at 18:54 +0100, Roberto Ostinelli wrote:</div><blockquote type="cite"><div dir="ltr">All,<div>I'm doing a conceptual exercise to evaluate the usage of ETS with secondary indices.</div><div><br></div><div>The exercise is really simple:</div><div><ol><li>There are elements which can belong to groups, in a m-to-n relationship (every element can belong to one or more groups).</li><li>Elements and groups can be created/deleted at will.</li><li>We need to find the groups an element belongs to.</li><li>We need to find the elements included into a group.</li><li>We need to not keep an element if it does not belong to a group, nor a group if it does not have elements in it (this is to avoid memory leaks since groups / elements get added / removed).</li></ol></div><div>All of these operations should be optimized as much as possible.</div><div><br></div><div><br></div><div>A. One possibility is to have 2 ETS tables of type <font face="monospace">set</font>, that contain the following terms:</div><div><br></div><div>1. table <font face="monospace">elements</font> with tuple format <font face="monospace">{Element, Groups}</font></div><div>2. table <font face="monospace">groups</font> with tuple format <font face="monospace">{Group, Elements}</font></div><div><br></div><div>Groups and Elements would be maps (so that finding an element of the map does not require traversing an array).</div><div><br></div><div>Adding an <font face="monospace">Element</font> to a <font face="monospace">Group</font> would mean:</div><div><ul><li>An insert in the table <font face="monospace">elements</font> where the <font face="monospace">Group</font> gets added to the <font face="monospace">Groups</font> map (bonus of using a map: no duplicates can be created).</li><li>An insert in the table <font face="monospace">groups</font> where the <font face="monospace">Element</font> gets added to the <font face="monospace">Elements</font> map.</li></ul><div>Retrieving the groups an element belongs to is simple as getting the <font face="monospace">Element</font> in the table <font face="monospace">elements</font>, the groups will be keys of the <font face="monospace">Groups</font> map.</div></div><div><div><div>Retrieving the elements a group contains to is simple as getting the <font face="monospace">Group</font> in the table <font face="monospace">groups</font>, the elements will be keys of the <font face="monospace">Elements</font> map.</div></div><div><br></div><div>Deleting is far from being optimized though. For instance, deleting an <font face="monospace">Element</font> means:</div><div><ul><li>Getting the <font face="monospace">Groups</font> it belongs to with a lookup in the table <font face="monospace">elements</font>.</li><li>For every <font face="monospace">Group</font> in the <font face="monospace">Groups</font> map, remove the <font face="monospace">Element</font> from the <font face="monospace">Elements</font> map.</li></ul><div>It becomes something like this:</div></div><div><font face="monospace"><br></font></div><div><font face="monospace">case ets:lookup(elements, Element) of<br> [{Element, Groups}] -></font></div><div><font face="monospace"> ets:delete(elements, Element),<br> lists:foreach(fun({Group}) -><br> case ets:lookup(groups, Group) of<br> [{Group, Elements}] -><br> case maps:remove(Element, Elements) of<br> Elements1 when map_size(Elements1) == 0 -><br> ets:delete(groups, Group);<br> Elements1 -><br> ets:insert(groups, {Group, Elements1})<br> end;<br> _ -><br> ok<br> end<br> end, maps:keys(Groups))<br> _ -><br> ok<br>end.</font><br></div><div><br></div><div>Ouch. Same goes for groups. And this is to delete <b>one</b> element, imagine if bigger operations need to be made.</div><div><br></div><div><br></div><div>B. Another possibility would be to have 2 ETS tables of type <font face="monospace">bag</font>, that contain the following terms:</div><div><br></div><div><div>1. table <font face="monospace">elements</font> with tuple format <font face="monospace">{Element, Group}</font></div><div>2. table <font face="monospace">groups</font> with tuple format <font face="monospace">{Group, Element}</font></div></div><div><div><br></div><div>Adding an <font face="monospace">Element</font> to a <font face="monospace">Group</font> means:</div><div><ul><li>An insert in the table <font face="monospace">elements</font> of the tuple <font face="monospace">{Element, Group}</font>.</li><li>An insert in the table <font face="monospace">groups</font> of the tuple <font face="monospace">{Group, Element}</font>.</li></ul></div></div></div><div><div>Retrieving the groups an element belongs to requires an <font face="monospace">ets:match_object/2</font> or similar such as:</div><div><span style="font-family:monospace">ets:match_object(elements, {Element, _ = '_'}).</span><br></div><div><br></div><div><div>Retrieving the elements a group belongs to requires an <font face="monospace">ets:match_object/2</font> or similar such as:</div><div><span style="font-family:monospace">ets:match_object(groups, {Group, _ = '_'}).</span></div></div><div><br></div><div>So retrieving requires the traversing of a table, but it should be relatively quick, given that the match is done on the index itself.</div><div><br></div><div><div>Deleting is not particularly optimized though, because it requires the traversing of a table with elements that are not indexed. For instance, deleting an <font face="monospace">Element</font> would look something like:</div></div></div><div><font face="monospace">ets:match_delete(elements, {Element, _ = '_'}). %% fast, indexed<br></font></div><div><font face="monospace">ets:match_delete(groups, {_ = '_', Element}). %% not fast, table is being traversed.</font><br></div><div><br></div><div><br></div><div>What would <i>you</i> do? Any takers are welcome ^^_</div><div><br></div><div>Cheers,</div><div>r.</div><div><br></div><div><br></div></div>
</blockquote></div><br></blockquote></div>
<br></blockquote></div>
</blockquote></body></html>