Proposal to add new kwarg, "distinct_parents", to  "_get_queryset_relatives"

``distinct_parents``

Let's start with an example:

``models.py``

    from django.db import models
    from mptt.models import TreeForeignKey, MPTTModel
    
    class Directory(MPTTModel):
        parent = TreeForeignKey(
            'self',
            null = True,
            blank = True,
            related_name = 'children')
    
        path = models.CharField(
            max_length = 255)
    
        def __unicode__(self):
            return self.path
    
    
    class File(models.Model):
        parent = models.ForeignKey(
            Directory,
            null = True,
            blank = True,
            related_name = 'files')
    
        path = models.CharField(
            max_length = 255)
    
        def __unicode__(self):
            return self.path



Our dataset is a recursive listing of all files and directories contained within ``/var`` taken from a random Ubuntu workstation. I used the following snippet to create this dataset:

	import os
	from myapp.filesanddirectories.models import *

	for root, directories, files in os.walk('/var'):
    	parent_dir, created = Directory.objects.get_or_create(path = root)
	    for directory in directories:
        	path = os.path.join(root, directory)
	        print path
        	object, created = Directory.objects.get_or_create(path = path, parent = parent_dir)
	        if created:
        	    print("CREATED: %s" % path)
	    for file in files:
        	path = os.path.join(root, file)
        	print path
        	object, created = File.objects.get_or_create(path = path, parent = parent_dir)
        	if created:
        	     print("CREATED: %s" % path)


Let's say that you want to generate a queryset that contains all of the directories whose descendants contain files that end with ``.gif``. This seems simple enough:

    Directory.objects.filter(files__path__endswith = ".gif")
    
But what if, instead of just getting the list of directories that contain files ending with ``.gif``, you wanted the ancestors of those directories who belong to a specific parent?

    parent_dir = Directory.objects.get(path = '/var/cache/ruby-rvm')
    Directory.objects.get_queryset_ancestors(Directory.objects.filter(files__path__endswith = ".gif")).filter(parent = parent_dir)
    
This works, but it produces the following ``Q`` object in order to execute the query:

