Django: Nested Queries from Non-Nested Models

Question

I'm trying to figure out the best way to derive a nested menu from a set of non-nested models. Given a layout something like this:

class Beverage(models.Model):
   country = models.ForeignKey(Country,null=True,blank=True)    
   region = models.ForeignKey(Region,null=True,blank=True)
   subregion = models.ForeignKey(SubRegion,null=True,blank=True) 
   in_stock = models.BooleanField()
   ...

The resulting menu will be something like:

France
    Region 1
        Subregion 1
        Subregion 2
    Region 2
        Subregion 3
        Subregion 4
Spain
    ....

No country, region, or subregion should appear in the menu if there are no beverages in it that are not in stock. Because a subregion always belongs to a region and a region always belongs to a country, my initial approach was to nest the models themselves, and only put SubRegion on Beverage. Region and Country would then always be known by the subregion of the beverage. Unfortunately there are too many real-world exceptions to make this viable - wines with a region but not a subregion, etc. So I flattened the layout as above.

The question now is how to derive the menu from this model layout. It's looking like a list of deeply nested querysets is going to be the way to go but that seems computationally expensive and complex code-wise. Is there a cleaner way?

Answer 1

A process that I've used in the past to solve a similar problem is to select all of the items with a single query an order based on country, then region, then subregion. You then loop through the query result and maintain variables pointing to the last id that you saw for country and region. If the next country/region id on the beverage doesn't match the last id, you save off the old list and start a new one. Here's some really rough/messy pythoncode to explain the idea:

beverages = Beverage.objects.order_by('country', 'region', 'subregion')
last_country = -1
menu = []
country_obj = None
for beverage in beverages:
    if beverage.country_id != last_country:
        if country_obj is not None:
            if region_obj is not None:
                if subregion_obj is not None:
                    region_obj['children'].append(subregion_obj)
                country_obj['children'].append(region_obj)
            menu.append(country_obj)
        country_obj = {'name': beverage.country.name, 'children': []}
        last_country = beverage.country_id
        last_region = -1
        region_obj = None
        last_subregion = -1
        subregion_obj = None
    if beverage.region is None:
        country_obj['children'].append(beverage)    
    else:
        if beverage.region_id != last_region:
            if region_obj is not None:
                if subregion_obj is not None:
                    region_obj['children'].append(subregion_obj)
                country_obj['children'].append(region_obj)
            region_obj = {'name': beverage.region.name, 'children': []}
            last_region = beverage.region_id
            last_subregion = -1
            subregion_obj = None
        if beverage.subregion is None:
            region_obj['children'].append(beverage)
        else:
            if beverage.subregion_id != last_subregion:
                if subregion_obj is not None:
                    region_obj['children'].append(subregion_obj)
                subregion_obj = {'name': beverage.subregion.name, 'children': []}
                last_subregion = beverage.subregion_id
            subregion_obj['children'].append(beverage)
if beverage.subregion is not None:
    region_obj['children'].append(subregion_obj)
if beverage.region is not None:
    country_obj['children'].append(region_obj)
menu.append(country_obj)

As you can probably tell, each of the levels has the same logic: check if the id has changed, if it has append the old x_obj and start a new one. The last five lines are to handle the last beverage, since you always save off the previous item during the current iteration (and there's no next iteration for the last item). This is really rough around the edges, but it's the process I've been using to only require one query.

I edited to fix a few bugs I found when I finally got around to running it. It appears to work for my simple test cases.

Answer 2

Two ideas

• To make your first approach work, you could hold GenericForeignKeys to either Country, Region or SubRegion. Or what ever can be identifying the origin. Use limit_choices_to with Q objects to control, what types can be added.

Code:

content_type = models.ForeignKey(ContentType)
object_id = models.PositiveIntegerField()
origin = generic.GenericForeignKey('content_type', 'object_id', 
                                   limit_choices_to = \
                              Q(name='contry', app_label='what ever is the name of the app')| \
                              Q(name='region', app_label='what ever is the name of the app')| \
                              Q(name='subregion', app_label='what ever is the name of the app')')))

• Or my second idea: dont optimize the db-query in first place — use some caching.

  You could first query just the countries, loop over this set and query this country's regions, ... and write the menu in the different loops.

  This leads to many db hits but the code will be quite simple.

  As you wont have this computation done with every site-request, you should write the menu to a global variable. This computation could be don an any save or delete action in the Models that forms the menu. So u could control it by signaling.

  But beware: Signals and global variables work only in process-scope. But maybe the webserver spans several process. Here u could write the menu to the database or to a file and keep timestamps to check, if it is necessary to reload it....

Of course this ideas can be combined

Answer 3

After much fiddling, I believe I've found a working solution that uses very few LOC by building a set of nested dictionaries and lists. I wanted to send real objects to the template, not just strings (basically trying to stay as close as possible to the general queryset methodology as possible). The form of the generated dictionary is:

{
    Country1:{
        region1:[subregion1,subregion2],
        region2:[subregion3,subregion4]
        },
    Country2: {
        region3:[subregion5,subregion6],
        region4:[subregion7,subregion8]    
    },
}

where each of country, region, and subregion is a real object, not a string. Here's the business end (this is in a templatetag). Note that we check for available inventory in each iteration, only setting a dictionary or list item if something is in stock.

regionmenu = {}
for c in Country.objects.all() :
    if Wine.objects.filter(country=c,inventory__gt=0).count() > 0 :
        regionmenu[c] = {}

    for r in c.region_set.all(): 
        if Wine.objects.filter(country=c,region=r,inventory__gt=0).count() > 0 :
            regionmenu[c][r] = []           

        for s in r.subregion_set.all():
            if Wine.objects.filter(country=c,region=r,subregion=s,inventory__gt=0).count() > 0 :
                regionmenu[c][r].append(s)

Dictionaries suit the needs perfectly except you lose the ability to sort, so I'll have to figure out something for alphabetization later.

To iterate through dicts in the template:

<ul>
{% for country, regions in regionmenu.items  %}
    <li>{{ country }} 
        <ul>
        {% for region, subregions in regions.items %}
        <li>{{ region }}
            <ul>
            {% for subregion in subregions %}
                <li>{{ subregion }}</li>
            {% endfor %}
            </ul>
        </li>
        {% endfor %}
        </ul>
    </li>
{% endfor %}
</ul>

Since we passed in objects rather than strings, I can now do URL reversals, get slugs etc. for each item at each level (removed in this example).