SQL return rows in a "round-robin" order

Question

I have a bunch of URLs stored in a table waiting to be scraped by a script. However, many of those URLs are from the same site. I would like to return those URLs in a "site-friendly" order (that is, try to avoid two URLs from the same site in a row) so I won't be accidentally blocked by making too many http requests in a short time.

The database layout is something like this:

create table urls (
    site varchar,       -- holds e.g. www.example.com or stockoverflow.com
    url varchar unique
);

Example result:

SELECT url FROM urls ORDER BY mysterious_round_robin_function(site);

http://www.example.com/some/file
http://stackoverflow.com/questions/ask
http://use.perl.org/
http://www.example.com/some/other/file
http://stackoverflow.com/tags

I thought of something like "ORDER BY site <> @last_site DESC" but I have no idea how to go about writing something like that.

Answer 1

I think you're overcomplicating this. Why not just use

ORDER BY NewID()

Answer 2

See this article in my blog for more detailed explanations on how it works:

• PostgreSQL: round-robin order

With new PostgreSQL 8.4:

SELECT  *
FROM    (
        SELECT  site, url, ROW_NUMBER() OVER (PARTITION BY site ORDER BY url) AS rn
        FROM    urls
        )
ORDER BY
        rn, site

With elder versions:

SELECT  site,
        (
        SELECT  url
        FROM    urls ui
        WHERE   ui.site = sites.site
        ORDER BY
                url
        OFFSET  total
        LIMIT   1
        ) AS url
FROM    ( 
        SELECT  site, generate_series(0, cnt - 1) AS total
        FROM    (
                SELECT  site, COUNT(*) AS cnt
                FROM    urls
                GROUP BY
                        site
                ) s
        ) sites
ORDER BY
        total, site

, though it can be less efficient.

Answer 3

You are asking for round-robin, but I think a simple

SELECT site, url FROM urls ORDER BY RANDOM()

will do the trick. It should work even if urls from the same site are clustered in db.

Answer 4

If the URLs don't change very often, you can come up with a somewhat-complicated job that you could run periodically (nightly?) which would assign integers to each record based on the different sites present.

What you can do is write a routine that parses the domain out from a URL (you should be able to find a snippet that does this nearly anywhere).

Then, you create a temporary table that contains each unique domain, plus a number.

Then, for every record in your URLs table, you look up the domain in your temp table, assign that record the number stored there, and add a large number to that temp table's number.

Then for the rest of the day, sort by the number.

---

Here's an example with the five records you used in your question:

URLs:

• http://www.example.com/some/file
• http://www.example.com/some/other/file
• http://stackoverflow.com/questions/ask
• http://stackoverflow.com/tags
• http://use.perl.org/

Temp table:

example.com       1
stackoverflow.com 2
perl.org          3

Then for each URL, you look up the value in the temp table, and add 3 to it (because it's got 3 distinct records):

Iteration 1:

URLs:

http://www.example.com/some/file         1
http://www.example.com/some/other/file   NULL
http://stackoverflow.com/questions/ask   NULL
http://stackoverflow.com/tags            NULL
http://use.perl.org/                     NULL

Temp table:

example.com       4
stackoverflow.com 2
perl.org          3

Iteration 2:

URLs:

http://www.example.com/some/file         1
http://www.example.com/some/other/file   4
http://stackoverflow.com/questions/ask   NULL
http://stackoverflow.com/tags            NULL
http://use.perl.org/                     NULL

Temp table:

example.com       7
stackoverflow.com 2
perl.org          3

et cetera until you get to

http://www.example.com/some/file         1
http://www.example.com/some/other/file   4
http://stackoverflow.com/questions/ask   2
http://stackoverflow.com/tags            5
http://use.perl.org/                     3

For a lot of records, it's going to be slow. And it will be difficult to work with many inserts/deletions, but the result will be a flawless round-robin ordering.

Answer 5

There is a much simpler and faster solution...

• add a sort_order column of type TEXT
• add an ON INSERT trigger which sets sort_order to md5( url )
• index on sort_order
• grab the rows in (sort_order, primary key) order

-> it's very fast and indexed -> rows will come in a repeatable, yet random order