Data storage using vectors of vectors

The systems and methods described here can reduce the storage space required (memory and/or disk) to store certain types of data, provide efficient (fast) creation, modification and retrieval of such data, and support such data within the framework of a multi-version database. In some embodiments, the systems and methods can store each field of a set of records as a vector of values, e.g., a data vector. A set of records can be represented using a vector id vector, or “vid” vector, wherein each element of the vid vector contains a reference to the memory location of a data vector. A header table can store associations between labels and “vid” vectors that pertain to those labels. Identical data vectors can be re-used between different record sets or vid vectors needing that vector, thus saving space.

TECHNICAL FIELD

This disclosure relates to database technology, in-memory computing, multi-version databases, and supply chain planning.

BACKGROUND

Current products are known to store all table data as discrete records or rows of data. To achieve high-performance and low-storage characteristics, systems have stored each reference to a related record explicitly in memory. On any referenced record, a corresponding “set” structure is used to directly access all the records that refer to that specific record. Known products can provide support for a multi-version feature in the same way for all tables. Specifically, a change to any field on that record causes a new version of the record to be created that contains the changed data for those fields. Thus, in order to retrieve a series of sequential data, each record is found and then resolved to its correct “version.”

SUMMARY

In one aspect, the present disclosure is directed at a computer system. The computer system can comprise at least one memory comprising: a first set of two or more data vectors, each data vector having a sequence of elements, wherein each element in each data vector can be configured to store a payload of data; and a first vector ID (vid) vector having a sequence of elements, wherein each element in the first vid vector can be configured to store a unique memory location reference associated with a data vector of the first set of data vectors. The computer system can also comprise at least one processor for directing said memory to store said first set of two or more data vectors, and said first vid vector.

In some embodiments, one of the two or more data vectors can be a key vector, wherein each of the two or more data vectors can be sorted according to an order determined by the key vector.

In some embodiments, the at least one memory can further comprise a first header table that stores an association between a first key label and a unique memory location reference associated with the first vid vector.

In some embodiments, the at least one memory can further comprise a second vid vector associated with a second key label, the second vid vector having a sequence of elements, wherein each element in the second vid vector can be configured to store a unique memory location reference associated with a data vector. The at least one memory can also comprise a second header table that stores an association between the second key label and a unique memory location reference associated with the second vid vector.

In some embodiments, at least one element in the second vid vector can store a memory location reference associated with a data vector of the first set of data vectors.

In some embodiments, the at least one processor can be configured to determine a proposed new data vector to be referenced by the second vid vector; and determine whether the at least one memory is already storing a matching data vector that matches the proposed new data vector. When the at least one memory is already storing a matching data vector, the at least one processor can store a unique memory location reference associated with the matching data vector in the second vid vector. When the at least one memory is not already storing a matching data vector, the at least one processor can store the proposed new data vector in the at least one memory, and store a unique memory location reference associated with the proposed new data vector in the second vid vector.

In some embodiments, the at least one processor can be configured to determine whether the at least one memory is already storing a matching data vector that matches the proposed new data vector by comparing a hash of the proposed new data vector with hashes of data vectors already stored in the at least one memory.

In some embodiments, each data vector in the first set of data vectors can comprise a subset of elements associated with a first group label. The at least one memory can further comprise a third header table that stores an association between the first group label and a unique memory location reference associated with the first vid vector.

In some embodiments, each element in the second vid vector can store a unique memory location reference associated with a data vector having a subset of elements associated with the first group label. The third header table can further store an association between the first group label and a unique memory location reference associated with the second vid vector.

In some embodiments, the first vid vector can be associated with one version. The at least one memory can further comprise a second vid vector associated with another version, the second vid vector having a sequence of elements, wherein each element in the second vid vector can be configured to store a unique memory location reference associated with a data vector. The first header table can further store an association between the first vid vector and the one version, and an association between the second vid vector and the another version.

In another aspect, the present disclosure is directed at a method of storing data. The method can comprise storing, in at least one memory, a first set of two or more data vectors, each data vector having a sequence of elements, wherein each element in each data vector can be configured to store a payload of data. The method can further comprise storing, in the at least one memory, a first vector ID (vid) vector having a sequence of elements, wherein each element in the first vid vector can be configured to store a unique memory location reference associated with a data vector of the first set of data vectors.

In some embodiments, one of the two or more data vectors can be a key vector, and each of the two or more data vectors can be sorted according to an order determined by the key vector.

In some embodiments, the method can further comprise storing, in the at least one memory, a first header table that stores an association between a first key label and a unique memory location reference associated with the first vid vector.

In some embodiments, the method can further comprise storing, in the at least one memory, a second vid vector associated with a second key label, the second vid vector having a sequence of elements, wherein each element in the second vid vector can be configured to store a unique memory location reference associated with a data vector. The method can also further comprise storing, in the at least one memory, a second header table that stores an association between the second key label and a unique memory location reference associated with the second vid vector.

In some embodiments, at least one element in the second vid vector can store a memory location reference associated with a data vector of the first set of data vectors.

In some embodiments, the method can further comprise determining a proposed new data vector to be referenced by the second vid vector, and determining whether the at least one memory is already storing a matching data vector that matches the proposed new data vector. When the at least one memory is already storing a matching data vector, the method can comprise storing a unique memory location associated with the matching data vector in the second vid vector. When the at least one memory is not already storing a matching data vector, the method can comprise storing the proposed new data vector in the at least one memory, and storing a unique memory location reference associated with the proposed new data vector in the second vid vector.

In some embodiments, the determining whether the at least one memory is already storing a matching data vector that matches the proposed new data vector can comprise comparing a hash of the proposed new data vector with hashes of data vectors already stored in the at least one memory.

In some embodiments, each data vector in the first set of data vectors can comprise a subset of elements associated with a first group label. The method can also further comprise storing, in the at least one memory, a third header table that stores an association between the first group label and a unique memory location reference associated with the first vid vector.

In some embodiments, each element in the second vid vector can store a unique memory location reference associated with a data vector having a subset of elements associated with the first group label. The method can also further comprise storing, in the third header table, an association between the first group label and a unique memory location reference associated with the second vid vector.

In some embodiments, the first vid vector can be associated with one version. The method can further comprise storing, in the at least one memory, a second vid vector associated with another version, the second vid vector having a sequence of elements, wherein each element in the second vid vector can be configured to store a unique memory location reference associated with a data vector. The method can also further comprise storing, in the first header table, an association between the first vid vector and the one version, and an association between the second vid vector and the another version.

In yet another aspect, the present disclosure is directed at at least one memory. The at least one memory can comprise a first set of two or more data vectors, each data vector having a sequence of elements, wherein each element in each data vector can be configured to store a payload of data. The at least one memory can further comprise a first vector ID (vid) vector having a sequence of elements, wherein each element in the first vid vector can be configured to store a unique memory location reference associated with a data vector of the first set of data vectors.

