SQLite4: Check-in [414ed6da4e]

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview

Comment:	Further documentation updates.
Downloads:	Tarball \| ZIP archive \| SQL archive
Timelines:	family \| ancestors \| descendants \| both \| trunk
Files:	files \| file ages \| folders
SHA1:	414ed6da4e175c29d4b27f893a3fd110fc4ca860
User & Date:	dan 2012-11-13 20:16:00

Context

2012-11-14
18:23		Improvements to lsmusr.wiki. check-in: e47b5e3ae6 user: dan tags: trunk
2012-11-13
20:16		Further documentation updates. check-in: 414ed6da4e user: dan tags: trunk
18:44		Add lsmapi.wiki. And the script that generates it from lsm.h - tool/mklsmapi.tcl. check-in: 2377f4f991 user: dan tags: trunk

Changes

Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to tool/mklsmapi.tcl.

   180    180   close $fd
   181    181   
   182    182   puts $document_preamble
   183    183   puts "<h1>LSM API Topics</h1>"
   184    184   puts <ol>
   185    185   puts $document_toc
   186    186   puts </ol>
   187         -set s "display:block;float:left;width:40ex"
          187  +set s "display:block;float:left;width:35ex"
   188    188   puts "<h1 style=clear:both>All LSM API Functions</h1>"
   189    189   foreach sym [lsort $document_functions] {
   190    190     puts "<span style=$s><a href=#$sym>$sym</a></span>"
   191    191   }
   192    192   puts "<br style=clear:both>"
   193    193   puts "<h1 style=clear:both>All LSM API Types</h1>"
   194    194   foreach sym [lsort $document_types] {

Changes to www/lsmapi.wiki.

     32     33     34     35     36     37     38     39     40     41     42     43     44     45     46     47     48     49     50     51     52     53     54     55     56     57     58     59     60     61     62     63     64     65     66     67                                   68     69     70      71     72     73     74     75     76     77     78     79     80     81     82     83     84     85     86     87     88     89     90     91     92     93     94     95     96     97     98     99    100    101    102    103    104    105    106    107    108    109    110    111    112                                            113    114    115    116    117    118    119

class="diffln"> 31 31 <li><a href="#opening" style=text-decoration:none>Opening and Closing Database Cursors</a> 32 <li><a href="#positioning" style=text-decoration:none>Positioning Database Cursors</a> 33 <li><a href="#extracting" style=text-decoration:none>Extracting Data From Database Cursors</a> 34 <li><a href="#change" style=text-decoration:none>Change these!!</a> 35 36 </ol> 37 <h1 style=clear:both>All LSM API Functions</h1> -<a href=#lsm_begin>lsm_begin</a> -<a href=#lsm_checkpoint>lsm_checkpoint</a> -<a href=#lsm_ckpt_size>lsm_ckpt_size</a> -<a href=#lsm_close>lsm_close</a> -<a href=#lsm_commit>lsm_commit</a> -<a href=#lsm_config>lsm_config</a> -<a href=#lsm_config_log>lsm_config_log</a> -<a href=#lsm_config_work_hook>lsm_config_work_hook</a> -<a href=#lsm_csr_close>lsm_csr_close</a> -<a href=#lsm_csr_cmp>lsm_csr_cmp</a> -<a href=#lsm_csr_first>lsm_csr_first</a> -<a href=#lsm_csr_key>lsm_csr_key</a> -<a href=#lsm_csr_last>lsm_csr_last</a> -<a href=#lsm_csr_next>lsm_csr_next</a> -<a href=#lsm_csr_open>lsm_csr_open</a> -<a href=#lsm_csr_prev>lsm_csr_prev</a> -<a href=#lsm_csr_seek>lsm_csr_seek</a> -<a href=#lsm_csr_valid>lsm_csr_valid</a> -<a href=#lsm_csr_value>lsm_csr_value</a> -<a href=#lsm_delete>lsm_delete</a> -<a href=#lsm_delete_range>lsm_delete_range</a> -<a href=#lsm_flush>lsm_flush</a> -<a href=#lsm_free>lsm_free</a> -<a href=#lsm_info>lsm_info</a> -<a href=#lsm_insert>lsm_insert</a> -<a href=#lsm_new>lsm_new</a> -<a href=#lsm_open>lsm_open</a> -<a href=#lsm_rollback>lsm_rollback</a> -<a href=#lsm_tree_size>lsm_tree_size</a> -<a href=#lsm_work>lsm_work</a> 38 +<a href=#lsm_begin>lsm_begin</a> 39 +<a href=#lsm_checkpoint>lsm_checkpoint</a> 40 +<a href=#lsm_ckpt_size>lsm_ckpt_size</a> 41 +<a href=#lsm_close>lsm_close</a> 42 +<a href=#lsm_commit>lsm_commit</a> 43 +<a href=#lsm_config>lsm_config</a> 44 +<a href=#lsm_config_log>lsm_config_log</a> 45 +<a href=#lsm_config_work_hook>lsm_config_work_hook</a> 46 +<a href=#lsm_csr_close>lsm_csr_close</a> 47 +<a href=#lsm_csr_cmp>lsm_csr_cmp</a> 48 +<a href=#lsm_csr_first>lsm_csr_first</a> 49 +<a href=#lsm_csr_key>lsm_csr_key</a> 50 +<a href=#lsm_csr_last>lsm_csr_last</a> 51 +<a href=#lsm_csr_next>lsm_csr_next</a> 52 +<a href=#lsm_csr_open>lsm_csr_open</a> 53 +<a href=#lsm_csr_prev>lsm_csr_prev</a> 54 +<a href=#lsm_csr_seek>lsm_csr_seek</a> 55 +<a href=#lsm_csr_valid>lsm_csr_valid</a> 56 +<a href=#lsm_csr_value>lsm_csr_value</a> 57 +<a href=#lsm_delete>lsm_delete</a> 58 +<a href=#lsm_delete_range>lsm_delete_range</a> 59 +<a href=#lsm_flush>lsm_flush</a> 60 +<a href=#lsm_free>lsm_free</a> 61 +<a href=#lsm_info>lsm_info</a> 62 +<a href=#lsm_insert>lsm_insert</a> 63 +<a href=#lsm_new>lsm_new</a> 64 +<a href=#lsm_open>lsm_open</a> 65 +<a href=#lsm_rollback>lsm_rollback</a> 66 +<a href=#lsm_tree_size>lsm_tree_size</a> 67 +<a href=#lsm_work>lsm_work</a> 68 69 <h1 style=clear:both>All LSM API Types</h1> -<a href=#lsm_compress>lsm_compress</a> 70 +<a href=#lsm_compress>lsm_compress</a> 71 72 <h1>All LSM API Constants</h1> -<a href=#LSM_BUSY>LSM_BUSY</a> -<a href=#LSM_CANTOPEN>LSM_CANTOPEN</a> -<a href=#LSM_CONFIG_AUTOCHECKPOINT>LSM_CONFIG_AUTOCHECKPOINT</a> -<a href=#LSM_CONFIG_AUTOWORK>LSM_CONFIG_AUTOWORK</a> -<a href=#LSM_CONFIG_BLOCK_SIZE>LSM_CONFIG_BLOCK_SIZE</a> -<a href=#LSM_CONFIG_GET_COMPRESSION>LSM_CONFIG_GET_COMPRESSION</a> -<a href=#LSM_CONFIG_LOG_SIZE>LSM_CONFIG_LOG_SIZE</a> -<a href=#LSM_CONFIG_MAX_FREELIST>LSM_CONFIG_MAX_FREELIST</a> -<a href=#LSM_CONFIG_MMAP>LSM_CONFIG_MMAP</a> -<a href=#LSM_CONFIG_MULTIPLE_PROCESSES>LSM_CONFIG_MULTIPLE_PROCESSES</a> -<a href=#LSM_CONFIG_NMERGE>LSM_CONFIG_NMERGE</a> -<a href=#LSM_CONFIG_PAGE_SIZE>LSM_CONFIG_PAGE_SIZE</a> -<a href=#LSM_CONFIG_SAFETY>LSM_CONFIG_SAFETY</a> -<a href=#LSM_CONFIG_SET_COMPRESSION>LSM_CONFIG_SET_COMPRESSION</a> -<a href=#LSM_CONFIG_USE_LOG>LSM_CONFIG_USE_LOG</a> -<a href=#LSM_CONFIG_WRITE_BUFFER>LSM_CONFIG_WRITE_BUFFER</a> -<a href=#LSM_CORRUPT>LSM_CORRUPT</a> -<a href=#LSM_ERROR>LSM_ERROR</a> -<a href=#LSM_FULL>LSM_FULL</a> -<a href=#LSM_INFO_ARRAY_PAGES>LSM_INFO_ARRAY_PAGES</a> -<a href=#LSM_INFO_ARRAY_STRUCTURE>LSM_INFO_ARRAY_STRUCTURE</a> -<a href=#LSM_INFO_DB_STRUCTURE>LSM_INFO_DB_STRUCTURE</a> -<a href=#LSM_INFO_FREELIST>LSM_INFO_FREELIST</a> -<a href=#LSM_INFO_LOG_STRUCTURE>LSM_INFO_LOG_STRUCTURE</a> -<a href=#LSM_INFO_NREAD>LSM_INFO_NREAD</a> -<a href=#LSM_INFO_NWRITE>LSM_INFO_NWRITE</a> -<a href=#LSM_INFO_PAGE_ASCII_DUMP>LSM_INFO_PAGE_ASCII_DUMP</a> -<a href=#LSM_INFO_PAGE_HEX_DUMP>LSM_INFO_PAGE_HEX_DUMP</a> -<a href=#LSM_IOERR>LSM_IOERR</a> -<a href=#LSM_MISUSE>LSM_MISUSE</a> -<a href=#LSM_NOMEM>LSM_NOMEM</a> -<a href=#LSM_OK>LSM_OK</a> -<a href=#LSM_PROTOCOL>LSM_PROTOCOL</a> -<a href=#LSM_SAFETY_FULL>LSM_SAFETY_FULL</a> -<a href=#LSM_SAFETY_NORMAL>LSM_SAFETY_NORMAL</a> -<a href=#LSM_SAFETY_OFF>LSM_SAFETY_OFF</a> -<a href=#LSM_SEEK_EQ>LSM_SEEK_EQ</a> -<a href=#LSM_SEEK_GE>LSM_SEEK_GE</a> -<a href=#LSM_SEEK_LE>LSM_SEEK_LE</a> -<a href=#LSM_SEEK_LEFAST>LSM_SEEK_LEFAST</a> 73 +<a href=#LSM_BUSY>LSM_BUSY</a> 74 +<a href=#LSM_CANTOPEN>LSM_CANTOPEN</a> 75 +<a href=#LSM_CONFIG_AUTOCHECKPOINT>LSM_CONFIG_AUTOCHECKPOINT</a> 76 +<a href=#LSM_CONFIG_AUTOWORK>LSM_CONFIG_AUTOWORK</a> 77 +<a href=#LSM_CONFIG_BLOCK_SIZE>LSM_CONFIG_BLOCK_SIZE</a> 78 +<a href=#LSM_CONFIG_GET_COMPRESSION>LSM_CONFIG_GET_COMPRESSION</a> 79 +<a href=#LSM_CONFIG_LOG_SIZE>LSM_CONFIG_LOG_SIZE</a> 80 +<a href=#LSM_CONFIG_MAX_FREELIST>LSM_CONFIG_MAX_FREELIST</a> 81 +<a href=#LSM_CONFIG_MMAP>LSM_CONFIG_MMAP</a> 82 +<a href=#LSM_CONFIG_MULTIPLE_PROCESSES>LSM_CONFIG_MULTIPLE_PROCESSES</a> 83 +<a href=#LSM_CONFIG_NMERGE>LSM_CONFIG_NMERGE</a> 84 +<a href=#LSM_CONFIG_PAGE_SIZE>LSM_CONFIG_PAGE_SIZE</a> 85 +<a href=#LSM_CONFIG_SAFETY>LSM_CONFIG_SAFETY</a> 86 +<a href=#LSM_CONFIG_SET_COMPRESSION>LSM_CONFIG_SET_COMPRESSION</a> 87 +<a href=#LSM_CONFIG_USE_LOG>LSM_CONFIG_USE_LOG</a> 88 +<a href=#LSM_CONFIG_WRITE_BUFFER>LSM_CONFIG_WRITE_BUFFER</a> 89 +<a href=#LSM_CORRUPT>LSM_CORRUPT</a> 90 +<a href=#LSM_ERROR>LSM_ERROR</a> 91 +<a href=#LSM_FULL>LSM_FULL</a> 92 +<a href=#LSM_INFO_ARRAY_PAGES>LSM_INFO_ARRAY_PAGES</a> 93 +<a href=#LSM_INFO_ARRAY_STRUCTURE>LSM_INFO_ARRAY_STRUCTURE</a> 94 +<a href=#LSM_INFO_DB_STRUCTURE>LSM_INFO_DB_STRUCTURE</a> 95 +<a href=#LSM_INFO_FREELIST>LSM_INFO_FREELIST</a> 96 +<a href=#LSM_INFO_LOG_STRUCTURE>LSM_INFO_LOG_STRUCTURE</a> 97 +<a href=#LSM_INFO_NREAD>LSM_INFO_NREAD</a> 98 +<a href=#LSM_INFO_NWRITE>LSM_INFO_NWRITE</a> 99 +<a href=#LSM_INFO_PAGE_ASCII_DUMP>LSM_INFO_PAGE_ASCII_DUMP</a> 100 +<a href=#LSM_INFO_PAGE_HEX_DUMP>LSM_INFO_PAGE_HEX_DUMP</a> 101 +<a href=#LSM_IOERR>LSM_IOERR</a> 102 +<a href=#LSM_MISUSE>LSM_MISUSE</a> 103 +<a href=#LSM_NOMEM>LSM_NOMEM</a> 104 +<a href=#LSM_OK>LSM_OK</a> 105 +<a href=#LSM_PROTOCOL>LSM_PROTOCOL</a> 106 +<a href=#LSM_SAFETY_FULL>LSM_SAFETY_FULL</a> 107 +<a href=#LSM_SAFETY_NORMAL>LSM_SAFETY_NORMAL</a> 108 +<a href=#LSM_SAFETY_OFF>LSM_SAFETY_OFF</a> 109 +<a href=#LSM_SEEK_EQ>LSM_SEEK_EQ</a> 110 +<a href=#LSM_SEEK_GE>LSM_SEEK_GE</a> 111 +<a href=#LSM_SEEK_LE>LSM_SEEK_LE</a> 112 +<a href=#LSM_SEEK_LEFAST>LSM_SEEK_LEFAST</a> 113 114 <h2 id=lsm>LSM Error Codes<a id=LSM_OK></a><a id=LSM_ERROR></a><a id=LSM_BUSY></a><a id=LSM_NOMEM></a><a id=LSM_IOERR></a><a id=LSM_CORRUPT></a><a id=LSM_FULL></a><a id=LSM_CANTOPEN></a><a id=LSM_PROTOCOL></a><a id=LSM_MISUSE></a></h2> 115 <verbatim>#define LSM_OK 0 116 #define LSM_ERROR 1 117 #define LSM_BUSY 5 118 #define LSM_NOMEM 7 119 #define LSM_IOERR 10

Changes to www/lsmusr.wiki.

    69     69   it is perhaps more accurate to say that an LSM database is stored on disk
    70     70   in a single database file and a single (optional) log file.
    71     71   
    72     72   <p>If required, it is possible to configure LSM to use external data
    73     73   compression and/or encryption functions to transform data before it is
    74     74   stored in the database file.
    75     75   
    76         -<p><i>Say something about the difference in performance characteristics 
    77         -between a b-tree and whatever it is LSM is. Link the performance graphs page.
    78         -</i>
           76  +<p>Many database systems that support range queries, including <a
           77  +href=http://www.sqlite.org>SQLite 3</a>, Berkeley DB and Kyoto Cabinet, are
           78  +based on a <a href="http://en.wikipedia.org/wiki/B-tree">b-tree data
           79  +structure</a> or variant thereof. A b-tree structure minimizes the number of
           80  +disk sectors that must be read from disk when searching the database for a
           81  +specific key. However, b-tree implementations usually suffer from poor write
           82  +localization - updating the contents of a b-tree often involves modifying the
           83  +contents of nodes scattered throughout the database file. If the database is
           84  +stored on a spinning disk (HDD), then the disk heads must be moved before
           85  +writing non-contiguous sector, which is extremely slow. If the database is
           86  +stored on solid state storage (SDD) a similar phenomena is encountered due 
           87  +to the large erase-block sizes. In general, writing to a series of contiguous
           88  +disk sectors is orders of magnitude faster than updating to the same number
           89  +of disk sectors scattered randomly throughout a large file. Additionally,
           90  +b-tree structures are prone to fragmentation, reducing the speed of range
           91  +queries.
           92  +
           93  +<p><i>Todo: Should have references for the claims above.</i>
           94  +
           95  +<p><i>Also, fix the link in the next paragraph to point to something more
           96  +specific.</i>
           97  +
           98  +<p>LSM uses a <a href=lsm.wiki>different data structure</a> that makes the
           99  +following performance tradeoffs relative to a b-tree:
          100  +
          101  +<ul>
          102  +  <li> A very large percentage of the disk sectors modified are contiguous.
          103  +       Additionally, in many cases the total number of sectors written
          104  +       to disk is reduced. This makes writing to an LSM database much
          105  +       faster than the equivalent b-tree.
          106  +
          107  +  <li> LSM databases do not suffer from fragmentation to the same degree
          108  +       as b-trees. This means that the performance of large range queries 
          109  +       does not degrade as the database is updated as it may with a b-tree.
          110  +
          111  +  <li> It is accepted that under some circumstances searching an LSM 
          112  +       database for a given key will involve examining more disk sectors
          113  +       than it would with a b-tree. In this sense both b-trees and LSM
          114  +       provide O(log(N)) efficiency, but the base of the logarithm is 
          115  +       generally larger for a b-tree than for LSM.
          116  +</ul>
          117  +
          118  +<p>In other words, all things considered equal, writing to an LSM database
          119  +should be very fast and scanning through large ranges of keys should also
          120  +perform well, but searching the database for specific keys may be slightly
          121  +slower than when using a b-tree based system. Additionally, avoiding random
          122  +writes in favour of largely contiguous updates can significantly reduce the
          123  +wear on SSD or flash memory devices.
          124  +
          125  +<p>Although it has quite different features to LSM in other respects, 
          126  +LevelDB makes similar performance tradeoffs.
          127  +
          128  +<p>Benchmark test results for LSM are available here. <i>Todo: Link to a page
          129  +with performance graphs here</i>
          130  +
    79    131   
    80    132   <h1 id=using_lsm_in_applications>2. Using LSM in Applications </h1>
    81    133   
    82    134   <p>LSM is not currently built or distributed independently. Instead, it
    83    135   is part of the SQLite4 library. To use LSM in an application, the application
    84    136   links against libsqlite4 and includes the header file "lsm.h" in any files
    85    137   that access the LSM API.