In our Tour of Extensions today’s article is about advanced tag indexing. We have a great data collection to play with and our goal today is to be able to quickly find data matching a complex set of tags. So, let’s find out those lastfm tracks that are tagged as blues and rhythm and blues, for instance.

We’re going to use the dataset from the Million Song Dataset project here. The article where they present their similarity searches is providing the whole dataset they have as a SQLite database and they propose to read their python script to make sense of it.

The Setup

First, we need to import this dataset into a PostgreSQL database. To do that the easier path I could think of was to hack the capability into pgloader of course, so here we go:

                    table name       read   imported     errors       time
------------------------------  ---------  ---------  ---------  ---------
                          tags          0     522366          0      3.922
                          tids          0     505216          0      3.746
                       tid_tag          0    8598630          0    115.349
        index build completion          0          0          0     33.099
------------------------------  ---------  ---------  ---------  ---------
                  create index          0          8          0     38.839
               reset sequences          0          0          0      0.064
------------------------------  ---------  ---------  ---------  ---------
          Total streaming time          0    9626212          0  2m36.180s

Here, pgloader extracted the table and index definitions from the SQLite database using the sqlite_master catalog and the PRAGMA table_info() commands, and migrated the data in a streaming fashion down to PostgreSQL, using the COPY protocol.

Having a look at the script we can actually see how to use the relations here, and we realize they are using the 64-bit signed integer ROWID system column. We need something comparable to be able to make sense of the data:

> alter table tags add column rowid serial;
Time: 3177.603 ms

> alter table tids add column rowid serial;
Time: 2528.680 ms

> SELECT tags.tag, COUNT(tid_tag.tid)
    FROM tid_tag, tags
   WHERE tid_tag.tag=tags.ROWID and tags.tag ~* 'setzer'
GROUP BY tags.tag;
             tag             | count 
 the brian setzer orchestra  |     1
 Setzer                      |    13
 rockabilly Setzer style     |     4
 setzer is a true guitarhero |     9
 brian setzer orchestra      |     3
 brian setzer is GOD         |     1
 Brian Setzer                |     1
 brain setzer orchestra      |     2
(8 rows)

Time: 644.826 ms

Here the query is mainly doing a JOIN in between the tid table (containing track ids) and the tid_tag table (containing association in between tracks and tags), filtering on the case insensitive regular expression 'setzer'. As we can imagine from reading the query execution time, we don’t have any index to implement the filtering here.

Advanced tag indexing

PostgreSQL comes with plenty of interesting datatypes, one of them is known as the Arrays Type. PostgreSQL also provides a very rich set of extensions, some of them found under the contrib package; one of them is intarray. Let me quote for you the most interesting part of the documentation for that extension:

The @@ and ~~ operators test whether an array satisfies a query, which is expressed as a value of a specialized data type query_int. A query consists of integer values that are checked against the elements of the array, possibly combined using the operators & (AND), | (OR), and ! (NOT). Parentheses can be used as needed. For example, the query 1&(2|3) matches arrays that contain 1 and also contain either 2 or 3.

> create extension intarray;

The way the intarray extension works, we need to build a new table that contains for each track the list of tags it’s been associated with, as an array of integers. We’re going to use our rowid identifier for that purpose, as in the following query:

>  SELECT tt.tid, array_agg(tags.rowid) as tags
     FROM tags JOIN tid_tag tt ON tags.rowid = tt.tag
 GROUP BY tt.tid
    LIMIT 3;
 tid |   tags    
   1 | {1,2}
   2 | {3,4}
   3 | {5,6,7,8}
(3 rows)

Time: 942.074 ms

So let’s build the full table then index it:

> CREATE TABLE track_tags AS
   SELECT tt.tid, array_agg(tags.rowid) as tags
     FROM tags join tid_tag tt on tags.rowid = tt.tag
 GROUP BY tt.tid;
SELECT 505216
Time: 45388.424 ms

> create index on track_tags using gin(tags gin__int_ops);
Time: 18645.931 ms


Now PostgreSQL is ready for the real magic. Let’s find all the tracks we have that have been tagged as both blues and rhythm and blues:

> select array_agg(rowid)
    from tags
   where tag = 'blues' or tag = 'rhythm and blues';
(1 row)

Time: 0.684 ms

Now what we want is a query_int query string, which looks like '(1880&179879)', so rather than just array_agg we’re going to use the following query:

> select format('(%s)',
            array_to_string(array_agg(rowid), '&')
         )::query_int as query
    from tags
   where tag = 'blues' or tag = 'rhythm and blues';
 3 & 739
(1 row)

Time: 0.747 ms

That query here allows us to easily inject as many tags as we want to, so that it’s easy to use it as a template from within an application where the user is going to provide for the tags list. The intarray extension’s query format also accepts other operators ( or and not) as we saw before, so if you want to expose those to your users you would need to tweak the query_int building part of the SQL.

Now, how many tracks have been tagged with both the blues and the rhythm and blues tags, will you ask me:

> with t(query) as (
       select format('(%s)',
                array_to_string(array_agg(rowid), '&')
             )::query_int as query
        from tags
       where tag = 'blues' or tag = 'rhythm and blues'
select count(*) from track_tags, t
 where tags @@ query;
(1 row)

Time: 8.242 ms

Now of course you might want to fetch some track meta-data, here the only one we have is the track hash id:

> with t(query) as (
    select format('(%s)',
                    array_to_string(array_agg(rowid), '&')
           )::query_int as query
      from tags
       where tag = 'blues' or tag = 'rhythm and blues'
 select track.tid
   from track_tags tt join tids track on tt.tid = track.rowid, t
  where tt.tags @@ t.query
  limit 10;
(10 rows)

Time: 7.630 ms


The usual way to handle a set of user defined tags and query against it involves join against a reference table of tags, but then it’s quite complicated to express the full search query: we want tracks tagged with both blues and rhythm and blues and might want then to exclude finger picking.

The intarray extension provides a powerful query specialized language with direct index support, so that you can build dynamic indexes searches directly from your application.