In some embodiments, one of the two or more data vectors can be a key vector, and each of the two or more data vectors can be sorted according to an order determined by the key vector.

In some embodiments, the at least one memory can further comprise a first header table that stores an association between a first key label and a unique memory location reference associated with the first vid vector.

In some embodiments, the at least one memory can further comprise a second vid vector associated with a second key label, the second vid vector having a sequence of elements, wherein each element in the second vid vector can be configured to store a unique memory location reference associated with a data vector. The at least one memory can also further comprise a second header table that stores an association between the second key label and a unique memory location reference associated with the second vid vector.

In some embodiments, at least one element in the second vid vector can store a memory location reference associated with a data vector of the first set of data vectors.

In some embodiments, each data vector in the first set of data vectors can comprise a subset of elements associated with a first group label. The at least one memory can also further comprise a third header table that stores an association between the first group label and a unique memory location reference associated with the first vid vector.

In some embodiments, each element in the second vid vector can store a unique memory location reference associated with a data vector having a subset of elements associated with the first group label. The third header table can further store an association between the first group label and a unique memory location reference associated with the second vid vector.

In some embodiments, the first vid vector can be associated with one version. The at least one memory can further comprise a second vid vector associated with another version, the second vid vector having a sequence of elements, wherein each element in the second vid vector can be configured to store a unique memory location reference associated with a data vector. The first header table can further store an association between the first vid vector and the one version, and an association between the second vid vector and the another version.

DISCLOSURE

The systems and methods described here can reduce the storage space (e.g., on memory and/or disk) required to store certain types of data, provide efficient (e.g., fast) creation, modification and retrieval of such data, and support such data within the framework of a multi-version database. This can be done using a vector-based implementation of database tables and records. As described herein, a “vector” can be a data structure in memory that stores data in an ordered sequence of elements, wherein each element can store data, such as a string, an integer, a floating point decimal, references to memory locations, Boolean data, or other data types. Vectors can have any arbitrary length, such as zero elements, one element, two elements, or hundreds, thousands, millions, or more elements.

In the systems and methods described here:1. Each field in a vector set can be stored as a vector of values—i.e., there is one value in the vector for each “record” in the set.2. Multi-version merge and conflict-resolution can be done on the vectors, without the benefit of record IDs.3. A vector can be a reference-counted global resource, which can be re-used by all instances having identical values. This pooling of resources benefits instances of repeated vectors in any vector set.4. A set can be represented as a vector of vectors—and hence the storage of the set itself naturally benefits from the same vector re-use.5. Other than identifying “vector” data in the data model definition (which in some embodiments can be seen only by an administrator), vector data can continue to appear to users as if individual records were stored.

The systems and methods described here can allow one or more of the following benefits:1. They can reduce the storage space required.2. Traversal of vector sets can typically be faster because processors retrieve a block of memory at a time. A vector can be stored in consecutive memory locations, and so much of the data for a vector set will be available in the processor cache once any portion of it is retrieved.3. Identical vector “columns” can be re-used between different elements of data needing that vector. For example, if a summary of data is to be stored in weekly “buckets”, then the date “vector” can be identical for many date/quantity sets. Therefore, the same date vector data can be re-used for each of those date/quantity sets. This brings further space savings.4. Vector re-use can also provide further speed improvement, as fewer blocks of memory need to be loaded and kept in the processor cache.

Turning to the figures,FIG. 1illustrates a non-limiting example of a system100for storing and viewing databases in accordance with certain embodiments of the present disclosure. System100includes a database server102, a database114, and client devices108aand108b. Database server102can include a memory104, a disk106, and one or more processors115. In some embodiments, memory104can be volatile memory, compared with disk106which can be non-volatile memory. In some embodiments, database server102can communicate with database114using interface112. Database can be a versioned database or a database that does not support versioning. While database114is illustrated as separate from database server102, database114can also be integrated into database server102, either as a separate component within database server102, or as part of at least one of memory104and disk106. A versioned database can refer to a database which provides numerous complete delta-based copies of an entire database. Each complete database copy represents a version. Versioned databases can be used for numerous purposes, including simulation and collaborative decision-making.

System100can also include additional features and/or functionality. For example, system100can also include additional storage (removable and/or non-removable) including, but not limited to, magnetic or optical disks or tape. Such additional storage is illustrated inFIG. 1by memory104and disk106. Storage media can include volatile and nonvolatile, removable and non-removable media implemented in any method or technology for storage of information such as computer-readable instructions, data structures, program modules or other data. Memory104and disk106are examples of non-transitory computer-readable storage media. Non-transitory computer-readable media also includes, but is not limited to, Random Access Memory (RAM), Read-Only Memory (ROM), Electrically Erasable Programmable Read-Only Memory (EEPROM), flash memory and/or other memory technology, Compact Disc Read-Only Memory (CD-ROM), digital versatile discs (DVD), and/or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, and/or any other medium which can be used to store the desired information and which can be accessed by system100. Any such non-transitory computer-readable storage media can be part of system100.

System100can also include interfaces110a,110b, and112. Interfaces110a-band112can allow components of system100to communicate with each other and with other devices. For example, database server102can communicate with database114using interface112. Database server102can also communicate with client devices108aand108bvia interfaces110aand110b, respectively. Client devices108aand108bcan be different types of client devices; for example, client device108acan be a desktop or laptop, whereas client device108bcan be a mobile device such as a smartphone or tablet with a smaller display. Non-limiting example interfaces110a-b, and112can include wired communication links such as a wired network or direct-wired connection, and wireless communication links such as cellular, radio frequency (RF), infrared and/or other wireless communication links. Interfaces110a-band112can allow database server102to communicate with client devices108a-bover various network types. Non-limiting example network types can include Fibre Channel, small computer system interface (SCSI), Bluetooth, Ethernet, Wi-fi, Infrared Data Association (IrDA), Local area networks (LAN), Wireless Local area networks (WLAN), wide area networks (WAN) such as the Internet, serial, and universal serial bus (USB). The various network types to which interfaces110a-band112can connect can run a plurality of network protocols including, but not limited to Transmission Control Protocol (TCP), Internet Protocol (IP), real-time transport protocol (RTP), realtime transport control protocol (RTCP), file transfer protocol (FTP), and hypertext transfer protocol (HTTP).

Using interface112, database server102can retrieve data from database114. The retrieved data can be saved in disk106or memory104. In some cases, database server102can also comprise a web server, and can format resources into a format suitable to be displayed on a web browser. Database server102can then send requested data to client devices108a-bvia interfaces110a-bto be displayed on an application116a-b. Application116a-bcan be a web browser or other application running on client devices108a-b.

