This database engine was first used on an Apple II computer with 143K floppy drives. The customer needed to store 5,000+ variable length pricing records per disk with instant access. This engine was also used in the MarketOrder Seamless Ordering Legacy system. The database engine had to handle computer crashes at any time. It was built ONLY for lookups and updates and was not built for enumerations.
Tool Specialty Company (Los Angeles, CA), Wetmore Cutting Tools (City of Industry, CA), MarketOrder.com (Seattle, WA)
This is a very specialized database engine. It was designed for ultra fast lookups and updates. The database had to maintain data integrity and the computer could be powered off at any time without warning. The original Apple II computer had a simple power-off switch and the MarketOrder legacy system used a Telxon 701 handheld computer with batteries that could fall out when dropped (and no backup power). The Apple II version could hold well over 5,000 variable length records on a 143K floppy disk. The MarketOrder version had to store up to 100,000 item records with UPC number, description, price, and qty in less than 4M of RAM. Some of the requirements for the database included:
Implementation: The original database engine wrote data directly to the sectors on the Apple II floppy disk and bypassed the normal file system. The MarketOrder version used a file but wrote to fixed blocks within that file. The engine used a double-hashing algorithm to store and retrieve the records, required no index or directory, included multiple data integrity checks, and could do limited data correction. The database used fixed data blocks (either disk sectors or file blocks). The number of data of blocks was a prime number. The lookup key was hashed using a double hashing function to generate primary and secondary hash values. Other details about the engine include:
The original test version of this engine used a more standard hashing function similar to ones that you might find in a computer science textbook. I found that these functions did not evenly distribute the data in the data blocks. The records clumped into groups with other data blocks containing fewer records. A computer science professor at the time told me that this phenomenon was called “harmonic clustering” and the record collided based on the mathematical harmonics of the hashing function. The final hashing was based on the prime number sequence was suggested by a math professor. He had no idea if that would work but his intuition told him that it might (and it did).
This database engine would normally find a record with a single access and required no indexes. The Telxon version used a simple blocked file and the file was opened, the record was found, and the file was closed. Since the Telxon 701 used a RAM-based file system this file open/close required very little overhead and was exceedingly fast. Since the engine require no directories or indexes the computer could crash at any time and crashed would almost never affect the data. If the computer crashed in the middle of a write operation the integrity check would catch the error and reconstruction routines could recover or fix the data. The database ran very comfortable even when the storage medium was over 90% full.
The MarketOrder version used Boolean masking when performed the hashing calculations. This way computers with differ word lengths and different math engines would always calculate the same hash values. The Telxon 701 used an 8-bit CPU with 16-bit words and the PCs at the time used different word lengths. When calculating the hashes each intermediate result was ANDed with a bit mask to ensure that the results did not exceed the 16-bit word length. The PC would thus create a populated database and this file could be copied to the 701 and the lookups.
This database engine was used for years in the machine shops for pricing records. The MarketOrder version allowed an outdated legacy handheld computer to operate on a huge database. The legacy system required lookups for all items in a large department store. A 100,000 item lookup and pricing table could be stored in a mere 4MB and the engine would comfortable operate on an 8-bit legacy CPU.
Before implementing this database engine we tried using a very well-known database system. After several weeks the company engineers stopped trying to make it work. Their database required too much processing power and could not compress the data sufficiently to meet the requirements. The off-the-shelf database did not even come close to working.
This database engine was very fast, very robust, almost impervious to data errors, and each data block was checked with each record access. The data checking tool took almost no CPU time and added an additional level of reliability. The MarketOrder version allowed legacy terminals to function at a much high level than previously possible. The legacy application was a bridge measure. The customer had a huge investment in the equipment and the old equipment could be used until the hardware failed. When the hardware failed it would be replaced by a more modern device.
The original database engine used the following:
The prototype application used the following: