sql/query.py add_q refactoring

[Anssi Kääriäinen]

I have worked on refactoring sql/query.py add_q. There are three reasons for doing this:

1. It was hard to see what was happening in add_q previously. I hope I have improved this situation.
2. The responsibilities in the code were not well divided. add_filter for example did some work that add_q normally does, but only in case when the filter was to the having clause.
3. The add_q resulted in inefficient where node structure.

It turned out that the django/utils/tree.py tree structure was hard to use. So that is also refactored. Finally where.as_sql got some refactoring.

The refactoring already resulted in some other cleanups around the code, for example sql/query.py combine() is now cleaner in its hadling of the where clause.

The first two changes are best explained by reading the patch. However I can give some examples of why no. 3 is important. First consider query M.objects.exclude(pk=1). Previously this would have generated the following where tree:

AND:
  AND:
    NOT AND:
      AND:
        pk=1

And now:

AND:
   NOT AND:
     pk=1

The query M.objects.filter(pk=1).filter(pk=2).filter(pk=3) would generate:

AND: 
   AND:
     pk=1 
   AND:
     pk=2
   AND:
     pk=3

And now:

AND:
  pk=1
  pk=2
  pk=3

Finally, the query User.objects.filter(~Q(pk=1)&~Q(Q(pk=3)|Q(pk=2))) did create:

AND: 
  AND: 
    AND: 
      NOT AND: 
        AND:
          pk=1 
  AND:
    NOT
      AND:
        OR:
          AND:
            pk=3
        OR:
          pk=2

And now:

AND:
  NOT AND:
    pk=1
  NOT AND:
    OR:
      pk=3
      pk=2

Some performance numbers, two tests:

#Test 1
for i in range(0, 1000):
    qs = M.objects.filter(pk=1)
# Test2
qs = M.objects.all()
for i in range(0, 200):
    qs = qs.filter(pk=1)

Results before:
0:00:00.326911
0:00:02.265825
Results after:
0:00:00.193199
0:00:00.086636

So, about 35% faster and about 25x faster. The patch includes deepcopy removal for qs.clone(), and large part of the performance gain is from there.

All tests passed, though I had to fix one test.

There would be still further work, but I wanted to keep this at least somewhat restricted. Even more restricted is hard to do, as the tree and where node restructuring would mean refactoring the add_q anyways.

This ticket is related to #16759, but as this goes deeper in scope, I have created another ticket for this.

[Anssi Kääriäinen]

For those interested in this ticket, there is even more radical patch in #17025. I will all three ticket open, as any of the three approaches might be the one chosen by Django's core developers. The #16759 is low risk, this doesn't touch too much on WhereNode internals, while #17025 does pretty total refactor of WhereNode. My suggestion is that if you test anything, test #17025, it has the highest potential and is my favorite.

[Anssi Kääriäinen]

I have a branch at github which does some refactoring to the django/utils/tree.py and to add_q(). There are a couple of reasons why I see some change is needed here:

