Reporting Queries: Best Way to Join Multiple Fact Tables?

I'm working on a reporting system that allows the user to arbitrarily query a set of fact tables, constraining on multiple dimension tables for each fact table. I've written a query-builder class that automatically assembles all the correct joins and subqueries based on the constraint parameters, and everything works as designed.

But, I have a feeling that I'm not generating the most efficient queries. On a set of tables with a few million records, these queries take about 10 seconds to run, and I'd like to get them down in the less-than-one-second range. I have a feeling that, if I could get rid of the subqueries, the result would be much more efficient.

Rather than show you my actual schema (which is much more complicated), I'll show you an analogous example that illustrates the point without having to explain my whole application and data model.

Imagine that I have a database of concert information, with artists and venues. Users can arbitrarily tag the artists and the venues. So the schema looks like this:

concert
  id
  artist_id
  venue_id
  date

artist
  id
  name

venue
  id
  name

tag
  id
  name

artist_tag
  artist_id
  tag_id

venue_tag
  venue_id
  tag_id

Pretty simple.

Now let's say I want to query the database for all concerts happening within one month of today, for all artists with 'techno' and 'trombone' tags, performing at concerts with 'cheap-beer' and 'great-mosh-pits' tag.

The best query I've been able to come up with looks like this:

SELECT
  concert.id AS concert_id,
  concert.date AS concert_date,
  artist.id AS artist_id,
  artist.name AS artist_name,
  venue.id AS venue_id,
  venue.name AS venue_name,
FROM
  concert
INNER JOIN (
  artist ON artist.id = concert.artist_id
) INNER JOIN (
  venue ON venue.id = concert.venue_id
)
WHERE (
  artist.id IN (
    SELECT artist_id
    FROM artist_tag
    INNER JOIN tag AS a on (
      a.id = artist_tag.tag_id
      AND
      a.name = 'techno'
    ) INNER JOIN tag AS b on (
      b.id = artist_tag.tag_id
      AND
      b.name = 'trombone'
    )
  )
  AND
  venue.id IN (
    SELECT venue_id
    FROM venue_tag
    INNER JOIN tag AS a on (
      a.id = venue_tag.tag_id
      AND
      a.name = 'cheap-beer'
    ) INNER JOIN tag AS b on (
      b.id = venue_tag.tag_id
      AND
      b.name = 'great-mosh-pits'
    )
  )
  AND
  concert.date BETWEEN NOW() AND (NOW() + INTERVAL 1 MONTH)
)

The query works, but I really don't like having those multiple subqueries. If I could accomplish the same logic purely using JOIN logic, I have a feeling the performance would drastically improve.

In a perfect world, I'd be using a real OLAP server. But my customers will be deploying to MySQL or MSSQL or Postgres, and I can't guarantee that a compatible OLAP engine will be available. So I'm stuck using an ordinary RDBMS with a star schema.

Don't get too hung up on the details of this example (my real application has nothing to do with music, but it has multiple fact tables with an analogous relationship to the ones I've shown here). In this model, the 'artist_tag' and 'venue_tag' tables function as fact tables, and everything else is a dimension.

It's important to note, in this example, that the queries are much simpler to write if I only allow the user to constrain against a single artist_tag or venue_tag value. It only gets really tricky when I allow the queries to include AND logic, requiring multiple distinct tags.

So, my question is: what are the best techniques that you know of for writing efficient queries against multiple fact tables?

From stackoverflow

• Denormalize the model. Include the tag name in venue and artist tables. This way, you avoid a many to many relationship and you have a simple star schema.

  By applying this denormalization, the where clause can only check this additional tag_name field in both tables (artist and venue).

  benjismith : But if I denormalize, how do I allow an artist or venue to have multiple tags? The thing is, I really CAN'T eliminate the many-to-many relationship without totally crippling the model.

  Cătălin Pitiș : You'll have multiple records for the same artist, but with different tags. It is usual practice in data warehousing to have denormalized data, to improve query performance. This is one of the reasons why ETL jobs (Extract-Transform-Load data) are employed: to convert from a normalized relational model to a data warehouse specific model (dimensional or star model).

  Dems : Agreed, on a couple of assumptions. This can cause a dramatic increase in data size, is the space available? (Come on, drives are cheap...) With changable data, refreshing the denormalised data be costly in terms of cpu, etc. Is the data relatively static, and/or can it be ETLed over night, etc? If so, such denormalising (to flat file format, for example) Can be Extremely beneficial to reporting.

  benjismith : I was thinking about doing it that way. But I'm going to be running a lot of aggregate queries (count, sum, avg, stddev, etc) and the duplicate records would screw up the calculations. For counting, I could use DISTINCT, but how would I eliminate the discrepancies for other aggregate functions?

  Dems : That completely depends on the exact queries you want to write and the exact schema. My experience has been that "data-warehousing" doesn't involve storing the data in One new format, but several. Each optimised for different reporting needs. It would be in that "ETL" that you would arrange the data to be suitable for different Aggregates, OR actually do the aggregates there. Either way, you may find that you need to solve your original question first...

