Fast data retrieval based upon contiguous consolidation of records according to frequency of access

[0002] This application claims priority, under 35 U.S.C. §119(e), from U.S. Provisional Patent Application Ser. No. 60/236,559 filed Sep. 28, 2000, the entirety of which is herein incorporated by reference.

[0003] 1. Field of Invention

[0004] The invention relates generally to computer databases, and more specifically to the quick retrieval of data records based upon contiguous consolidation according to access frequency.

[0005] 2. Background of Invention

[0006] Large amounts of data are typically stored in computer databases. Various database architectures are currently known in the art. These architectures have generally been developed during a time when computer hardware storage (both disk storage and random access memory) were relatively limited and expensive. However, these technologies have recently become significantly more powerful and less expensive. As a result, the hardware environment has changed considerably from when current database technologies were developed. Only a short time ago, the standard hard disk size was two gigabytes, and database server computers did not support more than two gigabytes of random access memory. Currently, the standard server computer is equipped with up to eighteen gigabytes of disk space, and over two gigabytes of random access memory. As a consequence of these hardware developments, much larger databases are not only now possible, but are expected by users and customers of database systems.

[0007] With the increase in size, new demands are placed on databases. Typically, a larger database results in significantly slower access time. Known database technologies were developed when less static and dynamic storage were readily available, and thus are not designed to take advantage of contemporary hardware configurations. For example, known database technologies typically rely on a highly partitioned storage strategy, that permits data to be distributed across multiple disks. Generally, each partition of the database is less than one gigabyte in size. Thus, in a large database, data records will be stored in multiple partitions, on multiple physical areas on a disk, and on multiple disks. Consequently, access to data records becomes slower as the size of the data (and thus the physical distribution) increases.

[0008] To access a data record, first the record must be located, then the read-head must be moved to the physical location of the record in order to read it. A similar set of operations is required in order to write an updated record to disk. The mechanical operation of physically moving a disk-head is much slower than executing an electronic operation, such as loading data from a disk into random access memory. Databases typically include the requirement that data records must be able to be accessed in a random rather than sequential manner (in other words, a user needs to be able to access any record, in any order). The data records of traditional databases are distributed across various physical locations. Therefore, randomly accessing a plurality of data records involves significant disk-head movement that is essentially random, resulting in lengthy average seek times. The larger the database, the greater the record distribution, and hence the slower the data access will be. In practice, when known database architectures are used to stored large databases, the system spends a significant amount of time moving the disk-heads to various physical locations on multiple disks, resulting in slow access time. Therefore, what is needed is a method and a system for facilitating quick access of data records in large databases.

[0009] According to an embodiment of the present invention, the most recently accessed data records are stored contiguously on static media, and the least recently accessed data records are stored contiguously on static media. Additionally, a buffer in random access memory is used to store a subset of the data records. preferably those that have been most recently accessed. When a data record is accessed, it is stored in the buffer. From time to time, the most recently accessed records from the buffer are flushed to static media, ensuring their contiguous storage. The least recently accessed records, which are stored on static media, are consolidated, such that they too are contiguously stored.

[0010] Access of data records is thus much faster than in a traditional database. The most recently accessed records are, statistically, the most likely records to be subsequently accessed. Because the most recently accessed records are in the buffer, they are accessed extremely quickly. Because these records are stored contiguously on static media, whenever one of these records is accessed from there, it is also likely that the read-head will already be proximate to the location of the record. In a traditional database system, an accessed record is not likely to be physically located proximately to a previously accessed record, and thus more disk-head movement is required. Because disk-head movement is slow, the substantial minimization thereof results in greatly increased performance.

[0011] Additionally, both a write process and a consolidator process store data records on static media contiguously in blocks. Therefore, there is very little movement of the disk write-head compared to that required by a traditional database system to store the same number of records across multiple physical disk locations.

[0012] The features and advantages described in this summary and the following detailed description are not all-inclusive, and particularly, many additional features and advantages will be apparent to one of ordinary skill in the art in view of the drawings, specification, and claims hereof. Moreover, it should be noted that the language used in the specification has been principally selected for readability and instructional purposes, and may not have been selected to delineate or circumscribe the inventive subject matter, resort to the claims being necessary to determine such inventive subject matter.

[0013] FIG. 1A is a high-level block diagram illustrating a system for facilitating fast, efficient database access based upon contiguous storage of data records according to frequency of access, according to one embodiment of the present invention.

[0014] FIG. 1B is a high-level block diagram illustrating an overview of the operation of the system according to one embodiment of the present invention.

[0015] FIG. 2 is a block diagram illustrating the pre-allocation of contiguous files on static media, according to one embodiment of the present invention.

[0016] FIG. 3 is a block diagram illustrating the operation of the system, according to one embodiment of the present invention.

