Is firebase's sort by a child O(n) for large data sets and is there a way to optimize it?

Question

Sorry if the title is unclear but I'm not clear as to what I'm asking specifically either.

I have a dataset like so

messages: {
   message_key1: {
       timeStamp: 1610236700000,
       message: message,
   }
   message_key2: {
       timeStamp: 1610236746542,
       message: message,
   }
   message_key3: {
       timeStamp: 1610236790000
       message: message,
   }
   message_key4: {
       timeStamp: 1610236810000
       message: message,
   }
   message_key5: {
       timeStamp: 1610236800000
       message: message,
   }
}

and I wanted to grab the data from the data from 1610236746542 to 1610236810000. Imagine we have tens of thousands of messages. That would require a sort then a fetch which would be extremely inefficient on a large scale. Can I tell firebase to sort the message_key's based off timeStamp and search based off that same time stamp?

I'm using Firebase Realtime Database.

question from:https://stackoverflow.com/questions/65649051/is-firebases-sort-by-a-child-on-for-large-data-sets-and-is-there-a-way-to-opt

Answer 1

Once you define an index on timeStamp, a sort/filter action will be performed on Firebase's servers and thus not need to download all data to your application code.

The time this takes on the server is dependent on the amount of data in the index, but it's not O(n) - it's typically much better. In general most of the performance of your queries will depend on the bandwidth needed to transfer the data to your application, much more than the size of the list.

There is a scalability impact of the size of the list, but that's not explicitly defined (and has improved over the years). I typically recommend not ordering/sorting lists of more than a couple of hundreds of thousands of nodes, although I've seen cases over 1m or more nodes also work (depending on the data size).

If you want a solution where the amount of data in the location has no impact on the performance of queries, consider using Cloud Firestore. This database guarantees that the time it takes to get data only depends on the size of the data you retrieve, not on the amount of data that is considered. So that's O(1) performance, which is pretty uncommon.