Categories
Databases Optimization

Optimizing Django ORM / Postgres queries using left join

For the latest project I’m working on, we’re using Django with Postgres. I was writing some code that had to find a list of objects that weren’t processed yet. The way they were stored in the DB is like so:

class SomeObject(models.Model):
    #some data
 
class ProcessedObjectData(models.Model):
    some_object = models.ForeignKey(SomeObject, db_index = True)
    #some more data

In this schema, SomeObject is the original object, and a ProcessedObjectData row is created as the result of the processing. You might argue that the two tables should be merged together to form a single table, but that is not right in our case: first, SomeObject “has standing on its own”. Second, we are interested in having more than one ProcessedObjectData per one SomeObject.

Given this situation, I was interested in finding all the SomeObject’s that don’t have a certain type of ProcessedObjectData. A relatively easy way to express it (in Python + Django ORM) would be:

SomeObject.objects.exclude(id__in = ProcessedObjectData.objects.filter(...some_filter...).values('some_object_id'))

Unfortunately, while this is reasonable enough for a few thousand rows (takes a few seconds), when you go above 10k and certainly for 100k objects, this starts running slowly. This is an example of a rule of mine:

Code is either fast or slow. Code that is “in the middle” is actually slow for a large enough data-set.

This might not be 100% true, but it usually is and in this case – very much so.

So, how to optimize that? First, you need to make sure that you’re optimizing the right thing. After a few calls to the profiler I was certain that it was this specific query that was taking all of the time. The next step was to write some hand-crafted SQL to solve that, using:

SomeObject.objects.raw(...Insert SQL here...)

As it turns out, it was suggested to me by Adi to use left-join. After reading about it a little bit and playing around with it, I came up with a solution: do a left join in an inner select, and use the outer select to filter only the rows with NULL – indicating a missing ProcessedObjectData element. Here is a code example of how this could look:

SELECT id FROM (
    SELECT some_object.id AS id, processed_object_data.id AS other_id FROM
    some_object
    LEFT JOIN
    processed_object_data
    ON
    (some_object.id = processed_object_data.some_object_id) AND
    (...some FILTER ON processed_object_data...)
) AS inner_select 
WHERE 
inner_select.other_id IS NULL
LIMIT 100

That worked decently enough (a few seconds for 100k’s of rows), and I was satisfied. Now to handling the actual processing, and not the logistics required to operate it.

Categories
Optimization Programming Python

Pyweb-il Presentation on Optimization Slides

Last Monday I gave a presentation in pywebil on optimization, that’s loosely based on my blog post on the same subject. Here are the slides for that presentation.

Categories
Javascript Optimization Programming Projects startup web-design

Javascript Element Creator

Some time ago I was working on optimizing the client side code of my website, plnnr.com, an online trip planner.
This website does automatic trip planning, and the problem was that recalculating trips was slow. After profiling, I found out that most of the time wasn’t actually taken up by the algorithm, but by the UI. Rendering the trip to html was the costly part. The process was like so:

Client-side Javascript code generates new trip prefs -> application calculates new trip -> Client-side Javascript gets the new trip, and creates new html.

It’s important to note that the app is “ajax based”, so the actual trip html was generated by the Javascript code, and not the server. At the time I was using Mochikit to generate the new html. Mochikit has a pretty nifty API for generating html, but it’s quite a bit on the slow side. Basically, this API is a wrapper around createElement.

Well, first I did a little test, and found out that generating html with cloneNode and innerHTML is much faster than createElement. Still, there was a problem – I needed to generate many similar elements – similar but not identical. Consider entries on a trip itinerary – they all look the same, yet each one has a different name, a different time string, and a different onclick event.

What I needed was a Javascript based html template library. My requirements:
1. Speed. Html had to be generated quickly.
2. Expressiveness. It had to be able to create pretty arbitrary html with a given context. For example, an anchor element (<a> tag) with a given href property, and a given text content.
3. References to inner elements: Many elements inside the generated html need various events attached to them, or various code processing. This should be easy to achieve.
4. The library has to allow the template html to be written as html, and not only as javascript strings.

