Karthikeyan Ramasamy
Research Interests
Data Warehousing, Web Servers and Caching Systems, Object Relational Database Systems and File Systems
Education
University of Wisconsin Madison, WI. Ph.D (Computer Science) - July 2001
University of Missouri Kansas City, MO. M.S (Computer Science) - August 1993
Anna University Madras, India. B.E (Computer Science and Engineering) - August 1989
Professional experience
Software Consulting Engineer NCR Corporation, Madison, WI - August 1998 - August 1999
Software Engineer Compuware Corporation, Cupertino, CA - September 1993 - August 1994
Senior Research Assistant Indian Institute of Technology, New Delhi, India - August 1990 - August 1991
Software Engineer Pertech Computers Limited, New Delhi, India - August 1989 - August 1990
Thesis Research
Sets in Object Relational Database Systems
Set valued attributes have long been studied by the data modeling community. However, it is only recently, with the advent of commercial object relational database systems supporting set-valued attributes, that the thorny issue of performance of operations over set-valued attributes has become apparent and relevant. Speeding up set valued attributes depends on efficiently storing sets and fast operations over them. My thesis studies in detail about these aspects.
High Performance Implementation Techniques for Set Valued Attributes
All the major O/R DBMS vendors either currently support or will support set-valued attributes in their universal servers. There has been little published about how sets should be stored in an O/R DBMS system. Two main options have been proposed for implementing set-valued attributes in object-relational systems: inlined, and external. In the inlined representation, the set itself is stored as a variable-length attribute within the tuple to which it belongs. On the other hand, in the external representation, the elements of a set-valued attribute are stored as tuples of an auxiliary table, and are connected back to the tuple to which they belong by a key-foreign key reference. While the O/R DBMS vendors generally do not publish their future design plans, it appears that at least initially O/R DBMS vendors will support sets using the external representation. This is the representation that was used by the Illustra O/R DBMS. The motivation for this is clear - the external representation has the overwhelming advantage of being simple to implement, since to the engine the set appears to be a standard table, and queries involving set-valued attributes are translated into standard relational operations on standard relational tables.
In our implementation we found that the external representation is indeed simple to implement, requiring essentially no changes to the query evaluation engine. Unfortunately, the performance of the external representation on some common forms of queries involving set-valued attributes was abysmal when compared to the performance of our inline representation. Perhaps surprisingly, this was true even for large sets, which contradicts the common wisdom that only small sets should be inline. The performance advantage of inline sets was so dramatic that inline would always be the method of choice but for one major drawback: on queries that reference tables with set-valued attributes, but do not reference set-valued attributes, the overhead of inline sets can be an almost intolerable burden. We classify these representations and develop a detailed analytical model to evaluate the trends and performance of conjunctive and disjunctive queries over these representations; furthermore, we verify our predictions by a complete implementation in the Paradise Object Relational System. Our experiments show that while there are substantial differences in the performance of the different representations, and in general nested representations perform better that unnested external. Unnested external suffers from effect of cardinality explosion and the associated tuple overheads of pinning and unpinning pages in the buffer pool and accessing tuples from them.
Set Containment Joins: The Good, The Bad and The Ugly
One of the most important and challenging operations on set valued attributes is the set containment join, because is provides a concise and elegant way to express otherwise complex queries. Unfortunately, evaluating these joins is difficult and naive approaches lead to algorithms that are very expensive. We developed a new partition based algorithm algorithm for joins. The Partitioned Set Join (PSJ) algorithm uses a replicating multilevel partitioning scheme based on a combination of set elements and signatures. It employs three phases: the partitioning phase, joining phase and the verification phase. During the partitioning phase, the first relation is partitioned and the second relation is replicated based on a partitioning function. Each of the partition contain the signatures of set instances rather than set themselves. In the joining phase, each partition is joined with its counterpart using signature based partitioning. Since signatures are approximation of set instances, a verification phase is needed to actually fetch the tuples and verify containment. We present a detailed performance study with a complete implementation in Paradise Object Relational Database System. Our results show that PSJ outperforms consistently previously proposed set join algorithms over a wide range of data sets.
Other Research
Data Warehousing
Fact File - Speeding Up Skipped Sequential Access
Bitmap indices are heavily used in current systems to speedup OLAP queries. By looking up selection predicates or join predicates in the query the corresponding set of bitmaps are retrieved and bit-wise AND and OR operations are employed to speedup the evaluation. However, the major issue to get to the actual records corresponding to the bits that are set in the final bitmap. Such an access pattern is called a skipped sequential access. Fact file is a storage structure for storing relations for speeding up such an access. It consists of a collection of extents and each extent is a set of 8 pages that are accessible contiguously. It uses the fixed record length, unslotted pages and a directory. The directory is tree based and provides fast lookup for records farther than an extent. In order to access a record a check is made for its presence in the current page or current extent or next extent. If these attempts fail then the directory is used. All the extents in the file are linked in list fashion. Depending upon the selectivity of the query, the use of directory is either increased or decreased. The file was completely implemented in SHORE storage manager and our performance results shows that fact file provided an improvement of over 40-50% over a wide range of data sets.
BORG - A Cache Based Middle Tier System for Accelerating OLAP Queries
In this project, we developed a heterogenous middle tier system to speedup ROLAP queries. It uses a multi-dimensional caching scheme by subdividing the multidimensional space into chunks. These chunks are used as the units of caching. The results of these queries spans over a set of chunks. When a query is issued it is split into two parts: one which can be answered from the cache if the contents are available and the other portion that needs to issued to the database. The results of the query issued to the database are put back into the cache. The cache uses a benefit based replacement policy. I developed a complete database internals like framework for executing queries. These queries can be executed in a pipelined fashion by allowing multiple operators to be scheduled simultaneously which are connected by data-pipes called streams. The scheduler breaks the plan into segments based on the presence of non-blocking operators and schedule these segments. The operators can be scheduled in a tree like fashion and execution pipelined the results all the way to the client. The design was extensible so that adding new operators is easy. The system is capable of using multiple data sources simultaneously by providing a multiple source abstraction. The source abstraction can be implemented for each tuple of source and can be loaded dynamically. The entire system was implemented on top of SHORE storage manager. I also jointly developed a plan generator for scheduling post calculations. It identifies the dependencies among various formulas and based on this information either allows a computation to be scheduled in an operator or moved up into the next operator thereby sharing the computation. Also implemented various moving aggregate operators so that many moving aggregates belonging to the same sort order can be computed simultaneously. An initial version of the BORG system is in public domain.
Middleware Systems
Architectural Framework for Middle Tier Servers
Most of the web systems typically fall under the category of middle tier servers which connect to the backend systems. Examples of such servers include Application Server, OLAP Server etc. A close examination of such servers reveal a common base functionality (similar to database internal architecture). A few of them include ability to schedule applications (similar to scheduling operators in OLAP server or in database), ability to pass on the results from one application to another (similar to pipelined execution in the database), ability to add new application or operators on the fly, and ability to connect to multiple data sources. Now the basic question is whether such a repeatable functionality can be abstracted and new systems be implemented on top this framework? This has the major advantage of reducing the development of such servers providing the necessary speed and scalability and reducing drastically the development time. Such an abstraction requires various sub-systems to be implemented. I am currently in the process of writing such a framework. Currently some of the components - abstracted thread package, a fast object communication package are being written that will be followed by application/task abstractions.
Publications
Object Relational Database Systems
 | High Performance Implementation Techniques for Set Valued Attributes - Karthikeyan Ramasamy, Jeffrey F. Naughton and David Maier (to be submitted). |
| Set Containment Joins: The Good, The Bad and The Ugly - Karthikeyan Ramasamy, Jignesh Patel, Jeffrey F. Naughton and Kaushik Raghav. Proceedings of 25th International Conference on Very Large Databases, Cairo, Egypt, 2000. |
| Building a Scalable Geo Spatial DBMS: Technology, Implementation and Evaluation - Jignesh Patel, Jiebing Yu, Navin Kabra, Kristin Tufte, Biswadeep Nag, Josef Burger, Nancy Hall, Karthikeyan Ramasamy, Roger Lueder, Curt Ellman, Jim Kupsch, Shelly Guo, Johan Larson, David DeWitt and Jeffrey F Naughton. Proceedings of the 1997 SIGMOD Conference, Tucson, Arizona, May 1997. |
Data Warehouse
| Caching Multidimensional Queries Using Chunks - Prasad M. Deshpande, Karthikeyan Ramasamy, Amit Shukla and Jeffrey F Naughton. Proceedings of the 1998 SIGMOD Conference, Seattle, Washington, June 1998. |
| Array-Based Evaluation of Multi-Dimensional Queries in Object Relational Database Systems - Yihong Zhao, Karthikeyan Ramasamy, Kristin Tufte and Jeffrey F Naughton International Conference on Data Engineering Databases, Orlando, United States, 1998. |
| Cubing Algorithms, Storage Estimation, and Storage and Processing
Alternatives for OLAP - Prasad M. Deshpande, Jeffrey F. Naughton,
Karthikeyan Ramasamy Amit Shukla, Kristin Tufte and Yihong Zhao Data Engineering Bulletin, IEEE Computer Society, March 1997, Vol 20 No.1 |
| Storage Estimation for Multidimensional Aggregates in the Presence of Hierarchies - Amit Shukla, Prasad M Deshpande, Jeffrey F Naughton and Karthikeyan Ramasamy. Proceedings of 22nd International Conference on Very Large Databases, Mumbai(Bombay), 1996. |
Patents Filed
Projects
VISMAD - A Video Indexing System in Madison
We used the idea of query caching for indexing video. When a new query comes in, we try to evaluate using cached queries. If not possible, we do a sequential scan. Developed the concept, query engine and front browser that displays the video segments that match the query.
Indexing structure for planar point data and an in disk representation for quad tree. Also came up with schemes for compacting a skewed quad tree and bulk loading. Implemented a prototype in SHORE and did a performance study.
Implemented a system using a centralized and space sharing approach for scheduling parallel jobs on COW. Features include the ability to join the scheduling pool, withdrawing from the pool, ability to monitor the running jobs and dynamic switching between the scheduling policies.
A scheduling add-on module for Condor that can take PVM jobs and schedule them on a Cluster of SMPs using space sharing. Various scheduling policies including best-fit, first-fit, priority based, shortest job first and longest job first were implemented.
Implemented the POSIX thread standard on top of the kernel threads in Windows NT and Solaris to ensure code portability. Supports some of the standard thread functionality except signals since NT has no support for thread level signals. Another thread package
Client Server Interaction in Paradise
I wrote the interaction between the Paradise client and server using sockets in order to have interoperability across different platforms. The main issues include the ability to ship large objects and ADTS efficiently. The design is also extensive since as new set of ADT's are added new type of packets need to be supported without having extensible modification to the system. Attempted to write a Java cursor interface for Paradise which exposed the limitations of Java language.
Designed and architected the idea of monitoring the health of the queries being executed in a parallel database system. The physical plan, the segments of the physical plan, the current segment that is executing and the status of each segment are displayed. Internal architecture uses a event driven mechanism and the events are collected and routed to the client in a push fashion.
Ported paradise database server and client to various platforms. The operating systems on the platforms are Solaris (Sparc and Intel), IRIX and AIX on SP2.
This project included the development of a system for studying the various effects of routing and signaling under link failures. This included the development a network specification language, intermediate data structure for representing a network, routing algorithm for finding optimal routes based on traffic demand, hourly variations of traffic, a curses based user interface in order to operate the system.
Professional Projects
A framework to manage database servers, networks and OS running on different machines from a single console. Management involved continuous monitoring for collecting performance data or raise events under exception conditions. Developed the logging mechanism to collect the monitored data and log in ORACLE or SYBASE or a flat file. Client interacts through RPC and includes a mechanism to cache the data at the client side.
Developed a system for automatically synthesizing a microprogram and hardwired controlled units for a given behavioral description and provide a graphical display of the synthesized control unit.
Unix and Remote Filing System for DOS
Developed a resident software to give DOS the power to map a directory or a file system in UNIX residing on the same hard disk in different partitions or on remote machine to a logical drive so that the users can have consistent usage like DOS files.