"Andreas Pokorny" <andreas.pokorny@gmx.de> wrote

On Wed, Oct 05, 2005 at 09:17:18AM -0400, Arkadiy Vertleyb <vertleyb@hotmail.com> wrote:

...

The RTL was discussed on this list at some time in the past. The early version of RTL is described in the March 2004 issue of CUJ. The main difference from currently discussed RML is that we decided against using SQL - like interface, and use the relational algebra-based interface instead.

The most important part for a library like that, is the ability to have the table stored in a file, and only partially mapped into memory. So

It's important, but I wouldn't say "most important". For many tasks having the ability to serialize tables should be enough.

some tree datastructure like a B+tree is an important requirement for a database library. Any chance that this will happen soon? Maybe you remember that I started an attempt to write such a datastructure, but I lost myself in details and had to give up, as soon as exams took most part of my free time.

So, "Any chance that this will happen soon?" :)

From the interface point of view, I also prefer the relational algebra "syntax". It somehow looks more familiar to me.

...

The RTL can currently be compiled with VC7.1 or GCC 3.3+ (although with GCC there might still remain some naming conflicts between MPL and STL, that show up with certain usages)

Because gcc also considers structures when doing adl of a function call?

Yes.

In some previous, and also private discussions you mentioned that you would like to have RTL rewritten, because you made some tradeoffs to support older versions of gcc and vc. Is that versions the overall rewrite?

No, this is just the port to Boost 1.33 (vary little changes, in fact). I would not think it should be fully rewritten, though, just re-factored to simplify the implementation. A few design choices, made in the very beginning, mostly related to the lack of partial template specialization in VC6... Nevertheless I wanted to once more attract people's attention to the library because the interest to relational issues seems to pop-up, and again, I don't believe to mimick SQL is the right way to go. The SQL was designed as yet another attempt to try to make computers understand a language that looks more or less like plain English. Now I don't think that even database comunity considers it a way to proceed. One of the main things that prevented us from moving forward, was not enough interest, but now we can re-consider this -- the number of downloads seems pretty high :) Regards, Arkadiy

On 10/05/2005 01:34 PM, Jose wrote: [snip]

Serialize tables is nice and many memory-based apps can benefit but for most databases persistence is a must.

I agree with previous statement that persistence is the top priority. RML has tackled this with a separate persist library that provides the persistent STL containers.

Why can't the existing boost serialize library be used instead of a separate persist library?

On Wed, 5 Oct 2005, Jose wrote:

On 10/5/05, Larry Evans <cppljevans@cox-internet.com> wrote:

...

Why can't the existing boost serialize library be used instead of a separate persist library?

I am not very familiar with the serialize library but I don't think they tackle persistence in the sense of providing persistant STL containers, i.e. containers that you can use in your app but that are stored in a file rather than the well known memory STL containers

The use of serializability as a prerequisite for storage in a persistent container seems quite logical. Im currently looking if I can wrap a simple string/file based persistent priority queue into a simple template library that is somewhat compatible with std::priority_queue (libppq on sourceforge). This should be quite do-able, but as Im not that experienced with templates, it may take some more efford. I think that dependancy on the serialisation library for classes that can be used to instanciate a persistent container template from would be a sane way of working. That way you just have to create a persistent container of strings using the filesystem, and wrap this class in a template. What I was currently thinking of was to require that each class that could be put into the persistent priority queue template should have its operator =(string) and operator string() overloaded by a serialisation method, so the template could simply cast its internaly used strings to and from the specified class, and each class should have its operator int() overloaded so that its integer priority could be retreived from the objects by using simple casts in the template. One other thing to considder are the aplicability and efficiency of algoritms paterns and adapters on persistent containers. I had to choose a vector of persistent fifo design for my persistent priority queue as a the heap aproach apeared to perform poorly in comparison. I think there may be more paterns that may be efficient in memory, but may be less optimal either in disk usage or in disk IO when mapped to files. I dont believe there is a fifo in stl, only a deque, but the deque again would be hard to code efficiently for both space and speed. Simple memory based templates may be quite a bit harder to implement when using serialisation+FS based storage. I think I could adjust the persistent fifo to implement shrinking on both sides, making it usable for some more algoritms that normaly work with a deque, but pushing data to both sides as can be done with the deque would be very hard to do efficiently. I think my libppq code might be of some use. I could probably use some help with the templates. Random access containers would I think be somewhat harder to implement efficiently. Rob

