Re: ALTER EXTENSION UPGRADE, v3

On Thu, Feb 10, 2011 at 3:58 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> Robert Haas <robertmhaas@gmail.com> writes:
>> On Thu, Feb 10, 2011 at 3:02 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>>> The design as I sketched it didn't need to make any assumptions at all
>>> about the meaning of the version identifiers.  But if you were willing
>>> to assume that the identifiers are comparable/sortable by some rule,
>
>> You don't need them to be sortable.  You just need them to be
>> comparable, and equality seems like a plenty good enough comparison
>> rule.  You can compute the shortest chain of upgrade scripts that can
>> take you from the current version to the target version.
>
> Hmm.  The problem with that is that once there are large numbers of
> intermediate versions, the number of potential paths grows
> exponentially.  I was envisioning an algorithm like this:
>
> 1.  Scan directory for upgrade scripts with oldversion = version we
> have, and take the one with largest newversion <= version we want.
>
> 2.  Apply this script (or more likely, just remember it until we've
> verified there is a chain leading to version we want).
>
> 3.  If now the version is not what we want, return to step 1.
>
> I don't see an equally efficient method if we only have equality.

It's certainly not exponential i.e. O(2^n) or something of that form.
Even a naive application of Dijkstra's algorithm is only going to be
O(n^2) in the number of versions, which is likely tolerable even if
upgrades are supported for dozens of old versions.  It might break
down if there are hundreds of old versions, but that doesn't seem
likely to be a real problem in practice.  But if you're concerned
about it, you can replace the linked list that the naive algorithm
uses with a binary heap or (if you really want to go nuts) a fibonacci
heap.  The latter approach has a runtime of O(n + m lg m), where n is
the number of versions and m is the number of upgrade scripts.  You
need one heck of a lot of backward compatibility before that algorithm
breaks a sweat.  Even the binary heap is only O((n + m) lg m), which
pretty darn fast.

Personally, I think we'll be lucky if people support ten back revs,
let alone three hundred, but it's a simple matter of programming - and
an afternoon with an introductory algorithms textbook - to make it as
efficient as we could ever want it to be.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company