Database system

BACKGROUND

0001The present invention relates to operating a database system and to the database system itself. In one embodiment, the invention provides a prefix-based memory allocator for paged leaf nodes of a search tree.

0002In database systems, a checkpoint is an administrative operation in which a database image is persistently stored for use in a possible future recovery of a shut down, or a failed server. In in-memory databases, a database image (a checkpoint image) is also instrumental in starting up the database server, because all the data has to be loaded into memory. Depending upon the implementation specifics, a checkpoint image may consist of complete indexes and storage pages (storing the user data), or may consist of storage pages only, or may consist of something between those two extremes. If the indexes are not included in the checkpoint image, they are called transient indexes, and they need to be recreated when the database is restored from a checkpoint image.

0003The user data may be envisaged as a collection of database table rows and are commonly referred to as tuples. The tuples are pointed to by index entries using direct pointers. During a database checkpoint, the tuples are copied to page-sized memory buffers (“checkpoint buffer”) for a disk write. When an in-memory database engine is started, all data is read from a checkpoint image stored on secondary storage, typically a hard disk. Client requests can be served as soon as the data (the database rows) becomes accessible in the main memory. In an in-memory database engine, user data and the necessary navigation information (indexes) need to be present. If indexes are transient, the rows are re-inserted into the database and, in addition, the indexes are re-created. Alternatively, if the checkpoint includes necessary navigation information within the image, it is possible to read data from the checkpoint so that the server can be opened instantaneously, and user data can be restored based on the client's needs.

0004The first option is becoming useless due to ever-increasing memory usage and corresponding database sizes. In practical database implementations, the reading of an entire checkpoint image to memory can last several hours. The second solution refers to necessary navigation information. That is, row pointers of indexes are useless because the rows are likely to be positioned in different memory locations when they are restored from the checkpoint. Thus, address translation is needed so that row pointers can be redirected to correct locations of the rows in the checkpoint image. Excluding transient indexes from a checkpoint greatly simplifies, and speeds up, checkpoint creation. The downside is that the possibility of rapidly finding individual rows from a large checkpoint image is impossible.

BRIEF SUMMARY

0005An embodiment of the present invention is directed to operating a database system, comprising: storing a database table comprising a plurality of rows, each row comprising a key value and one or more attributes; storing a primary index for the database table, the primary index comprising a plurality of leaf nodes, each leaf node comprising one or more key values and respective memory addresses, each memory address defining the storage location of the respective key value; creating a new leaf node comprising one or more key values and respective memory addresses; performing a memory allocation analysis based upon the lowest key value of the new leaf node to identify a non-full memory page storing a leaf node whose lowest key value is similar to the lowest key value of the new leaf node; and storing the new leaf node in the identified non-full memory page.

0006Embodiments of the present invention may be provided as methods, systems, and/or computer program products, and will now be described, by way of example only, with reference to the accompanying drawings, in which:

BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS

0007<figref idref="DRAWINGS">FIGS. 1 and 2</figref> are schematic diagrams of a database system;

0008<figref idref="DRAWINGS">FIGS. 3</figref> is a schematic diagram of a database table and a primary and secondary index derived from the database table;

0009<figref idref="DRAWINGS">FIG. 4</figref> is a schematic diagram of a row address translation table and disk address array;

0010<figref idref="DRAWINGS">FIG. 5</figref> is a schematic diagram of an allocator index and leaf node pages;

0011<figref idref="DRAWINGS">FIG. 6</figref> is a flowchart of a method of allocating memory to a new leaf node;

0012<figref idref="DRAWINGS">FIG. 7</figref> is a flowchart of a method of performing a checkpoint operation; and

0013<figref idref="DRAWINGS">FIG. 8</figref> is a flowchart of a method of performing a restore operation.

DETAILED DESCRIPTION

0014Owing to an embodiment of the present invention, it is possible to provide a database system that can be applied to database engines that use transient indexes, but provides means to locate individual rows from a checkpoint image in a much faster time compared to the time required for a full checkpoint image load. The effect of the invention is that instead of 1 to 10 hour start-up time with large database sizes, the database engine can start up in less than a minute, and be ready to serve client requests at the speed of commodity disk-based database engines. An embodiment of the invention makes it possible to find a leaf node of a database index from secondary storage, among millions of nodes, by reading less than 10% of the nodes (10% being the worst case scenario). The necessary navigation information is collected while leaf nodes are copied to the checkpoint image, and the invention generates no noticeable processing overhead in creation time for the checkpoint image.

