2.11 Secondary Indices

The indexed-btree class is a BTree which supports secondary indices. Suppose I store appointments as

     * (defclass appointment ()
         ((date :accessor ap-date :initarg :date :type integer)
          (type :accessor ap-type :initarg :type :type string))
         (:metaclass persistent-metaclass))
     => #<PERSISTENT-METACLASS APPOINTMENT {481CBBCD}>

and I put them in a table

     * (defvar *appointments* (with-transaction () (make-indexed-btree)))
     => *APPOINTMENTS*

keyed by their date (stored as universal-time):

     * (defun add-appointment (date type)
         (with-transaction ()
           (setf (get-value date *appointments*)
                 (make-instance 'appointment :date date :type type))))
     => ADD-APPOINTMENT
     
     * (add-appointment (encode-universal-time 0 0 0 22 12 2004) "Birthday")
     => #<APPOINTMENT {48A2D29D}>
     
     * (add-appointment (encode-universal-time 0 0 0 14 4 2005) "Birthday")
     => #<APPOINTMENT {48A2D29E}>
     
     * (add-appointment (encode-universal-time 0 0 0 1 1 2005) "Holiday")
     => #<APPOINTMENT {48A2D29F}>

But suppose I would also like to be able to lookup appointments by their type? This is what secondary indices are for.

First, we create a function which generates the secondary key:

     * (defun key-by-type (secondary-db primary value)
         (declare (ignore secondary-db primary))
         (let ((type (ap-type value)))
           (when type
             (values t type))))
     => KEY-BY-TYPE

It should take three arguments: the secondary index, the primary key, and the value. It should return two values: T (index it) and the secondary index, or NIL (don't index it.) Next we add the index:

     * (with-transaction ()
         (add-index *appointments* :index-name 'by-type
                                   :key-form 'key-by-type
                                   :populate t))
     => #<BTREE-INDEX {48DFBAA5}>

:index-name is a is a way to refer to the index; symbols are good for this. :key-form is the way to generate secondary keys. Note that you need to pass in the symbol bound to a function, or an actual list defining a lambda, not a function (since we can't directly serialize functions yet.) Finally :populate tells Elephant to walk the primary table and generate secondary keys for all the primary values.

     * (defvar *by-type* (get-index *appointments* 'by-type))
     => *by-type*
     
     * (decode-universal-time (ap-date (get-value "Holiday" *by-type*)))
     => 0
        0
        0
        1
        1
        2005
        2
        NIL
        6

What about conflicting keys? The secondary index (of type btree-index) supports duplicate keys. You can find the duplicate entries by using the cursor functions next, next-dup, next-nodup, prev, prev-nodup:

     * (with-btree-cursor (curs *by-type*)
         (loop for (more? k v) =
               (multiple-value-list (cursor-set curs "Birthday"))
     	  then (multiple-value-list (cursor-next-dup curs))
               do
     	  (unless more? (return t))
     	  (multiple-value-bind (s m h d mo y)
     	      (decode-universal-time (ap-date v))
     	    (declare (ignore s m h))
     	    (format t "~A/~A/~A~%" mo d y))))
     12/22/2004
     4/14/2005
     => T

There are also cursor-p* functions like pcurrent, pnext, et cetera which also return the primary key. See Cursors.