At what point is querying down a hierarchical tree faster than querying through all the end nodes?

[Sanket More]

Hello! I am having so much trouble understanding datastore queries!
This is my problem.
I can't seem to figure out whether querying from the top of a tree down to a end node is faster than querying through all end nodes.
I don't care about write cost or about transactions, I just want to know what would be faster.

Here is an example of what I mean.
Lets say I have stored all the restaurants in a country through a database hierarchy.
Level 0 is the world.
Level 1 are the countries.
Level 2 are the states.
Level 3 are the cities
Level 4 are the restaurants

Now my users want to search for information about a particular restaurant and give me the country state city and restaurant name.

Would it be faster for me to save the country, state, city and restaurant at level 4 and then query through all restaurants for a match? OR
Would it be faster for me to search the country for all children states, pick the state I want, search the state for cities, pick the city I want, and essentially narrow it down to the restaurant?

Because I feel that with option one, I would end up linearly increasing the time my requests take and that's just not good.
And with option two, it feels like I would end up having to run multiple queries to find all the children of each level and then pick the child I want. Do I really need to run that many queries?

A perfect solution for me would be one query that allows me to search through the tree and get to the node I want. Is that possible?

Please respond even if I am unclear, I will appreciate literally any help you can give me.

[Nick]

The general rule is optimize for your primary use case, denormalise to support others.
In addition, enforce and support constraints In your code.

If your primary case is restaurant search, embed and index all necessary data. This will be the fastest solution and easiest to work with

On Appengine extra data doesn't cost you unless it's indexed. There is a careful balance between optimising for speed, cost and transactional integrity. My advice is if this is your first go, expect to make mistakes and to need to reengineer your data a couple of times. Make that process as easy as possible.

[Sanket More]

Hey Nick!

After I submitted my question, I went through lots of information sources and gathered some information.
I feel like my question was based on many misconceptions about google app engine's datastore.

I think I have a strategy for the restaurant problem.
The user will provide me with country, state, city and the restaurant name, And I will provide the user with location(s).
So all I really need is one specific entity and the response will simply be the information in that entity.
And, I don't really need to index country, state, city, and restaurant name with each other independently. I just need one string that holds the country state city and restaurant.
In fact, I think that string is unique.
So, I am thinking about having a restaurant kind with key string "country_state_city_restaurant"

Once the user has finished submitting the form, I can get by "country_state_city_restaurant" and return some information to the user.

I wanted a smarter solution than this, because I feel that this solution won't scale well.
Furthermore, if I am flattening my tree structure like this, wouldn't gql be faster?

[David Skinner]

In classic terms:

• World is a List of Countries unique
• Country is a list of States in a Country one-to-many
• States is a list of Cities in a State one-to-many
• Names is a list of Restaurant Names unique
• Restaurant is Country.State.City.Name Address Data, many-to-many Names-to-City

A valid search may begin with the Name or the Country. Select one from the list of available.

If you select a Name first, the the selection of a country would be limited to the set that is linked to the Name.

If you select Country first then Name selection would be limited to Names linked to that Country And States would be limited to those linked to that Country and to that Name.

valid City selection would be a City linked to that State which is also linked to that Name.

The alternative of having the user enter all four fields at once will encourage searching for things not in the database and may require a data validation step to account for variations in spellings.

The advantage of data normalization, extremely rapid searches and very small memory as you need save only the id, although in modern times, you may not need be concerned with micro efficiency as the underlying engines will tend to optimise segmented index fields. 

I do like the idea of maintaining a segmented key with Country, State, City so that you can display intermediate results or an intermediate count of a large list of results.
  

[Karl MacMillan]

Just a suggestion - have you thought about letting the user query through the Google maps or similar API to find the restaurants and then based on those results returning information from your app? These location based queries are hard - both technically and from matching the users expectations. Especially as I'm betting that the city that a user thinks a restaurant is located in often differs from official addresses, especially in large cities.

This strategy could let you both control the user experience and leverage the hard work of others. 

Karl

 

--
You received this message because you are subscribed to the Google Groups "Google App Engine" group.
To unsubscribe from this group and stop receiving emails from it, send an email to google-appengi...@googlegroups.com.
To post to this group, send email to google-a...@googlegroups.com.
Visit this group at http://groups.google.com/group/google-appengine.
To view this discussion on the web visit https://groups.google.com/d/msgid/google-appengine/04705cc7-3673-4d82-984a-61c64b099fe8%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Sanket More]

Hey Karl!

