From: Calum Grant (calum_at_[hidden])
Date: 2005-10-23 10:14:06
Arkadiy Vertleyb wrote
> "Calum Grant" <calum_at_[hidden]> 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