BTW: We also need on-the-fly indexing for TextTable support.
Bob
>From: "Fred Toussi" <[EMAIL PROTECTED]>
>To: "Karl Meissner" <[EMAIL PROTECTED]>, <[EMAIL PROTECTED]>
>Subject: Re: [Hsqldb-developers] fine grain threading
>Date: Sat, 20 Apr 2002 12:09:56 +0100
>
>Thanks Karl,
>
>In my view, the cases where fine-grained locks can make a difference are
>very few. But since you've been working with databases with very high insert
>and update loads, you might know of a scenario that makes them desirable.
>Please let us know.
>
>Currently we are using 40 year old AVL trees. The paper by Lehman and Yao is
>20 years old. I'm wondering to what extent their approach was influenced by
>the state of hardware in their time. For sake of simplicity, let's assume
>the ratio between RAM and disk space (Primary and Secondary storage as they
>call it) has remained the same over the last 20 years. What has changed
>though is the number of nodes that can be held in primary storage by a
>process is probably on average a 1000 times that of 20 years ago (using the
>same proportion of total Primary storage available). Could this influence
>our approach? For example, if a node takes 16 bytes then we can store the
>index for a million rows in 16MB of memory. On a typical server, indexes for
>a very large database with multiple indexes can be processed mainly in
>memory and written to disk using the platform backed methods without any
>effort on our part.
>
>Also something to bear in mind is we need on the fly generation of indexes
>for result sets. Currently result sets are held entirely in memory and have
>no index. As a result, queries with subqueries perform poorly. Also, if we
>want be able to process and return very large result sets we need to create
>an index for the result set as it is built and then fetch the rows from
>tables when the result set is returned to the client. In short, we need an
>indexing solution that covers both permanent tables and temporary result
>sets.
>
>
>Fred Toussi
>
>----- Original Message -----
>From: "Karl Meissner" <[EMAIL PROTECTED]>
>To: <[EMAIL PROTECTED]>
>Sent: Friday, April 19, 2002 9:39 PM
>Subject: [Hsqldb-developers] fine grain threading
>
>
>
>
>I implemented BLink Trees in a tiny stand alone demo.
>The algorithm turned out to be a littttttle more
>complicated then I thought. So I have not had time
>to implement the nio paging system yet.
>
>The big claim to fame for the BLink Tree algorithm
>over regular B-Trees is that it allows read and write
>multiple threads to access the tree at the same time.
>
>The seminal paper on BLink Trees is
>http://lambda.cs.yale.edu/cs424/lect/btree.pdf
>
>This turns out to be really slow.
>
>With the help of some special data structures you lock
>single BTree nodes as you move up and down the tree.
>The cost of locking is enormous. It is about 10X
>slower with fine grain locking turned on then without
>locking.
>
>Doing a coarse lock that locks entire tables for a
>each query would be a lot faster but it increase the
>wait time for some queries. But a 10X speed up would
>you notice.
>
>Anyway how keen are you guys to have fine grain
>locking? I can't get it to go fast.
>
>If you don't need fine grain concurrency then I may
>abandon BLink-Trees and just do BTrees which are
>simpler anyway.
>
>I have an implementation (without nio) if you guys
>want to look at code.
>Oh and with fine grain locking turned off (and no
>memory page misses ) the BLink Tree is only 10%
>slower then the java.util.TreeMap. Most of that speed
>loss is from keeping the BTree nodes in a cache so
>they can be used with nio.
>
>Karl
>
>
>
>
>=====
>Karl Meissner
>
>...........................................................
>: Meissner Software Development, LLC :
>: "Software development and project management services." :
>: http://meissner.v0.net/resume.htm :
>...........................................................
>
>__________________________________________________
>Do You Yahoo!?
>Yahoo! Tax Center - online filing with TurboTax
>http://taxes.yahoo.com/
>
>_______________________________________________
>hsqldb-developers mailing list
>[EMAIL PROTECTED]
>https://lists.sourceforge.net/lists/listinfo/hsqldb-developers
>
>
>_______________________________________________
>hsqldb-developers mailing list
>[EMAIL PROTECTED]
>https://lists.sourceforge.net/lists/listinfo/hsqldb-developers
_______________________________________________
hsqldb-developers mailing list
[EMAIL PROTECTED]
https://lists.sourceforge.net/lists/listinfo/hsqldb-developers
