How can I make my code more efficient?

Question

I have a list of tuples that contains a tool_id, a time, and a message. I want to select from this list all the elements where the message matches some string, and all the other elements where the time is within some diff of any matching message for that tool.

Here is how I am currently doing this:

# record time for each message matching the specified message for each tool 
messageTimes = {} 
for row in cdata:   # tool, time, message 
    if self.message in row[2]: 
        messageTimes[row[0], row[1]] = 1 

# now pull out each message that is within the time diff for each matched message 
# as well as the matched messages themselves 

def determine(tup): 
    if self.message in tup[2]: return True      # matched message 

    for (tool, date_time) in messageTimes: 
        if tool == tup[0]: 
            if abs(date_time-tup[1]) <= tdiff: 
               return True 

    return False 


cdata[:] = [tup for tup in cdata if determine(tup)] 

This code works, but it takes way too long to run - e.g. when cdata has 600,000 elements (which is typical for my app) it takes 2 hours for this to run.

This data came from a database. Originally I was getting just the data I wanted using SQL, but that was taking too long also. I was selecting just the messages I wanted, then for each one of those doing another query to get the data within the time diff of each. That was resulting in tens of thousands of queries. So I changed it to pull all the potential matches at once and then process it in python, thinking that would be faster. Maybe I was wrong.

Can anyone give me some suggestions on speeding this up?

Updating my post to show what I did in SQL as was suggested.

What I did in SQL was pretty straightforward. The first query was something like:

SELECT tool, date_time, message 
FROM event_log
WHERE message LIKE '%foo%'
AND other selection criteria

That was fast enough, but it may return 20 or 30 thousand rows. So then I looped through the result set, and for each row ran a query like this (where dt and t are the date_time and tool from a row from the above select):

SELECT date_time, message
FROM event_log
WHERE tool = t 
AND ABS(TIMESTAMPDIFF(SECOND, date_time, dt)) <= timediff

That was taking about an hour.

I also tried doing in one nested query where the inner query selected the rows from my first query, and the outer query selected the time diff rows. That took even longer.

So now I am selecting without the message LIKE '%foo%' clause and I am getting back 600,000 rows and trying to pull out the rows I want from python.

Answer 1

The way to optimize the SQL is to do it all in one query, instead of iterating over 20K rows and doing another query for each one.

Usually this means you need to add a JOIN, or occasionally a sub-query. And yes, you can JOIN a table to itself, as long as you rename one or both copies. So, something like this:

SELECT el2.date_time, el2.message 
FROM event_log as el1 JOIN event_log as el2
WHERE el1.message LIKE '%foo%'
AND other selection criteria
AND el2.tool = el1.tool
AND ABS(TIMESTAMPDIFF(SECOND, el2.datetime, el1.datetime)) <= el1.timediff

Now, this probably won't be fast enough out of the box, so there are two steps to improve it.

First, look for any columns that obviously need to be indexed. Clearly tool and datetime need simple indices. message may benefit from either a simple index or, if your database has something fancier, maybe something fancier, but given that the initial query was fast enough, you probably don't need to worry about it.

Occasionally, that's sufficient. But usually, you can't guess everything correctly. And there may also be a need to rearrange the order of the queries, etc. So you're going to want to EXPLAIN the query, and look through the steps the DB engine is taking, and see where it's doing a slow iterative lookup when it could be doing a fast index lookup, or where it's iterating over a large collection before a small collection.

Answer 2

For tabular data, you can't go past the Python pandas library, which contains highly optimised code for queries like this.