5

Given the following relational model:

database model

I need to implement a typed search for hotels, which should be able to query on name, city, country, category, hoteltype, roomprice, customtype, room custom type and roomtype or any combination of these criteria.

At the moment I'm doing this though Entity Framework, dynamically constructing a query over the Hotel-entity (IQueryable). This is fine as currently there is very little data. However, this isn't very scalable and when there is a lot of data this will become very slow as it's a query over 10 tables. Note that I only need to load the hotel-data, not the entire graph.

I'm thinking of ways to improve the scalability of this part. I have been looking into CQRS and maybe NoSQL solutions.

One approach I had in mind is having this model on the write side (to enforce consistency) and having a different model on the read side. On write, I would then update the read-model (viewmodel).

However, since this is already a more or less complex model in terms of relations, I see a few problems with that:

  • Updating metadata (such as category, roomtype, hoteltype) would require me to update all of the hotels or rooms in the read-model. This could be quite slow or impossible once there's a lot of data.
  • Suppose I use a document database such as MongoDB and save a hotel with all the related items denormalized, won't the query over that table still be slow as it has to search inside each document, or is still still quite fast in NoSQL?

To summarize a few questions:

  • Is denormalizing this model the right approach and what would be the best way?
  • Will NoSQL be faster?
  • Are there any better approaches I can follow or ways to break up the relationship and flatten the hierarchy while still being able to do a typed search?
  • Ideally some fields should also support fuzzy search, what would be the best way to achieve that?
3
+100

First off, if that's your actual schema, it appears to be over-normalized.

  • Hotel_Category | Categories
  • Hotel_HotelType | HotelTypes
  • Room_RoomType | RoomTypes
  • Hotel_Room | Room

are all candidates for being merged together by the pairing. So instead of 8 tables you would have 4. The double prefix on some of your tables is a hint that the normalization has been taken too far.

Practical or pragmatic normalization is always a balancing act. In this case, I think you've gone too far down the normalization route.


Next up, performance on the relational DB side:

I need to implement a typed search for hotels, which should be able to query on name, city, country, category, hoteltype, roomprice, customtype, room custom type and roomtype or any combination of these criteria.

Apologies if this sounds pedantic, but you do have indexes in place for all of those elements, right? If sharding is the secret sauce of web scale1, indexes are a critical first step in making sure your relational DB can scale.
1 The phrase is from a viral video parodying certain reasons in selecting database. Just google the term, but know that it's an NSFW video.


After that, we need to look at write models & read models.

With as small as this schema is, I think that approach is overkill, especially if you don't de-normalize the schema you provided in the question. Taking this route is just adding gasoline to an already hot fire - all that you'll have accomplished is bringing your application down more quickly due to the complexity.

That's not to say read-only views wouldn't be worth considering after you reduce the schema. Thinking through the ways people are likely to query for rooms, you can build views by location + name, location + price, location + type, etc...

Ideally, you'll have metrics from existing use to drive which views you should build. But it sounds like you understand the domain well enough that you can take a reasonable guess at which ones to start with.


Finally, consider a noSQL approach. And there's a reason why I bring it up last.

If you don't attempt any of the above first, your noSQL implementation will perform significantly worse than your existing relational DB solution. The biggest challenge will be the number of joins that you have in your queries. While you aren't likely to have a lot of complex joins, noSQL systems run best with little to no joins in the queries.

If you reduce your schema as suggested in the first segment, then you may have a decent chance at migrating to noSQL. I would probably collapse Hotel, Country, Room, and Room_Type into one table though. That would leave simple joins from there against Hotel_Category and Hotel_Type, but I'm assuming that those two tables are used less often when finding rooms.

Along with collapsing the schema, you'll need to index against the major elements that you want to search against. Perhaps even more so than relational DBs, the noSQL approach relies heavily upon the prebuilt index in order to find the information you need quickly.


Bootnotes:

As far as which would be faster (relational vs. noSQL), I really don't know and I don't think anyone could know until you've spent some time building and tuning both. Work on one doesn't apply to the other, so you have to double your effort in order to truly answer that part of your question. If you're already invested on the relational side, I don't see anything compelling within your question to switch to noSQL.