FIG. 2shows an exemplary non-vector implementation of database records, according to some embodiments. These database records can be stored at database114, in memory104, and/or disk106. For ease of explanation,FIG. 2and other related figures describe an exemplary database of orders for parts, including information regarding dates, quantities, and part types. However, the systems, apparatus and methods described herein can be generalized, with appropriate modifications, to any arbitrary database.FIG. 2includes a DemandHeaders table201and a DemandLines table202; both depicted tables can be logical representations of data structures stored in database memory. DemandLines table202can include three columns: a “key label” column such as the “OrderId” column, a Date column, and a Quantity column. Each record (e.g., row) in DemandLines table202can refer to a different order. The “key label” column can include data used to match each record with records in other tables. In this case, the “key label” column is the OrderId column, which can store labels (e.g., Order ID) used to distinguish one set of orders from another. For example, Order ID can be used to distinguish between orders originating from different customers, or orders pertaining to different products or projects. The Date column can contain dates associated with each unique order, and the quantity column can contain quantities associated with each order.

DemandHeaders table201can contain two columns: a “key label” column, such as an OrderId column, and a DemandLines column. Each record (e.g., row) in DemandHeaders table201can contain data pertaining to a different key label (e.g., OrderId). The OrderId column in DemandHeaders table201can contain the same Order ID's stored in the OrderId column of DemandLines table202, except that each OrderId can appear only once in DemandHeaders table201(whereas they can appear multiple times in DemandLines table202). Every record (e.g., row) in the DemandLines column can store zero, one or more references to specific records (e.g., rows) in DemandLines table202. For example, for the record in DemandHeaders table201corresponding to OrderId SO-001, the DemandLines column can contain three separate references to three separate records in DemandLines table202: (i) the record in DemandLines table202pertaining to the SO-001 order dated Jan. 1, 2014, with quantity “12”; (ii) the record in DemandLines table202pertaining to the SO-001 order dated Feb. 1, 2014, with quantity “54”; and (iii) the record in DemandLines table202pertaining to SO-001 order dated Mar. 1, 2014, with quantity “37.” Each of these three separate references are illustrated inFIG. 2using a separate arrow linking DemandHeaders table201and DemandLines table202. Similarly, the DemandLines column in DemandHeaders table201can also contain separate references pertaining to OrderId's SO-002 and SO-003, as illustrated by further arrows linking DemandHeaders table201and DemandLines202.

In operation, DemandHeaders table201and DemandLines table202can be used together to look up specific orders related to different OrderId's. For example, if a user desires to search for all records pertaining to a particular key label, such as OrderId SO-001, the system can first look up DemandHeaders table201to determine the location of all records pertaining to SO-001. Once the system has determined the correct locations, the system can then navigate to the records in DemandLines table202containing the records (e.g., rows) corresponding to orders that have OrderId SO-001.

FIG. 3shows an exemplary vector implementation of database records, according to some embodiments. The vector implementation of a database can also be implemented at database114, disk106, and/or memory104.FIG. 3differs fromFIG. 2in that instead of including two database tables,FIG. 3includes one table, i.e., DemandHeader table301, as well as a plurality of vectors, i.e., “Vid” Vector303, Date Vector320, and Quantity Vector321.

DemandHeader table301can also include two columns: an OrderId column and a DemandLines column. The OrderId column can contain OrderId's, such as SO-001. However, instead of storing a plurality of memory references, wherein each reference relates to a separate record in another table, the DemandLines column can store, for each record (e.g., row), a memory reference that points to a vector. For instance, the DemandLines column can store a memory reference, denoted as VidVector Id302. A “memory reference” can be an identifier that uniquely identifies a location in database memory; in some embodiments, memory references can be a unique 64-bit memory location ID. As discussed above, a “vector” can be a data structure in memory that stores data in an ordered sequence of elements, wherein each element can store data, such as a string, an integer, a floating point decimal, references to memory locations, Boolean data, or other data types. Vectors can have any arbitrary length, such as zero elements, one element, two element, or hundreds, thousands, millions, or more elements.

In the depicted example, DemandHeader table301stores an association between OrderId SO-001 and memory reference VidVector Id302. VidVector Id302points to Vid Vector303. Vid Vector303can be a vector having two elements. The first element can be a DateVector Id310, which can contain a memory reference to a Date Vector320, while the second element can be a QuantityVector Id311, which can contain a memory reference to a Quantity Vector321. Vid Vector303can therefore be considered a “Vector ID” Vector (e.g., “vid” vector) because it is a vector that stores memory references to other vectors. In the depicted example, Date Vector320can in turn be a vector with three elements storing three dates: “Jan. 1, 2014”, “Feb. 1, 2014”, and “Mar. 1, 2014.” Quantity Vector321can also be a vector with three elements storing three quantities: “12”, “54” and “37.” Date Vector320and Quantity Vector321can therefore be considered data vectors, as each sequence in the vector contains a data payload.

Although not shown inFIG. 3, a vector-based database can also contain DemandHeader tables for OrderId's SO-002 and SO-003. Each DemandHeader Table for SO-002 and SO-003 can contain VidVector Id's to other Vid Vectors similar to Vid Vector303. Each Vid Vector can also contain DateVector Id's and Quantity Vector Id's similar to DateVector Id310and QuantityVector Id311, respectively. Each DateVector Id and Quantity Vector Id can also point to Date Vectors and Quantity Vectors similar to Date Vector320and Quantity Vector321, respectively.

In operation, DemandHeader table301, Vid Vector303, Date Vector320and Quantity Vector321can be used together to look up specific orders related to different OrderId's. For example, if a user desires to search for all records pertaining to OrderId SO-001, the system can first look up DemandHeader table301to determine the Vid Vector associated with SO-001. Once the system reads the memory reference located at VidVector Id302, the system can navigate to Vid Vector303. At Vid Vector303, the system can read the memory references stored at DateVector Id310and QuantityVector Id311, and using those references, navigate to Date Vector320and Quantity Vector321. By reading the contents of Date Vector320, the system can determine all the dates associated with orders having OrderId SO-001. Similarly, by reading the contents of Quantity Vector321, the system can determine all the quantities associated with orders having OrderId SO-001. Furthermore, the elements of Quantity Vector321can be sorted according to the dates contained in Date Vector320, such that the system can further determine that the quantity “12” is associated with the order associated with “Jan. 1, 2014”, the quantity “54” is associated with the order associated with “Feb. 1, 2014”, and the quantity “37” is associated with the order associated with “Mar. 1, 2014.”