``(OR: (AND: (u'rght__gt', 435), (u'lft__lt', 434), (u'tree_id', 1)), (AND: (u'rght__gt', 439), (u'lft__lt', 438), (u'tree_id', 1)), (AND: (u'rght__gt', 439), (u'lft__lt', 438), (u'tree_id', 1)), (AND: (u'rght__gt', 439), (u'lft__lt', 438), (u'tree_id', 1)), (AND: (u'rght__gt', 439), (u'lft__lt', 438), (u'tree_id', 1)), (AND: (u'rght__gt', 439), (u'lft__lt', 438), (u'tree_id', 1)), (AND: (u'rght__gt', 439), (u'lft__lt', 438), (u'tree_id', 1)), (AND: (u'rght__gt', 439), (u'lft__lt', 438), (u'tree_id', 1)), (AND: (u'rght__gt', 439), (u'lft__lt', 438), (u'tree_id', 1)), (AND: (u'rght__gt', 439), (u'lft__lt', 438), (u'tree_id', 1)), (AND: (u'rght__gt', 439), (u'lft__lt', 438), (u'tree_id', 1)), (AND: (u'rght__gt', 439), (u'lft__lt', 438), (u'tree_id', 1)), (AND: (u'rght__gt', 439), (u'lft__lt', 438), (u'tree_id', 1)), (AND: (u'rght__gt', 439), (u'lft__lt', 438), (u'tree_id', 1)), (AND: (u'rght__gt', 439), (u'lft__lt', 438), (u'tree_id', 1)), (AND: (u'rght__gt', 439), (u'lft__lt', 438), (u'tree_id', 1)), (AND: (u'rght__gt', 439), (u'lft__lt', 438), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 460), (u'lft__lt', 459), (u'tree_id', 1)), (AND: (u'rght__gt', 460), (u'lft__lt', 459), (u'tree_id', 1)), (AND: (u'rght__gt', 460), (u'lft__lt', 459), (u'tree_id', 1)), (AND: (u'rght__gt', 460), (u'lft__lt', 459), (u'tree_id', 1)), (AND: (u'rght__gt', 460), (u'lft__lt', 459), (u'tree_id', 1)), (AND: (u'rght__gt', 460), (u'lft__lt', 459), (u'tree_id', 1)), (AND: (u'rght__gt', 460), (u'lft__lt', 459), (u'tree_id', 1)), (AND: (u'rght__gt', 460), (u'lft__lt', 459), (u'tree_id', 1)), (AND: (u'rght__gt', 460), (u'lft__lt', 459), (u'tree_id', 1)), (AND: (u'rght__gt', 460), (u'lft__lt', 459), (u'tree_id', 1)), (AND: (u'rght__gt', 460), (u'lft__lt', 459), (u'tree_id', 1)), (AND: (u'rght__gt', 460), (u'lft__lt', 459), (u'tree_id', 1)), (AND: (u'rght__gt', 460), (u'lft__lt', 459), (u'tree_id', 1)), (AND: (u'rght__gt', 460), (u'lft__lt', 459), (u'tree_id', 1)), (AND: (u'rght__gt', 460), (u'lft__lt', 459), (u'tree_id', 1)), (AND: (u'rght__gt', 460), (u'lft__lt', 459), (u'tree_id', 1)), (AND: (u'rght__gt', 460), (u'lft__lt', 459), (u'tree_id', 1)), (AND: (u'rght__gt', 460), (u'lft__lt', 459), (u'tree_id', 1)), (AND: (u'rght__gt', 460), (u'lft__lt', 459), (u'tree_id', 1)), (AND: (u'rght__gt', 460), (u'lft__lt', 459), (u'tree_id', 1)), (AND: (u'rght__gt', 460), (u'lft__lt', 459), (u'tree_id', 1)), (AND: (u'rght__gt', 460), (u'lft__lt', 459), (u'tree_id', 1)), (AND: (u'rght__gt', 460), (u'lft__lt', 459), (u'tree_id', 1)), (AND: (u'rght__gt', 460), (u'lft__lt', 459), (u'tree_id', 1)), (AND: (u'rght__gt', 460), (u'lft__lt', 459), (u'tree_id', 1)), (AND: (u'rght__gt', 460), (u'lft__lt', 459), (u'tree_id', 1)), (AND: (u'rght__gt', 460), (u'lft__lt', 459), (u'tree_id', 1)), (AND: (u'rght__gt', 460), (u'lft__lt', 459), (u'tree_id', 1)), (AND: (u'rght__gt', 460), (u'lft__lt', 459), (u'tree_id', 1)), (AND: (u'rght__gt', 460), (u'lft__lt', 459), (u'tree_id', 1)), (AND: (u'rght__gt', 460), (u'lft__lt', 459), (u'tree_id', 1)), (AND: (u'rght__gt', 460), (u'lft__lt', 459), (u'tree_id', 1)), (AND: (u'rght__gt', 464), (u'lft__lt', 463), (u'tree_id', 1)), (AND: (u'rght__gt', 464), (u'lft__lt', 463), (u'tree_id', 1)), (AND: (u'rght__gt', 464), (u'lft__lt', 463), (u'tree_id', 1)), (AND: (u'rght__gt', 464), (u'lft__lt', 463), (u'tree_id', 1)), (AND: (u'rght__gt', 464), (u'lft__lt', 463), (u'tree_id', 1)), (AND: (u'rght__gt', 464), (u'lft__lt', 463), (u'tree_id', 1)), (AND: (u'rght__gt', 464), (u'lft__lt', 463), (u'tree_id', 1)), (AND: (u'rght__gt', 464), (u'lft__lt', 463), (u'tree_id', 1)), (AND: (u'rght__gt', 464), (u'lft__lt', 463), (u'tree_id', 1)), (AND: (u'rght__gt', 464), (u'lft__lt', 463), (u'tree_id', 1)), (AND: (u'rght__gt', 464), (u'lft__lt', 463), (u'tree_id', 1)), (AND: (u'rght__gt', 464), (u'lft__lt', 463), (u'tree_id', 1)), (AND: (u'rght__gt', 464), (u'lft__lt', 463), (u'tree_id', 1)), (AND: (u'rght__gt', 464), (u'lft__lt', 463), (u'tree_id', 1)), (AND: (u'rght__gt', 464), (u'lft__lt', 463), (u'tree_id', 1)), (AND: (u'rght__gt', 464), (u'lft__lt', 463), (u'tree_id', 1)), (AND: (u'rght__gt', 464), (u'lft__lt', 463), (u'tree_id', 1)), (AND: (u'rght__gt', 464), (u'lft__lt', 463), (u'tree_id', 1)), (AND: (u'rght__gt', 464), (u'lft__lt', 463), (u'tree_id', 1)), (AND: (u'rght__gt', 464), (u'lft__lt', 463), (u'tree_id', 1)), (AND: (u'rght__gt', 464), (u'lft__lt', 463), (u'tree_id', 1)), (AND: (u'rght__gt', 464), (u'lft__lt', 463), (u'tree_id', 1)), (AND: (u'rght__gt', 464), (u'lft__lt', 463), (u'tree_id', 1)), (AND: (u'rght__gt', 464), (u'lft__lt', 463), (u'tree_id', 1)), (AND: (u'rght__gt', 464), (u'lft__lt', 463), (u'tree_id', 1)), (AND: (u'rght__gt', 468), (u'lft__lt', 467), (u'tree_id', 1)), (AND: (u'rght__gt', 468), (u'lft__lt', 467), (u'tree_id', 1)), (AND: (u'rght__gt', 468), (u'lft__lt', 467), (u'tree_id', 1)), (AND: (u'rght__gt', 468), (u'lft__lt', 467), (u'tree_id', 1)), (AND: (u'rght__gt', 468), (u'lft__lt', 467), (u'tree_id', 1)), (AND: (u'rght__gt', 468), (u'lft__lt', 467), (u'tree_id', 1)), (AND: (u'rght__gt', 468), (u'lft__lt', 467), (u'tree_id', 1)), (AND: (u'rght__gt', 468), (u'lft__lt', 467), (u'tree_id', 1)), (AND: (u'rght__gt', 468), (u'lft__lt', 467), (u'tree_id', 1)), (AND: (u'rght__gt', 468), (u'lft__lt', 467), (u'tree_id', 1)), (AND: (u'rght__gt', 468), (u'lft__lt', 467), (u'tree_id', 1)), (AND: (u'rght__gt', 472), (u'lft__lt', 471), (u'tree_id', 1)), (AND: (u'rght__gt', 472), (u'lft__lt', 471), (u'tree_id', 1)), (AND: (u'rght__gt', 472), (u'lft__lt', 471), (u'tree_id', 1)), (AND: (u'rght__gt', 472), (u'lft__lt', 471), (u'tree_id', 1)), (AND: (u'rght__gt', 472), (u'lft__lt', 471), (u'tree_id', 1)), (AND: (u'rght__gt', 472), (u'lft__lt', 471), (u'tree_id', 1)), (AND: (u'rght__gt', 472), (u'lft__lt', 471), (u'tree_id', 1)), (AND: (u'rght__gt', 472), (u'lft__lt', 471), (u'tree_id', 1)), (AND: (u'rght__gt', 472), (u'lft__lt', 471), (u'tree_id', 1)), (AND: (u'rght__gt', 472), (u'lft__lt', 471), (u'tree_id', 1)), (AND: (u'rght__gt', 472), (u'lft__lt', 471), (u'tree_id', 1)), (AND: (u'rght__gt', 472), (u'lft__lt', 471), (u'tree_id', 1)), (AND: (u'rght__gt', 472), (u'lft__lt', 471), (u'tree_id', 1)), (AND: (u'rght__gt', 472), (u'lft__lt', 471), (u'tree_id', 1)), (AND: (u'rght__gt', 472), (u'lft__lt', 471), (u'tree_id', 1)), (AND: (u'rght__gt', 472), (u'lft__lt', 471), (u'tree_id', 1)), (AND: (u'rght__gt', 472), (u'lft__lt', 471), (u'tree_id', 1)), (AND: (u'rght__gt', 472), (u'lft__lt', 471), (u'tree_id', 1)), (AND: (u'rght__gt', 472), (u'lft__lt', 471), (u'tree_id', 1)), (AND: (u'rght__gt', 472), (u'lft__lt', 471), (u'tree_id', 1)), (AND: (u'rght__gt', 472), (u'lft__lt', 471), (u'tree_id', 1)), (AND: (u'rght__gt', 472), (u'lft__lt', 471), (u'tree_id', 1)), (AND: (u'rght__gt', 472), (u'lft__lt', 471), (u'tree_id', 1)), (AND: (u'rght__gt', 472), (u'lft__lt', 471), (u'tree_id', 1)), (AND: (u'rght__gt', 472), (u'lft__lt', 471), (u'tree_id', 1)), (AND: (u'rght__gt', 472), (u'lft__lt', 471), (u'tree_id', 1)), (AND: (u'rght__gt', 472), (u'lft__lt', 471), (u'tree_id', 1)), (AND: (u'rght__gt', 472), (u'lft__lt', 471), (u'tree_id', 1)), (AND: (u'rght__gt', 472), (u'lft__lt', 471), (u'tree_id', 1)), (AND: (u'rght__gt', 472), (u'lft__lt', 471), (u'tree_id', 1)), (AND: (u'rght__gt', 472), (u'lft__lt', 471), (u'tree_id', 1)), (AND: (u'rght__gt', 478), (u'lft__lt', 477), (u'tree_id', 1)), (AND: (u'rght__gt', 478), (u'lft__lt', 477), (u'tree_id', 1)), (AND: (u'rght__gt', 478), (u'lft__lt', 477), (u'tree_id', 1)), (AND: (u'rght__gt', 478), (u'lft__lt', 477), (u'tree_id', 1)), (AND: (u'rght__gt', 478), (u'lft__lt', 477), (u'tree_id', 1)))``
    
