[elephant-devel] Collection paging

Thu Oct 4 01:13:15 UTC 2007

When you say indexes are not sequential, do you mean UIDs are not sequentially allocated?  I think there is a BDB sequence issue that I've never worried about that jumps to the nearest 100 when you reconnect.  However, if you create anything other than a user object, you will also have gaps in the UID sequence so that's a fundamental issue.  Don't assume anything about UIDs other than the fact that they are unique.

You could create and index your own field which is a sequential ID for creation ordering, but it sounds like you probably want to return a sublist based on some sort order like alphabetical by name or by date.  In this case, at least doing the last page is easy, map from end and count the # of users you want before you terminate, but to find an element that is N elements away from the first or last element in less than O(n) time isn't possible with the underlying B-Trees we're using.

The first question is whether you database is guaranteed to be so big that you can't just do this linear time.  When you start to face performance issues, then you can look at building that additional data structure.

Otherwise, you will have to implement a data structure that maintains this information on top of the Elephant infrastructure. 

The first idea that occurs to me is to drop the idea of using an indexed class or standalone btrees and just build a red-black tree using object slots (you can inherit from a base class that implements the RB tree functionality).  This simultaneously solves the count problem and the access element # N problem.  The O(log (base 2) N) lookup time will have a higher fixed cost per level traversal, but if you start getting really large dbs (1000's to 10k's?) then it will certainly beat a linear map-index approach.  i.e.

http://en.wikipedia.org/wiki/Red-black_tree

There is a lisp example of this data structure here:

http://www.aviduratas.de/lisp/progs/rb-trees.lisp

Now there is a problem that you'll need one of these for each sorted order which for a list sorted many different ways is a problem.  Anyone know how SQL query systems implement this?

Just remember that premature optimization is one of the four horseman of the apocalypse for the effective programmer.

Ian
  ----- Original Message ----- 
  From: Mariano Montone 
  To: Elephant bugs and development 
  Sent: Wednesday, October 03, 2007 6:57 PM
  Subject: [elephant-devel] Collection paging

  Hello, it's me again :S.

  I would like to know how I can access persistent collection pages efficiently.

  What I'm trying to do is making work a web list component with elephant. The list component is supposed to support well known navigation commands, like look at the collection in pages, support for first, last, next, previous buttons, and display of collection size. 

  The collection size problem was treated here:  http://common-lisp.net/pipermail/elephant-devel/2007-October/001162.html.

  But now I have a problem with building the pages. 

  My first try was:
    (let*
        ((start (* (current-page self) (page-size self)))
         (end (+ start (page-size self)))
         )
          (<:ul
           (elephant:map-btree #'(lambda (key elem) (declare (ignore key))
                         (let ((elem-text (make-elem-text self elem)))
                           (<:li
                            (if (slot-value self 'selectable) 
                            (<ucw:a :action (answer elem)  (<:as-html elem-text))
                            (<:a (<:as-html elem-text))))))
                   (model self) :start start :end end)
           ) 

  with start and end previously fixed based in the current page number and size.

  But I realized indexes were not sequential when I created new objects, as this shows:

  ASKIT> (with-btree-cursor (cursor (find-class-index 'user)) 
    (iter 
      (for (values exists? k v) = (cursor-next cursor))
      (while exists?)
      (format *standard-output* "~A -> ~A ~%" k v)))
  2 -> #<USER name: dssdf {B043379}> 
  3 -> #<USER name: ttttt {B045C69}> 
  5 -> #<USER name: ff {B048179}> 
  6 -> #<USER name: other {B04A451}> 
  7 -> #<USER name: guest {AD61271}> 
  100 -> #<USER name: qqq {B053001}> 
  101 -> #<USER name:  {B055721}> 
  102 -> #<USER name:  {B057E01}> 
  103 -> #<USER name:  {B05A529}> 
  104 -> #<USER name:  {B05CCF1}> 
  105 -> #<USER name:  {B05F579}> 
  106 -> #<USER name:  {B063E91}> 
  107 -> #<USER name: qqq {B066851}> 
  200 -> #<USER name:  {B069519}> 
  201 -> #<USER name:  {B06C009}> 
  300 -> #<USER name:  {B06EBA1}> 
  301 -> #<USER name: aaa {B0717D1}> 
  NIL

  I don't think this is a bug, it must have to do with how Elephant manages btrees; but then how am I supposed to access through pages?
  I would like to have to access all the objects from the beggining just to discard them instantly (imagine a large collection and the user wanting to see the last page). 

  Thank you again :)

  Mariano

------------------------------------------------------------------------------

  _______________________________________________
  elephant-devel site list
  elephant-devel at common-lisp.net
  http://common-lisp.net/mailman/listinfo/elephant-devel
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.common-lisp.net/pipermail/elephant-devel/attachments/20071003/7e1e547d/attachment.html>