Generating example data for dataflow programs

ABSTRACT

While developing data-centric programs, users often run (portions of) their programs over real data, to see how they behave and what the output looks like. Doing so makes it easier to formulate, understand and compose programs correctly, compared with examination of program logic alone. For large input data sets, these experimental runs can be time-consuming and inefficient. Unfortunately, sampling the input data does not always work well, because selective operations such as filter and join can lead to empty results over sampled inputs, and unless certain indexes are present there is no way to generate biased samples efficiently. Consequently new methods are needed for generating example input data for data-centric programs.

We focus on an important category of data-centric programs, dataflow programs, which are best illustrated by displaying the series of intermediate data tables that occur between each pair of operations. We introduce and study the problem of generating example intermediate data for dataflow programs, in a manner that illustrates the semantics of the operators while keeping the example data small. We identify two major obstacles that impede naive approaches, namely (1) highly selective operators and (2) noninvertible operators, and offer techniques for dealing with these obstacles. Our techniques perform well on real dataflow programs used at Yahoo! for web analytics.

REFERENCES

• 1: Daniel J. Abadi , Don Carney , Ugur Çetintemel , Mitch Cherniack , Christian Convey , Sangdon Lee , Michael Stonebraker , Nesime Tatbul , Stan Zdonik, Aurora: a new model and architecture for data stream management, The VLDB Journal — The International Journal on Very Large Data Bases, v.12 n.2, p.120-139, August 2003 [doi>10.1007/s00778-003-0095-z]
• 2: Remzi H. Arpaci-Dusseau, Run-time adaptation in river, ACM Transactions on Computer Systems (TOCS), v.21 n.1, p.36-86, February 2003 [doi>10.1145/592637.592639]
• 3: ]]C. Binnig, D. Kossmann, and E. Lo. Reverse query processing. In Proc. ICDE, 2007.
• 4: Carsten Binnig , Donald Kossmann , Eric Lo , M. Tamer Özsu, QAGen: generating query-aware test databases, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247520]
• 5: Surajit Chaudhuri , Rajeev Motwani , Vivek Narasayya, On random sampling over joins, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.263-274, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 6: ]]V. Chvátal. A greedy heuristic for the set-covering problem. Mathematics of Operations Research, 4, 1979.
• 7: Jeffrey Dean , Sanjay Ghemawat, MapReduce: simplified data processing on large clusters, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.10-10, December 06-08, 2004, San Francisco, CA
• 8: Prabhakar Goel , Barry C. Rosales, PODEM-X: An automatic test generation system for VLSI logic structures, Proceedings of the 18th Design Automation Conference, p.260-268, June 29-July 01, 1981, Nashville, Tennessee, United States
• 9: Michael Isard , Mihai Budiu , Yuan Yu , Andrew Birrell , Dennis Fetterly, Dryad: distributed data-parallel programs from sequential building blocks, Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems 2007, March 21-23, 2007, Lisbon, Portugal
• 10: ]]D. S. Johnson. Approximation algorithms for combinatorial problems. Computer and System Sciences, 9, 1974.
• 11: B. Korel, Automated Software Test Data Generation, IEEE Transactions on Software Engineering, v.16 n.8, p.870-879, August 1990 [doi>10.1109/32.57624]
• 12: Heikki Mannila , Kari Jouko Raiha, Test data for relational queries, Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.217-223, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.15415]
• 13: Christopher Olston , Benjamin Reed , Utkarsh Srivastava , Ravi Kumar , Andrew Tomkins, Pig latin: a not-so-foreign language for data processing, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376726]
• 14: Peter Revesz, Introduction to constraint databases, Springer-Verlag New York, Inc., New York, NY, 2002
• 15: Michael Stonebraker , Jolly Chen , Nobuko Nathan , Caroline Paxson , Jiang Wu, Tioga: Providing Data Management Support for Scientific Visualization Applications, Proceedings of the 19th International Conference on Very Large Data Bases, p.25-38, August 24-27, 1993
• 16: Allison Woodruff , Michael Stonebraker, Supporting Fine-grained Data Lineage in a Database Visualization Environment, Proceedings of the Thirteenth International Conference on Data Engineering, p.91-102, April 07-11, 1997

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.m Miscellaneous

General Terms:
Algorithms, Experimentation

Keywords:
dataflow programming, example data