Fuzzy search can be a challenge regardless of underlying database type. The best thing you can do here is look at the options provided by the platform you pick and start trying to implement fuzzy search. Profile that; keep revising; and see where your iterations take you.

  • First of all, thanks for your elaborate answer! A few things: The DB is 3rd normal form. I guess my main issue is on how to collapse it. Collapsing them means duplicated data. For a category for example that would mean an update to a category name, would require an update to all hotels. With a lot of hotels this could be potentially a performance kill. How would you handle that? Probably my mind is just hard-wired for normalization. – Kenneth Dec 20 '13 at 19:44
  • @Kenneth - in and of itself, normalization isn't a bad thing. Neither is duplicating data; it's just another technique. (Yes, I know that's heresy to some). You need to know why you are using a particular technique though. I would ask how often are you going to change category names? I'm willing to bet that it's pretty infrequent. If it's infrequent, then take the odd performance hit for updates and duplicate the data. Your attempts to save space are what's killing your ability to scale the queries. So you need to pick between saving space versus more easily scaling your system. – GlenH7 Dec 20 '13 at 19:52
  • That makes sense, I guess categories can be modified, but they certainly won't be modified daily, whereas queries will run thousands of times a day. – Kenneth Dec 20 '13 at 19:54
  • 1
    Thanks for that. I knew throwing NoSQL at it without knowing enough wasn't the right thing to do :-) I will look into denormalizing first and then maybe later I can check whether NoSQL could actually be beneficial. – Kenneth Dec 20 '13 at 19:59
1

Have a look at Solr. It can do all the things that you want and much more, out of the box. One possible downside is that you have to push your data into the server every time you have an update (or do it in batches at specific intervals) but since Solr supports delta imports, it shouldn't be that much of a hassle.

  • There's still the issue when you update metadata. Suppose I have 10 categories and 10000 products. If I update the name of a category, then I'd need to update 10000 records. – Kenneth Dec 20 '13 at 17:20
  • what's the maximum possible number of categories that you can have? – devnull Dec 20 '13 at 17:57
  • At the moment there's about 120, I don't expect it to grow much more (say not an order of magnitude). It might get to 200 – Kenneth Dec 20 '13 at 17:58
  • in this case you can use the category ids in the index and implement a filterable checked dropdown for the category field in the interface. solr supports multivalued fields and queries. you'd only have hotels or rooms as documents in the index, depending on how granular you want to go. – devnull Dec 20 '13 at 18:01
  • if you want to implement fuzzy searches on the metadata fields, you can index those as separate documents and query them when someone types something in the respective fields. you can then show the results as autocomplete suggestions. – devnull Dec 20 '13 at 18:07
1

If your complex queries are always based on Hotel Rooms, I'd say that you need in order to escalate is to denormalize (or otherwise build an index).

If you denormalize on SQL, I'd go for an OLAP approach. A simple denormalized, indexed table seems should be enough to escalate to millions of rows.

NoSQL (ie MongoDB) can also be used for this. The design principle is similar to an OLAP approach, but backed by a NoSQL database.

In any case, I'd suggest to use such an OLAP/denormalized backend only for the indexed search part, while maintaining your SQL structure for the transactional processing part (exactly as you mention, using a "read-model").

You can use a search engine like Solr (or Lucene in your case) as suggested, which can perhaps be seen as a way of denormalizing too. I tend to dislike this approach when I don't need fuzzy/score-based/text-based search. Depending on which kind of fuzzy search you need, you can avoid Lucene and resolve fuzzy search with a custom (ie using string-distance algorithms). As a concrete example: I'd consider a seach engine like Lucene if I need to do fuzzy search based on "City" or other text fields, but I'd perhaps go with something custom based on "Levenshtein distance" if I only need to do simple fuzzy searches on "Country". If you, however, need score-based search (like: some room attribute is not really important and doesn't disqualify the room from being listed) then go with some search engine like Lucene.

Finally, note that when querying your database the number of tables is not really a big concern as long as you are using indexed columns to join tables and their cardinality is not too big (ie, a "country" table can be contained in memory, and joining it on its primary key doesn't normally impact performance). Such joins are very common in Relational-OLAP systems.

  • wouldn't OLAP be the wrong approach for the job? i mean, it's search not BI. the single benefit that you get is speed, at the cost of doing everything else by yourself (faceting, fuzzy/partial searches etc) – devnull Dec 20 '13 at 16:50
  • you'd use an olap engine for seaches, but yes, I think that advice must be taken with a pinch of salt... to me it's mostly another strategy for denormalization. But most DB systems can scale, so I still think that I'd go for a search engine only when needing text-based/score-based search. Just my two cents. – jjmontes Dec 24 '13 at 15:56
-2

What I have done for complex queries over large datasets is this:

  • Perform a simple query which includes only one or two tables
  • Truncate the number of results to a reasonable amount (500k?)
  • Perform a more complicated query to narrow down options based on the truncated records

This is a scalable solution to your problem. Once you start joining many tables with millions of records, you multiply the size of your temporary table used in the join. By truncating the results to a manageable amount, the queries will still run quickly, and in a majority of cases, you will get 100% of the results. In the case where your truncate removes valid hotels, you will find that you'll still get tens of thousands of results. It's a matter of being okay with not getting a perfectly complete solution in order to get results in a timely manner.

As far as fuzzy searching goes, you may be talking about Semantic Web implementations. This is a difficult task, but your refined results may well be superior to another competing site. Take a look into Gate for an idea (it's Java). Essentially, it generates annotations on text blocks that will let you do additional term searches. Once you add stemming and a comprehensive ontology to your annotator, it becomes a very powerful search tool.

I haven't tried switching to NoSQL. I find relational models have more tools and more developers that are comfortable with them. Flattening and distributing data isn't always the best choice, but if you have 10+ systems that can participate in a distributed data model, you may find the searches running faster. That's only if you have the resources to make this happen. Certainly flattening the database with a single server as the data source would be a mistake.

Hope this helps!

  • Once I had added annotations, I created an indexed table of quick lookups of popular stemmed words / phrases in order to optimize the query. With record sets in the millions, tweaks are going to be necessary. – Kieveli Dec 20 '13 at 15:02
  • 1
    Hm, that would mean that certain results will never get shown under some criteria because of the truncation. This is a real problem. – Kenneth Dec 20 '13 at 15:15
  • It is indeed, but how much of one. How often have you looked through 10,000 items on an online shopping catalog. – Kieveli Dec 20 '13 at 16:57
  • Suppose in the first search you cut off 5000 items, and the second query doesn't yield any results. Then you have no results, where maybe in the second cut there were 50 results. That's just wrong, and there's no way to predict that. – Kenneth Dec 20 '13 at 17:17
  • You don't cut off the first query at 5000 items. You cut it off where there is a performance degradation. ~500,000 items. It's about accepting a realistic result vs a 'perfect' answer when you have limited resources. – Kieveli Dec 20 '13 at 17:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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