How to properly type a multi-keys index using maps

user_1180416 0
Viewed 68

I am looking for a nice solution to build and query an indexed store for documents, in my case "pages with metadata".

My pages have various fields of metadata, such as "tags", "authors" etc.

Such a page could be modeled like so

data Page = 
  Page { content :: Text
       , tags :: [Text]
       , authors :: [Text]
       , score :: Int
       , online :: Bool }

The software handle a collection of such Pages, and need to query through this collection. My current solution is to manually handle a Map for each field of metadata, then populate each of this map manually anytime a new Page is created (using a Map of key -> Set Page). Then for each individual case of my application, I query one or more Map, intersect (or unite) results, then process. This is tedious and error prone.

This is why I would like to design a generic document store, a bit like what Data.IxSet offers. Please note that my question is about properly typing such a store, not about using IxSet.

If all fields had the same type of keys K (like Text), such an Index could be typed as : Map Field (Map K (Set Page)), where Field is the type of the fields, for example 

data Field = Tag | Author | ...

Unfortunately, it is not the case, fields keys can be Text or Date or Int or Bool etc. All of them satisfy Map constraints Ord though, so this part is not problematic.

How would you design this datatype and type it properly, so that the following interfaces could be used with it. I have put question marks where I don't know what to do with the types. Often this will be related to properly handle collections of possibly-heterogeneous types.

data Field model key = Field { fieldId :: FieldId
                             , extractKeys :: model -> [key] }

-- initIndex create an index for values 'model' with descriptions for fields and keys extractors. 
initIndex :: [Field model ?] -> Index ? model

-- adding a document to the index
addToIndex :: Index ? model -> model -> Index ? model

-- a request combines filters with boolean logic
data Request field ? = And [Request field ?] | Or [Request field ?] | Term (Filter field ?)
-- a filter is a constraint on a field keys. 'All' will intersect, 'Any' will unite ...
data Filter field k = All field [k] | Any field [k] | GreaterThan field k | LowerThan field k

queryIndex :: Index ? model -> Request field ? -> Set model

I hope this is clear enough, if not I will update it as necessary. Thank you

haskell
1 Answers

One approach would be to store all your indexes in a single Map.

First, define a union data type for your different keys:

data Key =
   KeyTag Text,
   KeyAuthor Text,
   KeyScore Int
   -- etc.
   deriving (Eq, Ord)

Then write a function which returns all the keys for a page.

pageKeys :: Page -> [Key]

Now you can write a function that adds the page to all the keys for a single index, and you can retrieve the set of documents for a single author or tag using the appropriate constructor. If you are using Map.split to match score ranges then that will work in the same way too.

Edit: More on Map.split:

From Data.Map: split :: Ord k => k -> Map k a -> (Map k a, Map k a)

The first result is all the values with key < k, the second is all the values with key > k. So you can get all the pages with keys between k1 and k2 like this (assuming import qualified Data.Map as M):

subRange :: (Ord k) => (k, k) -> M.Map k a -> M.Map k a
subRange (k1, k2) = fst . M.split k2 . snd . M.split k1

Note that this will exclude keys equal to k1 and k2: an inclusive function will need to use M.splitLookup and be rather hairier.

If you have this grand unified index to your pages then you can easily get a date subrange like this:

dateSubRange :: (Date, Date) -> Map Key (Set Page) -> Map Key (Set Page)
dateSubRange (d1, d2) = subRange (KeyDate d1, KeyDate d2)

The trick is that the Ord instance for Key has exactly the same ordering as its components, so compare d1 d2 == compare (KeyDate d1) (KeyDate d2). If you were to print the big index out in key-order you would get all the tags first, then all the authors, then all the scores etc.

The efficiency of a single big index is barely lower than several partial indexes. Remember that lookup for a Map is O(log n), so multiplying the size of the map by a constant c merely adds a constant time to the lookup of O(log c). Unless you are trying to bum every possible microsecond out of your code it's not worth worrying about.

(In fact, having the CPU cache the top levels of your index might even make it faster than multiple indices when you look up several different keys. But that's complicated and depends on a bunch of things).

user_492200
Related