And it takes about 0.025 seconds to execute. But we don't really need a ``Q`` object that complicated in order to filter for the ancestors of directories containing ``.gif`` files that belong to a specific parent. For this purpose, much of what is contained in the ``Q`` object above is redundant, because in order to determine whether a directory should appear in the dataset, it only has to have *one* child that matches our initial filter (``files__path__endswith = ".gif"``). So that's where the ``distinct_parents`` kwarg shines:

	Directory.objects.get_queryset_ancestors(Directory.objects.filter(files__path__endswith = ".gif"), distinct_parents = True).filter(parent = parent_dir)

That produces a much smaller ``Q`` object:

``(OR: (AND: (u'rght__gt', 435), (u'lft__lt', 434), (u'tree_id', 1)), (AND: (u'rght__gt', 439), (u'lft__lt', 438), (u'tree_id', 1)), (AND: (u'rght__gt', 452), (u'lft__lt', 451), (u'tree_id', 1)), (AND: (u'rght__gt', 460), (u'lft__lt', 459), (u'tree_id', 1)), (AND: (u'rght__gt', 464), (u'lft__lt', 463), (u'tree_id', 1)), (AND: (u'rght__gt', 468), (u'lft__lt', 467), (u'tree_id', 1)), (AND: (u'rght__gt', 472), (u'lft__lt', 471), (u'tree_id', 1)), (AND: (u'rght__gt', 478), (u'lft__lt', 477), (u'tree_id', 1)))``