Some reference info on the topics discussed here and in the RML thread that might be useful: 2001 USENIX paper: PSTL - The Persistent Standard Template Library for C++ http://www.infosys.tuwien.ac.at/Staff/tom/Publications/Gschwind2001-pstl.pdf http://www.infosys.tuwien.ac.at/NewsCache/pstl.html This papers covers the issues and has simple app benchmarks that compare to the widely used Berkeley DB (alse note Berkeley DB provides the underlying b-tree for MySQL) Reflection support by means of template metaprogramming http://www.di.unipi.it/~attardi/Paper/GCSE01.pdf Which has a good discussion on interfacing to a relational table using meta programming

"Jose" <jmalv04@gmail.com> wrote

On 10/5/05, Arkadiy Vertleyb <vertleyb@hotmail.com> wrote:

...

"Andreas Pokorny" <andreas.pokorny@gmx.de> wrote

...

On Wed, Oct 05, 2005 at 09:17:18AM -0400, Arkadiy Vertleyb <vertleyb@hotmail.com> wrote:

The most important part for a library like that, is the ability to

have

...

...

the table stored in a file, and only partially mapped into memory. So

It's important, but I wouldn't say "most important". For many tasks having the ability to serialize tables should be enough.

Serialize tables is nice and many memory-based apps can benefit but for most databases persistence is a must.

I agree with previous statement that persistence is the top priority. RML has tackled this with a separate persist library that provides the persistent STL containers. Also shmem I think provides persistent stl containers using mmap files (persist library even has benchmarks comparing to mysql)

Well, RTL addresses (or delays) the issue of persistense by separating table implementation from the rest of the library. We currently give the user a choise between an std::vector - based implementation and Boost.Multi-index - based implementation. A disk-based implementation can also be developed. (alternatively, someone may comeup with a persistent std::vector :-) Regards, Arkadiy

Arkadiy Vertleyb wrote:

...

...

OTOH, writing a primitive optimizer, would, in our opinion do more harm than good.

By "harm" do you mean have worse performance?

Yes, and also (possibly) inability to handle more complicated cases.

Well I certainly agree that a library that couldn't handle complicated cases, or whose performance was poor, would need a rethink. But I don't think RML is in that category. It has excellent performance and can handle very complex queries. I should exercise caution however - I await to see how well your library copes with 1000000 items, does a self-join, adds another 1000000 items and does a second self join. You sound fairly confident that you will beat me! If you like you can come up with an extremely complex query - and we can compare again.

...

If you're going to make claims about the performance of an approach, then you need to have benchmarks. You can't argue about air. For example the RML benchmarks

http://visula.org/relational/benchmarks.html

show RML to be matching or outperforming std::map.

Would you care to benchmark your RTL versus RML or the STL before making such claims? I think that would settle which approach did more "harm".

Note that I didn't say RML's approach is harmful. All I said is that a simplistic approach to implementing optimizer is IMO inacceptable. Are you saying your optimizer is simplistic? :-)

Of course not!

I believe that talks about performance are premature. I think it's time to talk about what can and what can't be done with this libraries. Then comes the optimization.

I don't think talking about performance is premature. If we are going to provide a practical library, then performance matters. If a user has a choice between using RTL in a real application, but it is 10 times slower than Boost.MultiIndex, then I expect most users would stick with Boost.MultiIndex. People need to know. On the other hand, I believe that RML is a much easier and more efficient (than std:: containers) way to manage collections. But I am biassed :-)

As for benchmarks, for such simple case as yours, you don't need RTL -- you can benchmark sorted std::vector or Boost.Multi_index. The performance of RTL will not be different, since it's based on these containers. To outperform STL is definitely not one of RTL's tasks.

For more complicated cases though, such as ones that I described in my original post, RTL does provide an efficient, index-based solution, while other libraries, AFAIK, don't.

In that case, could you give an example where RTL would be efficient, while "other libraries" would be inefficient. I have a case for you that might not be so efficient in RTL: What about indexing on multiple columns? This is what RML is designed for, otherwise you may as well just use std::map. Although it sounds a little competitive, I think it's pretty instructive to be able to compare different implementations. Regards, Calum

