CODEWITHSUNDEEP
neo4jtime-complexitygraph-databasesquery-performance
Sai Sri Krishna Kotha
Sai Sri Krishna Kotha

Reputation: 113

What is the Time Complexity of search query in Neo4j?

I have 5 million products and 100 000 sellers as data in Neo4j database.The sellers have some common products among all the products portfolio. These products and sellers are the nodes and the relationships between them are edges in the Neo4j database.

What is the time complexity for the search query to find all the products for each seller in Neo4j database?

Upvotes: 1

Views: 929

Answers (1)

InverseFalcon
InverseFalcon

Reputation: 30397

Going by the requirement of looking up a particular seller (or sellers, if looking up several at a time), the complexity for traversing the relationships is proportional to the products sold by those particular sellers (not all sellers) (let's call that k), so O(k).

You would look up the :Seller node(s) by index (lucene index lookup for that particular label/property index, which I THINK is O(log(n)), where n is the number of entries in that particular index), then traverse all of the relevant relationships (:Sells?) to the :Product nodes sold by those sellers, then collect the products per seller.

The traversals only walk the relevant portion of the graph, so if your query was for 1 seller and its 100 products, the query time should not change whether those were the only nodes in the graph, or if you were using your proposed graph of 5 million products and 1 lakh sellers.

If you weren't using an index for the lookup of your initial sellers, that would of course change the complexity, as you'd be performing a label scan across all seller nodes instead, which would greatly impact your query proportional to the number of :Seller nodes.

That's why it's vital to create indexes and use index lookup to your starting nodes whenever possible.

EDIT:

I clarified the above a little...the index lookup via lucene, while it may not be the most expensive part of the query (given a high number of products sold), WILL grow with the number of indexed nodes (for that one particular label/property index). There is probably a tighter way to describe the complexity of a lucene index lookup, however. This kind of lookup is fairly common for finding a starting place in most databases, it's not specific to Neo4j or graph dbs, so I wouldn't consider the index lookup very important in your consideration of graph db performance.

Upvotes: 2

Related Questions