Sort-merge join instead of nested-loop join

sshikov / cumulusrdf

Automatically exported from code.google.com/p/cumulusrdf

0 stars 0 forks source link

Sort-merge join instead of nested-loop join #26

Open GoogleCodeExporter opened 9 years ago

GoogleCodeExporter commented 9 years ago

Currently, we use the standard nested-loop join (with index support) from 
Sesame. 

However, stored SPO-style indexes in a sorted fashion is fairly easy in 
Cassandra (and already implemented to some extend). Thus, a sorted-merge could 
be implemented without that much work. See, e.g., [1].

- Andreas

[1] http://www.informatik.uni-freiburg.de/~mschmidt/docs/sp2b_exp.pdf

Original issue reported on code.google.com by andreas.josef.wagner on 29 Jan 2014 at 9:14

GoogleCodeExporter commented 9 years ago

"Fast Intersection of Sorted Lists Using SSE Instructions" instead of linear 
processing, see [1]

- Andreas

[1] 
http://highlyscalable.wordpress.com/2012/06/05/fast-intersection-sorted-lists-ss
e/

Original comment by andreas.josef.wagner on 30 Mar 2014 at 1:17

GoogleCodeExporter commented 9 years ago

See also: Sort vs. Hash revisited: fast join implementation on modern 
multi-core CPUs.

Original comment by andreas.josef.wagner on 30 Mar 2014 at 1:32