Re: [sqlite] Relative efficiency of joins, subselects, and union/intersect

[John LeSueur]

Nathan Kurz wrote:
Hello --
I've got a SQL problem that I'm guess is about half general and half
SQLite specific.  I'm pretty new to SQLite, familiar with basic SQL
(mostly from MySQL), and I'm accessing SQLite through C and Perl.
The problem I'm working on relates to tagging music for some music
management software I'm thinking about.  It currently exists mostly in
my head, but it will be released as open source if it pans out.
In my model, a 'song' record consists of a unique artist/album/title
A 'tag' is a name/value pair associated with a 'song': 
  Song: song_id artist album title
  Tag:  song_id name value
Searching for the tags associated with a given song would be pretty
easy, but complicating matters I need for tags to 'cascade'.  

This is so that a tag can be set for an entire album, and then
overridden if necessary on a song by song basis.  For example, if I am
checking the value of the tag 'rating' for Artist/Album/Title, but no
such tag is found, I want to fall back on the tag for
Artist/Album/NULL; failing that I search for Artist/NULL/NULL.
 


ps. I'd like to be able to do this search in a single SQL statement
   (rather than multiple queries) because at some point I need to
   start doing intersects of multiple tag searches.  Another bridge
   I'll cross when I get to it!
 

As far as I know, generally speaking, subselects are less efficient than 
joins. This is because joins
can make use of indexes, and subselects are unable to. I can't say for 
sure about using unions,
especially since I'm not sure how you would use them for this specific 
case, but again, unions/intersects
would not be able to take advantage of indexes, but with 10,000 songs 
and 100,000 tags,
as long as you have indexes set up and use them correctly, you shouldn't 
have a problem.

select
   coalesce(songtag.name, albumtag.name, artisttag.name) as name,
   -- you might need to use a case statement instead if the value of a 
tag can be null
   -- in that case this would return a value that did not match the tag
   coalesce(songtag.value, albumtag.value, artisttag.value) as value
from 
   song
   left outer join
      tag songtag
         on song.id = tag.object_id
   left outer join
      tag artisttag
         on song.artist_id = tag.object_id
   left outer join
      tag albumtag
         on song.album_id = tag.object_id
where
   song.id = ?
   and tag.name = ?

This could be surprisingly fast if you do it like itunes does and load 
the entire song database
into memory(which sqlite supports), and using a file(itunes uses xml) 
only to load initially, and store
permanent changes. There's probably something even simpler you can do, 
but I can't think of it
at this moment.

John