Research On Optimization Of Physical Layer In Column-Oriented Database

Because of the rapid growth of massive data on the Internet, the development of datawarehouse and OLAP, and the needs of business analysis, column-oriented storage model,with its storing and querying advantages, has been developing pretty quickly. Itscolumn-oriented storage feature means that, different methods should be used to designphysical layer of database. Meanwhile, as many optimization techniques in row-orienteddatabases can’t apply to column-oriented databases, especially the index techniques, weneed to design new optimization techniques. Therefore, to do research on the structure ofphysical layer and index techniques based on columns, is very important to thedevelopment and use of column-oriented databases.Based on the above requirements, the physical layer structure in column-orienteddatabase has been studied, and a prototype system been implemented. In the dataorganization and management, fixed-records data blocks style and large memory poolmechanism are adopted. LZW compression algorithm, based on the dictionary encoding,is used for compressing data. And a comparison between LZW and PPM compressionalgorithm based on statistical coding, is made to show the performance differencesbetween the two algorithms.At the same time, based on the string index techniques in column-oriented storage, anew kind of tree structure named vowel-consonant tree, is designed to reduce theretrievals of uncorrelated data packs. First, according to the needs of column-orienteddatabase and string queries, a more simplified tree structure is designed. Based on thestructure of the tree, a Deterministic Finite Automaton and its tuples are defined. Based onthe definitions of the structure and DFA, a series of common operations, such asinitialization, storage and string matching functions, are designed.When applied to the column storage, further improvements, including a double-levelstructure of vowel-consonant root tree and data pack trees, are applied to vowel-consonanttree. While using a single-mode and dual-mode matching strategy, a dual-mode matchingbased on a single-mode matching can further improve query efficiency.