"Calum Grant" <calum@visula.org> wrote

Arkadiy Vertleyb wrote:

...

...

...

OTOH, writing a primitive optimizer, would, in our opinion do more harm than good.

By "harm" do you mean have worse performance?

Yes, and also (possibly) inability to handle more complicated cases.

Well I certainly agree that a library that couldn't handle complicated cases, or whose performance was poor, would need a rethink.

But I don't think RML is in that category. It has excellent performance and can handle very complex queries. I should exercise caution however - I await to see how well your library copes with 1000000 items, does a self-join, adds another 1000000 items and does a second self join. You sound fairly confident that you will beat me!

I am not confident about this. We didn't spent a lot of time on optimization. But if I wanted to compete with you on this particular example, I would not use the technique I showed -- I wouldn't use transactions, indexing, etc. -- I would just use a merge-join, and stopped after ten results, like you did, and it would take no time. I might beat you or not, but RTL is flexible enough to allow me to build an expression that would evaluate this (or any other) expression efficiently, with the minimal overhead. And since I do it by hand, I don't have to worry about my optimizer not being able to cope with this.

If you like you can come up with an extremely complex query - and we can compare again.

For starters, try to change the expression to something like abs(c1 - c2) == 1, and output (or just walk) _all_ the results. Then repeat this 1000 times. You can go back from 1000000 to 3000 :-)

...

...

If you're going to make claims about the performance of an approach, then you need to have benchmarks. You can't argue about air. For example the RML benchmarks

http://visula.org/relational/benchmarks.html

show RML to be matching or outperforming std::map.

Would you care to benchmark your RTL versus RML or the STL before making such claims? I think that would settle which approach did more "harm".

Note that I didn't say RML's approach is harmful. All I said is that a simplistic approach to implementing optimizer is IMO inacceptable. Are you saying your optimizer is simplistic? :-)

Of course not!

...

I believe that talks about performance are premature. I think it's time to talk about what can and what can't be done with this libraries. Then comes the optimization.

I don't think talking about performance is premature. If we are going to provide a practical library, then performance matters. If a user has a choice between using RTL in a real application, but it is 10 times slower than Boost.MultiIndex, then I expect most users would stick with Boost.MultiIndex. People need to know.

Of course. However I don't believe RTL even targets this niche. Relational approach is much more than just indexing on multiple fields.

On the other hand, I believe that RML is a much easier and more efficient (than std:: containers) way to manage collections. But I am biassed :-)

...

As for benchmarks, for such simple case as yours, you don't need RTL -- you can benchmark sorted std::vector or Boost.Multi_index. The performance of RTL will not be different, since it's based on these containers. To outperform STL is definitely not one of RTL's tasks.

For more complicated cases though, such as ones that I described in my original post, RTL does provide an efficient, index-based solution, while other libraries, AFAIK, don't.

In that case, could you give an example where RTL would be efficient, while "other libraries" would be inefficient. I have a case for you that might not be so efficient in RTL: What about indexing on multiple columns? This is what RML is designed for, otherwise you may as well just use std::map.

I don't know if we are much less efficient with multiple columns. Again, the matter of fine tuning. And again, relational approach is much more than just indexing on multiple columns. For just indexing on multiple columns one can use Boost.MultiIndex. IMO, relational approach is about providing multiple views into the same data model. And making these views most efficient. The constrained language of relational algebra allows one to achieve this. This is what RTL is about.

Although it sounds a little competitive, I think it's pretty instructive to be able to compare different implementations.

Nothing wrong about being competitive :) Regards, Arkadiy

Arkadiy Vertleyb wrote

"Arkadiy Vertleyb" <vertleyb@hotmail.com> wrote

...

Another example -- you have table of cities, and you need to get all the pairs, such as the distance between them is less than certain number. How would one solve the problem with the conventional SQL approach? This is a self-join. But how to make this query fast?

With RTL approach, we could create an index on this self-join.

Here is a simple example that illustrates this. The attached program does the following:

1) creates table of one column; 2) self-joins the table 3) selects records where columns are equal.

This by itself doesn't make any sence, but it closely approximates the task of finding close cities, stars, billiard balls, monsters and soldiers, etc.