0015Being able to find index leaf nodes quickly provides numerous advantages. For example, an in-memory database server which uses transient indexes (where indexes are not checkpointed) with a very large database can be opened for client requests in less than a minute compared to the several hours that it takes if the database has to be loaded into memory before opening the database. After a few minutes, an embodiment of the invention provides an average performance that is comparable to commodity disk-based database engine. The checkpoint operation is arranged so that the leaf nodes of indexes are included in checkpoint images. Thus, a checkpoint image will consist of a small amount of navigation information, called a leaf page index, to address the disk pages where leaf nodes are stored, leaf pages that include leaf nodes, and database contents.

0016In order to create a checkpoint image as described above, a new memory allocation scheme for leaf nodes is introduced. Every new leaf node needs memory, and that is requested from a memory allocator which then returns the address of a memory location where a new leaf node can be created. The memory allocator has several pools of memory (pre-allocated from the operating system), and chooses a location for every new leaf node by using a criteria (described in detail below). As a consequence, those leaf nodes that include keys which are close to each other by value will end up in memory areas from the same pool. In other words, the memory allocator loosely classifies leaf nodes so that they will be included in the checkpoint close to each other, thus making it possible to easily find all similar values by examining only a few disk pages in the checkpoint image.

0017<figref idref="DRAWINGS">FIG. 1</figref> shows a database system <b>100</b> in which an in-memory database management system <b>120</b> is run by the database system <b>100</b>. The in-memory database management system <b>120</b> allows one or more users to access a database concurrently. A user can be an end user who interacts with the database management system <b>120</b> from a client side workstation <b>115</b> through an online application <b>110</b> or from an interface provided by the in-memory database management system <b>120</b>. The database management system <b>120</b> comprises a number of hardware and software components which interact with each other in order to query, retrieve, and store user requests. The hardware components are depicted in <figref idref="DRAWINGS">FIG. 1</figref> and the software components are depicted in <figref idref="DRAWINGS">FIG. 2</figref>. Clients of the system <b>100</b> can be located either in the same computer with the database server process or on a different computer. A “client” of the system can be either a specific device or a process that make requests to the database.

0018The hardware components form the computing platform in which the database management system <b>120</b> resides and operates, for example a server which is accessible across a network. These hardware components comprise main memory <b>135</b>, secondary storage volumes <b>105</b>, I/O devices, device controllers, I/O channels and CPUs <b>125</b>, etc. The main memory <b>135</b> is in the form of random access memory (RAM) and is used as a primary storage unit where all data is stored “in-memory”. Database files are contained within a database file unit and transaction logs provide a persistent backup of the data in the database. In this document, the term RAM means the main memory <b>135</b> and is the primary storage unit. Secondary storage is provided by secondary storage volumes <b>105</b> such as disk storage. However, it will be obvious to a person skilled in the art that disk storage is not the only technological means in which to implement persistent storage.

0019The secondary storage volumes <b>105</b>, which may be magnetic disk storage, are used to backup data and to store checkpoint information and logging information. Data may be backed up onto one or a plurality of secondary storage volumes <b>105</b>. The secondary storage volumes <b>105</b> may be directly connectable to the database management system <b>120</b> or connectable and accessed across a network. Therefore in an in-memory database management system <b>120</b>, the data resides in RAM <b>135</b> and the data is backed up to a secondary storage volume <b>105</b>.

0020Referring to <figref idref="DRAWINGS">FIG. 2</figref>, a communication component <b>200</b> of the database management system <b>120</b> receives requests from users for data stored in one or more of the databases. A request received from a user is in the form of a query in a query language specified by the database management application, for example, a structured query language, such as SQL. The communication component <b>200</b> also receives the results of the query for transmitting back to the requesting user <b>115</b>. A query parser, estimator, and optimiser component <b>210</b> receives a query from the communication component <b>200</b>, transforms the query into a set of actions, and determines the optimal strategy for executing the query. A query can comprise both read and update operations or only a single type of operation.

0021A tasking subsystem <b>205</b> provides a means to receive tasks requested by users <b>115</b> (the client devices or processes) and, if necessary, to split the received tasks into sub-tasks and assign the sub-tasks to server threads. This allows the database system to serve all user requests. Alternatively, a client/thread model is deployed in which each client request is served by a single thread. Thus each client task is executed continuously from the beginning to the end of the assigned task.

0022A memory management component <b>220</b> receives memory allocations and memory release requests from an in-memory engine (not shown). There is typically a plurality of memory managers <b>220</b> assigned to different types of requests in order to satisfy a large number of simultaneous requests. A table engine <b>215</b> comprises a transaction engine <b>225</b>, an in-memory index engine <b>230</b>, an in-memory storage engine <b>235</b>, and a lock manager <b>240</b>. The purpose of the table engine <b>215</b> is to manage all of the database tables and indexes of the database management system <b>120</b>. The transaction engine <b>225</b> receives inputs from the query parser component <b>210</b> and creates transactions from the input. For example, the input may comprise a query written in SQL, for example