And the whole operation takes 0.015. Those tiny increments of time add up. Furthermore, trimming the number of SQL variables required to make the query lowers the risk of hitting the limit of allowed variables in database backends such as sqlite, where the limit is 999.

This is all fine and good but you need to be cautious when using ``distinct_parents`` because most of the time simply writing a better query will avoid use cases where ``distinct_parents`` appears to be necessary. But for those other times, when there is just no better way to query your data, the ``distinct_parents`` kwarg can be indispensable.

But what about ``get_queryset_descendants``? It can be used here too, but the effect isn't as drastic:

	Directory.objects.get_queryset_descendants(Directory.objects.filter(path__contains = "backbone")).filter(parent__path__contains = "test")

This is the ``Q`` object generated by the above query (without ``distinct_parents``):

``(OR: (AND: (u'lft__gt', 79), (u'tree_id', 1), (u'rght__lt', 94)), (AND: (u'lft__gt', 80), (u'tree_id', 1), (u'rght__lt', 89)), (AND: (u'lft__gt', 81), (u'tree_id', 1), (u'rght__lt', 82)), (AND: (u'lft__gt', 83), (u'tree_id', 1), (u'rght__lt', 84)), (AND: (u'lft__gt', 85), (u'tree_id', 1), (u'rght__lt', 86)), (AND: (u'lft__gt', 87), (u'tree_id', 1), (u'rght__lt', 88)), (AND: (u'lft__gt', 90), (u'tree_id', 1), (u'rght__lt', 91)), (AND: (u'lft__gt', 92), (u'tree_id', 1), (u'rght__lt', 93)))``


And here's what it looks like when ``distinct_parents = True``:

	Directory.objects.get_queryset_descendants(Directory.objects.filter(path__contains = "backbone"), distinct_parents = True).filter(parent__path__contains = "test")

``(OR: (AND: (u'lft__gt', 79), (u'tree_id', 1), (u'rght__lt', 94)), (AND: (u'lft__gt', 80), (u'tree_id', 1), (u'rght__lt', 89)), (AND: (u'lft__gt', 81), (u'tree_id', 1), (u'rght__lt', 82)), (AND: (u'lft__gt', 90), (u'tree_id', 1), (u'rght__lt', 91)))``

So there's a slight reduction in the number of variables that end up in your SQL query.


Summary
=======

``distinct_parents`` is intended to assist with those use cases where you want to build a queryset of objects based on the attributes of the descendants of those objects. I've used the file/directory paradigm in the above examples because it most easily demonstrates when and why you may need this functionality. It is no replacement for well-structured queries!