search

mehemmedv / DB_Imp_Seminar

Seminar: Techniques for implementing main memory database systems
https://db.in.tum.de/teaching/ws1718/seminarHauptspeicherdbs/?lang=en
4 stars 2 forks source link

Store edges sorted #14

Closed jboettcher closed 7 years ago

jboettcher commented 7 years ago

I just came up with a new implementation idea. ...If you don't want to start writing yet :p

At the moment you are just appending the edges. By sorting the edges by node-ids, we could increase the probability of cache-hits: imagine a node with edges to n5, n6, ..., n3000. If the edges are sorted, we would access n6 after n5. Since they are neighbors the probablity is very high that n6 is already in our cache ;)

Would be interesting to see how big this effect is. You could call std::sort on all edge-lists after building the graph. Just add a method sortByEdgesByNodeId to the graphs and run the benchmarks once with/and once without sorting the edges.

jboettcher commented 7 years ago

That would also be cool in your paper: since sorting is an interesting design decision ;)

mehemmedv commented 7 years ago

Resolved.