Optimize version sorting handling

[dstufft]

Currently when inserting a new release, PyPI legacy will load all of the releases for a particular project and then sort them in memory and it will then record in the database what the integer based order number is for each release. This makes it possible to sort the releases inside of the database.

Warehouse needs a solution to sorting releases inside of the database as well. Ideally this would be something that didn't require loading all of the releases, sorting, then saving all of the releases back to the database. However that is an OK solution as long as it's done using something like SQLAlchemy's event system so that the fact it's doing that is transparent to code that is adding a new release.

A better solution would be to figure out if we can somehow manage to create a PostgreSQL function that we can use to massage a PEP 440 version string into something that will naturally sort the correct way inside of PostgreSQL. Then wen can simply use that to handle our sorting.

[b4stien]

Hey @dstufft, I wrote a small function to build an easily sortable tuple of integers from a PEP440 version string: https://gist.github.com/b4stien/69cf63792b0c6f278aa1. This kind of array can be used by Postgres to sort rows (see http://www.postgresql.org/docs/9.4/static/functions-array.html).

I'm afraid it doesn't work with local version identifiers for now, but I hope it could give food for thoughts.

As a small explanation of what is done there, it builds a tuple of 16 integers, representing a version. The resulting tuple looks like:

(epoch, major, minor, macro, post, <>, rc, b, a, dev, post, <>, dev, <>, dev, local)

>>> build_sort_tuple('3.5.0')
(0, 3, 5, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1)

>>> build_sort_tuple('1!1.0c1.dev456')
(1, 1, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 457, 0, 0, 1)

>>> build_sort_tuple('1.0b2.post345.dev456')
(0, 1, 0, 0, 0, 0, 0, 3, 0, 0, 346, 0, 0, 0, 457, 1)

I tested it against https://github.com/pypa/packaging/blob/master/tests/test_version.py#L37, it works flawlessly (again, except for the local version identifier part).

[dstufft]

Hmm, somehow I missed this comment. We actually don't need to care about local version identifiers in Warehouse because we disallow using local versions on PyPI. They are designed solely for downstream to be able to mark modifications. That means we don't actually need to care about handling local versions.

[dstufft]

Right now I just merged some code that uses the old behavior, but does it inline with file uploads. Ideally that code would move to change to some sort of hook (SQLAlchemy event?) and when it does that, I think it would be a reasonable step to take to move to the code you've showed to build an array field that we can sort on instead of just an integer.

Ultimately I still think it'd be better to have it handled entirely in the database, however not needing to update the "index" numbers of a bunch of versions and getting natural sorting (even if it's via a denormalized field) is a much better end result.

[b4stien]

I'm not sure to fully understand your reasoning, but iirc I tried the code shown "in database" (via stored procedure) and it worked flawlessly. It was even possible to index the produced array to speed up sorting. That would be the "ultimate end result" you're talking about, right ?

I'm currently on vacation, but if you're interested I'll try to set up a simple demo when I'll come back (in ~ 10 days).

[dstufft]

Well, it'd require PLPython and installing the packaging library into the Python that PostgreSQL is using. Since PLPython isn't a "safe" language most (all?) providers won't allow it's use which would mean copying this chunk of code directly into the database would lock us into self hosting PostgreSQL. I don't think it would be impossible to translate it into PL/pgSQL though since at it's heart it's not incredibly complex code, it's just a regex (assuming of course that PostgreSQL's regex syntax is powerful enough for it).

I guess the main thing is needing to decide if it'd be better to use the tested and reusable code from the packaging library and just have it be used as part of a SQLAlchemy event, or if it would be better to try and duplicate that code in PL/pgSQL or another safe PL for PostgreSQL and push all of the work into the database.

[b4stien]

Oh, I see, I didn't know about PL/Python being unavailable with external providers.

I'll be glad to try to write a PR for either alternative.

An SQLAlchemy event seems easier (to write, understand and maintain) especially because it doesn't split the code between two locations (webapp & DB). On the other hand a PL/pgSQL function seems cleaner on a data-architecture standpoint...

[dstufft]

I'm going to drop this out of the shutdown milestone, because it's not really needed to shut down legacy.

[brainwane]

In our meeting today I double-checked and we confirmed that this backend optimization is low-priority.