Here is the equivalent in RML. Forget 3000 rows, what about adding 1000000 rows, then adding another 1000000 to it? What time does the equivalent RTL take? I don't think self-joins come up that often in real life however. Regards, Calum #include <ctime> #include <relational.hpp> using namespace relational; RM_DEFINE_ROW_1(MyRow, unique<int>, x); int main(int argc, char*argv[]) { int total=0; clock_t t0 = clock(); { table<MyRow> my_table; const int N1=1000000, N2=1000000; for(int i=0; i<N1; ++i) my_table.insert(MyRow(i)); std::cout << select( (my_table, my_table), col<0,0>() == col<1,0>() ).size() << std::endl; // Print only 10 results output_results(limit(select( (my_table, my_table), col<0,0>() == col<1,0>() ), 10)); for(int i=1; i<=N2; ++i) my_table.insert(MyRow(-i)); std::cout << select( (my_table, my_table), col<0,0>() == col<1,0>() ).size() << std::endl; } clock_t t1 = clock(); std::cout << "That took just " << (1000*(t1-t0))/CLOCKS_PER_SEC << "ms\n"; return 0; } Here is the output on my 1.7GHz laptop: 1000000 ((0),(0)) ((1),(1)) ((2),(2)) ((3),(3)) ((4),(4)) ((5),(5)) ((6),(6)) ((7),(7)) ((8),(8)) ((9),(9)) Total 10 results 2000000 That took just 1687ms Press any key to continue Arkadiy Vertleyb wrote

"Arkadiy Vertleyb" <vertleyb@hotmail.com> wrote

...

Another example -- you have table of cities, and you need to get all the pairs, such as the distance between them is less than certain number. How would one solve the problem with the conventional SQL approach? This is a self-join. But how to make this query fast?

With RTL approach, we could create an index on this self-join.

Here is a simple example that illustrates this. The attached program does the following:

1) creates table of one column; 2) self-joins the table 3) selects records where columns are equal.

This by itself doesn't make any sence, but it closely approximates the task of finding close cities, stars, billiard balls, monsters and soldiers, etc.

Here is the text (Boost CVS head was used to be able to use typeof):

///////////////////// #include <table_delta.hpp> #include <utils.hpp> #include <selection_delta.hpp> #include <key_index_delta.hpp> #include <crossproduct_delta.hpp> #include <rename_delta.hpp> #include <boost/lambda/lambda.hpp> #include <boost/typeof/typeof.hpp> #include <expression_registry.hpp> #include <transaction.hpp> #include <cstdlib>

using namespace boost; using namespace boost::lambda;

BOOST_RTL_DEFINE_COLUMN(int, c1);

struct my_info : rel::table_info< mpl::vector<c1>

...

{};

typedef rel::table<my_info> my_table; typedef my_table::value_type my_tuple;

struct a; typedef rel::alias<c1, a> c2;

main() { // populate table

my_table t;

for (int i = 0; i < 3000; ++i) t.insert(my_tuple(i + 1));

// create and print the view

BOOST_AUTO(t2, rel::auto_rename<a>(t));

BOOST_AUTO(xp, rel::cross_product(t, t2));

BOOST_AUTO(pred, _1[c1()] == _1[c2()] );

BOOST_AUTO(sel, rel::selection(xp, pred) );

std::cout << "building index" << std::endl;

BOOST_AUTO(idx, (rel::key_index<mpl::vector<c1, c2> >(sel)) );

std::cout << "printing index" << std::endl;

rel::print(idx);

// update table (index doesn't get fully rebuilt)

rel::expression_registry exprs; exprs.add(idx);

rel::transaction tr;

for (i = 0; i < 10; ++i) tr.insert(t, my_tuple(-i));

tr.commit(exprs);

// print the view once again

std::cout << "printing updated index" << std::endl; rel::print(idx);

return 0; } /////////////////

Regards, Arkadiy

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/bo> ost

...

Here is the equivalent in RML. Forget 3000 rows, what about adding 1000000 rows, then adding another 1000000 to it? What time does the equivalent RTL take?

Calum, I think you are missing my point. The above example was provided to illustrate my two statements:

1) RTL can index any (arbitrary complicated) expression, not just table;