Vector-based implementations for storing records can have several advantages over non-vector-based implementations. For example, non-vector-based implementations can require storing a key label (e.g., an OrderId) column as part of DemandLines table202. With vector-based implementations, there can be no need to store a corresponding key label vector. This is because when the system navigates to Vid Vector303, it will have reached Vid Vector303by looking up DemandHeader301, and will therefore know that Vid Vector303, and Date Vector320and Quantity Vector321which Vid Vector303references, all pertain to a particular key label, such as OrderId SO-001. In other words, the system will always know the “context” behind its access of Vid Vector303, Date Vector320, and Quantity Vector321. There is therefore no need to store a corresponding key label, such as OrderId inFIG. 2, for each record, which saves memory space. Furthermore, whereas each record in the DemandLines column of DemandLines table202had to store multiple memory references (e.g., one for each record in DemandLines table202pertaining to a specific OrderId), the DemandLines column of DemandHeader table301can, in some embodiments, contain a single memory reference: VidVector Id302. This results in further memory space savings. Yet another way in which vector-based implementations can save space relative to non-vector implementations is by compressing vectors using run-length encoding. Since vectors can sometimes comprise sequences of data that exhibit a degree of regularity or predictability, such vectors can be amenable to compression using run-length encoding.

Another advantage of vector-based implementations is that they can store data having repeated data fields more efficiently than non-vector-based implementations. For certain types of data, sequences of values can sometimes occur with a degree of repeatability or predictability. For instance, if orders are placed on a specific day each month, order records for different part types, projects, and/or customers can all have date fields that are identical to each other, such as “Jan. 1, 2014”, “Feb. 1, 2014”, and “Mar. 1, 2014.” Or, if a database is keeping track of sales activities, and sales are kept track of on a monthly basis, all sales orders, regardless of part type, project, and/or customer, will all have identical date fields (again, such as “Jan. 1, 2014”, “Feb. 1, 2014”, and “Mar. 1, 2014”). In yet another example, if a customer always orders the same quantities of certain products, such as a retailer that always orders 100 red widgets and 100 blue widgets every month, the quantities for both types of products will both be recorded as “100”, “100”, “100”, etc. When storing records that have data fields that occur with a degree of repeatability or predictability, vector-based implementations can save space by re-using vectors.

FIG. 4depicts another vector implementation of database records that illustrates an example of vector re-use, according to some embodiments. This vector database can be implemented at database114, memory106, and/or disk106. For ease of explanation,FIG. 4builds upon the example dataset and data structures described with regards toFIGS. 2 and 3. For example, just as inFIG. 3,FIG. 4also includes DemandHeader301storing an association between OrderId SO-001 and VidVector Id302, VidVector303storing an association between DateVector Id310and QuantityVector Id311, and Date Vector320and Quantity Vector321. These tables, memory references, and vectors can be configured similarly to those tables, memory references and vectors described above in relation toFIG. 3.

In addition to these previously-described elements,FIG. 4also includes a DemandHeader table350. DemandHeader table350can store an association between OrderId SO-002 and VidVector Id351. Similar to VidVector Id302, VidVector351can also be a memory reference that points to a Vid Vector—in this case, Vid Vector330. Similar to Vid Vector303, VidVector330can be a two-element vector that stores two memory references: a first reference DateVectorId361to a date vector, and a second reference QuantityVector Id362to a Quantity Vector370. Similar to Quantity Vector321, which stores quantities of orders associated with OrderId SO-001, Quantity vector370can store quantities of orders associated with OrderId SO-002, i.e., “10”, “20” and “18.”

Referring back toFIG. 2, it can be observed that the order records associated with OrderId SO-002 has a date progression that is identical to the order records associated with OrderId SO-001—both types of records have the date progression “Jan. 1, 2014”, “Feb. 1, 2014”, and “Mar. 1, 2014.” In the non-vector implementation described inFIG. 2, DemandLines table202must devote space to storing the sequence “Jan. 1, 2014”, “Feb. 1, 2014”, and “Mar. 1, 2014” twice: once for orders related to SO-001, and once for orders related to SO-002. In contrast, in the vector-based database depicted inFIG. 4, this date progression is stored only once, e.g., in Date Vector320. Instead of creating and storing a new vector having a redundant date progression, DateVector Id361, which is associated with OrderId SO-002, can point to the same Date Vector320which stores the dates associated with OrderId SO-001. In this way, Date Vector320is “re-used” by the database to store information pertaining to two OrderId's, which saves space.

To achieve this re-use, vectors can be stored as a “pool” so they can be shared by different records. In some embodiments, a database can also compute hashes of each vector in the pool, which can be used to facilitate determining whether a new vector needs to be created and referenced, or whether an existing vector can be re-used.

FIG. 5depicts an exemplary process500by which a vector implementation of a database can determine whether a new vector needs to be created, or whether an existing vector can be re-used, according to some embodiments. At step502, process500can determine that a new reference to a vector needs to be added. This can be because a new record is being added, or because an existing record is being modified or updated.

At step504, process500can compute the hash of the proposed new vector. This hash computation can be done using any known hashing method that converts the proposed new vector into a shorter string or sequence of data.

At step506, process500can compare the hash of the proposed new vector against hashes of vectors in a pool of vectors. If the hash of the proposed new vector does not match any hashes of vectors in the pool of vectors, process500can branch to step508, where the process can create, store, and reference a new vector. If, however, the hash of the proposed new vector does match one or more hashes of vectors in the pool of vectors, process500can branch to step510.

At step510, process500can compare the proposed new vector against existing vectors in the vector pool. In some embodiments, only vectors that correspond to hashes that matched with the hash of the proposed new vector are compared to the proposed new vector. If no existing vectors in the vector pool match the proposed new vector, process500can branch to step508, where the process creates and references a new vector. If, however, an existing vector is found that matches the proposed new vector, process500can branch to step512, where the process inserts a reference to the existing vector rather than creating a new vector.

It can sometimes be desirable to group records in a database according to different “sets” of records. For instance, in the examples discussed above, records have all been grouped according to the key field OrderId, e.g., “SO-001”, “SO-002”, and “SO-003.” However, it can also be desirable to group records according to other groups, such as part type, project ID, customer, manufacturing facility, geographic location, etc. Grouping records according to these other fields can give users of databases more flexibility in quickly accessing all records that pertain to a specific part type, to a specific project ID, or to a specific customer, etc.

FIG. 6shows an exemplary non-vector implementation of database records that illustrates how records can be grouped according to multiple groups, according to some embodiments. This non-vector database can be implemented at database114, disk106, and/or memory104. For ease of explanation,FIG. 6builds upon the example dataset and data structures described with regards toFIG. 2. DemandLines table602can be similar to DemandLines table202inFIG. 2, except that DemandLines table602can also include a “Part” column. The “Part” column can store data associating each order with a specific part type, such as “Part 1”, “Part 2”, and “Part 3.”

