CODEWITHSUNDEEP
pythondjangotreehierarchical-data
Chema
Chema

Reputation: 745

Efficient way to filter a hierarchical structure in Django?

I have a simple hierarchical model, 3 turtles high. Let's say Artist, Album, Song. What would be an efficient way to filter the resulting tree in my view?

To get an Artist/Album/Song tree to pass to my template, filtered with an arbitrary condition, I'm currently doing something like:

for current_artist in Artist.objects.filter(album__song__genre='funkadelic mariachi').distinct():
    yield current_artist

    for current_album in Album.objects.filter(song__genre='funkadelic mariachi').distinct():
        yield current_album

        for current_song in Song.objects.filter(genre='funkadelic mariachi'):
            yield current_song

        yield 'End of album'
    yield 'End of artist'

But I'm pretty certain there must be a much more efficient way than querying all the way to the leaves in every level, unless distinct() and Django's optimisations provide some magical cache from the other side of the rainbow.

Perhaps creating a whole tree (v.g. with every artist and album, not checking for leaves), and then pruning the leafless branches? Or should I be looking at select_related()?

For extra points, some actual test/benchmark/write-up would be welcome. Danke!

P.S: I know of django-mptt's goodness, but it's overkill for this.

The detailed model is not important, as I'm looking for a general solution, but it could be something like:

class Artist:
    name = models.CharField(max_length=200)

class Album:
    name = models.CharField(max_length=200)
    artist = models.ForeignKey(Artist, on_delete=models.CASCADE)

class Song:
    name = models.CharField(max_length=200)
    album= models.ForeignKey(Album, on_delete=models.CASCADE)
    genre = models.CharField(max_length=200)

Upvotes: 0

Views: 1076

Answers (1)

Chema
Chema

Reputation: 745

I ended up with the following:

filters = { "genre": 'funkadelic mariachi' }
artist = None
album = None
result = []

# select_related() fetches our chosen songs, and their albums and artists, in a single query
for song in Song.objects.select_related(
        'album__artist').filter(**filters):

    if album != song.album and album != None:
        result.append('End of Album')

    if artist != song.album.artist:
        if artist != None:
            result.append('End of Artist')
        artist = song.album.artist
        result.append(artist)

    if album != song.album:
        album = song.album
        result.append(album)

    result.append(song)

if result:
    result.append('End of Album')
    result.append('End of Artist')

Not so pretty, but much more efficient. Perhaps prefetch_related() would allow to keep the three loops, using Prefetch('artist', to_attr='filtered_artists') or so, but with one extra query per turtle.

Upvotes: 1

Related Questions