Database system with data organization providing improved bit parallel processing
A database system provides vertical or horizontal pre-packing of database data elements according to a size of physical processor words in order to obtain improved parallel processing at the bit level. After processor words are populated with data from multiple data elements of the database, query operations are used which may simultaneously process the multiple data elements in each data word simultaneously in the computer arithmetic logic unit.
1. A database system comprising:
a data storage device for holding database data elements;
a processor in communication with the data storage device, the processor executing a stored program held in a non-transient medium to:
(a) receive input indicating a projected type of database activity to be conducted on the database elements:
(b) based on the received input, read the database data elements from a first memory structure in memory and reorganize the database data elements in a second memory structure in memory in a selected one of a horizontal bit parallel structure and vertical bit parallel structure as determined from the received input;
wherein the horizontal bit parallel structure provides multiple logical rows and columns and organizes multiple data elements in each logical row, where the logical row may be receivable in its entirety by an arithmetic logic unit of the processor for execution by the arithmetic logic unit of bits of the multiple data elements in parallel; and
wherein the vertical bit parallel structure provides multiple logical rows and columns and organizes multiple data elements in multiple logical columns so that bits only of a single order of the organized data elements are in each logical row, where the logical row may be receivable in its entirety by an arithmetic logic unit of the processor for execution by the arithmetic logic unit of all of the bits of the single order of the multiple data elements in parallel; and
(c) execute queries on multiple data elements in parallel by bit-parallel processing of the multiple logical rows of data using the arithmetic logic unit.
2. The database system of claim 1 wherein, the queries evaluate query conditions of equals, not equals, greater than, less than, greater than or equal, less than or equal, and between with respect to at least one query value.
3. The database system of claim 2 wherein the bit parallel processing of the query applies to at least one argument of a length matching a length of the logical row to data of multiple data elements, simultaneously, to all data elements in the logical row.
4. The database system of claim 3 wherein the bit-parallel processing generates a result of length equal to the length of the logical row and having a single bit corresponding to each data element of the logical row and indicating whether the data element meets the query condition.
5. The database system of claim 1 wherein the data elements, when organized in a horizontal bit parallel structure, are organized in a logical row with bits in a sequence according the order of the bit with all bits of each data element preceded by a delimiter bit.
6. The database system of claim 5 wherein multiple adjacent data elements when organized in a horizontal bit parallel structure are not sequential in a database order of the data in the logical row.
7. The database system of claim 6 wherein the multiple adjacent data elements within a data word are each k+1 greater in database order from a previous data element where k is a bit length of the data elements.
8. The database system of claim 1 wherein the data elements when organized in a vertical bit parallel structure are arranged in adjacent logical columns so that bits of sequential data elements are in database order in the logical row.
9. The database system of claim 1 wherein the bit parallel processing of the queries uses only operations that do not require bit carry or bit shifting.
10. The database system of claim 1 wherein the bit parallel processing of the vertical bit parallel structure by the queries sequentially processes logical rows holding the more significant bits of the data elements and proceeds in order toward processing logical rows holding less significant bits of the multiple data elements and wherein the bit parallel processing stops before evaluation of a query condition on all logical rows of given data elements in cases when applying an argument to a current logical row precludes a possibility of the query condition being met in the processing of later logical rows.
11. The database system of claim 10 wherein the processor executes the stored program to monitor the stopping before evaluation of a query condition on all logical rows of given data elements to selectively separate ranges of bit orders of the multiple data elements of the logical words into separately pre-loadable increments of data so that an earlier stopping causes a separation into a smaller range of bit orders and a later stopping causes a separation into a larger range of bit orders.
12. A database system comprising:
a data storage device for holding database data elements; and
a processor in communication with the data storage device, the processor executing a stored program held in a non-transient medium to:
(a) pre-process database data elements from a first memory structure in memory to reorganize the database data elements in a second memory structure in memory in a horizontal bit-parallel structure providing multiple logical rows and columns and organizing multiple data elements in each logical row, where the logical row may be receivable in its entirety by an arithmetic logic unit of the processor for execution by the arithmetic logic unit of bits of the multiple data elements in parallel; and
(b) execute queries on multiple data elements in parallel by bit-parallel processing of the multiple logical rows of data using the arithmetic logic unit.
13. The database system of claim 12 wherein the data elements are organized in a logical row with bits in a sequence according to an order of the bit with all bits of each data element preceded by a delimiter bit.
14. The database system of claim 12 wherein multiple adjacent data elements are not sequential in a database order of the data in the logical row.
15. The database system of claim 14 wherein the multiple adjacent data elements within a data word are each k+1 greater in database order from a previous data element where k is a bit length of the data elements.
16. A database system comprising:
a data storage device for holding database data elements; and
a processor in communication with the data storage device, the processor executing a stored program held in a non-transient medium to:
(a) pre-process database elements from a first memory structure in memory to reorganize the database data elements in a second memory structure in memory in a vertical bit parallel structure wherein the vertical bit parallel structure provides multiple logical rows and columns and organizes multiple data elements in multiple logical columns so that bits only of a single order of the organized data elements are in each logical row, where the logical row may be receivable in its entirety by an arithmetic logic unit of the processor for execution by the arithmetic logic unit of all of the bits of the single order of the multiple data elements in parallel; and
(c) execute queries on multiple data elements in parallel by bit-parallel processing of the multiple logical rows of data using the arithmetic logic unit.
17. The database system of claim 16 wherein the data elements when organized in a vertical bit parallel structure are arranged in adjacent logical columns so that bits of sequential data elements are in database order in the logical row.
18. The database system of claim 16 wherein the bit parallel processing of the query uses only operations that do not require bit carry or bit shifting.
19. The database system of claim 16 wherein the bit parallel processing of the vertical bit parallel structure by the queries sequentially processes logical rows holding the more significant bits of the data elements and proceeds in order toward processing logical rows holding less significant bits of the multiple data elements and wherein the hit parallel processing stops before evaluation of a query condition on all logical rows of given data elements in eases when applying an argument to a current logical row precludes a possibility of the query condition being met in the processing of later logical rows.
20. The database system of claim 19 wherein the processor executes the stored program to monitor the stopping before evaluation of a query condition on all logical rows of given data elements to selectively separate ranges of bit orders of the multiple data elements of the logical words into separately pre-loadable increments of data so that an earlier stopping causes a separation into a smaller range of bit orders and a later stopping causes a separation into a larger range of bit orders.