0023(INSERT INTO TAB1 VALUES (1, ‘John’);)

0024The transaction engine <b>225</b> decomposes the statements to ensure that there is no row with identifier ‘1’ already in the database, and inserts the key ‘1’ into the index and the row into storage.

0025A logging subsystem component <b>255</b> records all of the modifications to the data stored in RAM <b>135</b> and writes the modifications to the secondary storage <b>105</b>. Logs are used to ensure that a consistent database can be recovered even if the database image is not available. The lock manager <b>240</b> provides a shared and exclusive lock for client threads that need to perform protected operations to the data stored in the database. A requesting client thread must acquire a lock to a row and the row is exclusively locked for the client thread for the duration of operation before its execution is permitted. Such a client thread acquires a lock name by using a primary key of the row, for example. Then the client requests the lock from the lock manager <b>240</b> for the lock name. The modified in-memory index engine <b>230</b> provides one or more indexes for each database table which is held in memory <b>135</b>.

0026<figref idref="DRAWINGS">FIG. 3</figref> illustrates two types of indexes, namely a primary index <b>300</b> and a secondary index <b>305</b>, and illustrates how these indexes are derived from a database table <b>310</b>. A simplified database table <b>310</b> is shown, having columns that comprise a memory address <b>320</b> (shown in the figures using the notation OX followed by a value) of the row and two attributes <b>325</b>, <b>330</b>. The first attribute <b>325</b> is a numeric value, and is also the primary key attribute. A second attribute <b>330</b> is of character type, and is indexed by the secondary index. For example, the data attribute ‘g’ in the first row of column <b>330</b> has a primary key attribute of the value ‘3’ and has a memory address of ‘5’ (and accordingly, a hexadecimal value of the memory address is in the figure as 0x5) and the data attribute T in the third row of column <b>330</b> has a primary key attribute of the value ‘6’ and has a memory address of ‘4’. Typically, every database table <b>310</b> has a user-specified primary key attribute <b>325</b>, which can consist of one or multiple attributes. The primary key attribute <b>325</b> must be unique among the rows in the table <b>310</b>. If there is no user-defined primary key attribute <b>325</b>, the database management system generates an identifier for each row in the table.

0027The primary index <b>300</b> comprises a number of values, namely the primary key attribute <b>325</b> and a memory address <b>320</b> that specifies where the database row <b>335</b> is located in memory <b>135</b>. Each of these values is held in a leaf node <b>315</b>, and a plurality of leaf nodes <b>315</b> form a leaf node page <b>360</b> of a specified page size. The secondary index <b>305</b> comprises the secondary key attribute <b>330</b> and its associated pointer to the memory address <b>320</b>. During a checkpoint operation, row addresses and offsets to their corresponding disk page number in the disk array are stored in a row address translation table <b>400</b> (as discussed below with reference to <figref idref="DRAWINGS">FIG. 4</figref>).

0028Each row <b>335</b> in a database table <b>310</b> comprises two attributes, namely a name <b>330</b> and a primary key identifier <b>325</b>. For example, the name <b>330</b> may be a customer name and the attribute <b>325</b> may be a customer identifier, in which case the primary key identifier <b>325</b> is used as an identifier for each customer listed in the table (i.e., for each row <b>335</b> of data). When a new customer is inserted into the database table <b>310</b>, the new row must at least have a primary key attribute <b>325</b>. The row is stored in tuple storage and the primary key attribute is stored/inserted into the primary index <b>300</b> and then the name of the customer is inserted into the secondary index <b>305</b>. Both the primary and the secondary indexes are transient, except their leaf nodes <b>315</b> which are stored in a checkpoint image.

0029Indexes are typically tree-like data structures or hash function based indexes (hash indexes). A typical tree like structure is a “B+-tree”. Each tree-like data structure comprises a root node, branch nodes, and leaf nodes. The root node <b>340</b> may be either a leaf node <b>315</b> or a node having two or more children. Internal nodes (i.e., not leaf nodes) may comprise between v and 2v keys, and a node with k keys has k+1 children. Leaves are always on the same level of a branch. Nodes that do not have any child nodes are described as leaf nodes, i.e., terminal nodes. An internal node is any node of the tree that comprises pointers to one or more child nodes. Leaf nodes comprise one or more key values, and are pointed to by pointers <b>355</b>. Pointers <b>355</b> and <b>345</b> are internal pointers of the primary index. Every memory address (shown in the figure as 0x followed by a value) in each of the leaf nodes is a row/tuple pointer referring to a memory address where the row is located.

0030A root node <b>340</b> comprises node pointers <b>345</b> to branch nodes <b>350</b> A branch node <b>350</b> comprises pointers <b>355</b> to leaf nodes <b>315</b> or to other branch nodes. A leaf node <b>315</b> comprises index keys, pointers to database rows, and horizontal pointers to other leaf nodes. A leaf node page <b>360</b> is a page including one or more leaf nodes <b>315</b>. This is because leaf nodes <b>315</b> in in-memory database management systems are typically smaller than disk pages. For example, some types of in-memory database have a node size of 512 bytes and a default page size of 16 kilobytes. Storage pages are collections of database rows called “tuples”. Tuples are ordered by the primary key, grouped to logical storage pages, and pointed to by index entries using direct pointers. During a database checkpoint, the storage pages including one or more modified tuples are copied to a page size memory buffer called a checkpoint buffer for disk write operations.

0031When a checkpoint operation is performed, a checkpoint component <b>250</b> (<figref idref="DRAWINGS">FIG. 2</figref>) communicates with the in-memory index engine <b>230</b>, the in-memory storage engine <b>235</b>, and the table engine <b>215</b> to generate and write a checkpoint image of a database to a secondary storage medium <b>105</b>. A checkpoint is created when a database is open and active. The checkpoint component <b>250</b> performs a process whereby altered storage pages are written from one storage unit, such as RAM <b>135</b>, to another storage unit, such as disk <b>105</b>. The end result of a checkpoint is a snapshot of a database being stored on the disk <b>105</b>.

0032The in-memory index engine <b>230</b> associates a global checkpoint counter with each database or database instance stored on the server, and the global checkpoint counter is incremented by the value of one each time a new checkpoint operation commences. A copy of the global checkpoint counter is also associated with each leaf node page <b>360</b>. If the copy of the global checkpoint counter associated with each leaf node page <b>340</b> equals that of the global checkpoint counter, then the index has already been checkpointed, i.e., its altered leaf node pages <b>360</b> are already copied to the checkpoint buffer for disk write. However, if the copy of the global checkpoint counter associated with a leaf node page <b>340</b> comprises a value which is smaller than that of the value of the global checkpoint counter, then the leaf node page <b>360</b> has not been checkpointed.

0033The in-memory index engine <b>230</b> is responsible for providing a global access controlling mechanism, for example a global gate. Entering the global gate ensures that there are no further updates to any of the database tables. Each time a database is checkpointed, the checkpointing operation enters the global gate in an exclusive mode, thus preventing any updates to the tables. This process is called a checkpoint freeze.

0034The checkpoint component <b>250</b>, during a checkpoint freeze operation, prevents updates to any of the indexes and pages. The checkpoint component <b>250</b> in conjunction with the in-memory storage engine <b>235</b> writes “dirty” pages <b>360</b> (i.e., pages that have been updated but not incorporated into any checkpoint image) for storage to a checkpoint buffer, and internal index pointers <b>355</b>, <b>345</b> and offsets pointing to their corresponding relative disk page locations are collected and written to a row address translation table.

0035An internal index pointer <b>355</b>, <b>345</b> is a direct memory reference to a row (tuple) pointer stored in either an internal node or a leaf index node. An offset is a location relative to the beginning of a location in a disk address array. If, for example, there is an address ‘0x12345’ having an offset value of 2 in a row address table, this means that the row in memory position ‘0x12345’ has a copy in the checkpoint image and the actual disk address of the copy is the third from the beginning of the disk address array. A “two” offset means two steps forwards from the beginning. Row pointers are hexadecimal addresses in leaf nodes.

0036<figref idref="DRAWINGS">FIG. 4</figref> shows an example of a row address translation table <b>400</b> which translates the row addresses (i.e., addresses in RAM) to secondary storage disk addresses after checkpointing. The row address translation table <b>400</b> is stored and managed by the in-memory index engine <b>230</b>. Disk page addresses <b>415</b> are stored in an ordered array, which is a continuous memory area where 4-byte disk addresses are stored next to each other, and this is where offsets in the row address translation table <b>400</b> point. The array <b>405</b> of disk page addresses <b>415</b> is also incorporated into the checkpoint image <b>410</b>. Leaf node pages' relation identifiers (discussed below) and disk addresses are stored in a relation identifier directory. Database rows are written to the checkpoint image <b>410</b> as pages equal in size to the disk block. Every page has rows from the same table.

0037A relation identifier is a value that identifies one database table from another. The table engine <b>215</b> generates the relation identifier for each table at the time a new table is created. When leaf node pages (of indexes) are written to a checkpoint image, the relation identifier and the target address of the newly created table are stored into a relation identifier directory. The relation identifier directory is incorporated into the checkpoint image, and this directory is used when the database is being restored to find leaf nodes pages of indexes of tables. When all necessary pages are copied to disk, the relation identifier directory itself is copied to disk, thus becoming part of the checkpoint image <b>410</b>.

0038Also for incorporation into the checkpoint image <b>410</b> is the row address translation table <b>400</b> which comprises direct row pointers and their offsets which point to their corresponding relative disk page locations. The row address translation table <b>400</b> is created when leaf nodes <b>315</b> are copied for checkpointing. Each row address that is stored in a leaf node <b>315</b> is copied to row address translation table <b>400</b> and the disk page address is copied to the disk address array <b>405</b>. The offset of the disk page address <b>415</b> in the disk address array <b>405</b> is copied with the row addresses. The forthcoming target address on the disk is known already when the row addresses are copied from leaf nodes so that disk page addresses can be copied first to the disk address array <b>405</b> and the disk address offset can be inserted into the row address translation table <b>400</b> with each row address. Thus the generated checkpoint image <b>410</b> comprises database table rows <b>335</b>, leaf nodes <b>315</b> associated with the indexes <b>300</b> and <b>305</b> of the database table rows, the row address translation table <b>400</b>, the disk address array <b>405</b>, and the relation identifier directory.

0039<figref idref="DRAWINGS">FIG. 4</figref> shows the row address translation table <b>400</b> and a disk address array <b>405</b>. The values specified in the first row of the row address translation table <b>400</b> refer to positions in memory and the values specified in the second row refer to positions in the disk address array <b>405</b>. For example, value 0x9=2 in the row address translation table <b>400</b> means that the same row that is located in memory address 0x9 is copied to the disk address stored in the third position in the disk address array (daddr[<b>2</b>]) <b>405</b>. During a checkpoint operation, tuple addresses (row addresses) and offsets to their corresponding disk page addresses <b>415</b> in disk address array <b>405</b> are stored in the row address translation table <b>400</b>. Once the checkpoint image <b>410</b> has been created, a restore component <b>245</b> will use the latest version of checkpoint image <b>410</b> in the event of a database failure.

0040The database system discussed above is able to perform a checkpoint operation and restart from the checkpoint image much faster than conventional database systems that use conventional checkpoint processes. The core of the improved system is how the leaf nodes <b>315</b> of primary index <b>300</b> and secondary index <b>305</b> are organized in the main memory <b>135</b>. The main principal is that the leaf nodes <b>315</b> are arranged close to other leaf nodes <b>315</b> that have similar key values in the physical memory pages (where a page is a contiguous memory area equal in size with a disk page size). Organizing the leaf nodes <b>315</b> in this way makes it possible to find a key from a large amount of pages (including leaf nodes) while examining only a small fraction of them, even if they are copied from memory to disk, or to another persistent memory (such as a non-volatile memory) or to another computer.

0041During run time, when new leaf nodes <b>315</b> are created and deleted, a memory allocator within the management system <b>120</b> uses a special-purpose data structure, called an allocator index, to assist in managing memory pools and to make it possible to quickly find the right location in memory for a new leaf node <b>315</b>. The allocator index makes it possible to physically cluster index leaf nodes <b>315</b> by the prefixes of their low keys (i.e., the smallest key in a leaf node <b>315</b>). As a result, leaf nodes <b>315</b> that have similar prefixes in their low keys are located in the same memory pages.

0042<figref idref="DRAWINGS">FIG. 5</figref> illustrates an example of this process. In the allocator index, on the first level there are three leaf node pages <b>360</b> filled with leaf nodes whose low key prefixes are 0x5 (shortened hex value, 0x50000000 in its complete form). In this case, the allocator limits each level to include a maximum of three pages, and if and when that limit is exceeded, future allocations will be done on the next level. On the second level, every node's low key's two most significant bytes must match with branching bytes, for example, with 0x5A. In this example, the first level (shown in the figure as level=0) is full and the memory allocation for the new leaf node <b>315</b> will therefore be located on the second level (shown in the figure as level=1) in branch 0x5A. As a consequence, there are two full pages <b>360</b> and one half full page <b>360</b> on the second level.

0043The allocator index, which includes the branch nodes <b>350</b>, is transient, so it will not be copied to a checkpoint image during the checkpoint process and will not exist at the time of any future database restart (e.g., a restore operation). Branch is a set of main memory pages for nodes, whose low keys' prefix equals with the branch prefix. The allocator index is a variant of a trie (also known as a digital tree). Common trie compression techniques, such as width compression, or different node types (as alternatives to 255-value branch nodes) can be applied to shrink the size of the allocator index. Trie compression, however, is not essential.

