[Neo] Retrieving nodes ordered by property

Craig Taverner craig at amanzi.com
Mon Jan 4 12:21:56 CET 2010


I think a generic solution would mean a generic numerical index.

I wrote an index recently that is very similar in principle to the timeline
index Tobias mentioned below, except I allow multiple dimensions and
indexing over any numerical primitive type. Then we get to the next point,
combining indexes. Like in Tobias example: "give me all nodes where x=15
ordered by y". This requires an index that works on x and y at the same
time. Otherwise you have to index one, and do a brute force search on the
other in the result set.

I have an idea about dynamically generating a combined index based on
queries received by the database. So if the user does a query like the one
above, involving both x and y, and both of these are indexed, then a
combined index can be added dynamically. The first query will not be fast,
but subsequent ones would be.

And as far as I can see, a combined index should be as simple as linking
nodes between the un-combined indexes. Now who's up for a n-way combination
of k-dimensional indexes? I think I'm getting a headache just thinking about
it :-)

On Mon, Jan 4, 2010 at 10:17 AM, Raul Raja Martinez <raulraja at gmail.com>wrote:

> Hi Tobias,
>
> Thanks for the info!
>
> I understand the implications of returning ordered nodes.
> Do you guys plan to build such support natively to neo4j even if it is
> for a basic set of node properties?
>
> While retrieving results ordered by property values or more extensive
> queries capabilities is provably not easy when dealing with a graph,
> it is currently one of
> the main things a programmer encounters when comparing neo4j to
> relational databases for storage and info retrieval.
>
> Would it make sense to have something like
> node.setOrderedProperty(property, value); so that the linked list
> based on the natural order of the value is kept internally by neo4j
> and then have another param in the traversers to specify that the
> traversal should follow the relationships established by the ordered
> linked nodes?
>
> If you guys think ordering based on property is out of the scope
> that's fine, I'm just asking in case we can avoid having to roll our
> own hack or component to get it working since ordered entities is a
> requirement in all of our current projects where we plan to use neo4j
>
> Thanks
>
> Raul
>
>
> 2010/1/4 Tobias Ivarsson <tobias.ivarsson at neotechnology.com>:
> > Getting ordered results from any system always requires sorting, unless
> the
> > ordering property is stored. And sorting always requires (at least) O(n)
> > memory and O( log(n!) ) time for comparison sort, possibly O( n ) time
> for
> > sorting integer keys.
> >
> > So if you want results to be sorted on an arbitrary property you will
> have
> > to sort the entire result set and keep it around during your pagination
> > process (possibly redoing the query + entire sorting + skipping a few
> pages,
> > to preserve memory).
> >
> > If you know which properties you will want to order your results by when
> you
> > are designing your database you can store the ordering information in the
> > database. I would suggest a linked list of relationships in between the
> > nodes, in the natural order for the sorting property.
> >
> > You need to be aware of two things with this approach though.
> > The first one is that if the sorting property is unrelated to the
> filtering
> > property, if you want something like "give me all nodes where x=15
> ordered
> > by y", you will either have to store separate linked lists for each value
> of
> > x, filter the result set while traversing through the results as they are
> > ordered by y, or revert to the sorting approach.
> > The second thing to be aware of is that insertion (and changing the value
> of
> > the ordering property in some node) will require some overhead, to
> preserve
> > the order.
> >
> > If your queries are as simple as "give me all nodes where x>LOWER_LIMIT
> and
> > x<UPPER_LIMIT ordered by x", and you can reduce the x property to a long
> > integer value, then the timeline index will do this for you. Otherwise
> there
> > is no ready made component for this today.
> >
> > Happy hacking,
> > Tobias
> >
> > On Mon, Jan 4, 2010 at 1:30 AM, Raul Raja Martinez <raulraja at gmail.com
> >wrote:
> >
> >> Hi,
> >>
> >> Anybody has any experience returning indexed nodes ordered by a given
> >> property?.
> >> For example return all nodes ordered by creationDate. I understand that
> if
> >> the node property is not indexed I'd have to iterate over all nodes
> first
> >> then order then limit the results which seems overkill to me.
> >> I'd like to be able to do... "get me all nodes from start to limit
> ordered
> >> by property".
> >> This is necessary when the data is iterated over using pagination and
> the
> >> order determines what the next start node is next.
> >> _______________________________________________
> >> Neo mailing list
> >> User at lists.neo4j.org
> >> https://lists.neo4j.org/mailman/listinfo/user
> >>
> >
> >
> >
> > --
> > Tobias Ivarsson <tobias.ivarsson at neotechnology.com>
> > Hacker, Neo Technology
> > www.neotechnology.com
> > Cellphone: +46 706 534857
> > _______________________________________________
> > Neo mailing list
> > User at lists.neo4j.org
> > https://lists.neo4j.org/mailman/listinfo/user
> >
>
>
>
> --
> Raul Raja
> _______________________________________________
> Neo mailing list
> User at lists.neo4j.org
> https://lists.neo4j.org/mailman/listinfo/user
>


More information about the User mailing list