I definitely would leverage Google's API for this problem, but I actually was more interested in the approach for this hierarchical type of problem.
To flatten or not to flatten, that is the question!
But yes, APis would allow me to check for user error when it comes to cities and such.
I think my current format doesn't allow me to figure this out efficiently.
I would need to get the city, find neighbouring cities and then find restaurants in those cities.

Actually, I could submit their original query and ask some other api for nearby cities.
Once I got cities I could also run queries for the same restaurant name in those neighbouring cities.

Even better I think, would be when I create my restaurant information, I find the neighbouring cities using some other API, and create restauants there pointing back to the correct city...
For instance City 1 and City2 are close to each other.
When I put a restaurant via, Country, State, City1.Restaurant, I could also run a query through some other api for neighbouring cities.
Once I get that information I could put the restaurant information into, Country, State, City2, Restaurant.
Then if someone screws up and searches Country,State.City2.Restaurant instead of the correct City1 alternative, I would still be able to give them information that points back to the correct city.
This means extra time for creating data, but hopefully less for searching through it.

Thanks Karl!

On Monday, August 17, 2015 at 5:41:25 PM UTC-7, Karl MacMillan wrote:

On Sunday, August 16, 2015, Sanket More <sanke...@gmail.com> wrote:

Hey Nick!

After I submitted my question, I went through lots of information sources and gathered some information.
I feel like my question was based on many misconceptions about google app engine's datastore.

I think I have a strategy for the restaurant problem.
The user will provide me with country, state, city and the restaurant name, And I will provide the user with location(s). 

So all I really need is one specific entity and the response will simply be the information in that entity.
And, I don't really need to index country, state, city, and restaurant name with each other independently. I just need one string that holds the country state city and restaurant.
In fact, I think that string is unique.
So, I am thinking about having a restaurant kind with key string "country_state_city_restaurant"

Once the user has finished submitting the form, I can get by "country_state_city_restaurant" and return some information to the user.

I wanted a smarter solution than this, because I feel that this solution won't scale well.
Furthermore, if I am flattening my tree structure like this, wouldn't gql be faster?


On Sunday, August 16, 2015 at 4:14:33 PM UTC-7, Nick wrote:

The general rule is optimize for your primary use case, denormalise to support others.
In addition, enforce and support constraints In your code.

If your primary case is restaurant search, embed and index all necessary data. This will be the fastest solution and easiest to work with

On Appengine extra data doesn't cost you unless it's indexed. There is a careful balance between optimising for speed, cost and transactional integrity. My advice is if this is your first go, expect to make mistakes and to need to reengineer your data a couple of times. Make that process as easy as possible.

Just a suggestion - have you thought about letting the user query through the Google maps or similar API to find the restaurants and then based on those results returning information from your app? These location based queries are hard - both technically and from matching the users expectations. Especially as I'm betting that the city that a user thinks a restaurant is located in often differs from official addresses, especially in large cities.

This strategy could let you both control the user experience and leverage the hard work of others. 

Karl

 

--
You received this message because you are subscribed to the Google Groups "Google App Engine" group.

To unsubscribe from this group and stop receiving emails from it, send an email to google-appengine+unsubscribe@googlegroups.com.
To post to this group, send email to google-appengine@googlegroups.com.

[husayt]

My advice is to not use queries for search. appengine queries are good for set known of specific preset requests. Restaurant search can have too variations and to design a query to cater for all possible search options would not be the best investment for your time. Instead, use what Appengine already has for this usecase: Text Search

Plus, with this you could cater for partial search as well.

[Nick]

Having given my view on structuring, I'll give me opinion on the problem.

You're attempting to store information which at some point will be queryable on a wide variety of criteria, from spatially, cuisines, partial names matches etc. I would design a solution that respects these potential problems, but doesn't necessarily cater for them.

Assuming you're building a product that succeeds, it's a fair assumption you'll end up using elastic search (or something similar) at the end of the day.

A good bridging gap for this is the full text search API, but it does have severe limitations which you will outgrow. You'll probably hack around them for a while first to keep your architecture with minimal moving pieces.

I can almost guarantee you'll hit the edges of an indexed datastore entity very quickly. Composite keys are a killer for complexity, and will be required on any faceted search as soon as you permit sorting.

I have actually done this before (specifically restaurant search), I was able to make assumptions about the locations based on the user, so they only had to supply suburb name.

With a discrete list of cuisines and interesting factors (vegetarian, disabled access etc) the search api was enough.

Introducing distance (restaurants within 10km of me) it was not, so that was the cutover point.