0044The keys within any leaf node <b>315</b> form an ascending sequence of values. Leaf nodes <b>315</b> are linked with each other so that the next leaf node <b>315</b> includes bigger keys, and previous leaf node <b>315</b> includes smaller keys. When a new leaf node <b>315</b> is created, there is performed a memory allocation analysis, using the allocator index, based upon the lowest key value of the new leaf node <b>315</b> to identify a non-full memory page <b>360</b> storing a leaf node whose lowest key value is similar to the lowest key value of the new leaf node <b>315</b>, and the new leaf node is stored in the identified non-full memory page <b>360</b>. If no such page <b>360</b> is identified, then a new page <b>360</b> will be created in the correct place within the index.

0045As a part of every checkpoint process, the leaf node pages <b>360</b> are included in checkpoint image <b>410</b>. The allocator index, however, is not part of the checkpoint process. However, the address of each memory pool branch is included in the checkpoint image, and thus the checkpoint image <b>410</b> includes information about where the index leaf nodes with certain kind of keys are located. The similarity between leaf node keys is based on byte comparisons starting from most significant bytes, that is, leftmost bytes of the key's byte value. For example, keys ‘0xa9f’ and ‘0xac1234’ would be stored in the same branch in the memory pool and they would end up on same disk block or disk blocks that are near to each other in the checkpoint image <b>410</b>.

0046<figref idref="DRAWINGS">FIG. 6</figref> shows a flowchart of the memory allocation process that takes place following the creation of a new leaf node <b>315</b>. The first step S<b>6</b>.<b>1</b> comprises the creation of a branch node <b>350</b> at level 0. At step S<b>6</b>.<b>2</b>, a memory allocation request is received which has the lowest key of the new leaf node <b>315</b> as the allocation parameter. (Leaf nodes <b>315</b> usually contain multiple key values, so the lowest is used as there is more than one key value present.) At step S<b>6</b>.<b>3</b>, the appropriate branch within the branch node <b>350</b> is chosen according to the most significant byte of the low key. In the example of <figref idref="DRAWINGS">FIG. 5</figref>, the most significant byte of the low key would be “5”.

0047At step S<b>6</b>.<b>4</b>, a check is made to see if the branch is empty. If it is empty, then at step S<b>6</b>.<b>5</b> there is created a new branch header and a node to the empty branch. If the branch is not empty, then the process moves directly to step S<b>6</b>.<b>6</b>. In the example of <figref idref="DRAWINGS">FIG. 5</figref>, the branch “5” is not empty; there already exists a header and node pages <b>360</b>. At step S<b>6</b>.<b>6</b>, a check is made to see if there is a leaf node page <b>360</b> on the current level which has space to store the new leaf node <b>315</b>. If yes, then at step S<b>6</b>.<b>7</b> the allocation information of the page is updated and at step S<b>6</b>.<b>8</b>, there is returned the address of the memory slot reserved for the new leaf node <b>315</b>.

0048In the example of <figref idref="DRAWINGS">FIG. 5</figref>, the check of step S<b>6</b>.<b>6</b> would return the answer “no”, as there is no page <b>360</b> with room for a new leaf node <b>315</b> at the branch level 0x5. The process would therefore move to the check at step S<b>6</b>.<b>9</b>, which checks to see if there is room at the current level for a new page <b>360</b>. If the answer is no, as would be the case in the example of <figref idref="DRAWINGS">FIG. 5</figref> (since the allocator index is limited to 3 pages at each level), then the process would move to step S<b>6</b>.<b>10</b> which is the selection of a branch at the next lower level according to the next most significant byte of the low key of the new leaf node <b>315</b>. In the <figref idref="DRAWINGS">FIG. 5</figref> example, this would be the “A” of the key “0x5A . . . ”. The process then returns to the step S<b>6</b>.<b>4</b> and cycles through the appropriate steps.

0049If the check made at step S<b>6</b>.<b>9</b> returns a “yes”, meaning that there is room at the current level for a new page <b>360</b>, then the process moves to step S<b>6</b>.<b>11</b>, which is the request for a new memory page from the operating system. The process then proceeds to step S<b>6</b>.<b>12</b>, which comprises adding a new page to the current level and performing the appropriate administration. As shown in the figure, the administration preferably comprises increasing the page counter, updating the last page pointer, and updating the low key value in the branch header. The process then moves to step S<b>6</b>.<b>13</b>, where the low key value from the new leaf node <b>315</b> is copied to the new page header, and the process moves to step S<b>6</b>.<b>7</b> and completes steps S<b>6</b>.<b>7</b> and S<b>6</b>.<b>8</b> as discussed above.

0050The modified memory allocation process makes it possible for an in-memory database to access all data, and execute transactions long before the database has been fully loaded in memory. The process provides means to load the database, access all the data, and execute client transactions all at the same time thus providing service hours before such a traditional in-memory database server which needs to load the full database into memory before it can execute client transactions.