Similar toFIG. 2,FIG. 6also contains a DemandHeaders table201. Just as inFIG. 2, DemandHeaders table201can store associations between each OrderId (e.g., SO-001) and specific records (e.g., rows) in DemandLines table602.FIG. 6also contains a new PartsHeaders table601. PartsHeaders table601can contain two columns: a Part column and a DemandLines column. The Part column in PartsHeaders table601can contain the same Parts stored in the Part column of DemandLines table602, except that each Part can appear only once in PartsHeaders601(whereas they can appear multiple times in DemandLines602). The DemandLines column in PartsHeaders table601can store references to specific records (e.g., rows) in DemandLines table602that are associated with those part types. For example, for the record in PartsHeaders table601corresponding to Part 1, the DemandLines column can contain four separate references to four separate records: (i) the record in DemandLines table602pertaining to the SO-001 order dated Jan. 1, 2014, with quantity “12”; (ii) the record in DemandLines table602pertaining to the SO-001 record dated Mar. 1, 2014, with quantity “37”, (iii) the record in DemandLines table602pertaining to the SO-002 record dated Jan. 1, 2014, with quantity “30”, and (iv) the record in DemandLines table602pertaining to the SO-002 record dated Feb. 1, 2014, with quantity “25.” Similarly, the DemandLines column in PartsHeaders table601can also contain separate references pertaining to Part 2 and Part 3, as illustrated by further arrows linking PartsHeader601and DemandLines table602.

In operation, DemandHeaders table201, PartsHeaders table601, and DemandLines table602can be used together to group records according to different groups. For example, if a user desires to search for all records pertaining to OrderId SO-001, the system can consult the record associated with SO-001 within DemandHeaders table601to determine the location of all records associated with SO-001. On the other hand, if a user desires to search for all records pertaining to Part 1, the system can consult the record associated with Part 1 within PartsHeaders table601to determine the location of all records associated with Part 1. Additional Header tables and associated fields can also be added toFIG. 6to enable this database to group records according to other groups.

One potential disadvantage of non-vector databases is that each header table, e.g., DemandHeaders table201and/or PartsHeaders table601can be required to store many references to separate records for each group. In the example depicted inFIG. 6, the PartsHeaders table601must store four separate references to four records corresponding to Part 1, two separate references to two records corresponding to Part 2, and one reference to a record corresponding to Part 3. Referring back toFIG. 2, DemandHeaders table201must store three separate references corresponding to OrderId SO-001, three separate references corresponding to OrderId SO-002, and one reference corresponding to OrderId SO-003. Each separate reference can require a separate location in memory to store the association between that record and that part number or OrderId number. For databases that store a large number of records, storing and accessing record associations in this way can require a large amount of memory resources, as well as slow down database operations.

FIG. 7depicts an exemplary vector implementation of database records that illustrates how records can be grouped according to multiple groups, according to some embodiments. This vector-based database can be implemented at database114, disk106, and/or memory104. For ease of explanation,FIG. 7builds upon the example data set and data structures described with regards toFIG. 4. Just as inFIG. 4,FIG. 7also includes DemandHeader table301that stores an association between OrderId SO-001 and VidVector Id302, as well as DemandHeader table350that stores an association between OrderId SO-002 and VidVector Id351. VidVector Id302stores a memory reference that points to Vid Vector703, which is similar to Vid Vector303in that it stores memory references DateVector Id310and QuantityVector Id311. The memory reference stored in DateVector Id310points, in turn to Date Vector320, whereas the memory reference stored in QuantityVector Id311points to Quantity Vector321. Similarly, VidVector Id351stores a memory reference that points to Vid Vector730, which is similar to Vid Vector330in that it stores memory references DateVector Id361and QuantityVector Id362. The memory reference stored in DateVector Id361points to Date Vector320. As discussed above, Date Vector320can be associated with both OrderId's SO-001 and SO-002, thereby saving space. The memory reference stored in QuantityVectorId362points to Quantity Vector370.

InFIG. 7, the exemplary data structures inFIG. 4have been further extended to store part type information. Specifically, Vid Vector703includes an additional memory reference: PartsVector Id712, whereas Vid Vector730includes PartsVector Id762. PartsVector Id712can store a memory reference that points to Parts Vector722, whereas PartsVector Id762can store a memory reference that points to Parts Vector772.

Quantity Vector321, Parts Vector722, Quantity Vector370, and Parts Vector772can all be sorted according to the order of dates stored in Date Vector320. In operation, when a user desires to determine the part types of orders associated with a specific OrderId, such as SO-001, the system can first look up the appropriate DemandHeader table (e.g., DemandHeader table301) to determine the Vid Vector associated with that OrderId (e.g., Vid Vector703, which the system can navigate to by going to the memory location pointed to by VidVector Id302). Once the system navigates to the appropriate Vid Vector (e.g., Vid Vector703), the system can find the appropriate date, quantity and parts vectors (e.g., Date Vector320, Quantity Vector321, and Parts Vector722). Since all vectors are sorted according to Date Vector320, the system can determine that the order associated with “Jan. 1, 2014” is also associated with quantity “12” and “Part 1”, that the order associated with “Feb. 1, 2014” is also associated with quantity “54” and “Part 2”, and that the order associated with “Mar. 1, 2014” is also associated with quantity “37” and “Part 1”. Sorting vectors according to a key field, such as date vector320, can, under some circumstances, result in a higher rate of re-use for vectors corresponding to key fields. Also, sorting vectors according to a key field, such as date vector320, can also facilitate comparison, updating, and merging of vectors, as further described below.

FIG. 7also includes a PartsHeaders table701. PartsHeaders table701can be similar to PartsHeaders table601inFIG. 6in that it can also include a separate record (e.g., row) for each Part type (e.g., “Part 1”, “Part 2”, and “Part 3”). Instead of storing a reference to every individual DemandLine record that is associated with that Part type, however, PartsHeaders table701can store references to DemandHeader tables associated with Parts Vectors that include that Part type. For instance, PartsHeaders table701can store an association between Part 1 and two DemandHeader tables: DemandHeader table301and DemandHeader table350. This is because DemandHeader table301is associated with Parts Vector722, which includes “Part 1” (as well as other Part types), and because DemandHeader table350is associated with Parts Vector772, which also includes “Part 1” (as well as other Part types). Similarly, PartsHeaders table701can store an association between Part 2 and DemandHeader table301. This is because DemandHeader table301is associated with Parts Vector722, which includes Part 2. In some embodiments, PartsHeader table701would not store an association between Part 2 and DemandHeader table350, since DemandHeader table350is not associated with a Parts vector that includes Part 2. Similarly, in some embodiments, PartsHeader table701would store an association between Part 3 and DemandHeader table350, but not an association between Part 3 and DemandHeader table301.