In SQL/RML you can index any arbitrarily complicated expression. If you need to index something complex, you create a column for it. For example if you had a table of people, with (name, height, weight). If you needed to work with bmi = weight/(height^2), you create another column for it. people.insert(Person(name, height, weight, weight/(height*height)); The RTL approach would not need to add the fourth column, and that is an advantage that RTL has over RML. Similarly for self-join. If you wanted to store an all-pairs distance between two cities, you create a table (city1, city2, distance). But in practice, in SQL I have never seen an index on anything other than a column. Occasionally I have seen a multi-column index. So this is why supporting computed indexes has not been a priority for RML.

2) RTL can _incrementally_ update any such index when the underlying table has been changed.

Same in RML. You add data, indexes change automatically. You change a field in a row, indexes update automatically. Probably more efficiently.

Did I use the most efficient expression for this particular task? Of course not. I used cross-product where I would use a range (or merge)

join otherwise. I did it _intentionally_, because I wanted to provide

an analogy of a complicated condition, such condition for which optimization is simply not possible.

I am pretty sure your library figured out how to do this query efficiently, without considering every possible combination (it didn't

consider 10^12 combinations, did it?). However, what it would do if the condition was more complicated? Like calculating the distance, matching people by certain characteristics, etc.? RTL can build an index on even slow expression, after which subsequent queries become a

few orders of magnitude faster. And the indexes are not broken when the tables are changed.

That is a nice idea. One could generalize - have a generic observer on any container. It could turn your entire application data-driven. Nice. I have seen observer-driven architectures work extremely well in practice.

Having said all this, RTL doesn't enforce this kind of usage. If the query needs to be executed only once, or if one doesn't want to consum

memory for indexes, any appropriate relational expression can be built, with any number of indexes in different nodes, to achieve needed tradeof between speed, initial response, memory consumption, etc. My firm belief is that this kind of flexibility is simply impossible with SQL-like approach.

I wouldn't knock the SQL approach - it is an extremely effective paradigm for data query and represention. There are some things that would not be possible in SQL, but one can always work around them. For example maintaining an all-pairs distance between two cities. One can simply declare a table (city1, city2, distance), and index on the columns you wanted. Whereas in RTL this data would be stored implicitly in an index, RML would require an explicit table. The reason RML uses the SQL paradigm is because I know that it works. The RTL view approach would make this much easier to maintain. The question is, what are the overheads of this convenience?

...

I don't think self-joins come up that often in real life however.

I think they are. I just gave examples where they could be (and are) used. This, however, is not about a self-join. This is about any query

which is slightly more complicated than just a simple index-based selection.

Self-joins don't come up in SQL. The assumption you make is that the query analyser is some kind of black box that will fail in mysterious ways. Actually the rules for query optimization are very well spelt out in the tutorial. It is precisely because the rules for indexing are so straightforward that there will be no unexpected performance penalties in RML. It will pick indexes in any complex multi-table conjunction for any comparators.

Once again, I don't believe this is a right time for any performance contests. They will not prove anything. I think RML will be faster in some cases, and RTL -- in the others. And a couple of days spent on

optimization can dramatically change the picture.

I think you should work on that, and then we can see what's what. The only reason I make a fuss is because you say your approach is more efficient.

What I would like to be discussing instead is the _design principles_ behind the libraries.

Okay, that is a good way forward. RTL has (from what I understand) an observer-driven architecture. Correct me if I am wrong. This means that you don't index the underlying data, you index views of the data. RML on the other hand is a multi-index architecture. The query analyser is basically a way of avoiding writing complex index probes, iteration and filters. From an efficiency point of view, it is exactly the same as writing out C++ to manipulate a multi-index. So, RML has the potential to be more efficient because multi-indexes are more efficient than multiple single-indexes. Best Regards, Calum