0051For example, assuming a terabyte database with one table, where the key size is 8 bytes, the row size is 512 B, the page size is 64 kB (65536 B), the data can be read from disk at the speed of 100 MB/s, the number of keys with 1.5 overhead factor is 3.2 billion, and the number of pages with 1.3 overhead factor is 1.1 million. If all data must be loaded into memory before opening the server for clients, the bytes to read in total is 67.4 GB (65536*1.1*10̂6), and reading that from very fast secondary storage lasts 687.5 seconds, that is, about 11 minutes. In other words, it takes at least eleven minutes before the first transaction can be executed in the database server. It is not unusual to have 10 to 20 times bigger databases than this. With such larger databases, the start-up time for a database server will be several hours.

0052In addition to the assumptions above, with the node allocation strategy and leaf node index, it can be assumed that every pool has at most 10,000 pages on each level (noting that in the example of <figref idref="DRAWINGS">FIG. 5</figref>, a value of three is used), and the searched-for key value is found from the right-most page at the bottom-most level (which is the worst case scenario). With the proposed leaf node allocation scheme combined with leaf node checkpointing, by using the leaf page index, the searched data page can be found by reading 70,255 pages. Data to be read is then approximately 4.4 GB, and reading this data to memory lasts approximately 44 seconds. At this moment, the first transaction has found an index leaf node page that includes or doesn't include, depending on the existence of the searched-for value, the location of the row that is identified by the search key. At that time, the database performance is roughly on the performance level of a common disk-based database engine.

0053Operations that search for keys in leaf nodes that have not been read yet to memory are served slower than in a common disk-based database engine but faster than the worst case. Operations that search for keys in leaf nodes that have already been accessed are served faster than in a common disk-based database engine. Other transactions are served at the speed of an in-memory database.

0054In relation to the allocator index, the number of pages that there can be in a branch is limited. When there are a maximum number of full pages in a branch, and a new page is needed, a new level must be created. Instead of allocating a new page in addition to previous pages, a new array of pointers is created. The array includes <b>255</b> (initially NULL) pointers to branches on the next level. If the level that became full was the first, then the nodes' smallest keys' first byte determined that the nodes belonged to that branch. The branch for the new node on the second level is chosen by the second byte value of the node's low key.

0055The maximum height of the allocator index (where maximum height=number of levels) with 8-byte keys is as follows. Pages on a previous level are not relocated although a new level would be created, but as long as the first level remains full, all new nodes go to the second level. When the second level becomes full, the third level is created, and so on. With 8-byte keys, there can be at most h different levels, as shown by the following.

0056Let k=keys on each level.

0057Let h=height, i.e., number of levels.

0058Let n=number of bytes in key.

0059Let x=number of memory pages per level.

0060h=n−x, where 2̂8x&lt;=k(8−x)

0061In a first example, if k=10,000, then 2̂8x+10,000x&lt;=<b>80</b>,<b>000</b>

0062x=1, then 256+10,000&lt;=80,000, thus h=7.

0063In a second example, if k=100,000, then 2̂8x+100,000x&lt;=800,000

0064if x=2, then 265,536<=800,000<=> true, thus h=6.

0065The checkpoint operation is summarised in the flowchart of <figref idref="DRAWINGS">FIG. 7</figref>. The checkpoint operation creates a copy of all of the database tables <b>310</b> being stored by the main memory <b>135</b> and creates a checkpoint image <b>410</b> for storage in a secondary storage device <b>105</b>. Leaf node pages <b>360</b> also form part of the checkpoint image <b>410</b>, as will be described below. The first step of the process is step S<b>7</b>.<b>1</b>, which comprises freezing the database, marking the “dirty” tables <b>310</b>, and then unfreezing the database. A “dirty” table <b>310</b> is one that has changed since the last checkpoint operation was carried out.

0066At step S<b>7</b>.<b>2</b>, a check is made to see if there are still dirty tables <b>310</b> within the database. If there are not, then the process moves to step S<b>7</b>.<b>3</b>, where the process is terminated, as the checkpoint is complete. However, if there are dirty tables <b>310</b> within the database, then the process moves to step S<b>7</b>.<b>4</b>, where a dirty table <b>310</b> is selected to be checkpointed. At step S<b>7</b>.<b>5</b>, dirty rows <b>335</b> are copied to a checkpoint buffer and their addresses are copied to the row address translation table <b>400</b> (as described above in detail with reference to <figref idref="DRAWINGS">FIG. 4</figref>). At step S<b>7</b>.<b>6</b>, page-sized checkpoint buffers are written to disk <b>105</b> and the resulting disk addresses are written to the row address translation table <b>400</b>. The next step is the step S<b>7</b>.<b>7</b>, which comprises adding the row address translation table <b>400</b> to the checkpoint image <b>410</b>.