So, I sat down with Benny, and we wrote the Javascript Element Creator, which we are now releasing under the BSD license. I originally wrote it to work with Mochikit and the Sizzle library, and Benny changed his version to worked with jquery.

After adding the code to my project, I got two things: first, everything worked much, much faster. Second, it was much easier changing the generated html when it was generated according to a template, and not directly in code.

Instructions

1. Write your html somewhere visible to the javascript code. Add the “template” class to the upper node, and the id will be the name of the template. For example:

<body>
    <div id="some_div" class="template">
    </div>
</body>

2. Similarly to other template engines, add double brackets to signify where text should be inserted:

<body>
    <div id="some_div" class="template">
        <a href="[[link_url]]">[[link_text]]</a>
    </div>
</body>

3. Create a creator object. It will “collect” your template, and will make it available to your code.

var creator = new ElementCreator();

4. Generate your DOM object, and add it to the document;

var obj = creator.generate("some_div",
                           {link_url: '/url/',
                            link_text: 'hello world'});
appendChildNodes(foo, obj);

The code

We decided to publish for now only the jquery version. I might publish the mochikit version as well at a later date. Since Benny wrote the jquery version, he also wrote the tests for that version.

All in all, the final code is pretty short, and could probably be even shorter. Still, it’s good enough, and gave me a very real performance boost.

Here is the code, have fun with it.

Categories
computer science Design Optimization Programming Python

10 Python Optimization Tips and Issues

Following my previous post on Optimizing Javascript, I thought I’d write a similar post regarding Python optimization.

Categories
Javascript Optimization

Javascript Optimization Tricks

Profiling, Profiling, Profiling

This seems obvious, but still merits a mention. Don’t optimize your code before profiling it. If you need a profiler, just use firebug’s. Having tests to make sure that your post-profiling code is equivalent to the original is also nice.

Later is better than now

As is well known, it is usually useful to have some of the page content to be fetched in the original http get, but have non-essential content fetched using ajax after page-load.

In some cases, user interaction with your website does not require fetching new content, but doing some processing. Generating html is especially slow. In that case, the user will have to wait until the processing is done. Unless of course, you can also ‘postpone it for later’: simply use setTimeout to do the work outside of the even handler.
For example, I used Bill Chadwick’s ArrowLine, which redraws on zoom-in/out. Since the redraw isn’t quick, this makes zooming in pretty slow, especially when quickly zooming more than once.
My solution: since what takes time is drawing the arrows themselves, I put arrow drawing code in a timeout callback, which means the interface doesn’t get unresponsive.

(Of course, this might misbehave, and I had to make sure my code still works if multiple timeouts are enqueued, etc..)

A single div is all you need!

I had to write a dropdown widget for UI, one which could show arbitrary html inside the dropdown box. Problem is, I had to to have a lot of similar dropdowns. This in itself is pretty easy, as we all know how to use a for-loop.
It gets complicated when you find out that adding these dropdowns takes a lot of time. What’s worse, the part that takes time is adding the div that gets displayed when you show it, but is otherwise hidden.

To solve this, first you may apply “Later is better than now”, and create each dropdown only when it’s needed. This will work. In some cases, a different approach is warranted: all of these dropdowns share the same design of the ‘dropdown div’, and only one of these divs will be shown at any time (I had to write code to make sure of it). So, instead of making a new drop-down div for each dropdown, create just one, and let them share it. This might complicate your code, but the rewards may be great.

To make it work, you may use an object factory, or a function that creates widget classes, or any other pattern that works for you.

Categories
web-design

PNG Minification

Following Ned Batchelder’s advice I’ve used pngout to minify the png’s on my startup’s web page.

It took them down from 641,281 bytes to 338,705. This is quite a nice return for the effort of a download and a single command line:

for %i in (*.png) do pngout “%i”