Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

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

1 view
Skip to first unread message

Heikki Linnakangas

unread,
Mar 15, 2013, 12:46:10 PM3/15/13
to
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
0001-Eliminate-looping-through-chain-of-results-in-perfor.patch
0 new messages