1

Imagine that we have a storage of objects O (can be in SQL, NoSQL, doesn't matter) where the object contains some property P_1 to P_n. Some of these properties are stored in storage S1, some in storage S2, etc. In general, imagine that the full definition of the a single object can only be done by invoking some kind of lookup or join across many storage. You can also think that the object is vertically partitioned across different logical database, and each database is oblivious of other database.

Now, we want to define a way to filter and sort these objects. But the function to filter and sort the objects are dependent on properties that span multiple database. At a glance, that means if we were to perform any kind of sorting or filtering, we have to pull the whole database and join the properties in the caller side, which can quickly get expensive for non-trivial sized database.

How can we implement this efficiently?

Some options come to mind:

  1. Store columns that are used for filtering/sorting together in one storage. In other words, make sure that properties that are used for filtering/sorting stick together, so that we can perform the filtering/sorting in the database server. But this is inflexible, because as and when we need to change the filtering/sorting algorithm we potentially have to change the storage schema. Admittedly not too painful in NoSQL database, but still a change in the implicit schema.
  2. Limit any filtering/sorting algorithm only to properties that exist stick together in one database. This is effectively a variant of no. 1, but put the burden of being inflexible on the caller side.
  3. Have a storage specifically to store a filtered + sorted list of object. This feels a bit dumb, and totally space-inefficient especially if the filter/sorting algorithm is very generic.

While thinking about this problem, it also occurs to me that it is similar problem to how Facebook can give customized News Feed to every user. How does it perform the sorting of the News Feed efficiently when the relevancy score of each News Feed item is specific to the user?

2 Answers 2

2

Having a separate pre-filtered list isn't that bad of an idea for many use cases and I imagine FB do use something like that for its News Feed.

For example, product recommendations on a web shop. You don't have time to do fancy AI every-time a user browses or adds an item to a basket. But you can premake lists of items that are similar to each other and tag items with the ids of those lists.

Similarly if you have restricted search criteria, "Hotels suitable for a family holiday" You aren't going to search through the descriptions every-time someone types family, but you can pre-categorise.

The technique works for any expensive search operation where you don't really need it to be 100% up to date, or it's not fully specified behaviour. ie in my two examples you are just trying to drive sales rather than give people an accurate report.

2
  • In FB case though, the items of News Feed per-user is unique, and seems to change very rapidly, e.g. if I pull my News Feed 5 seconds apart I actually see different result. Doing precomputation of News Feed per-user sounds quite expensive, both in terms of computational load and storage Jan 7, 2020 at 9:28
  • smoke and mirrors
    – Ewan
    Jan 7, 2020 at 9:29
1

If you have gone with a Heterogenous DB setup, you have only a couple of options.
1. Handle aggregations in the application: I wouldn't mind doing this if the data is of small size or the response is small (for instance, deriving some data for a single logged in user from 2 sources) and you don't have to do multiple joins in the critical path of your application. However, your application will bloat up and you are more prone to issues with added complexity.
2. Pre-process or aggregate data: Data flow pipelines are particularly for this reason. You can have applications that don't execute in your critical path, but prepares data for your critical path to access. This can be as simple as a view or as complex as another storage/cache saving this data (as you have mentioned). This will lead to separation of responsibility, lighten your application code and you can work on independently scaling your services.

Facebook also has pre-aggregated data for users based on their likes, interests and categories. In addition, they would have a real time fan out to update feeds whenever there is a new activity. Once a set of news feed is delivered, events would likely be triggered to refresh feeds and keep them ready as well as possibly deliver them in real time.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.