0067This is followed by the processing of the primary index <b>300</b>, which is selected at step S<b>7</b>.<b>8</b>. At step S<b>7</b>.<b>9</b>, the contents of the primary index <b>300</b> are processed. This involves adding any and all dirty leaf node pages <b>360</b> to the checkpoint image <b>410</b> and copying the value of the low key of each dirty leaf page <b>360</b> to a sparse leaf page index (which is currently in memory <b>135</b>), and copying the memory address of the dirty leaf node pages <b>360</b> to a leaf page address translation table (also currently in memory <b>135</b>). At step <b>57</b>.<b>10</b>, the leaf page address translation table is added to the checkpoint image <b>410</b>, and at step <b>57</b>.<b>11</b>, the sparse leaf page index is also added to the checkpoint image <b>410</b>.

0068At step <b>57</b>.<b>12</b>, a check is made to see if there are any further dirty indexes for the current table <b>310</b> and if there are, then the process moves to step <b>57</b>.<b>13</b> and selects the next secondary index <b>305</b>. If not, then the process moves to step S<b>7</b>.<b>2</b> and continues to cycle until all of the dirty tables <b>310</b> have been checkpointed.

0069Once a checkpoint operation has been performed, the checkpoint image <b>410</b> is available for a restore operation. If a restore is required using the checkpoint image, then the method of the memory allocation (<figref idref="DRAWINGS">FIG. 6</figref>) and the method of the checkpoint process (<figref idref="DRAWINGS">FIG. 7</figref>) mean that it is possible for a client to access usable data very quickly from the checkpoint image <b>410</b>, without having to first load and organise the entire checkpoint image <b>410</b>. The operation of the restore process is summarised in <figref idref="DRAWINGS">FIG. 8</figref>.

0070At step S<b>8</b>.<b>1</b>, a user requests data identified by an index key. At step S<b>8</b>.<b>2</b>, a check is made to see if the leaf page address translation table, the row address translation table, and the sparse leaf page index have been loaded and if not, then at step S<b>8</b>.<b>3</b> these are loaded. At step S<b>8</b>.<b>4</b>, a check is made to see if the key being searched for is present in the sparse leaf page index and if not, a further check is made at step S<b>8</b>.<b>5</b> to see if there are any unread keys left in the sparse leaf page index. If not, then the method terminates at step S<b>8</b>.<b>6</b>, which returns a “data not found” message to the requesting client.

0071If there are unread keys left in the sparse leaf page index, then the process moves to step S<b>8</b>.<b>7</b> where a key is chosen from the sparse leaf page index which has a common prefix with the key being searched and which refers to a leaf node page <b>360</b> in the checkpoint image <b>410</b>. At step <b>8</b>.<b>8</b>, the disk address of the relevant leaf node page <b>360</b> is resolved from the leaf page address translation table At step S<b>8</b>.<b>9</b>, the leaf node page <b>360</b> is loaded from the resolved disk address within the checkpoint image <b>410</b> on the secondary storage <b>105</b> to the main memory <b>135</b>. At step S<b>8</b>.<b>10</b>, the keys found on the loaded page <b>360</b> are inserted into the sparse index. The process returns to the check step S<b>8</b>.<b>4</b>.

0072If the check step S<b>8</b>.<b>4</b> returns a yes, then the process continues to step <b>58</b>.<b>11</b> where the row address attached with the key is read and at step <b>8</b>.<b>12</b>, the row address to the data location in the checkpoint image <b>410</b> is translated using the row address translation table <b>400</b>, thereby obtaining the offset into the disk page. At step <b>58</b>.<b>13</b>, the relevant data is fetched using the value obtained from the translation table and the row of data is restored to the in-memory storage <b>135</b>. At step <b>58</b>.<b>14</b>, the user request for the data can be fulfilled.

0073The improved database system can take the form of an entirely hardware embodiment, an entirely software embodiment, or an embodiment containing both hardware and software elements. In a preferred embodiment, the database system is implemented in software, which includes but is not limited to firmware, resident software, microcode, etc. The database system can take the form of a computer program product accessible from a computer-usable or computer-readable medium providing program code for use by or in connection with a computer or any instruction execution system. For the purposes of this document, a computer usable or computer readable medium can be any apparatus that can contain or store the program for use by or in connection with the instruction execution system, apparatus, or device. The medium can be an electronic, magnetic, optical, electromagnetic, or semiconductor system (or apparatus or device). Examples of a computer-readable medium include a semiconductor or solid state memory, magnetic tape, a removable computer diskette, a random access memory (RAM), a read only memory (ROM), a rigid magnetic disk, and an optical disk. Current examples of optical disks include compact disk read only memory (CD-ROM), compact disk read/write (CD-R/W), and DVD.