[0017] FIG. 4 is a block diagram illustrating the writing of data records stored in the buffer to static media, according to one embodiment of the present invention.

[0018] FIG. 5 is a block diagram illustrating the consolidation of data records stored on static media, according to one embodiment of the present invention.

[0019] FIG. 6 is a block diagram illustrating the chaining of multiple versions of data records, according to one embodiment of the present invention.

[0020] The figures depict embodiments of the present invention for purposes of illustration only. One skilled in the art will readily recognize from the following discussion that alternative embodiments of the structures and methods illustrated herein may be employed without departing from the principles of the invention described herein.

[0021] I. System Overview

[0022] FIG. 1A illustrates a system 100 for facilitating fast, efficient database access based upon contiguous storage of data records according to frequency of access, according to one embodiment of the present invention.

[0023] A computer includes random access memory 101 and static media 103. Static media 103 can comprise, for example, magnetic or optical disks. A database application program 105 executes in memory 101. It is to be understood that although a single application program 105 is illustrated, the functionality of the application program 105 can be provided by a single program, or by multiple programs and processes as desired. The application program 105 accesses data records 107 in a database. Non-exhaustive examples of access operations include read, write, add and delete. Data records 107 are stored contiguously in one or more files 109 on static media 103. A subset of data records 107 are stored in a buffer 111 in memory 101. Additionally, an index 113 is stored in memory 101, the index 113 facilitating access of data records 107 stored both on static media 103 and in the buffer 111. The index 113 generally contains information such as the location of each data record 107 on static media 103 (and in memory 101 where applicable), keywords associated with the data record 107, indicators of locked records 107, and the like. The implementation details of the index 113 will be readily apparent to one of skill in the art.

[0024] A consolidator process 115 also executes in memory 101. As explained in detail below, the consolidator process 115 contiguously stores non-obsolete data records 107 in available files 109, and makes obsolete files 109 available to the system 100.

[0025] A writer process 117 also executes in memory 101. The writer process 117 reads data records 107 from the buffer 111 in memory 101, and contiguously stores the data records 107 in available files 109 on static media 103. As explained in detail below, this results in the most frequently accessed data records 107 being stored contiguously.

[0026] II. Overview of System Operation

[0027] FIG. 1B illustrates an overview of the operation of the system, according to one embodiment of the present invention. The operation is based upon the premise that the most recently accessed data records 107 statistically tend to be the most frequently accessed data records 107. Thus, by contiguously grouping both the most frequently and least frequently accessed data records 107, access of data records 107 during system 100 operation will tend to be in a contiguous as opposed to a random order. Because contiguous access involves significantly less disk-head movement than random access, the system 100 yields significantly improved performance over traditional database technologies.

[0028] The operation of the system 100 implements this approach by dynamically, contiguously, and separately grouping both the most frequently and least frequently accessed data records 107. As explained in detail below, the system 100 operation begins with all data records 107 stored contiguously in files 109 on static media 103. When a data record 107 is accessed, it is stored in the buffer 111, such that the most recently accessed data records 107 are stored therein, for fast subsequent access.

[0029] It will be readily apparent that the buffer 111 will in time become full. Therefore, from time to time, the writer process 117 reads the buffer 111, and contiguously writes data records 107 stored therein to static media 103. Recall that these data records 107 have been recently accessed, and hence they are in the buffer 111. When the writer process 117 flushes the most recently accessed records 107 to media 103, the result is that the most recently accessed records will be stored contiguously, as illustrated in file 109dfor fast subsequent access. The system 100 then keeps track of the fact that the flushed version of the data record 107 is the current version, and that the previous version, which was loaded from media 103 into the buffer 111 for access, is now obsolete.

[0030] The files 109a, 109bfrom which data records 107 are loaded into the buffer 111 for access will, in time, comprise both obsolete records 107 (that is to say, records that have subsequently been accessed and contiguously written to a separate file 109don static media 103) and non-obsolete records 107 (that is to say, records that have not been subsequently accessed and written to a separate file 109d). It will be readily apparent that the obsolete records 107 comprise earlier versions of the most recently accessed data records 107, which have been subsequently contiguously written to a separate file 109d. The non-obsolete records 107 comprise the least recently accessed records 107. In other words, the non-obsolete records 107 have not subsequently been accessed and rewritten since being stored in their current location on static media 103.

[0031] As the most frequently accessed records 107 are contiguously stored, so too are the least frequently accessed records 107 contiguously stored. To achieve this, the consolidator process 115 reads files 109a, 109bstored on static media 103. Where a file 109a, 109bcontains both non-obsolete records 107 and obsolete records 107, the consolidator process 115 writes the non-obsolete records 107 to a separate file 109con static media 103, such that they are stored contiguously for subsequent access. Obsolete records can be skipped, since the updated versions of such records have already been written to file 109d. The consolidator process 115 then classifies the file 109a, 109bcontaining non-obsolete records 107 and obsolete records 107 as being available for subsequent contiguous storage of data records 107, by either the writer process 117 or the consolidator process 115. That is, this area of static media is reclaimed. In this manner, the most recently accessed and the least recently accessed data records 107 are both stored contiguously.

[0032] III. Pre-allocation of Contiguous Media

[0033] FIG. 2 illustrates the pre-allocation of contiguous files 109 on static media 103. In order to contiguously store data records 107, one or more contiguous files 109 are pre-allocated from an operating system 201. Generally, this pre-allocation is performed by a pre-allocation module 203, which can be a part of the application program 105, or a separate process as desired. In one embodiment, the pre-allocation module 203 allocates a desired number of files 109, each file 109 being a desired number N bytes in size. The pre-allocation module 203 sequentially writes N bytes to each file 109, to ensure that each file 109 occupies contiguous physical storage space on the static media 103. In other embodiments, other techniques known in the art are utilized to ensure contiguous physical allocation of file space on static media 103.

[0034] In one embodiment, the physical space on which all of the files 109 are stored is contiguous. In other embodiments, each file 109 comprises contiguous storage space on static media 103, but one or more of the files 109 may be stored non-contiguously relative to other files 109.

[0035] IV. Detailed System Operation

[0036] FIG. 3 illustrates the operation of the system. Data records 107 are stored contiguously in one or more files 109 on static media. The most recently (and hence most frequently) accessed data records 107 are also stored in a buffer 111 in memory 101. The buffer is large enough to hold some number M data records. The value of M is generally configurable, and comprises a design choice to be made by a system administrator or other party as desired. As explained above, the index 113 is also stored in memory 101.

[0037] The application program 105 utilizes the index 113 to access data records 107. Where an accessed record 107 is already in the buffer 111, the application program 105 utilizes the buffered copy of the data record 107 for fast access. Where the data record 107 is not in the buffer 111, the application program 105 loads the data record from static is media 103 into memory 101, and stores a copy of the data record 107 in the buffer 111. If there is room in the buffer 111, the data record 107 is simply stored there in available space. If the buffer 111 is full, the least recently accessed data record 107 (or alternatively some other data record 107) is overwritten. Of course, data records 107 that have been updated are not overwritten without first being written to static media 103 by the writer process 117, as explained below. When a data record 107 is stored in the buffer 111, the index 113 is updated to indicate the location of the data record 107 therein.

[0038] In one embodiment, the buffer 111 comprises a circular queue (as illustrated in FIG. 3). In that embodiment, data records 117 are stored at the tail of the queue, such that when the queue is full, the least recently entered data records 107 are overwritten with new data records 107. Other data structures and storage methodologies are utilized in other embodiments as desired.

[0039] It is to be understood that some accesses of data records 107 update the contents thereof (e.g. a write operation), whereas other accesses do not (for example, a read operation). In one embodiment, only updated data records 107 are stored in the buffer 111. In another, all accessed records 107 are so stored. Regardless, the application program 105 (or alternatively another element of the system 100) keeps track of which data records 107 in the buffer 111 have been updated since they were loaded from static media 103. The application program 105 uses entries in the index 113, or other conventional methodology apparent to one of skill in the art, to keep track of this information.

[0040] V. Writing of Records from Buffer to Media

[0041] FIG. 4 illustrates the writing of data records 107 stored in the buffer 111 to static media 103. A writer process 117 executes in memory 101. FIG. 4 illustrates the writer process 117 executing as a discrete process. It is to be understood that the associated functionality can be provided by a single process as illustrated, by the application program, or by more than one process or program as desired.

[0042] From time to time as desired, the writer process 117 reads the buffer, and contiguously stores data records 107 contained therein in one or more files 109 on static media 103. Generally, the writer process 117 determines which records 107 in the buffer 111 have not been stored on media 103 since last being updated, as described below. The writer process 117 contiguously appends these records 107 to an active file 109 on static media 103. An active file 109 is a file 109 in which the writer process 117 stores updated records 107 from the buffer 111, the active file 109 having available room for additional records 107. Generally, an active file 109 is a file that is available for storage of records 107, either as a result of being pre-allocated by the pre-allocation module 201, or as a result of having been made available by the consolidation process 115, as explained below. Once an active file 109 becomes full, the system 100 designates a new available file 109 as being active, and begins storing records 107 therein. The full file 109 is designated as no longer being active or available.

