[MonetDB-users] Benefits of sorted columns
Hi, I know that when a table is sorted on a column, value look-ups on that column will use a binary search instead of a linear search. Is there a similar benefit for joins? E.g. if I have 2 tables that contain a sorted column C and I do an equality join on this column (or a self-join using 2 aliases of the same table), I would expect a traditional DBMS to do a merge-join. Cheers, Viktor
Hi, shortest answer is: yes. Longer answer is: In case the BATs that enter the actual join operator are (still) sorted and the kernels know that they are sorted (i.e., the respective property is set), then the join operator will use a merge-join algorithm. Whether these prerequisites hold depends on a number of factors, among others whether the base BATs are indeed know to be sorted, and which operators they go through before hitting the join, i.e., the generated MAL plan, which is generated without knowing that the base BATs are sorted. Stefan On Mon, Dec 19, 2011 at 09:56:54AM +0100, Viktor Rosenfeld wrote:
Hi,
I know that when a table is sorted on a column, value look-ups on that column will use a binary search instead of a linear search. Is there a similar benefit for joins? E.g. if I have 2 tables that contain a sorted column C and I do an equality join on this column (or a self-join using 2 aliases of the same table), I would expect a traditional DBMS to do a merge-join.
Cheers, Viktor
------------------------------------------------------------------------------ Learn Windows Azure Live! Tuesday, Dec 13, 2011 Microsoft is holding a special Learn Windows Azure training event for developers. It will provide a great way to learn Windows Azure and what it provides. You can attend the event by watching it streamed LIVE online. Learn more at http://p.sf.net/sfu/ms-windowsazure _______________________________________________ MonetDB-users mailing list MonetDB-users@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/monetdb-users
-- | Stefan.Manegold @ CWI.nl | DB Architectures (INS1) | | http://CWI.nl/~manegold/ | Science Park 123 (L321) | | Tel.: +31 (0)20 592-4212 | 1098 XG Amsterdam (NL) |
Hi, thanks, good to know. Cheers, Viktor Stefan Manegold wrote:
Hi,
shortest answer is: yes.
Longer answer is: In case the BATs that enter the actual join operator are (still) sorted and the kernels know that they are sorted (i.e., the respective property is set), then the join operator will use a merge-join algorithm.
Whether these prerequisites hold depends on a number of factors, among others whether the base BATs are indeed know to be sorted, and which operators they go through before hitting the join, i.e., the generated MAL plan, which is generated without knowing that the base BATs are sorted.
Stefan
On Mon, Dec 19, 2011 at 09:56:54AM +0100, Viktor Rosenfeld wrote:
Hi,
I know that when a table is sorted on a column, value look-ups on that column will use a binary search instead of a linear search. Is there a similar benefit for joins? E.g. if I have 2 tables that contain a sorted column C and I do an equality join on this column (or a self-join using 2 aliases of the same table), I would expect a traditional DBMS to do a merge-join.
Cheers, Viktor
------------------------------------------------------------------------------ Learn Windows Azure Live! Tuesday, Dec 13, 2011 Microsoft is holding a special Learn Windows Azure training event for developers. It will provide a great way to learn Windows Azure and what it provides. You can attend the event by watching it streamed LIVE online. Learn more at http://p.sf.net/sfu/ms-windowsazure _______________________________________________ MonetDB-users mailing list MonetDB-users@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/monetdb-users
-- | Stefan.Manegold @ CWI.nl | DB Architectures (INS1) | | http://CWI.nl/~manegold/ | Science Park 123 (L321) | | Tel.: +31 (0)20 592-4212 | 1098 XG Amsterdam (NL) |
------------------------------------------------------------------------------ Learn Windows Azure Live! Tuesday, Dec 13, 2011 Microsoft is holding a special Learn Windows Azure training event for developers. It will provide a great way to learn Windows Azure and what it provides. You can attend the event by watching it streamed LIVE online. Learn more at http://p.sf.net/sfu/ms-windowsazure _______________________________________________ MonetDB-users mailing list MonetDB-users@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/monetdb-users
participants (2)
-
Stefan Manegold -
Viktor Rosenfeld