From: Björn Stenberg <bjorn_at_haxx.se>
Date: Fri, 22 Oct 2004 11:03:28 +0200

Peter van Hardenberg wrote:
> PERFORMING COMPLEX QUERIES:
> Because the data is sorted and stored using fixed length records
> wherever possible, computing a query involving multiple fields is quite
> simple. Here is a breakdown of the procedure, using a search for "80s rock".
>
> 1) Load the song database header. Find the genre segment.
> 2) Search the binary tree for the offset/size of rock.
> 3) Load the "rock" song IDs into memory.
> 4) Search the binary tree for the offset/size of 1980s.
> 5) Load the "1980s" song IDs into memory.
> 6) Create an intersection list from the data. (Because the ids are
> already sorted, this is very fast.)
> 7) Create a playlist by loading the song filenames based on the songIDs.

This is nice, but it only solves the searching part. We also want to be able to _browse_ equally complex queries. This means we not only want to find the relevant files, we want lists of matching artists and albums too:

Artists
Albums
Songs
Year
Genre
 |- Rock
 `- Pop
     |- Artists
     |- Albums
     |- Songs
     `- Year
         |- 1980
         `- 1981
             |- Artists
             | |- artist1
             | | |- a1album1
             | | | |- a1a1song1
             | | | |- a1a1song2
             | | | `- a1a1song3
             | | `- a1album2
             | | |- a1a2song1
             | | `- a1a2song2
             | `- artist2
             | `- a2album1
             | |- a2a1song1
             | `- a2a1song2
             |- Albums
             `- Songs

This could be solved using a few more cross-reference tables:

genre2artist
genre2album
genre2song
genre2year
year2artist
year2album
year2song
year2genre

And cross-match them as you describe to find for example "all artists with albums with Pop songs released in 1981".

Adding another level of complexity, you hint at the desire to match against *ranges* of values ("the 1980s"), which would mean we cannot even limit ourselves to comparing against a single entry in the tables. Code complexity is increasing rapidly! :-)

This brings back my old thinking that Artist, Album and Song are "main" attributes for which browsing is solved in the database without searching. Year and Genre are "filtering" attributes which can be combined with the main attributes, but this will require a bit more cpu work and disk access.

-- 
Björn
_______________________________________________
http://cool.haxx.se/mailman/listinfo/rockbox

Received on 2004-10-22