• My approach is a bit more generic, putting the filter parameters in tables and then using GROUP BY, HAVING and COUNT to filter the results. I've used this basic approach several times for some very sophisticated 'searching' and it works very well (for me grin).

  I also don't join on the Artist and Venue dimension tables initially. I'd get the results as id's (just needing artist_tag and venue_tag) then join the results on the artist and venue tables to get those dimension values. (Basically, search for the entity id's in a sub query, then in an outer query get the dimension values you need. Keeping them separate should improve things...)

  DECLARE @artist_filter TABLE (
    tag_id INT
  )
  
  DECLARE @venue_filter TABLE (
    tag_id INT
  )
  
  INSERT INTO @artist_filter
  SELECT id FROM tag
  WHERE name IN ('techno','trombone')
  
  INSERT INTO @venue_filter
  SELECT id FROM tag
  WHERE name IN ('cheap-beer','great-most-pits')
  
  
  SELECT
    concert.id AS concert_id,
    concert.date AS concert_date,
    artist.id AS artist_id,
    venue.id AS venue_id
  FROM
    concert
  INNER JOIN
    artist_tag
      ON artist_tag.artist_id = concert.artist_id
  INNER JOIN
    @artist_filter AS [artist_filter]
      ON [artist_filter].tag_id = artist_tag.id
  INNER JOIN
    venue_tag
      ON venue_tag.venue_id = concert.venue_id
  INNER JOIN
    @venue_filter AS [venue_filter]
      ON [venue_filter].tag_id = venue_tag.id
  WHERE
    concert.date BETWEEN NOW() AND (NOW() + INTERVAL 1 MONTH)
  GROUP BY
    concert.id,
    concert.date,
    artist_tag.artist_id,
    venue_tag.id
  HAVING
    COUNT(DISTINCT [artist_filter].id) = (SELECT COUNT(*) FROM @artist_filter)
    AND
    COUNT(DISTINCT [venue_filter].id)  = (SELECT COUNT(*) FROM @venue_filter)
  

  (I'm on a netbook and suffering for it, so I'll leave out the outer query getting the artist and venue names from the artist and venue tables grin)

  EDIT
  Note:

  Another option would be to filter the artist_tag and venue_tag tables in sub-queries/derived-tables. Whether this is worth it depends on how influential the join on the Concert table is. My assumption here is that there are MANY artist and venues, but once filtered on the concert table (itself filtered by the dates) the number of artists/venues decreases dramatically.

  Also, there is often a need/desire to deal with the case where NO artist_tags and/or venue_tags are specified. From experience it is better to deal with this programatically. That is, use IF statements and queries specially suited to those cases. A single SQL query CAN be written to handle it, but is much slower than the programatic alternative. Equally, writing similar queries several times may look messy and degrade maintainability, but the increase in complexity need to get this to be a single query is often harder to maintain.

  EDIT

  Another similar layout could be...
  - Filter concert by artist as sub_query/derived_table
  - Filter results by venue as sub_query/derived_table
  - Join results on dimension tables to get names, etc

  (Cascaded filtering)

  SELECT
     <blah>
  FROM
    (
      SELECT
        <blah>
      FROM
        (
          SELECT
            <blah>
          FROM
            concert
          INNER JOIN
            artist_tag
          INNER JOIN
            artist_filter
          WHERE
          GROUP BY
          HAVING
        )
      INNER JOIN
        venue_tag
      INNER JOIN
        venue_filter
      GROUP BY
      HAVING
    )
  INNER JOIN
    artist
  INNER JOIN
    venue
  

  By cascading the filtering, each subsequent filtering has a reduce set it has to work on. This MAY reduce the work done by the GROUP BY - HAVING section of the query. For two levels of filtering I would guess this to be unlikely to be dramatic.

  The original may still be more performant as it benefits additional filtering in a different manner. In your example:
  - There may be many artist in your date range, but few which meet at least one criteria
  - There may be many venues in your date range, but few which meet at least one criteria
  - Before the GROUP BY, however, all concerts are eliminated where...
  ---> the artist(s) meets NONE of the criteria
  ---> AND/OR the venue meets NONE of the criteria

  Where you are searching by many criteria this filtering degrades. Also where venues and/or artists share a lot of tags, the filtering also degrades.

  So when would I use the original, or when would I use the Cascaded version?
  - Original : Few search criteria and venues/artists are dis-similar from each other
  - Cascaded : Lots of search criteria or venues/artists tend to be similar

  Dems : I didn't use the "tag_artist_user" table as it didn't impact the results in your example

  benjismith : Oops. The "tag_artist_user" table was an artifact of a previous draft of the query. Just edited the original post to remove it.