In operation, PartsHeaders table701can be used together with the other data structures depicted inFIG. 7to group records according to different groups. For example, if a user desires to search for all records pertaining to OrderId SO-001, the system can consult DemandHeader table301according to the procedure described above. On the other hand, if the user desires to search for all records pertaining to Part 1, the system can consult the record associated with Part 1 within PartsHeaders table701. From there, the system can determine that the DemandHeader tables associated with OrderId SO-001 and SO-002 (i.e., DemandHeader table301and DemandHeader table350) are associated with parts vectors that contain “Part 1”. By tracing through the appropriate memory references, the system can traverse Parts Vector722and Parts Vector772and select only those records within those vectors that have a value corresponding to “Part 1.” This comparison can involve a simple comparison between two data values, and so can be very fast. Once the records that have values corresponding to “Part 1” have been selected (e.g., the first and the third element in Parts Vector722), the system can also retrieve corresponding records from Date Vector320and Quantity Vector321.

The vector-based implementation described inFIG. 7can save space relative to the non-vector-based implementation described inFIG. 6. This can be seen in the smaller number of references that must be stored in PartsHeaders table701relative to PartsHeaders table601. For example, PartsHeaders table601stores four references for Part 1, whereas PartsHeaders table701stores only two references for Part 1. In database implementations using long vectors (e.g., vectors with dozens, hundreds, thousands, millions, or even more elements), this space savings can become considerable. Database performance can also be improved in vector-based implementations because retrieving groups of records can require fewer memory-accesses. The reduction in memory-access can be due to the densely-compacted nature of the vectors, in comparison with the non-vector use of points and a container.

Another benefit of vector-based implementations (e.g., databases that use vector-based tables) is that the header tables can absorb the responsibility for overhead that would otherwise be on each record in a set. Vector-based implementations can therefore avoid consuming space to store values that are generally required to support different features, such as maintaining different versions of the same data.

FIG. 8depicts an exemplary non-vector implementation of database records that supports a versioning feature, according to some embodiments. This non-vector database can be implemented at database114, disk106, and/or memory104. For ease of explanation,FIG. 8builds upon the example data set and data structures described with regards toFIG. 2. Just as inFIG. 2,FIG. 8also includes DemandHeaders table201that stores associations between different OrderId's and specific records.FIG. 8also includes DemandLines table802. DemandLines table802is the same as DemandLines table202inFIG. 2except that records pertaining to OrderId's other than SO-001 have not been shown, and an additional column labeled “Version” has been added. This additional “Version” column can store a version number associated with each record. The first three records (e.g., rows) in DemandLines table802corresponds to the first three rows of DemandLines table202. Assume that a user then changes the order associated with “Mar. 1, 2014” to have a quantity of “40” instead of “37.” To capture this change in a new version, the system can add a new record (e.g., row) to DemandLines table802that is identical to the previous “Mar. 1, 2014” record except that the quantity has been revised from “37” to “40”, and its version number has been incremented from “1” to “2”. This newly created record is depicted as the fourth record (e.g., row) in DemandLines table802. DemandHeaders table201is then updated to store a new association between OrderId SO-001 and the newly created fourth record, which is depicted as an arrow linking DemandHeaders table201with the newly created fourth record in DemandLines table802. In this implementation, every version update can result in a new record being added to DemandLines table802, and a new reference being stored in DemandHeaders table201linking the appropriate OrderId with the new record.

FIG. 9depicts an exemplary vector implementation of database records that supports a versioning feature, according to some embodiments. This vector-based database can also be implemented in database114, disk106and/or memory104. For ease of explanation,FIG. 9builds upon the example data set and data structures described with regards toFIG. 3. Just as inFIG. 3,FIG. 9also includes Vid Vector303, which contains a Date Vector Id310that references a Date Vector320, as well as a QuantityVector Id311that references a quantity vector321.FIG. 9also includes a DemandHeader table901. DemandHeader table901is similar to DemandHeader table301inFIG. 3except that it has been extended to include a new “Version” column. This “version” column keeps track of version numbers associated with different Vid Vectors.

In general, when one or more values associated with a record is updated, a new data vector is created that reflects the change. In addition, a new Vid vector is created that references the newly created data vector. Then, a new record (e.g., row) is added to the appropriate header table that references the newly created Vid vector, and associates that newly created Vid vector with an incremented version number.

An example of this operation is depicted inFIG. 9. Consider again the case where the record associated with “Mar. 1, 2014” is updated from a quantity of “37” to “40.” The system can create a new vector, e.g., Quantity Vector921. Quantity Vector921can be a duplicate of Quantity Vector321except that the last record is changed from “37” to “40” to reflect the change. Then, a new Vid Vector903is created. Vid Vector903can have the same structure as Vid Vector303in that it can also contain a reference to a Date Vector (e.g., DateVector Id910) and a reference to a Quantity Vector (e.g., QuantityVector Id911). Since the update of the “Mar. 1, 2014” order from “37” to “40” does not involve a change to any dates, DateVector Id910of Vid Vector903can refer to the same Date Vector320as Vid Vector303. However, since the update does involve a change to a Quantity Vector, QuantityVector Id911can refer to the newly created Quantity Vector921. After Vid Vector903has been created and stored, DemandHeader table901can be updated to include an additional record (e.g., row). This new row can also refer to OrderId SO-001, but have its version number incremented from “1” to “2”. This new record can also contain a memory reference to Vid Vector903in its DemandLines column, e.g., at VidVector Id902.

In operation, when a user wishes to retrieve the latest version of all orders associated with OrderId SO-001, the system can consult DemandHeader table901and determine that the record with the highest version number is the second record, having version number “2”. The system can then follow VidVector Id902to navigate to Vid Vector903. At Vid Vector903, the system can then navigate to Date Vector320and Quantity Vector921, which corresponds to the latest records associated with OrderId SO-001. If, on the other hand, the user wishes to retrieve version 1 of orders associated with OrderId SO-001, the system can consult DemandHeader table901and determine that VidVector303(as stored in VidVector Id302) corresponds to version 1. By navigating to Vid Vector303, the system can determine that Date Vector320and Quantity Vector321is associated with version 1 of orders associated with OrderId SO-001.

Certain embodiments of vector-based implementations can also support updating and merging of vectors. Updating and merging of vectors can be advantageous when a database maintained by a central server, or portions of said database, can be checked out and edited offline by multiple users simultaneously, or can be edited by multiple users at once. When these users check in their offline versions of the database back into the central server, or when these users finish their simultaneous edits, updating and merging of multiple vectors can comprise reconciling conflicts and updates between different versions.

FIG. 10depicts an exemplary scenario where multiple versions of a database, or portions thereof, can be compared, updated, and/or merged with one another.FIG. 10includes a timeline1001which shows the progression of time from left to right. At step1002, which corresponds to time value t=0, a central database maintains a version CV P of a compound vector. A “compound vector”, or “CV”, can be a combination of two or more vectors, in which one vector can be considered a “key” vector that determines the sort order of the other vectors. A “compound vector” can also refer to a set of records represented by a VidVector, such as VidVector703inFIG. 7. In this example, compound vector CV P comprises two vectors: a key vector “KP” that lists an ascending series of dates (e.g., “Jan. 1”, “Jan. 2”, “Jan. 5”, and “Jan. 6”), and a data vector “Pn” whose contents are sorted according to the sequence of dates stored in KP. While compound vector CV P is depicted as including two vectors, additional data vectors can also be included, wherein each data vector is sorted according to the sequence in KP.

