Avoid O(n^2) behavior with large parameter arrays

From: Heikki Linnakangas <hlinnakangas(at)vmware(dot)com>
To: pgsql-odbc(at)postgresql(dot)org
Subject: Avoid O(n^2) behavior with large parameter arrays
Date: 2013-03-15 16:46:10
Message-ID: 51435052.5060304@vmware.com
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-odbc

While digging deeper into the array binding code, I noticed that a lot
of time is spent chasing the end of the linked list of query result, to
append a new result at the end. When executing a statement with array
binding, SC_execute iterates through all the previous results, leading
to O(n^2) behavior. With a large parameter array, a lot of CPU time is
spent doing that.

Attached patch fixes that by keeping track of the tail of the linked
list, and the StatementClass that "owns" each QResultClass object (if
any). By "owning", I mean that the QResultClass object is linked in the
linked list of that StatementClass. That avoids having to traverse the
list to check if a QResultClass is already in the chain.

With this patch, I'm no longer seeing O(n^2) behavior, and it becomes
feasible to use large parameter arrays with > 100000 elements.

(as usual, this patch is also available in my github repository)

- Heikki

Attachment Content-Type Size
0001-Eliminate-looping-through-chain-of-results-in-perfor.patch text/x-diff 5.8 KB

Browse pgsql-odbc by date

  From Date Subject
Next Message Ben Morgan 2013-03-18 08:12:55 Bug: attributes dynamically filled (e.g. xml) truncated
Previous Message Heikki Linnakangas 2013-03-15 13:52:32 Migrating from CVS to git