Hi All. I updated the recently discussed RTL example to demonstrate the performance gain that can be achieved by using the RTL transaction mechanism. The original query, that involves a self-join of the ~20,000 row table on a complex condition, currently takes ~79 sec. on my setup (1.5 Ghz, MinGW, g++ -O2). Then a record is removed from the table, which invalidates all the indexes built by that point. The transaction commit repairs indexes, and the query is re-run. Update, commit, and re-run together take just 1 sec. Please take the example and the updated library (again, a few performance issues were fixed) at the usual location: http://www.boost-consulting.com/vault/index.php?&direction=0&order=&director y=RTL Please note that the directory structure of the library has been "boostified" so please ajust you include path accordingly (although I haven't yet put "boost/rtl" into #include statements, so it should go into the include path for now). Regards, Arkadiy
"Arkadiy Vertleyb" <vertleyb@hotmail.com> wrote
Please take the example and the updated library (again, a few performance issues were fixed) at the usual location:
http://www.boost-consulting.com/vault/index.php?&direction=0&order=&director
y=RTL
Please note that the updated version of the RTL _is required_ to compile the example. Also, here is a more convenient link: http://tinyurl.com/8lbmg Regards, Arkadiy
Hi Arkadiy, I've got the RML example for the new query and it is in the miliseconds range. There is one optimization that you would need to add so that we can compare RML vs RTL: before running the query you can create a 2-dimensional map with the city locations so that when you check the distances for each city you don't use compute the distance for all points but you limit the calculation to a range of cities that are below a cutoff distance (where the cutoff distance is greater than 5 km) Regards Jose On 10/17/05, Arkadiy Vertleyb <vertleyb@hotmail.com> wrote:
Hi All.
I updated the recently discussed RTL example to demonstrate the performance gain that can be achieved by using the RTL transaction mechanism.
The original query, that involves a self-join of the ~20,000 row table on a complex condition, currently takes ~79 sec. on my setup (1.5 Ghz, MinGW, g++ -O2). Then a record is removed from the table, which invalidates all the indexes built by that point. The transaction commit repairs indexes, and the query is re-run.
Update, commit, and re-run together take just 1 sec.
Please take the example and the updated library (again, a few performance issues were fixed) at the usual location:
http://www.boost-consulting.com/vault/index.php?&direction=0&order=&director y=RTL
Please note that the directory structure of the library has been "boostified" so please ajust you include path accordingly (although I haven't yet put "boost/rtl" into #include statements, so it should go into the include path for now).
Regards, Arkadiy
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
"Jose" <jmalv04@gmail.com> wrote
I've got the RML example for the new query and it is in the miliseconds range.
Would it be possible for you to also run the RTL example on your setup? It will not be in milliseconds range, but we would have a more accurate starting point to compare. Also, is it possible to see what the RML solution looks like? Regards, Arkadiy
Sorry, I forgot to mention that your query was 6 seconds on my x86_64 3Gb box I didn't want to compare any results yet because geographical queries really need special auxiliary coding, e.g. like building a cities worldmap before actually running the queries. So once I have your updated code I will run both on identical setting. Calum's is the code author so I am sure he'll post that but I propose the solutions are coded separately so that the best ideas come up and then after the benchmark the code is distributed for further analysis, otherwise we have some bias in the benchmark. I just wanted to bring up the worldmap optimization so that the relational benchmarks can be compared on equal terms I will email you directly some of my own optimization ideas as I have not yet looked in detail at calum's code On 10/17/05, Arkadiy Vertleyb <vertleyb@hotmail.com> wrote:
"Jose" <jmalv04@gmail.com> wrote
I've got the RML example for the new query and it is in the miliseconds range.
Would it be possible for you to also run the RTL example on your setup? It will not be in milliseconds range, but we would have a more accurate starting point to compare.
Also, is it possible to see what the RML solution looks like?
Regards, Arkadiy
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
"Jose" <jmalv04@gmail.com> wrote
Sorry, I forgot to mention that your query was 6 seconds on my x86_64 3Gb box
Is this a latest one -- I expect it to take a little longer now... Also I am curious how long it took to re-run the query after the update.
I didn't want to compare any results yet because geographical queries really need special auxiliary coding, e.g. like building a cities worldmap before actually running the queries.
Right, so I am afraid we may fall into the trap of comparing the cleverness of hand-coded solutions rather than the libraries' capabilities.
So once I have your updated code I will run both on identical setting.
Calum's is the code author so I am sure he'll post that but I propose the solutions are coded separately so that the best ideas come up and then after the benchmark the code is distributed for further analysis, otherwise we have some bias in the benchmark. I just wanted to bring up the worldmap optimization so that the relational benchmarks can be compared on equal terms
I will email you directly some of my own optimization ideas as I have not yet looked in detail at calum's code
The reason I wanted to take a look at it is that I want to see if it looks more like a library-based solution or a hand-coded solution. Also, I want to try more relational-based optimizations before starting to apply other tricks. But, again, could you see how long the re-run (after update) takes? Thanks, Arkadiy
Below are my results with g++ -O3 The query should group by city given that in the aslatlong.txt file all AS in a city have the same (lat, long). This would make the output more useful (right now the query outputs all the AS from amsterdam first which is redundant info given that all AS in the amsterdam area have the same lat/long) ================================================== loading table... 21598 records loaded 3317 AMSTERDAM ? 991 [ ... ] The query took 11 sec 0 records will be added to the index 1982 records will be removed from the index done with updates 5390 AMSTERDAM ? 990 [ ... ] Update and query re-run took 0 sec ==================================================== More comments below On 10/17/05, Arkadiy Vertleyb <vertleyb@hotmail.com> wrote:
"Jose" <jmalv04@gmail.com> wrote
Sorry, I forgot to mention that your query was 6 seconds on my x86_64 3Gb box
Is this a latest one -- I expect it to take a little longer now... Also I am curious how long it took to re-run the query after the update.
Above results are the latest. Files and RTL library just d/l from vault
I didn't want to compare any results yet because geographical queries really
need special auxiliary coding, e.g. like building a cities worldmap before actually running the queries.
Right, so I am afraid we may fall into the trap of comparing the cleverness of hand-coded solutions rather than the libraries' capabilities.
I don't think this is exactly right. Geographic queries should have some additional logic that may well be part of the library. I don't think either library has this type of logic now so both might have a hand coded solution for the time being
"Jose" <jmalv04@gmail.com> wrote
Below are my results with g++ -O3
The query should group by city given that in the aslatlong.txt file all AS in a city have the same (lat, long). This would make the output more useful (right now the query outputs all the AS from amsterdam first which is redundant info given that all AS in the amsterdam area have the same lat/long)
================================================== loading table... 21598 records loaded 3317 AMSTERDAM ? 991 [ ... ] The query took 11 sec 0 records will be added to the index 1982 records will be removed from the index done with updates 5390 AMSTERDAM ? 990 [ ... ] Update and query re-run took 0 sec ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Would it be possible for you to change the code a little, so that it outputs milliseconds here?
Right, so I am afraid we may fall into the trap of comparing the cleverness of hand-coded solutions rather than the libraries' capabilities.
I don't think this is exactly right. Geographic queries should have some additional logic that may well be part of the library.
I would rather it belong to a separate library, highly compatible with the relational one.
I don't think either library has this type of logic now so both might have a hand coded solution for the time being
Right, but the relative impact of these hand-coded solutions maybe too high, so we may not really be comparing the libraries. At this point the RTL solution is coded completely as a relational expression (although rather complex), a single relational view. I also might be able to further optimize it inside the relational boundaries. Please note also that I had to somewhat decrease the performance in exchange to fast re-runs after the update, so, depending on the context (update and re-run pattern, etc.), RTL solution might even now be much more efficient than it looks. Regards, Arkadiy
On 10/17/05, Arkadiy Vertleyb <vertleyb@hotmail.com> wrote:
Update and query re-run took 0 sec ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Would it be possible for you to change the code a little, so that it outputs milliseconds here?
loading table... 21598 records loaded [...] The query took 11 sec 0 records will be added to the index 1982 records will be removed from the index done with updates [...] Update and query re-run took 320 milisec Regards Jose
I've got the RML example for the new query and it is in the miliseconds range.
Would it be possible for you to also run the RTL example on your setup? It will not be in milliseconds range, but we would have a more accurate starting point to compare.
Also, is it possible to see what the RML solution looks like?
Here is the RML solution. I have annotated the source more heavily than normal to explain what is going on. It runs in 16-30 ms on my setup. It gains speed by using Cartesian coordinates rather than polar coordinates, and also outputs to a std::stringstream during the timing loop because otherwise writing to the terminal completely swamps the results. Nevertheless I don't consider any of this as cheating - this is how RML would be used in a real application. It's not designed for complex numerical computation - leave that to C++ I say. The geographic test is actually quite an interesting case for RML because it shows off how one would create tables of user C++ classes (as opposed to just rows). It is also extremely fast to add or delete cities from this data structure. I would feel extremely confident in an insert/run/update/rerun test. Calum
"Calum Grant" <calum@visula.org> wrote
Is it also possible to see the result?
Attached, Calum
I don't believe this is the required result, is it?
The problem with this data is that it contains a lot of duplicates. If I cluster the cities into 5103 clusters, I get 47ms. On the other hand if I don't cluster them, then I get 4.1s. The expensive part is building the index of indexing on distances. The results are rather odd - the 500 locations I get have 991 neighbours. Regards, Calum
Given the problems with the datasets, I would change the initial query to one that clusters the cities as you do and show only the city + (lat,long) and number of neighbours in the query results. Some cities will show with the right string and others not given that the data doesn't map all coordinates to the same city name. RTL result is also 991 neighbours. The problem is that the Amsterdam area has the 991 neighbours (and most likely all AS with the same identical coordinates) so it is better to group the results by city i.e.: Amsterdam (lata, lonb) 991 city B (latc,lond) xyz city C (late, lonf) abc With these results we can compare both queries and although the string names from the cities my differ the numerical values should not. On 10/18/05, Calum Grant <calum@visula.org> wrote:
"Calum Grant" <calum@visula.org> wrote
Is it also possible to see the result?
Attached, Calum
I don't believe this is the required result, is it?
The problem with this data is that it contains a lot of duplicates. If I cluster the cities into 5103 clusters, I get 47ms. On the other hand if I don't cluster them, then I get 4.1s. The expensive part is building the index of indexing on distances. The results are rather odd - the 500 locations I get have 991 neighbours.
Regards, Calum
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
"Jose" <jmalv04@gmail.com> wrote
Given the problems with the datasets, I would change the initial query to one that clusters the cities as you do and show only the city + (lat,long) and number of neighbours in the query results. Some cities will show with the right string and others not given that the data doesn't map all coordinates to the same city name.
RTL result is also 991 neighbours. The problem is that the Amsterdam area has the 991 neighbours (and most likely all AS with the same identical coordinates) so it is better to group the results by city i.e.:
Amsterdam (lata, lonb) 991 city B (latc,lond) xyz city C (late, lonf) abc
With these results we can compare both queries and although the string names from the cities my differ the numerical values should not.
Well, this may make more sence (depending on what you want to find out). However, this is a much simpler query -- just sort on the sity, groupby, and then re-sort on the counter -- I am sure both libraries will be efficient enough. Also I don't think one can specify (lat, lon) for a city. I would finish with the original example before we proceed to anything else. Regards, Arkadiy
On 10/18/05, Arkadiy Vertleyb <vertleyb@hotmail.com> wrote:
"Jose" <jmalv04@gmail.com> wrote
With these results we can compare both queries and although the string names from the cities my differ the numerical values should not.
Well, this may make more sence (depending on what you want to find out). However, this is a much simpler query -- just sort on the sity, groupby, and then re-sort on the counter -- I am sure both libraries will be efficient enough.
I realized the modified query might give more meaningful output but I didn't realize that it was much simpler query Also I don't think one can specify (lat, lon) for a city. what i was suggesting is consider each (lat, long) as a city but the actual string name for the city might not be meaningful b/c the data doesn't map always the same (lat,lon) to the same string I would finish with the original example before we proceed to anything else. ok
"Calum Grant" <calum@visula.org> wrote
The problem with this data is that it contains a lot of duplicates. If I cluster the cities into 5103 clusters, I get 47ms. On the other hand if I don't cluster them, then I get 4.1s. The expensive part is building the index of indexing on distances. The results are rather odd - the 500 locations I get have 991 neighbours.
This sounds like a correct result -- can I see the first 50 items? Regards, Arkadiy
The problem with this data is that it contains a lot of duplicates. If I cluster the cities into 5103 clusters, I get 47ms. On the other hand if I don't cluster them, then I get 4.1s. The expensive part is building the index of indexing on distances. The results are rather odd - the 500 locations I get have 991 neighbours.
This sounds like a correct result -- can I see the first 50 items?
The output is at the bottom. I've managed to get my times down a bit by reimplementing the solution in a much more straightforward way. I can insert all 21421 items, calculate the number of neighbours, and display the top 500 in 235ms. Then I can remove 1982 items, and redisplay the results, in 47 milliseconds. This of course makes me suspicious that I'm doing something wrong......... The solution I have is not terribly elegant from RML's point of view, since as I said before RML is designed for logical queries rather than numerical computation. It was not a terribly interesting problem because it needed just a single table with two indexes. Regards, Calum =============================================== 17882 ALTEC-AS 991 16918 BILIM-AS 991 16917 IXEUROPE-FR-ASN 991 8734 WISH-NOKNOK 991 16915 DHMS-NET 991 17700 IOMART-AS 991 17494 RAMSATCOM 991 17670 GETIT 991 17493 AS-IKSYS 991 16913 UNSPECIFIED 991 16912 ASN-MPLS 991 17491 ABB 991 17490 UNSPECIFIED 991 17698 MEGAPROVIDER-AS 991 18013 CITCO-AS 991 16911 YACAST-AS 991 17803 KHODA 991 .... 17278 AS-PETERSTAR 991 6399 Novaxess 991 17277 UNSPECIFIED 991 17868 RTK-Primorye 991 17276 UNSPECIFIED 991 17275 AS-SYNCHROLINE 991 11605 UNSPECIFIED 991 18167 RIPE 991 17274 AS-SUNET2000 991 11599 Swisscom-NA 991 11598 HPPOLAND-AS 991 17273 STARTVAS 991 There are 21421 locations 17219 ASN-CEDECRA 990 17587 UNSPECIFIED 990 17778 KIWWI-HU-AS 990 17777 Actimage 990 17433 EBS-Europe 990 ... 17280 LiberCom-AS 990 18207 RIPE 990 18206 RIPE 990 17279 UNIFFM-NET 990 17493 AS-IKSYS 990 There are 19439 locations Insert time = 234 milliseconds Delete and redisplay = 47 milliseconds
"Calum Grant" <calum@visula.org> wrote
This sounds like a correct result -- can I see the first 50 items?
The output is at the bottom.
This result is not sorted by (counter, city) as requested, which makes it impossible to compare it with mine.
I've managed to get my times down a bit by reimplementing the solution in a much more straightforward way. I can insert all 21421 items, calculate the number of neighbours, and display the top 500 in 235ms. Then I can remove 1982 items,
from where?
and redisplay the results, in 47 milliseconds. This of course makes me suspicious that I'm doing something wrong.........
This numbers are very impressive, but they don't tell much unless Jose runs it on his setup (after the result is properly sorted).
The solution I have is not terribly elegant from RML's point of view, since as I said before RML is designed for logical queries rather than numerical computation. It was not a terribly interesting problem because it needed just a single table with two indexes.
Hmm, I managed to program it in RTL as a single relational view on the original table, without doing _anything_ by hand. The correctness of this view is preseved by the library when the data is changed. In your case _you_ remove 1982 items. In my case _the library_ removes 1982 items. I think your solution is rather by-hand than RML-based. Can you create a single RML query on the original table that solves the problem? Can you claim that using RML added a lot to your solution? Is it faster/more elegant/readable/etc. than just using STL directly? Regards, Arkadiy
Hi, Find attached the results for RTL. Calum, I need your output to provide the a 3rd column with the AS name (like RTL output does) so that the query results are identical. There seems to be a mismatch in the number of records: RTL shows 21598 records loaded and RML 19439. Also, the update queries need to be the same. The update of the query consists of deleting the first record in the result: AS 3317 The number of records deleted in the update for RTL (1982) is irrelevant. The two benchmark times that matter is the query time and the update time. For RTL: 11 sec and 330 ms Regards Jose Regards On 10/18/05, Arkadiy Vertleyb <vertleyb@hotmail.com> wrote:
"Calum Grant" <calum@visula.org> wrote
This sounds like a correct result -- can I see the first 50 items?
The output is at the bottom.
This result is not sorted by (counter, city) as requested, which makes it impossible to compare it with mine.
I've managed to get my times down a bit by reimplementing the solution in a much more straightforward way. I can insert all 21421 items, calculate the number of neighbours, and display the top 500 in 235ms. Then I can remove 1982 items,
from where?
and redisplay the results, in 47 milliseconds. This of course makes me suspicious that I'm doing something wrong.........
This numbers are very impressive, but they don't tell much unless Jose runs it on his setup (after the result is properly sorted).
The solution I have is not terribly elegant from RML's point of view, since as I said before RML is designed for logical queries rather than numerical computation. It was not a terribly interesting problem because it needed just a single table with two indexes.
Hmm, I managed to program it in RTL as a single relational view on the original table, without doing _anything_ by hand. The correctness of this view is preseved by the library when the data is changed. In your case _you_ remove 1982 items. In my case _the library_ removes 1982 items. I think your solution is rather by-hand than RML-based.
Can you create a single RML query on the original table that solves the problem? Can you claim that using RML added a lot to your solution? Is it faster/more elegant/readable/etc. than just using STL directly?
Regards, Arkadiy
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
The solution I have is not terribly elegant from RML's point of view, since as I said before RML is designed for logical queries rather than numerical computation. It was not a terribly interesting problem because it needed just a single table with two indexes.
Hmm, I managed to program it in RTL as a single relational view on the original table, without doing _anything_ by hand. The correctness of this view is preseved by the library when the data is changed. In your case _you_ remove 1982 items. In my case _the library_ removes 1982 items. I think your solution is rather by-hand than RML-based.
Can you create a single RML query on the original table that solves the problem? Can you claim that using RML added a lot to your solution? Is it faster/more elegant/readable/etc. than just using STL directly?
You make a very fair point. This problem does not lend itself very well to RML's queries. RML's queries are much simpler, and therefore need to be glued together with C++. But even so, even these simple queries make it easier to access data in the table, and the test was exercising the library. But my line-count was 243 lines, yours was 214, so it's not such a huge difference. I frankly have no idea how I would implement that problem in SQL, but then this was a problem you chose to be very difficult to solve using a SQL notation. But that does not of course mean that SQL is a bad approach for other things. Even so, it is extremely interesting to see how far one can take RTL's queries. And it looks like considerable fun! I would like to test a database-style application. I feel RML's notation and design would be much better suited to that type of problem. Regards, Calum
"Calum Grant" <calum@visula.org> wrote
I frankly have no idea how I would implement that problem in SQL, but then this was a problem you chose to be very difficult to solve using a SQL notation.
I am not an SQL expert, but should be something like this (if I remember correctly): SELECT number, name, city, COUNT(*) AS cnt FROM mytable a, mytable b WHERE [the long condition based on coordinates] GROUP BY a.number ORDER BY cnt DESC; Then you hope that the optimizer figures out how to not compare every possible pair ;-) This exact statement I modeled in RTL, but RTL also specifies HOW to do things in addition to WHAT to do, so I was able to do a smartrer (range-based) query. I am thrilled with your performance results, though (although I consider them the results of a by-hand solution). Did you completely avoid calculating the distance? If so, I think any such solution would provide only approximate result (although it might happen to be a pretty good approximation). Regards, Arkadiy
RML an order of magnitude faster RTL: 11 sec and 330 ms RML: 340 ms and 50 ms RML output attached On 10/21/05, Arkadiy Vertleyb <vertleyb@hotmail.com> wrote:
"Calum Grant" <calum@visula.org> wrote
I frankly have no idea how I would implement that problem in SQL, but then this was a problem you chose to be very difficult to solve using a SQL notation.
I am not an SQL expert, but should be something like this (if I remember correctly):
SELECT number, name, city, COUNT(*) AS cnt FROM mytable a, mytable b WHERE [the long condition based on coordinates] GROUP BY a.number ORDER BY cnt DESC;
Then you hope that the optimizer figures out how to not compare every possible pair ;-)
This exact statement I modeled in RTL, but RTL also specifies HOW to do things in addition to WHAT to do, so I was able to do a smartrer (range-based) query.
I am thrilled with your performance results, though (although I consider them the results of a by-hand solution). Did you completely avoid calculating the distance? If so, I think any such solution would provide only approximate result (although it might happen to be a pretty good approximation).
Regards, Arkadiy
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
"Jose" <jmalv04@gmail.com> wrote
RML an order of magnitude faster
Calum, is it possible to see the latest code of your example?
Here it is. It would definitely look better if - I didn't have to hack to get around not being able to sort on multiple columns - I had user-defined predicates I think your code wins in terms of neatness however. Calum
"Calum Grant" <calum@visula.org> wrote
Calum, is it possible to see the latest code of your example?
Here it is.
I see... A couple of questions: 1) You modify counter all the time -- does RML allow to do this with the fields on which the table is sorted? 2) When you say : select(m_locations, m_locations.x>=loc.x-m_cutoff && m_locations.x<=loc.x+m_cutoff && m_locations.y>=loc.y-m_cutoff && m_locations.y<=loc.y+m_cutoff && m_locations.z>=loc.z-m_cutoff && m_locations.z<=loc.z+m_cutoff) Do you use any kind of special index for this? In any case this seems to prove that RML does a good job when searching on multiple indexes -- you do quite a bit of that. Also, inserts/updates are probably very efficient. But, as I said before, the overall efficiency of this example is based on the fact that this is a very smart, custom, hand-coded solution (see how you maintain the counter). No library would be able to beat its performance using a higher-level abstraction (If RTL had a count() operator in addition to generic groupby(), we could be much smarter in maintaining it during updates). OTOH, RTL doesn't seem to have much visible overhead. What's happenning during the request is that for every record a range query is executed on the index sorted by lattitude to cut off most of the records (about 90%). This range query is then walked and the proper selection condition (based on distance) is applied, and the counter is calculated. This all gets indexed on the (counter, city, name). Everything except indexing is done lazily. The major performance overhead is introduced by indexing of the selection (about 2,000,000 records), but this also provides a major gain with updates, since selection is (at least at the moment) the most expensive part of this. Still, I can't do as good as you can, since I don't have a notion of "counter", so groupby has to be run over and over again (even if on a faster argument). I should be able to find some major inefficiencies in selection, and improve the performance. I don't think I'll be able to beat your result though (by the reasons I described above). But again, I don't believe this all proves RML is faster than RTL, since the coding approaches were so different. I don't even know if it's possible to compare the libraries at this point, since they have their strong points in different areas. RTL's strong point in the ability to build and run SQL-like views. This I tried to show in my example. RML seems to be very efficient at maintaining and using multiple indexes, but, despite its more SQL-like interface, can mimique only very simple SQL queries. Regards, Arkadiy
Arkadiy Vertleyb wrote
"Calum Grant" <calum@visula.org> wrote
Calum, is it possible to see the latest code of your example?
Here it is.
I see...
A couple of questions:
1) You modify counter all the time -- does RML allow to do this with the fields on which the table is sorted?
Yes - by using table.update_row() or table.update_where(), the indexes are automatically updated. That's the whole point of RML - it uses/updates indexes implicitly. If you decide to index a column, and no code needs to change.
2) When you say :
select(m_locations, m_locations.x>=loc.x-m_cutoff && m_locations.x<=loc.x+m_cutoff && m_locations.y>=loc.y-m_cutoff && m_locations.y<=loc.y+m_cutoff && m_locations.z>=loc.z-m_cutoff && m_locations.z<=loc.z+m_cutoff)
Do you use any kind of special index for this?
Yes - the TMP query analyser sees that m_locations.z is an indexed column, and uses that index. If on the other hand x or y were indexed, that index would be used in preference to z. If I had implemented user-defined queries, I could write select(m_locations, m_locations.x>=loc.x-m_cutoff && m_locations.x<=loc.x+m_cutoff && m_locations.y>=loc.y-m_cutoff && m_locations.y<=loc.y+m_cutoff && m_locations.z>=loc.z-m_cutoff && m_locations.z<=loc.z+m_cutoff && query(test_distance(loc)) ) where test_distance would be some user-defined functor to check the distance more precisely. Even in this scenario, the TMP query analyser would use m_locations.z as an index. It's not magic, it just uses the first index is sees.
In any case this seems to prove that RML does a good job when searching on multiple indexes -- you do quite a bit of that. Also, inserts/updates are probably very efficient.
Insertion carries the same overheads as Boost.MultiIndex. Update is possibly more efficient, since nodes can be relocated in a single index - without needing to destroy/create a new indexed item. This is one of the inefficiencies of std::set or std::map - if you change the key you need to allocate a new node.
But, as I said before, the overall efficiency of this example is based on the fact that this is a very smart, custom, hand-coded solution (see how you maintain the counter). No library would be able to beat its performance using a higher-level abstraction (If RTL had a count() operator in addition to generic groupby(), we could be much smarter in maintaining it during updates).
The RML solution is actually slower because of the incremental updates to the "neighbours" column. Had they been calculated in one go, then the query would I suspect run faster. I would really like to be able to write for_each( limit( sort( (descending(col<2, 0>()), col<0, Location::name>() ), group_by( col<0, Location::id_column>(), select( (locations, locations), col<1, Location::x_column>() <= col<0, Location::x_column>() + m_cutoff && col<1, Location::x_column>() >= col<0, Location::x_column>() - m_cutoff && col<1, Location::y_column>() <= col<0, Location::y_column>() + m_cutoff && col<1, Location::y_column>() >= col<0, Location::y_column>() - m_cutoff && col<1, Location::z_column>() <= col<0, Location::z_column>() + m_cutoff && col<1, Location::z_column>() >= col<0, Location::z_column>() - m_cutoff && query(test_distance()) ), ), ), 50), display_result() ); In order to achieve this, I would need to implement sorting using multiple columns, group_by(), and query(). And this query would I suspect run as fast as the original. (Though it would not support dynamic update). So the fact that I needed to split my query up is nothing to do with the fundamental design of RML. It was because some of the functions were not implemented. I will work towards getting these extra functions implemented, but I have a long todo-list and it won't happen immediately.
But again, I don't believe this all proves RML is faster than RTL, since the coding approaches were so different. I don't even know if it's possible to compare the libraries at this point, since they have their strong points in different areas. RTL's strong point in the ability to build and run SQL-like views. This I tried to show in my example. RML seems to be very efficient at maintaining and using multiple indexes, but, despite its more SQL-like interface, can mimique only very simple SQL queries.
You're only saying that because I haven't got around to implementing group_by and multi-column sorts. These are less commonly used features that were not a priority to implement. But they would not be difficult. When RML can implement the entire query in one statement, we can re-run the tests if you'd like. Indexed views can give performance improvements in real SQL databases - but they can also reduce performance. I believe the same phenomenon might be occurring in your in-memory relational models. I believe that you would gain a huge performance increase by using Boost.MultiIndex as your underlying data structure (as opposed to std::vector), and indexing the columns you require. That is I believe the fundamental architectural difference between RML and RTL. By storing the columns pre-indexed, you don't have any extra overhead. Regards, Calum
"Calum Grant" <calum@visula.org> wrote
I would really like to be able to write
for_each( limit( sort( (descending(col<2, 0>()), col<0, Location::name>() ), group_by( col<0, Location::id_column>(), select( (locations, locations), col<1, Location::x_column>() <= col<0, Location::x_column>() + m_cutoff && col<1, Location::x_column>() >= col<0, Location::x_column>() - m_cutoff && col<1, Location::y_column>() <= col<0, Location::y_column>() + m_cutoff && col<1, Location::y_column>() >= col<0, Location::y_column>() - m_cutoff && col<1, Location::z_column>() <= col<0, Location::z_column>() + m_cutoff && col<1, Location::z_column>() >= col<0, Location::z_column>() - m_cutoff && query(test_distance()) ), ), ), 50), display_result() );
In order to achieve this, I would need to implement sorting using multiple columns, group_by(), and query(). And this query would I suspect run as fast as the original. (Though it would not support dynamic update).
And, once you are done with this, you will have pretty much the same that RTL has right now, and even your interface will look the same. Except, as you mentioned, you won't have dynamic updates that RTL has. I wonder if your query will still be faster by then ;-) Regards, Arkadiy
"Arkadiy Vertleyb" <vertleyb@hotmail.com> wrote
And, once you are done with this, you will have pretty much the same that RTL has right now, and even your interface will look the same.
Except, as you mentioned, you won't have dynamic updates that RTL has.
And also pluggable table implementations. Regards, Arkadiy
Arkadiy Vertleyb wrote:
"Calum Grant" <calum@visula.org> wrote
I frankly have no idea how I would implement that problem in SQL, but then this was a problem you chose to be very difficult to solve using a SQL notation.
I am not an SQL expert, but should be something like this (if I remember correctly):
SELECT number, name, city, COUNT(*) AS cnt FROM mytable a, mytable b WHERE [the long condition based on coordinates] GROUP BY a.number ORDER BY cnt DESC;
Then you hope that the optimizer figures out how to not compare every possible pair ;-)
Needless to say, implementing a query analyser to do all that purely in TMP would be rather difficult! But I don't believe there are any hidden costs in RML - what you see is what you get.
This exact statement I modeled in RTL, but RTL also specifies HOW to do things in addition to WHAT to do, so I was able to do a smartrer (range-based) query.
Ah, but you can specify "how" using C++.
I am thrilled with your performance results, though (although I consider them the results of a by-hand solution). Did you completely avoid calculating the distance? If so, I think any such solution would provide only approximate result (although it might happen to be a pretty good approximation).
I compare on Euclidean distance squared. It does not actually matter whether Euclidean distance, Euclidean distance squared, or surface distance is used, the ordering will be preserved. Best regards, Calum
participants (3)
-
Arkadiy Vertleyb -
Calum Grant -
Jose