[MonetDB-users] mal index
Hello,
I'm working in a research problem and we need to create a graph database. We think that MonetDB can be useful to represent this graph since the use of bats may make the graph traversal efficient. Nevertheless, SQL is limited for the type of operations that we need to do, and that is why we have decided to resort to MAL.
Our database is like this:
- Nodes: a) node ident b) name - Edges: a) edge ident b) head node ident c) tail node ident
One of the operations is to find the node with maximum out degree and, after that, to do a BFS using this node as the source.
I have stored all the information in bats:
batNode1=[oid,node ident] batNode2=[oid,name] batEdge=[oid, edge ident] batEdgeHead=[oid, head node ident] batEdgeTail=[oid,tail node ident]
For getting the node with the maximum out degree, I access batEdgeHead and store the number of occurrences of every node id in a batAux.
batAux=[node ident, times]
After that I only select the node id with the largest number of occurrences.
Now, we are ready to do the BFS. In every iteration, I have to save all the tail nodes for exploring them in the next generation. This is the pseudocode explanation:
Put the node id to NodesToVisit While there are NodesToVisit currentNode=NodesToVisit; edgeToVisit=get edges idents from batEdgeHead from currentNode ident While there are edgesToVisit currentEdge=edgesToVisit nodeFinal=get tail node ident from batEdgeTail from currentEdge ident If notExist nodeFinal in NodesToVisit put nodeFinal in NodesToVisit endIf endWhile endWhile
The main problem happens when I perform a select from batEdgeHead from the ident node. batEdgeHead might become very large and accessing it might be very expensive in terms of time. Is there any kind of indexing? I tried with crackers and AVL index but, if I am not wrong, this is only useful if I had to do the same selection more than once. The number of the nodes is 325.000 and the number of edges 925.000. At the end of this e-mail you will find the code.
May any one help in improving the performance of this code?
Best regards,
Miquel Àngel Àguila
Bat equivalence: batEdge, batNode1 --> b1:= bat.new(:oid,:lng); batNode2 --> b2:= bat.new(:oid,:str); batEdgeHead --> rh:= bat.new(:oid,:lng); batEdgeTail --> rt:= bat.new(:oid,:lng); batType --> b4:= bat.new(:oid, int) (Type: 1. nodeType1, 2. nodeType2 , 3. edgeType1, 4. edgeType2, 5. edgeType3)
Loaded the bats, here is the code:
Maxium out degree:----------------------------------------------------- edart:=algebra.select(b4,3); nodOut:=algebra.semijoin(rh,edart); res:=bat.new(:lng,:int); valor:=0; barrier (mloop16:lng ,h16:oid ,tl16:lng ) := bat.newIterator(nodOut); bite1:=algebra.exist(res,tl16); barrier ifpart:= bite1; valor:=algebra.find(res, tl16); valor:=calc.+(valor,1); res:=bat.replace(res,tl16,valor); exit ifpart; barrier elsepart:= calc.!=(bite1,true); bat.insert(res,tl16,1); exit elsepart; redo (mloop16:lng ,h16:oid ,tl16:lng ) := bat.hasMoreElements(nodOut); exit mloop16:lng ;
maxOutDegree:=aggr.max(res); node:=algebra.select(res,maxOutDegree); io.print(node); nodart:=algebra.select(b4,1); nodart2:=algebra.semijoin(b1,nodart); ident2:=algebra.join(nodart2,node); name2:=algebra.semijoin(b3,ident2); secondtime:=alarm.time(); #Traversals------------------------------------------------------------ node2:=algebra.semijoin(b1,name2); aux:=0:lng; idoid:=0@0; barrier (mloop17:lng ,h17:oid ,tl17:lng) := bat.newIterator(node2); aux:=tl17; idoid:=h17; exit mloop17:lng ; nod:=bat.new(:lng,:lng); dif:=bat.new(:lng,:lng); vis:=bat.new(:lng,:lng); ar:=bat.new(:oid,:oid); tr:=bat.new(:oid,:oid); bat.insert(nod,aux,aux); dif:=algebra.difference(nod,vis); outer6:= aggr.count(dif); rhtaux:=bat.new(:oid,:int); rhaux:=bat.new(:oid,:lng); rtaux:=bat.new(:oid,:lng); rhtaux:=algebra.select(b4,3); rtaux:=algebra.semijoin(rt,rhtaux); rhaux:=algebra.semijoin(rh,rhtaux); barrier outer:=true; barrier (mloop18:lng ,h18:lng ,tl18:lng ) := bat.newIterator(dif); # This is the problem, I need to do a lot of selects rhaux2:=algebra.select(rhaux,tl18); rtaux2:=algebra.semijoin(rtaux,rhaux2); barrier (mloop19:lng ,h19:oid,tl19:lng ) := bat.newIterator(rtaux2); bite1:=algebra.exist(nod,tl19); barrier ifpart:= bite1; bat.insert(tr,h19,h19); exit ifpart; barrier elsepart:= calc.!=(bite1,true); bat.insert(ar,h19,h19); bat.insert(nod,tl19,tl19); exit elsepart; redo (mloop19:lng ,h19:oid ,tl19:lng ) := bat.hasMoreElements(rtaux2); exit mloop19:lng ; bat.insert(vis,h18,tl18); redo (mloop18:lng ,h18:lng ,tl18:lng ) := bat.hasMoreElements(dif); exit mloop18:lng ; dif:=algebra.difference(nod,vis); outer6:= aggr.count(dif); outer:=calc.!=(outer6,0); redo outer:=calc.!=(outer6,0); exit outer;
Hi Miguel,
the solution to this problem would be to sort your edges on head node ident so you can have binary search (log(n)) when you select. Monet will automatically see that the bat is sorted and thus will use binary search. In addition you have to sort your nodes table on node ident to have binary search there too, and if you want you can make a copy of edges table to have a second order on tail for backtracking etc.
Don't forget that in monet you have to keep the heads aligned and you have to do that manually since you are in the MAL level. After ordering head node edge, you have to align the edge id and tail node id with the order imposed by the head node id.
good luck,
lefteris
2010/4/21 Miguel Ángel Águila maguila@ac.upc.edu:
Hello,
I'm working in a research problem and we need to create a graph database. We think that MonetDB can be useful to represent this graph since the use of bats may make the graph traversal efficient. Nevertheless, SQL is limited for the type of operations that we need to do, and that is why we have decided to resort to MAL.
Our database is like this:
- Nodes:
a) node ident b) name
- Edges:
a) edge ident b) head node ident c) tail node ident
One of the operations is to find the node with maximum out degree and, after that, to do a BFS using this node as the source.
I have stored all the information in bats:
batNode1=[oid,node ident] batNode2=[oid,name] batEdge=[oid, edge ident] batEdgeHead=[oid, head node ident] batEdgeTail=[oid,tail node ident]
For getting the node with the maximum out degree, I access batEdgeHead and store the number of occurrences of every node id in a batAux.
batAux=[node ident, times]
After that I only select the node id with the largest number of occurrences.
Now, we are ready to do the BFS. In every iteration, I have to save all the tail nodes for exploring them in the next generation. This is the pseudocode explanation:
Put the node id to NodesToVisit While there are NodesToVisit currentNode=NodesToVisit; edgeToVisit=get edges idents from batEdgeHead from currentNode ident While there are edgesToVisit currentEdge=edgesToVisit nodeFinal=get tail node ident from batEdgeTail from currentEdge ident If notExist nodeFinal in NodesToVisit put nodeFinal in NodesToVisit endIf endWhile endWhile
The main problem happens when I perform a select from batEdgeHead from the ident node. batEdgeHead might become very large and accessing it might be very expensive in terms of time. Is there any kind of indexing? I tried with crackers and AVL index but, if I am not wrong, this is only useful if I had to do the same selection more than once. The number of the nodes is 325.000 and the number of edges 925.000. At the end of this e-mail you will find the code.
May any one help in improving the performance of this code?
Best regards,
Miquel Àngel Àguila
Bat equivalence: batEdge, batNode1 --> b1:= bat.new(:oid,:lng); batNode2 --> b2:= bat.new(:oid,:str); batEdgeHead --> rh:= bat.new(:oid,:lng); batEdgeTail --> rt:= bat.new(:oid,:lng); batType --> b4:= bat.new(:oid, int) (Type: 1. nodeType1, 2. nodeType2 , 3. edgeType1, 4. edgeType2, 5. edgeType3)
Loaded the bats, here is the code:
Maxium out degree:----------------------------------------------------- edart:=algebra.select(b4,3); nodOut:=algebra.semijoin(rh,edart); res:=bat.new(:lng,:int); valor:=0; barrier (mloop16:lng ,h16:oid ,tl16:lng ) := bat.newIterator(nodOut); bite1:=algebra.exist(res,tl16); barrier ifpart:= bite1; valor:=algebra.find(res, tl16); valor:=calc.+(valor,1); res:=bat.replace(res,tl16,valor); exit ifpart; barrier elsepart:= calc.!=(bite1,true); bat.insert(res,tl16,1); exit elsepart; redo (mloop16:lng ,h16:oid ,tl16:lng ) := bat.hasMoreElements(nodOut); exit mloop16:lng ;
maxOutDegree:=aggr.max(res); node:=algebra.select(res,maxOutDegree); io.print(node); nodart:=algebra.select(b4,1); nodart2:=algebra.semijoin(b1,nodart); ident2:=algebra.join(nodart2,node); name2:=algebra.semijoin(b3,ident2); secondtime:=alarm.time(); #Traversals------------------------------------------------------------ node2:=algebra.semijoin(b1,name2); aux:=0:lng; idoid:=0@0; barrier (mloop17:lng ,h17:oid ,tl17:lng) := bat.newIterator(node2); aux:=tl17; idoid:=h17; exit mloop17:lng ; nod:=bat.new(:lng,:lng); dif:=bat.new(:lng,:lng); vis:=bat.new(:lng,:lng); ar:=bat.new(:oid,:oid); tr:=bat.new(:oid,:oid); bat.insert(nod,aux,aux); dif:=algebra.difference(nod,vis); outer6:= aggr.count(dif); rhtaux:=bat.new(:oid,:int); rhaux:=bat.new(:oid,:lng); rtaux:=bat.new(:oid,:lng); rhtaux:=algebra.select(b4,3); rtaux:=algebra.semijoin(rt,rhtaux); rhaux:=algebra.semijoin(rh,rhtaux); barrier outer:=true; barrier (mloop18:lng ,h18:lng ,tl18:lng ) := bat.newIterator(dif); # This is the problem, I need to do a lot of selects rhaux2:=algebra.select(rhaux,tl18); rtaux2:=algebra.semijoin(rtaux,rhaux2); barrier (mloop19:lng ,h19:oid,tl19:lng ) := bat.newIterator(rtaux2); bite1:=algebra.exist(nod,tl19); barrier ifpart:= bite1; bat.insert(tr,h19,h19); exit ifpart; barrier elsepart:= calc.!=(bite1,true); bat.insert(ar,h19,h19); bat.insert(nod,tl19,tl19); exit elsepart; redo (mloop19:lng ,h19:oid ,tl19:lng ) := bat.hasMoreElements(rtaux2); exit mloop19:lng ; bat.insert(vis,h18,tl18); redo (mloop18:lng ,h18:lng ,tl18:lng ) := bat.hasMoreElements(dif); exit mloop18:lng ; dif:=algebra.difference(nod,vis); outer6:= aggr.count(dif); outer:=calc.!=(outer6,0); redo outer:=calc.!=(outer6,0); exit outer;
MonetDB-users mailing list MonetDB-users@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/monetdb-users
Hello Miquel,
first of all, I agree with you that MonetDB is the proper choice for your problem ;-)
As a first quick answer --- I hope to come back with more once I find more time to dive into it --- here is one general hint of using MonetDB the most efficient way (in addition to the comments that Lefteris already gave).
Your below code for calculating the "Maxium out degree" basically re-implements in MAL (and interpreted language) what does already exist as ((hopefully higly optimized) MAL primitive that is implemented in C (and hence compiled code: a histogram.
In other words, to get the most out of MonetDB, one should not see and use MAL as an imperative programming language to iteratively process data items one at a time, but rather as a declarative query language to process large amount of data in one go (you may also think of it as something like "SIMD").
Here's a small example regarding your "Maxium out degree" code.
My attached code compares the execution time (and results) of your "Maxium out degree" and a simple "aggr.histrgram()" call in MAL that does exactly the same. (I use our "microbenchmark" module to conveniently create a synthetic input BAT of 1000000 tuples with 10 different randomly distributed edgeHead values.)
Here are the result for two runs of each approach:
time for 'Maxium out degree': 1053135 usec [ "result of 'Maxium out degree'" ] #-----------------# # h t # name # lng int # type #-----------------# [ 9, 99597 ] [ 7, 100023 ] [ 4, 99919 ] [ 2, 100936 ] [ 6, 99970 ] [ 8, 99796 ] [ 0, 100056 ] [ 1, 100046 ] [ 5, 99942 ] [ 3, 99715 ] time for 'aggr.histogram()': 9864 usec [ "result of 'aggr.histogram()'" ] #-----------------# # h t # name # lng int # type #-----------------# [ 9, 99597 ] [ 7, 100023 ] [ 4, 99919 ] [ 2, 100936 ] [ 6, 99970 ] [ 8, 99796 ] [ 0, 100056 ] [ 1, 100046 ] [ 5, 99942 ] [ 3, 99715 ] time for 'Maxium out degree': 1035288 usec [ "result of 'Maxium out degree'" ] #-----------------# # h t # name # lng int # type #-----------------# [ 9, 99597 ] [ 7, 100023 ] [ 4, 99919 ] [ 2, 100936 ] [ 6, 99970 ] [ 8, 99796 ] [ 0, 100056 ] [ 1, 100046 ] [ 5, 99942 ] [ 3, 99715 ] time for 'aggr.histogram()': 9978 usec [ "result of 'aggr.histogram()'" ] #-----------------# # h t # name # lng int # type #-----------------# [ 9, 99597 ] [ 7, 100023 ] [ 4, 99919 ] [ 2, 100936 ] [ 6, 99970 ] [ 8, 99796 ] [ 0, 100056 ] [ 1, 100046 ] [ 5, 99942 ] [ 3, 99715 ]
Note in particular that aggr.histogram() is more than 100(!) times faster than your code (for the reasons mentioned above).
I expect that similar changes to the remainder of your code will have likewise positive effects. Please feel free to play yourself --- I know that getting familiar with "thinking the MonetDB way" takes some time. As mentioned above, I hope to come back with more sometime later (within the next days).
Regards, Stefan
On Wed, Apr 21, 2010 at 09:15:52AM +0200, Miguel Ángel Águila Lorente wrote:
Hello,
I'm working in a research problem and we need to create a graph database. We think that MonetDB can be useful to represent this graph since the use of bats may make the graph traversal efficient. Nevertheless, SQL is limited for the type of operations that we need to do, and that is why we have decided to resort to MAL.
Our database is like this:
- Nodes: a) node ident b) name
- Edges: a) edge ident b) head node ident c) tail node ident
One of the operations is to find the node with maximum out degree and, after that, to do a BFS using this node as the source.
I have stored all the information in bats:
batNode1=[oid,node ident] batNode2=[oid,name] batEdge=[oid, edge ident] batEdgeHead=[oid, head node ident] batEdgeTail=[oid,tail node ident]
For getting the node with the maximum out degree, I access batEdgeHead and store the number of occurrences of every node id in a batAux.
batAux=[node ident, times]
After that I only select the node id with the largest number of occurrences.
Now, we are ready to do the BFS. In every iteration, I have to save all the tail nodes for exploring them in the next generation. This is the pseudocode explanation:
Put the node id to NodesToVisit While there are NodesToVisit currentNode=NodesToVisit; edgeToVisit=get edges idents from batEdgeHead fromcurrentNode ident While there are edgesToVisit currentEdge=edgesToVisit nodeFinal=get tail node ident from batEdgeTail from currentEdge ident If notExist nodeFinal in NodesToVisit put nodeFinal in NodesToVisit endIf endWhile endWhile
The main problem happens when I perform a select from batEdgeHead from the ident node. batEdgeHead might become very large and accessing it might be very expensive in terms of time. Is there any kind of indexing? I tried with crackers and AVL index but, if I am not wrong, this is only useful if I had to do the same selection more than once. The number of the nodes is 325.000 and the number of edges 925.000. At the end of this e-mail you will find the code.
May any one help in improving the performance of this code?
Best regards,
Miquel Àngel Àguila
Bat equivalence: batEdge, batNode1 --> b1:= bat.new(:oid,:lng); batNode2 --> b2:= bat.new(:oid,:str); batEdgeHead --> rh:= bat.new(:oid,:lng); batEdgeTail --> rt:= bat.new(:oid,:lng); batType --> b4:= bat.new(:oid, int) (Type: 1. nodeType1, 2. nodeType2 , 3. edgeType1, 4. edgeType2, 5. edgeType3)
Loaded the bats, here is the code:
Maxium out degree:----------------------------------------------------- edart:=algebra.select(b4,3); nodOut:=algebra.semijoin(rh,edart); res:=bat.new(:lng,:int); valor:=0; barrier (mloop16:lng ,h16:oid ,tl16:lng ) := bat.newIterator(nodOut); bite1:=algebra.exist(res,tl16); barrier ifpart:= bite1; valor:=algebra.find(res, tl16); valor:=calc.+(valor,1); res:=bat.replace(res,tl16,valor); exit ifpart; barrier elsepart:= calc.!=(bite1,true); bat.insert(res,tl16,1); exit elsepart; redo (mloop16:lng ,h16:oid ,tl16:lng ) := bat.hasMoreElements(nodOut); exit mloop16:lng ;
maxOutDegree:=aggr.max(res); node:=algebra.select(res,maxOutDegree); io.print(node); nodart:=algebra.select(b4,1); nodart2:=algebra.semijoin(b1,nodart); ident2:=algebra.join(nodart2,node); name2:=algebra.semijoin(b3,ident2); secondtime:=alarm.time(); #Traversals------------------------------------------------------------ node2:=algebra.semijoin(b1,name2); aux:=0:lng; idoid:=0@0; barrier (mloop17:lng ,h17:oid ,tl17:lng) := bat.newIterator(node2); aux:=tl17; idoid:=h17; exit mloop17:lng ; nod:=bat.new(:lng,:lng); dif:=bat.new(:lng,:lng); vis:=bat.new(:lng,:lng); ar:=bat.new(:oid,:oid); tr:=bat.new(:oid,:oid); bat.insert(nod,aux,aux); dif:=algebra.difference(nod,vis); outer6:= aggr.count(dif); rhtaux:=bat.new(:oid,:int); rhaux:=bat.new(:oid,:lng); rtaux:=bat.new(:oid,:lng); rhtaux:=algebra.select(b4,3); rtaux:=algebra.semijoin(rt,rhtaux); rhaux:=algebra.semijoin(rh,rhtaux); barrier outer:=true; barrier (mloop18:lng ,h18:lng ,tl18:lng ) := bat.newIterator(dif); # This is the problem, I need to do a lot of selects rhaux2:=algebra.select(rhaux,tl18); rtaux2:=algebra.semijoin(rtaux,rhaux2); barrier (mloop19:lng ,h19:oid,tl19:lng ) := bat.newIterator(rtaux2); bite1:=algebra.exist(nod,tl19); barrier ifpart:= bite1; bat.insert(tr,h19,h19); exit ifpart; barrier elsepart:= calc.!=(bite1,true); bat.insert(ar,h19,h19); bat.insert(nod,tl19,tl19); exit elsepart; redo (mloop19:lng ,h19:oid ,tl19:lng ) := bat.hasMoreElements(rtaux2); exit mloop19:lng ; bat.insert(vis,h18,tl18); redo (mloop18:lng ,h18:lng ,tl18:lng ) := bat.hasMoreElements(dif); exit mloop18:lng ; dif:=algebra.difference(nod,vis); outer6:= aggr.count(dif); outer:=calc.!=(outer6,0); redo outer:=calc.!=(outer6,0); exit outer;
MonetDB-users mailing list MonetDB-users@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/monetdb-users
Hello Stefan, ..
Your below code for calculating the "Maxium out degree" basically re-implements in MAL (and interpreted language) what does already exist a=
s
((hopefully higly optimized) MAL primitive that is implemented in C (and hence compiled code: a histogram.
In other words, to get the most out of MonetDB, one should not see and us=
e
MAL as an imperative programming language to iteratively process data ite=
ms
one at a time, but rather as a declarative query language to process larg=
e
amount of data in one go (you may also think of it as something like "SIMD").
..
Well, it looks like you just got me interested in diving deeper into MAL :)
However, to get more out of this than mere researching curiosity, I am viewing it in context of a long-term deployment strategy, where I have to care about standardization. So I have a couple of questions:
I get the impression that MAL is currently a unique tool in the global software landscape, so once an application is developed using MAL, migrating to another database engine would be rather expensive. Has it been considered to get MAL more standardized? Or are there other, standardized languages serving a related purpose, for which it is considered to evolve MAL in the direction of that language of a (sub|super)-set thereof?
A possibly easier approach to dive into MAL and still be able to build upon it in a standardized environment would be to stay with SQL for interfacing, and to use MAL for developing application-specific optimizations on the intermediate MAL code. What is the best way to get started on that? Do you have any design documents specific to the SQL-MAL compilation layer?
Many thanks.
Best regards,
Isidor
Isidor,
On Thu, Apr 22, 2010 at 10:45:40AM +0200, Isidor Zeuner wrote:
Hello Stefan, ..
Your below code for calculating the "Maxium out degree" basically re-implements in MAL (and interpreted language) what does already exist a=
s
((hopefully higly optimized) MAL primitive that is implemented in C (and hence compiled code: a histogram.
In other words, to get the most out of MonetDB, one should not see and us=
e
MAL as an imperative programming language to iteratively process data ite=
ms
one at a time, but rather as a declarative query language to process larg=
e
amount of data in one go (you may also think of it as something like "SIMD").
..
Well, it looks like you just got me interested in diving deeper into MAL :)
If you do so, please be aware that MAL is intended and designed as a MonetDB-specific interface between the MonetDB columnar kernel (back-end) and the any front-end that provides the user- and application-level logical data model and respective query language, such as, e.g., our SQL front-end provides the (n-ary) relational data model with SQL as its query language.
However, to get more out of this than mere researching curiosity, I am viewing it in context of a long-term deployment strategy, where I have to care about standardization. So I have a couple of questions:
I get the impression that MAL is currently a unique tool in the global software landscape, so once an application is developed using MAL, migrating to another database engine would be rather expensive. Has it been considered to get MAL more standardized? Or are there other, standardized languages serving a related purpose, for which it is considered to evolve MAL in the direction of that language of a (sub|super)-set thereof?
As mentioned above, MAL is MonetDB specific. Although it might look like (are even be close to) a computational complete programming language, its main purpose is a textual representation of MonetDB's closed binary (read: two-column) relational algebra.
I would recommend to base your applications on the logical data model they use and the respective query language, e.g., relational tables and SQL. These are standadized and hence (supposed to be) portable. (Or XML & XQuery as opposed to MIL in the case of MonetDB4/XQuery.)
Using MAL directly is only to be considered if the available highler-level data models, query languages and API's do not provide sufficient functionality for your applications. Even in that case, you might want to consider choosing or designing a suitable logcal data model and query language and translate that to MAL in a generic fashion as we already do with SQL (& XML/XQuery).
A possibly easier approach to dive into MAL and still be able to build upon it in a standardized environment would be to stay with SQL for interfacing, and to use MAL for developing application-specific optimizations on the intermediate MAL code. What is the best way to get started on that? Do you have any design documents specific to the SQL-MAL compilation layer?
Indeed that is also an option to be considered. Some "design" documentation of translating n-ary relational schemas and related algebra to MonetDB's binary (two-column) tables (BAT) and their (closed) algebra are to be found in many of the scientific publications related to MonetDB, in particular these two might be a good starting point: http://repository.cwi.nl/search/fullrecord.php?publnr=11183 http://repository.cwi.nl/search/fullrecord.php?publnr=14832 More publications are listed here: http://monetdb.cwi.nl/Development/Research/Articles/index.html
More information is on the MonetDB web site.
For most details the code is the documentation outside our heads ;-)
Stefan
Many thanks.
Best regards,
Isidor
MonetDB-users mailing list MonetDB-users@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/monetdb-users
participants (4)
-
Isidor Zeuner -
Lefteris -
Miguel Ángel Águila Lorente -
Stefan Manegold