Hi, I am trying to compare RML vs RTL performance on a 3GHz x86_64 . The result I got for RML is 1260 ms (see below). The result greatly varies with the compiler optimization. Not sure what was Calum's 1.7GHz environment (his result was 1687ms) without optim. --> 21230 ms g++ -O2 --> 3200 ms g++ -O3 --> 1260 ms (see below) Arkadiy, I would need your latest realease so that I can compile it against boost head (I d/l your library from the vault, pls see compile error below. I also made some changes to compile in Linux) Regards, Jose =========================================== RML 1000000 ((0),(0)) ((1),(1)) ((2),(2)) ((3),(3)) ((4),(4)) ((5),(5)) ((6),(6)) ((7),(7)) ((8),(8)) ((9),(9)) Total 10 results 2000000 That took just 1260ms =========================================== g++ -O6 arkadiy.cpp -o test2 -Irtl -I/usr/local/include/boost-1_33 -L/usr/local/lib rtl/identifiable.hpp: In member function 'unsigned int rel::identifiable::id() const': rtl/identifiable.hpp:22: error: cast from 'char*' to 'unsigned int' loses precision make: *** [test2] Error 1 ===========================================

The results are in: I'm running Linux FC4 on x86_64 The RTL results are quite amazing with -O3 optimization 1000000 records added 2000000 records added That took just 320ms RML RTL -O3 1260ms 320ms -O2 3200 ms 780 ms w/o 21230ms 13760ms Maybe there is something hampering RML 64-bit performance, as my best RML result on a 3GHz box doesn't differ much from Calum's 1.7GHz laptop ! I would like to see a more complex test with insert, select and delete, e.g. something like the resorce reservation system in http://www.infosys.tuwien.ac.at/NewsCache/pstl.html#evaluation where you have insertion, iteration, lookup/select and deletion On 10/9/05, Arkadiy Vertleyb <vertleyb@hotmail.com> wrote:

"Jose" <jmalv04@gmail.com> wrote

...

===========================================

g++ -O6 arkadiy.cpp -o test2 -Irtl -I/usr/local/include/boost-1_33 -L/usr/local/lib rtl/identifiable.hpp: In member function 'unsigned int rel::identifiable::id() const': rtl/identifiable.hpp:22: error: cast from 'char*' to 'unsigned int' loses precision make: *** [test2] Error 1 ===========================================

This actually is just a warning in VC7, and never came up in MinGW, so I didn't pay much attention to it. But why wouldn't it be able to cast, is it a 32 or 64-bit system?

Could you modify your copy of identifiable.hpp, and replace:

return reinterpret_cast<unsigned int>(p.get());

with

return p.get() - (char*)0;

This may fix the problem (at least it removes the warning in vc71).

Regards, Arkadiy

PS: my results for RTL (MinGW with optimization) --3094ms. My PC has a 1.5 GHz processor.

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

My results are using gcc 4.0.1 I agree the benchmark is quite silly so maybe each of you should come up with a mixed-operation benchmark that exploits your library well and then we can run both benchmarks This is not intended to pit one library against the other but to gain some insights on which approaches bring best performance I think it would also be useful to have RTL's basic distance example shown in RML and then benchmark that with 10k+ points On 10/9/05, Calum Grant <calum@visula.org> wrote:

...

PS: my results for RTL (MinGW with optimization) --3094ms. My PC has a 1.5 GHz processor.

I should warn you both that gcc's ability to optimize RML is quite poor. I had to move to gcc 4.0.1 to get decent performance. VC7.1 does a much better job, which is where my number came from.

I also don't really understand the purpose of this "benchmark". The test itself does nothing useful other than to probe the index 1000000 times. It would be better with a real-life problem.

Calum

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

On 10/10/05, Arkadiy Vertleyb <vertleyb@hotmail.com> wrote:

"Jose" <jmalv04@gmail.com> wrote

...

I think it would also be useful to have RTL's basic distance example shown in RML and then benchmark that with 10k+ points

Well, I guess it would be quite difficult to come up with exact locations of 10k+ cities (unless somebody already have this data).

The list below is up to date and has 20K+ coordinates that show the location of IP Autonomous Systems (basically major ISPs). http://netgeo.caida.org/aslatlong.txt One query idea that comes to my mind is sorting the AS locations by the number of other AS that are in a 5 Km radius and limiting this to the top 500. That would give a "rough" idea of which locations in the world that have the highest IP connectivity. The name, so that is understandable, should be something like "CEDEL-MRS, LONDON, GB" (example taken from concatenating fields for CEDEL-MRS AS name). This file changes regularly, as the net topology changes, so a second query would be the time it takes, having the current file in memory, to read the updated file and run the updated query (and maybe show the list of locations that have gained the most positions in the rank list)

On 10/10/05, Arkadiy Vertleyb <vertleyb@hotmail.com> wrote:

"Jose" <jmalv04@gmail.com> wrote

...

I think it would also be useful to have RTL's basic distance example shown in RML and then benchmark that with 10k+ points [...]

(http://lists.boost.org/Archives/boost/2005/10/94890.php). All that needs

to be done is to complicate the condition, so that such things as merge or nested loops join are not possible. I think something like "abs(c1 - c2) < 1" should do fine. I already suggested this before.

Can you explain "such tings as merge or nested loop joins are not possible" ? I'm not sure I understand

BTW, the file you provided is very interesting. I played with it yesturday, but so far my results are pretty slow (no wonder -- I have to consider more than 400,000,000 possible combinations). One of possible reasons is the lack of co-processor on my PC (quite a bit of math is done), but I also found some RTL inefficiencies (as I said, we haven't spend a lot of time on the optimization yet). I will do some more research and then provide the results. Will probably take a few days to a week.

You could instead sort on the square of the distance - saving you one square root per iteration, and since you don't need square root, you can just work with integers. I'm just intrigued how you are going to fit 400,000,000 items into an index in memory!! Cheers, Calum

"Calum Grant" <calum@visula.org> wrote

// Print only 10 results output_results(limit(select( (my_table, my_table), col<0,0>() == col<1,0>() ), 10));

So, you don't seem to iterate the whole selection, only first ten results. Since we both evaluate the expressions lazily, this doesn't look like a right test to me. If you apply the merge-join, such a query would take the same time on a 10-row table or on a 1000000-row table, wouldn't it? Regards, Arkadiy

"Calum Grant" <calum@visula.org> wrote

Here is the output on my 1.7GHz laptop:

1000000 ((0),(0)) ((1),(1)) ((2),(2)) ((3),(3)) ((4),(4)) ((5),(5)) ((6),(6)) ((7),(7)) ((8),(8)) ((9),(9)) Total 10 results 2000000 That took just 1687ms ^^^^^^^^^^^^^^^^^^^ Press any key to continue

These results are so unbelievably impressive, that I had to see them with my own eyes. So I downloaded your library from http://visula.org/relational. My PS has a 1.5 Ghz processor, and I used VC71 public edition (no optimization), release mode. Unfortunately my results were slightly different from yours: 1000000 ((0),(0)) ((1),(1)) ((2),(2)) ((3),(3)) ((4),(4)) ((5),(5)) ((6),(6)) ((7),(7)) ((8),(8)) ((9),(9)) Total 10 results 2000000 That took just 35453ms ^^^^^^^^^^^^^^^^^^ Press any key to continue This is a little less impressive :-( What am I missing? Regards, Arkadiy PS: The RTL (after modifications I mentioned before) was more than twice faster: 1000000 records added 2000000 records added That took just 14906ms ^^^^^^^^^^^^^^^^^^ Press any key to continue Here is the modified text (again, I am using current Boost CVS): #include <table_delta.hpp> #include <utils.hpp> #include <selection_delta.hpp> #include <key_index_delta.hpp> #include <crossproduct_delta.hpp> #include <rename_delta.hpp> #include <boost/lambda/lambda.hpp> #include <boost/typeof/typeof.hpp> #include <expression_registry.hpp> #include <transaction.hpp> #include <cstdlib> #include <merge_delta.hpp> #include <windows.h> #include <ctime> using namespace boost; using namespace boost::lambda; BOOST_RTL_DEFINE_COLUMN(int, c1); struct my_info : rel::table_info< mpl::vector<c1>

{};

typedef rel::table<my_info> my_table; typedef my_table::value_type my_tuple; struct a; typedef rel::alias<c1, a> c2; main() { using namespace std; clock_t t0 = clock(); my_table t; t.reserve(2000000); int i; for (i = 0; i < 1000000; ++i) t.insert(my_tuple(i + 1)); BOOST_AUTO(t2, rel::auto_rename<a>(t)); BOOST_AUTO(mr, rel::merge<1>(t, t2)); cout << count(mr) << " records added" << endl; for (; i < 2000000; ++i) t.insert(my_tuple(i + 1)); cout << count(mr) << " records added" << endl; clock_t t1 = clock(); std::cout << "That took just " << (1000*(t1-t0))/CLOCKS_PER_SEC << "ms\n"; return 0; }