[0043] The writer process 117 (or alternatively the application program 105) keeps track of which records 107 in the buffer 111 have been copied to static media. The writer process 117 uses entries in the index 113, or other conventional methodology apparent to one of skill in the art, to keep track of this information. Because the system 100 keeps track of which records 107 in the buffer 111 have been updated since being copied from media 103, and which updated records 107 in the buffer 111 have been written to media 103, the writer process 117 is able to only contiguously write those records 107 to media 103 that are more current than the latest version stored on media. Additionally, when the writer process 117 copies an updated data record 107 to static media, the system 100 classifies earlier versions of the data record 107 stored on media as being obsolete. The system uses methodology apparent to one of skill in the art to keep track of obsolete records.

[0044] The frequency with which the writer process 117 executes is configurable, and comprises a design choice to be made by a system administrator or other party as desired. In some embodiments, the writer process 177 executes at least whenever the buffer 111 is full, such that before an updated data record 107 is overwritten, all updated data records 107 are contiguously written to one or more active files 109 on media 103.

[0045] Additionally, when the writer process 117 contiguously writes data records from the buffer 111 to media 103, the index 113 is updated accordingly.

[0046] VI. Consolidation of Records on Media

[0047] FIG. 5 illustrates the consolidation of data records 107 stored on static media 103. A consolidator process 115 executes in memory 101. FIG. 5 illustrates the consolidator 115 as a single process, but of course the associated functionality can alternatively be provided by the application program, or by more than one process or program as desired.

[0048] From time to time as desired, the consolidator process 115 reads the files 109 on static media 103 in which data records 107 are stored. When the consolidator process 115 encounters a file 109 in which both obsolete and non-obsolete records are stored, the consolidator process 115 reads the non-obsolete records 107 from that file 109, and contiguously stores them in an available file 109, such that the least recently accessed data records (in other words, the ones that have not been updated recently, and hence are non-obsolete) are stored contiguously. The file 109 containing obsolete and non-obsolete records is then classified by the system as being available for subsequent use by the writer process 117 or the consolidator process 115.

[0049] The frequency with which the consolidator process 115 executes is configurable, and comprises a design choice to be made by a system administrator or other party as desired. Additionally, when the consolidator process 117 stores data records in available files and classifies existing files as being available, the index 113 is updated accordingly.

[0050] VII. Chaining of Records

[0051] FIG. 6 illustrates the chaining of versions of data records 107. In some embodiments of the present invention, when a data record 107 is updated, a pointer 601 is maintained from the updated data record 107 to the previous version thereof. This pointer 301 can be in the record 107 itself (as illustrated), in the index 113, or elsewhere as desired.

[0052] Where each version of a data record 107 has a pointer 301 to the previous version, the “chain” of pointers 301 can be traversed in order to examine editing history of a data record 107. The chain has other uses as well, for example error recovery after a system crash.

[0053] In one embodiment, no version of a data record 107 is classified as obsolete until a certain number of more recent versions of the record always exist. For example, a system administrator could configure the system 100 such that three versions of each data record always exist. Then, only when three more recent versions exist would a prior version of a data record be classified as obsolete. In one embodiment, this result is achieved by setting the size of the buffer 111 and files 109, as well as the execution frequency of the writer process 117 and the consolidator process 115 accordingly.

[0054] VIII. Flexibility of Record Type

[0055] Data records 107 can comprise data of any kind, for example, names and addresses, employee information, inventory information, or profiles summarizing transactions, for example credit card transactions. Data records 107 can be exported or imported into other applications as desired. For example, in one embodiment, data records 107 comprise profiles summarizing credit card transactions. These profiles are utilized as input for a predictive statistical modeling program. In another embodiment, the profiles comprise output from the predictive statistical modeling program.

[0056] IX. Conclusion

[0057] The system 100 contiguously stores the most recently accessed data records 107 together, and contiguously stores the least recently accessed records 107 together. The most recently accessed records 107 are maintained in the buffer 111 and contiguously written to active files 109 on static media 103. The least recently accessed data records 107 are contiguously stored in available files 107 on static media 103. Because the storage of both the most and least recently (and thus frequently) accessed data records 107 is contiguous, a minimum of disk-head movement is required in order to read and write the data records 107. Because the mechanical operation of disk-head movement is significantly slower than the other, electrical operations required for data record 107 access, the system 100 provides remarkable performance improvements over previously known database technologies.

[0058] As will be understood by those familiar with the art, the invention may be embodied in other specific forms without departing from the spirit or essential characteristics thereof. Likewise, the particular capitalization or naming of the modules, protocols, features, attributes or any other aspect is not mandatory or significant, and the mechanisms that implement the invention or its features may have different names or formats. Additionally, it will be readily apparent to one of skill in the art that functionality described herein can be implemented as software, hardware, firmware or any desired combination thereof. All such instantiations are within the scope of the present invention. Accordingly, the disclosure of the present invention is intended to be illustrative, but not limiting, of the scope of the invention, which is set forth in the following claims.