1. add_q() is hard to understand
2. add_q() produces inefficient trees, which results in query.clone() overhead, and as_sql() overhead
3. add_q() and add_filter(), and WhereNode.as_sql() only work if the boolean tree is formed just like it is currently done in add_q(). When using general boolean trees, the WhereNode.as_sql() falls down for example (see pull request: ​https://github.com/django/django/pull/92)
4. the utils/tree.py contains some hard-to-use methods. More specifically the .negate() method which isn't the same as changing self.negated, and the start_subtree()/end_subtree() which prevents holding a reference to a certain node of the tree. Do a_node.start_subtree(), then the a_node is mutated in place and made empty and it will be a children of a new node b_node, which essentially contains a_node
5. the refactoring fixes some bugs, see the added tests

Even the new version isn't as clean as I would like, but cleaning it up more will lead to unmanageable amount of changes. I don't particularly like the path argument from add_q() to add_filter() and would like to invent a cleaner solution here. The solution seems to be to just maintain one boolean tree up until execution stage, and split the tree into where and having at that stage.

The work is available from ​https://github.com/akaariai/django/compare/refactor_utils_tree. Note that the idea is to make the logic easier to follow. If reviewing this, it is important that the new logic must be easier to understand than the current logic or there isn't much point in the work. It is hard for me to see if the new logic is easier to understand to others.

[Anssi Kääriäinen]

Actually, the correct approach might not be to defer the where/having splitting to execution stage. Maybe it is to have an additional preprocess stage before add_q instead.

The problem is that currently we are going into the q-objects blind. This causes multiple issues: We might stumble upon aggregates (at which point we must have the path information available to produce correctly negated having tree), or we might stumble upon multi-joins (we use the except MultiJoin in this case currently, and this isn't the cleanest of approaches), or we might stumble upon filters that produce additional filters (extra_filters, and the need to keep a fresh AND node constantly at hand for this possibility, and the mutual recursion between setup_joins() and add_filter()).

If we pre-processed the q-objects (travelled the lookup paths in the q-objects, and checked what there is to expect) then the add_q where/having logic would be much easier to refactor, the MultiJoin case would be cleaner, and the extra_filters would be trivial to handle. The benefits seem clear. Of course, without actual code many ideas seem great... I definitely think this approach is worth investigating a lot closer before proceeding further in this ticket. The start is to handle the where/having split. The checking for extra_filters and MultiJoin needs much larger changes.

[Anssi Kääriäinen]

I used the above idea and now I have something clean and nice implemented. Same branch as above. The patch needs some cleanup still, but otherwise it is pretty much ready. If nothing else, check the new add_q and _add_q implementations. Now, that is cleaner than before, right?

When committing this, the correct approach is to first commit the wherenode.as_sql() refactoring ​https://github.com/django/django/pull/92, then rebase this patchset on that work.

I removed a short-cut of "any object having 'add_to_query' attribute will can add itself directly to the query". This isn't tested or documented, and to me it seems any such add_to_query object must use deep internals of the ORM, and has been likely broken multiple times already since its introduction. Any objections of removing this?

The patch seems to be little faster than before using djangobench. query_filter_chaining is around 5-10% faster, other query operations maybe 2-3% faster and query_in_bulk around 5% slower. The reason for in_bulk slowdown is that it now uses public APIs instead of internal APIs of the inner query class. The test in djangobench is for fetch one object by using in_bulk and is hardly relevant for any real use case anyways. If the fetch was for 10 objects, I doubt if there would be any significant speed difference.

After this gets committed, a larger refactor of the lookup system could be the next step.

[Anssi Kääriäinen]

Requesting a review for ​https://github.com/akaariai/django/commits/refactor_utils_tree. The patch is somewhat large, and I can split it to smaller pieces if required. Below I will list the main portions of the patch.

Refactor django.utils.tree: The django.utils.tree refactor isn't absolutely needed, but the tree API has two issues I find confusing: the start_subtree/end_subtree which prevents one from keeping reference to a node (do node.start_subtree() and the node will be emptied of data, and get a new subtree_parent containing the data the node contained before), and then there is node.negate() - which isn't the same thing as using the variable node.negated. If you think the utils.tree should be left alone, then I can rework the patch to work without the refactor, too.

For the add_q part of the refactor the idea is to do cleanup & bug fixes. A major reason for this is to make the add_q easier to understand. Check it, if it isn't easier to understand to you, then it is a failure worth fixing. Also, the add_q handles now negated lookups better, and it produces cleaner trees. There is also some DRYer logic for handling aggregates.

The where.as_sql() part has a different patch which I think I will commit soon. This is just a cleanup to make sure it handles better some corner cases. See: ​https://github.com/django/django/pull/92. I will then rebase the refactor_utils_tree on this, so you can ignore the where.as_sql() parts of the above branch.

I will mark this ticket as accepted on basis of ​http://groups.google.com/group/django-developers/browse_thread/thread/e0f1ed71a7f61958.

[Anssi Kääriäinen]

For the record, I think the patch is still too complex. This needs one more go to get the complexities sorted out.

[Anssi Kääriäinen]

This was fixed in d3f00bd5706b35961390d3814dd7e322ead3a9a3.