At time t=1, two things can occur. At step1004: a first user A can copy the out the compound vector CV P to create a local version specific to A. At step1010: a second user “B” also copies the compound vector P to create a local version specific to B. In some embodiments, this copying operation can be referred to as creating a new scenario. At this point, three versions, or “scenarios”, of compound vector CV P exist: one maintained in a central database, one in the possession of A, and one in the possession of B.

At step1006, the first user can modify the compound vector CV P in her possession to create compound vector CV A.

At step1008, which corresponds to time value t=2, user A can commit compound vector CV A back into the central database. “Committing” a database, or a portion of a database (such as a compound vector), can refer to saving changes made to a first version of a database into a second version of the database, thereby combining the two versions of the database in a way that preserves changes made later in time. Since CV A contains changes made later in time than any changes made to CV P, the commit operation at step1008can simply comprise saving the changes that A had made to CV A into the central database as a new version that takes precedence over the previously existing CV P.

At step1012, the second user can modify the compound vector CV P in his possession to create compound vector CV B.

At step1014, which corresponds to time value t=3 (e.g., later in time compared to time value t=2), user B can commit compound vector CV B back into the central database. At this point, the system can merge compound vector CV B, which contains edits to CV P, with CV A, which is currently stored in the central database.

This merge operation can, in some embodiments, be implemented by comparing three different compound vectors: CV A (the version saved in the central database at time t=2), CV B (the version being checked-in by user B at time t=3), and CV P (the last common ancestor of CV A and CV B). The merge operation can proceed by comparing each element of KP, KA, and KB in sequence.

FIGS. 11A and 11Blist an exemplary set of rules that can be used to implement this merge operation. Condition column1102lists a series of conditions, where each condition is listed with the smallest number first. So for instance, Rule1102acan apply when KP equals KA and KB. Rule1102bcan apply when KP equals KA, and both are smaller than KB. Rule1102ccan apply when KP equals KA, and both are greater than KB. Rule1102dcan apply when KP=KB, and both are less than KA, etc. Rules1102ithrough1102papply when CV A, CV B and CV P are of unequal length, such that one vector runs out before the other two vectors run out. In those cases, a “-” symbol is used to signify that one vector has run out.

Rule column1104lists the appropriate action to take in the event of each condition. References to inserting various element pairs (e.g., (KA, An) or (KB, Bn)) into a merged vector refers to adding an element to a new merged compound vector, such as CV M, having key vector KM and data vector Mn. References to “advancing” a vector refers to moving to the next element in that vector.

FIGS. 12A-Fdepict an example of how the rules listed inFIGS. 11A-Bcan be applied to compound vectors CV P, CV A, and CV B inFIG. 10. Recall that in this illustrative example, CV P is the original version of the compound vector, CV A is the compound vector that user A had first committed back to the database, and CV B is the compound vector that user B had subsequently committed back to the database, and which now needs to be merged. AtFIG. 12A, the merge operation begins by comparing the first records in CV P, CV A, and CV B. The current records being compared in each compound vector CV P, CV A, and CV B are highlighted using bolded black boxes. As can be seen, the first record (KP, Pn) in CV P is (“Jan. 1”, 34), the first record (KA, An) in CV A is (“Jan. 1”, 34), and the first record (KB, Bn) in CV B is (“Jan. 1”, 52). Since KP==KA==KB==“Jan. 1”, rule1102aapplies. Since An and Pn are equal to one another (i.e., they are both 34) but are not equal to Bn (i.e., 52), rule1102aspecifies to insert (KB, Bn) into the merged vector. This can be seen by the addition of (“Jan. 1”, 52) into merged vector CV M, on the right. Rule1102aalso specifies that in this situation, the system can “advance each vector.” This is denoted by the downward arrows attached to the bottom of each bolded black box.

FIG. 12Billustrates the next step of the merge operation. The system now compares the second record of each compound vector. The second record (KP, Pn) in CV P is (“Jan. 2”, 50), the second record (KA, An) in CV A is (“Jan. 2”, 50), and the second record (KB, Bn) in CV B is (“Jan. 3”, 4). Since KP is equal to KA (i.e., they are both “Jan. 2”), and both are less than KB (“Jan. 3”), rule1102bapplies. In this case, the system can determine that a record is missing from CV B. Nothing gets added to compound vector CV M, and CV A and CV P are advanced, meaning that the system moves on to consider the next element in each vector. The advancement of CV A and CV P is denoted by the downward arrows at the bottom of the black boxes on CV P and CV A.

FIG. 12Cillustrates the next step of the merge operation. The system now compares the third records of compound vectors CV P and CV A with the second record of CV B. The third record (KP, Pn) in CV P is (“Jan. 5”, 17), the third record (KA, An) in CV A is (“Jan. 5”, 69), and the second record (KB, Bn) in CV B is (“Jan. 3”, 4). Since KP is equal to KA (i.e., they are both “Jan. 5”), and both are greater than KB (i.e., “Jan. 3”), rule1202capplies. In this case, the system can determine to insert (KB, Bn) into the merged vector CV M. This can be seen by the addition of (“Jan. 3”, 4) into merged vector CV M, on the right. Rule1102calso specifies that in this situation, the system can advance CV B. This is denoted by the downward arrow at the bottom of the black box on CV B.

FIG. 12Dillustrates the next step of the merge operation. The system now compares the third records of compound vectors CV P, CV A, and CV B. The third record (KP, Pn) in CV P is (“Jan. 5”, 17), the third record (KA, An) in CV A is (“Jan. 5”, 69), and the third record (KB, Bn) in CV B is (“Jan. 6”, 80). Since KP is equal to KA (i.e., they are both “Jan. 5”), and both are smaller than KB (i.e., “Jan. 6”), rule1102bapplies. Nothing gets added to compound vector CV M, and CV A and CV P are advanced. This can be because although the record associated with Jan. 5 had previously existed in CV P and CV A, user B had subsequently deleted that record, and so it is not saved in the merged vector. The advancement of CV A and CV P is denoted by the downward arrows at the bottom of the black boxes on CV P and CV A.

FIG. 12Eillustrates the next step of the merge operation. The system now compares the fourth records of compound vectors CV P and CV A, and the third record of CV B. The fourth record (KP, Pn) in CV P is (“Jan. 6”, 20), the fourth record (KA, An) in CV A is (“Jan. 7”, 77), and the third record (KB, Bn) in CV B is (“Jan. 6”, 80). Since KP is equal to KB (i.e., they are both “Jan. 6”) and both are smaller than KA (“Jan. 7”), rule1102dapplies. Nothing gets added to the compound vector CV M, and CV P and CV B are advanced. This can be because although user B had included a record for “Jan. 6”, user A had deleted that record, and so the merged vector does not include a record for “Jan. 6”. This is denoted by the downward arrow at the bottom of the black boxes on CV P and CV B.

FIG. 12Fillustrates the next step of the merge operation. Since CV P has no more records left to compare, the system now compares the fourth records of CV A and CV B. The fourth record (KA, An) of CV A is (“Jan. 7”, 77), while the fourth record (KB, Bn) of CV B is (“Jan. 7”, 84). Since KA is equal to KB, rule1102kapplies. In this case, the system inserts (KA, An) into merged vector CV M. This can be seen by the addition of (“Jan. 7”, 77) into merged vector CV M, on the right. Rule1102kalso specifies that in this situation, the system can advance CV A and CV B. This is denoted by the downward arrow at the bottom of the black boxes on CV A and CV B.

Since CV A and CV B have no more records, the merge operation can end at this point. The resulting merged vector CV M now has three records: (“Jan. 1”, 52), (“Jan. 3”, 4), and (“Jan. 7”, 84). This merged vector CV M can be saved into the central database at time t=3.

While the above figures and description have been focused on a database of parts orders, the non-vector and vector-based implementations of databases can be adapted and generalized to any arbitrary database. Any database that organizes data according to a plurality of records, each record having one or more fields, and which optionally supports grouping and versioning features can be implemented according to both the non-vector and vector-based implementations described above. Non-limiting examples of databases that can be implemented using one or both approaches can include databases recording sales activities and/or forecasts, manufacturing activities and/or forecasts, inventory levels, weather patterns and/or observations, student and/or employee performance indicators, cargo tracking and/or planning data, astrometric data, computational resources, consumer spending habits and patterns, macroeconomic data, etc. Instead of using dates as a key field for determining sort orders in compound vectors, any arbitrary field can serve as a key field. Non-limiting examples of fields that can be used as a key field include customer name, ship-to location, customer contact, project type, project name, product type, etc. Instead of using OrderId to organize records, any arbitrary field can be used as a key label to organize records, including all of the aforementioned fields. In no way should the aforementioned examples limit the scope of the invention, as they are only exemplary embodiments of vector and non-vector-based implementations of databases.

In some embodiments, databases can combine both vector and non-vector-based approaches. For example, databases can store a database in non-volatile memory using a non-vector-based implementation, and then convert the non-vector database into a vector-based implementation when loading the database, or a portion thereof, into volatile memory upon startup (or vice-versa). In some embodiments, databases can store certain types of data using a non-vector-based implementation, and other types of data using a vector-based approach. This can exploit the fact that certain types of data exhibit higher degrees of repeatability or predictability than other types of data, thereby making them more amenable to vector-based implementations. In some cases, databases can be configured to convert between vector-based and non-vector-based implementations depending on expected or observed characteristics of datasets, such as the dataset's predictability, periodicity, and/or entropy.

The features described can be combined in other ways as well. For example, each of the vector re-use feature described in relation toFIGS. 4-5, the grouping feature described in relation toFIG. 7, the versioning feature described in relation toFIG. 9, and the merge and update feature described in relation toFIGS. 10-12Fare optional features and are not necessary to the described embodiments. However, any or all of these features can also be combined in any database implemented using vector-based tables. While the figures above describe each feature in isolation, this is for ease of explanation only, and does not preclude combinations of these features in the same database.

FIG. 13depicts an example of a computer system1300with which embodiments of the present invention can be implemented. Client devices108a,108b, and/or data server102can be implemented according to parts or all of the computer system1300. According to the present example, the computer system can include a bus1301, at least one processor1302, at least one communication port1308, a memory1306, a display1304, and a user interface1310.

Processor(s)1302can include any known processor, such as but not limited to, an Intel® Itanium® or Itanium 2® processor(s), AMD® Opteron® or Athlon MP® processor(s), Motorola® lines of processors, Apple® A7®, A8®, A9® lines of processors, or Qualcomm® lines of processors. Communication port(s)1308can be any communication interface used for communicating with another device, such as an RS-232 port for use with a modem based dial-up connection, a 10/100 Ethernet port, a Bluetooth® or WiFi interface, a Gigabit port using copper or fiber, or a 3GPP, LTE, or other wireless cellular network-based interface. Communication port(s)1308can enable computer system1300to communicate over a network such as a Local Area Network (LAN), Wide Area Network (WAN), or any network to which computer system1300connects. Memory1306can comprise Random Access Memory (RAM) or any other dynamic storage device(s) commonly known to one of ordinary skill in the art. Memory can also comprise Read Only Memory (ROM) that can include any static storage device(s) such as Programmable Read Only Memory (PROM) chips for storing static information such as instructions for processor1302, for example. Furthermore, memory1306can also comprise mass storage memory for storing information and instructions. For example, hard disks such as the Adaptec® family of SCSI drives, an optical disc, an array of disks such as RAID (e.g., the Adaptec family of RAID drives), or any other mass storage devices may be used. Bus1301can be a PCI/PCI-X or SCSI based system bus depending on the storage devices used, for example.

Display1304can include any known device for displaying data in a visual format, including screens or displays integrated into computer system1300, as well as screens, displays or monitors that communicate but are not integrated with computer system1300. User-interface1310can include any known device for receiving user input, including keyboards, microphones, optical or trackball mouse, joysticks, trackballs, gesture recognition devices, etc. In some embodiments, user-interface1310can be integrated with display1304, as in the case of a responsive touchscreen. In other embodiments, user-interface1310can be a separate device that is integrated with computer system1300(e.g., a built-in physical keyboard, as in the case of a laptop) or that communicate but are not integrated with computer system1310. The components described are meant to exemplify some types of possibilities. In no way should the aforementioned examples limit the scope of the invention, as they are only exemplary embodiments of computer system1300and related components.

The implementations described herein can be implemented for both in-memory storage and disk-based storage. Re-use of vectors can provide an improvement, but is not a necessary aspect of the systems and methods described herein. Furthermore, the systems and methods described herein can be implemented without versioning of the database. Vectors can also be compressed with run-length encoding to get further savings on disk and possibly in memory. Included here is the possibility of using deltas to handle changes across versions. However, neither use of run-length encoding nor use of deltas are necessary features of the systems and methods described herein.

The systems and methods can be implemented in a processor using hardware and/or software processing, with a processor that can include one or more general purpose CPUs, and/or special purpose processing. The processor can include execution circuitry and memory for storing data and instructions. The system can be used to save data in in-system memory, or on other data storage media including magnetic or optical media. The memory can reside in one location or in multiple locations. Interfaces can also be provided between the processor and memory. Instructions to be executed by processing circuitry can be stored in various types of memory in a non-transitory manner.