15.10 - Query Processing References - Teradata Database

Teradata Database SQL Request and Transaction Processing

prodname
Teradata Database
vrm_release
15.10
category
Programming Reference
User Guide
featnum
B035-1142-151K

Scott Aaronson, “Is P Versus NP Formally Independent?” Bulletin of the European Association for Theoretical Computer Science, 81:109-136, 2003.

Scott Aaronson, “NP-Complete Problems and Physical Reality,” ACM SIGACT News, 36(1):30-52, 2005.

Ashraf Aboulnaga and Surajit Chaudhuri, “Self-Tuning Histograms: Building Histograms Without Looking at Data,” Proceedings of SIGMOD 1999, 181-192, 1999.

Swarup Acharya, Phillip B. Gibbons, Viswanath Poosala, and Sridhar Ramaswamy, “Join Synopses for Approximate Query Answering,” Proceedings of SIGMOD 1999, 275-286, 1999.

Rafiul Ahad, K.V. Bapa Rao, and Dennis McLeod, “On Estimating the Cardinality of the Projection of a Database Relation,” ACM Transactions on Databases, 14(1):28-40, 1989.

Gennady Antoshenkov, “Dynamic Query Optimization in Rdb/VMS,” Proceedings of 9th IEEE International Conference on Data Engineering, 538-547, 1993.

Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Aproach, New York: Cambridge University Press, 2009.

M.M. Astrahan, M. Schkolnick, and W. Kim, “Performance of the System R Access Path Selection Mechanism,” Information Processing 80, IFIP, North-Holland Publishing Co., 1980, pp. 487-491.

Brian Babcock, Surajit Chaudhuri, and Gautam Das, “Dynamic Sample Selection for Approximate Query Processing,” Proceedings of SIGMOD 2003, 539-550, 2003.

Shivnath Babu, Pedro Bizarro, and David DeWitt, “Proactive re‑optimization with Rio,” Proceedings of SIGMOD 2005, 936-938, 2005.

Armin Biere, Marijn Heule, Hans van Maaren, and Toby Walsh (eds.), Handbook of Satisfiability, Amsterdam: IOS Press, 2009.

M.W. Blasgen and K.P. Eswaran, “Storage and Access in Relational Data Bases,” IBM Systems Journal, 16(4):363-377, 1977.

Béla Bollobás, Modern Graph Theory, Berlin: Springer-Verlag, 1998.

J.A. Bondy and U.S.R. Murty, Graph Theory With Applications, Amsterdam: North‑Holland, 1976.

Kjell Bratbergsengen, “Hashing Methods and Relational Algebra Operations,” Proceedings of 10th International Conference on Very Large Data Bases, 323-333, 1984.

Stephen Brobst and Dominic Sagar, “The New, Fully Loaded, Optimizer,” DB2 Magazine, 4(3), 1999.

Stephen Brobst and Bob Vecchione, “Starburst Grows Bright,” Database Programming and Design, 11(2), 1998.

Sharma Chakravarthy, John Grant, and Jack Minker, “Foundations of Semantic Query Optimization” in Jack Minker (ed.) Foundations of Deductive Databases and Logic Programming, San Francisco, CA: Morgan Kaufmann Publishers, Inc., 1988.

Sharma Chakravarthy, John Grant, and Jack Minker, “Logic based approach to semantic query optimization,” ACM Transactions on Database Systems, 15(2):162-207, 1990.

Don Chamberlin and Paul McJones, Bibliography of the System R Project, 1995 and 2000, http://www.mcjones.org/System_R/bib.html

Philip Y. Chang, “Parallel Processing and Data Driven Implementation of a Relational Data Base System,” Proceedings of 1976 ACM National Conference, 314-318, 1976.

Gary Chartrand, Introductory Graph Theory, Mineola, NY: Dover Publishing Co., 1984.
Republication of Boston, MA: Prindle, Weber, and Schmidt, Inc., Graphs as Mathematical Models, 1977.

Surajit Chaudhuri, "An Overview of Query Optimization in Relational Systems," Proceedings of PODS 1998, 34-43, 1998.

Surajit Chaudhuri and Kyuseok Shim, “Including Group-By in Query Optimization,” Proceedings of 20th VLDB Conference, 354-366, 1994.

Surajit Chaudhuri, Gautam Das, and Vivek Narasayya, “A Robust Optimization‑Based Approach for Approximate Answering of Aggregate Queries,” Proceedings of SIGMOD 2001, 295-306, 2001.

Surajit Chaudhuri, Gautam Das, and Utkarsh Srivastava, “Effective Use of Block‑Level Sampling in Statistics Estimation,” Proceedings of SIGMOD 2004, 287-298, 2004.

Surajit Chaudhuri, Rajeev Motwani, and Vivek Narasayya, “On Random Sampling Over Joins,” Proceedings of SIGMOD 1999, 263-274, 1999.

Richard L. Cole and Goetz Graefe, “Optimization of Dynamic Query Evaluation Plans,” Proceedings of SIGMOD 1994, 150-160, 1994.

Richard L. Cole, Mark J. Anderson, and Robert J. Bestgen, “Query Processing in the IBM Application System 400,” IEEE Data Engineering Bulletin, 16(4):18-27, 1993.

Stephen Cook, “The Complexity of Theorem‑Proving Procedures,” Proceedings of 3rd ACM Symposium on the Theory of Computing 1971, pp. 151-158, 1971.

Stephen A. Cook and David G. Mitchell, “Finding Hard Instances of the Satisfiability Problem: A Survey,” in Dingzhu Du, Jun Gu, and Panos M. Pardalos (eds.), Satisfiability Problem: Theory and Applications-DIMACS Series in Discrete Mathematics and theoretical Computer Science, Volume 35, Providence, RI: American Mathematical Society, 1997, pp. 1‑17.

C.J. Date, An Introduction to Database Systems (8th ed.), Reading, MA: Addison‑Wesley, 2004.

C.J. Date, Logic and Databases: The Roots of Relational Theory, Victoria, BC, Canada: Trafford Publishing, 2007.

Thomas Day, “ARX (Arnie Rhom’s eXtractor),” http://www.mcjones.org/System_R/arx.html, no date.

David J. DeWitt, Randy H Katz, Frank Olken, Leonard D Shapiro, Michael R. Stonebraker, and David Wood, “Implementation Techniques for Main Memory Database Systems,” Proceedings of SIGMOD 1984, 1-8, 1984.

Reinhard Diestel, Graph Theory (2nd ed.), Berlin: Springer-Verlag, 2000.

Shimon Even, Graph Algorithms, Rockville, MD: Computer Science Press, 1979.

Stéphane Faroult and Pascal L’Hermite, Refactoring SQL Applications. Sebastapol, CA: O’Reilly Media, Inc., 2008.

Stéphane Faroult and Peter Robson, The Art of SQL. Sebastapol, CA: O’Reilly Media, Inc., 2006.

Lance Fortnow, “The Status of the P Versus NP Problem,” Communications of the ACM, 52(9):78-86, 2009.

Lance Fortnow and Steve Homer, “A Short History of Computational Complexity,” Bulletin of the European Association for Theoretical Computer Science, 80:95-133, 2003.

Oris D. Friesen and James A. Weeldreyer. "Multics Integrated Data Store: An Implementation of a Network Data Base Manager Utilizing Relational Data Base Methodology,” Proceedings of 11th Hawaii International Conference on System Sciences, Volume 1 (January 1978), pp. 67-84.

Oris D. Friesen, N.S. Davids, and Rickie E. Brinegar. "MRDS/LINUS: System Evaluation" in J. W. Schmidt and M. L. Brodie, editors. Relational Database Systems: Analysis and Comparison. Berlin, Springer-Verlag (1983), pp. 182-220.

Sumit Ganguly, Phillip B. Gibbons, Yossi Matias, and Avi Silberschatz, “Bifocal Sampling for Skew‑Resistant Join Size Estimation,” Proceedings of SIGMOD 1996, 271-281, 1996.

Michael R. Garey and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP‑Completeness, San Francisco: W.H. Freeman, 1979.

Peter Gassner, Guy Lohman, and K. Bernhard Schiefer, “Query Optimization in the IBM DB2 Family,” IEEE Data Engineering Bulletin, 16(4):4-17, 1993.

Ahmad Ghazal and Ramesh Bhashyam, “Dynamic Constraints Derivation and Maintenance in the Teradata RDBMS,” Database and Expert Systems Applications 2001, 390-399, 2001.

Ahmad Ghazal, Block Optimization In Teradata, Teradata Database Orange Book 541-0003787A02, 2002.

Ahmad Ghazal, Ramesh Bhashyam, and Alain Crolotte, “Block Optimization in the Teradata RDBMS,” Database and Expert Systems Applications 2003, 782-791, 2003.

Ahmad Ghazal, Alain Crolotte, and Ramesh Bhashyam, “Outer Join Elimination in the Teradata RDBMS, Database and Expert Systems Applications 2004, 739-740, 2004.

Ahmad Ghazal, Dawit Yimam Seid, Alain Crolotte, and Bill McKenna, “Exploiting Interactions Among Query Rewrite Rules in the Teradata DBMS,” Database and Expert Systems Applications 2008, 596-609, 2008.

Ahmad Ghazal, Dawit Seid, Ramesh Bhashyam, Alain Crolotte, Manjula Koppuravuri, and Vinod G., “Dynamic Plan Generation for Parameterized Queries,” Proceedings of SIGMOD 2009, 909‑915, 2009.

Philip B. Gibbons and Yossi Matias, "Synopsis Data Structures for Massive Data Sets," in: External Memory Systems: DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society, 1998a.

Phillip B. Gibbons and Yossi Matias, “New Sampling‑Based Summary Statistics for Improving Approiximate Query Answers,” Proceedings of SIGMOD 1998, 331-342, 1998b.

Phillip B. Gibbons, Yossi Matias, and Viswanath Poosala, “Fast Incremental Maintenance of Approximate Histograms,” ACM Transactions on Database Systems, 27(3):261-298, 2002.

Goetz Graefe, "Query Evaluation Techniques for Large Databases," ACM Computing Surveys, 25(2):73-170, 1993.

Ashish Gupta and Inderpal Singh Mumick, “Maintenance of Materialized Views: Problems, Techniques, and Applications,” IEEE Data Engineering Bulletin, 18(2):3-18, 1995.

Ashish Gupta and Inderpal Singh Mumick (eds.), Materialized Views: Techniques, Implementations, and Applications, Cambridge, MA: MIT Press, 1999.

Lex de Haan and Toon Koppelaars, Applied Mathematics for Database Professionals, Berkeley, CA: Apress, 2007.

Peter J. Haas and Christian König, “A Bi‑Level Bernoulli Scheme for Database Sampling,” Proceedings of SIGMOD 2004, 275-286, 2004.

Peter J. Haas, Jeffrey F. Naughton, and Arun N. Swami, “On the Relative Cost of Sampling for Join Selectivity Estimation,” Proceedings of PODS 1994, 14-24, 1994.

P.A.V. Hall, “Optimization of Single Expressions in a Relational Data Base System,” IBM Journal of Research and Development, 20 (3):244-257, 1976.

Waqar Hasan, Optimization of SQL Queries for Parallel Machines, Ph.D. dissertation, Department of Computer Science, Stanford University, 1996.

Waqar Hasan, Optimization of SQL Queries for Parallel Machines, Berlin: Springer‑Verlag, 1996.

Stephen Henley, “G‑EXEC Geological Data Handling System,” http://www.mcjones.org/System_R/g-exec.html, no date.

Toshihide Ibaraki and Tiko Kameda, “On the Optimal Nesting Order for Computing N‑Relational Joins,” ACM Transactions on Database Systems, 9(3):482-502, 1984.

Neil Immerman, Descriptive Complexity, Berlin: Springer‑Verlag, 1998.

Neil Immerman, “Descriptive and Computational Complexity,” Proceedings of Symposia in Applied Mathematics, 38:75-91, 1989.

Neil Immerman, “Descriptive Complexity: a Logician’s Approach to Computation,” Notices of the American Mathematical Society, 42(10):1127-1133, 1995.

Yannis E. Ioannidis, “The History of Histograms (abridged),” Proceedings of 29th VLDB Conference, 2003.

Yannis E. Ioannidis and Stavros Christodoulakis, “On the Propagation of Errors in the Size of Join Results,” Proceedings of SIGMOD 1991, 268-277, 1991.

Yannis E. Ioannidis and Stavros Christodoulakis, "Optimal Histograms for Limiting Worst-Case Error Propagation in the Size of Join Results," ACM Transactions on Database Systems, 18(4):709-448, 1993.

Yannis E. Ioannidis and Younkyung Cha Kang, “Left-deep vs. bushy trees: an analysis of strategy spaces and its implications for query optimization,” Proceedings of SIGMOD 1991, 168 - 177, 1991.

Yannis Ioannidis and Viswanath Poosala, “Histogram‑Based Solutions to Diverse Database Estimation Problems,” IEEE Data Engineering Bulletin, 18(3):10-18, 1995.

Matthias Jarke and Jürgen Koch, "Query Optimization in Database Systems," ACM Computing Surveys, 16(2):111-152, 1984.

K.G. Jeffery and E.M. Gill, “The Design Philosophy of the G‑EXEC System,” Computers and Geosciences, 2:345-346, 1976.

K.G. Jeffery and E.M. Gill, “The Geological Computer,” Computers and Geosciences, 2:347‑349, 1976.

Christopher Jermaine, “Robust Estimation With Sampling and Approximate Pre‑Aggregation,” Proceedings of 29th International Conference on Very Large Data Bases, 886‑897, 2003.

Christopher Jermaine, Abhijit Pol, and Subramanian Arumugam, “Online Maintenance of Very Large Random Samples,” Proceedings of SIGMOD 2004, 299-310, 2004.

Navin Kabra and David J. DeWitt, “Efficient Mid‑Query Re‑Optimization of Sub‑Optimal Query Execution Plans,” Proceedings of SIGMOD 1998, 106-117, 1998.

Ibrahim Kamel and Christos Faloutsos, “On Packing R‑Trees,” Proceedings of 2nd International Conference on Information and Knowledge Management (CIKM) 1993, 490-499, 1993.

Ibrahim Kamel and Christos Faloutsos, “Hilbert R‑tree: An Improved R‑tree Using Fractals,” Proceedings of 20th VLDB Conference 1994, 500-509, 1994

Masaru Kitsuregawa, Hidehiko Tanaka, and Tohru Moto-Oka, “Application of Hash to Data Base Machine and Its Architecture,” New Generation Computing, 1(1):63-74, 1983.

Donald Knuth, The Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd. ed.), Reading, MA: Addison-Wesley, 1997.

Robert Philip Kooi, The Optimization of Queries in Relational Databases, Ph.D. dissertation, Case Western Reserve University, 1980.

Rama Krishna Korlapati, Optimizer Cardinality Estimation Improvements, Teradata Database Orange Book 541-0006588A02, 2007.

Rama Krishna Korlapati, Statistics Extrapolations, Teradata Database Orange Book
541-0008668A02, 2010.

Rama Krishna Korlapati, Teradata 14.0 Statistics Enhancements, Teradata Database Orange Book 541-0009064A02, 2011.

Edmund Landau, Foundations of Analysis (3rd ed.), London: Chelsea Publishing Co., 2001.
Translation by F. Steinhardt of the third German edition Grundlagen der Analysis, Berlin: Heldermann Verlag, 1970.

Chiang Lee and Chia-Jung Chen, “Query Optimization in Multidatabase Systems Considering Schema Conflicts,” IEEE Transactions on Knowledge and Data Engineering, 9(6):941-955, 1997.

Leonid Levin, “Universal Sorting Problems,” Problems of Information Transmission, 9:265‑266, 1973.
An English translation of the original paper from the Soviet journal Problemy Peredaci Informacii.

Alon Y. Levy and Yehoshua Sagiv, “Semantic Optimization in Datalog Programs,” Proceedings of Principles of Database Systems 95: 163-173, 1995.

Alon Y. Levy, Inderpal Singh Mumick, and Yehoshua Sagiv, “Query Optimization by Predicate Move‑Around,” Proceedings of 20th VLDB Conference 1994, 96-107, 1994.

Richard J. Lipton, Jeffrey F. Naughton, and Donovan A. Schneider, “Practical Selectivity Estimation Through Adaptive Sampling,” Proceedings of SIGMOD 1990, 1-11, 1990.

Witold Litwin and Abdelaziz Abdellatif, “Multidatabase Interoperability,” IEEE Computer 19(12):10-18, 1986.

Bill McKenna and Ahmad Ghazal, Query Rewrite in Teradata, Teradata Database Orange Book 541‑0006383A02, 2007.

Benjamin J. McMahan, Guoqiang Pan, Patrick Portere, and Moshe Y. Vardi, “Projection Pushing Revisited,” in: Elisa Bertino, Stavros Christodoulakis, Dimitris Plexousakis, Vassilis Christophides, Manolis Koubarakis, Klemens Böhm, and Elena Ferrari (eds.), Advances in Database Technology - EDBT 2004: 9th International Conference on Extending Database Technology, Heraklion, Crete, Greece, March 14-18, 2004, Proceedings, Berlin: Springer-Verlag, 2004.

David Maier, The Theory of Relational Databases, Rockville, MD: Computer Science Press, 1983.

Sharad Malik and Lintao Zhang, “Boolean Satisfiability: From Theoretical Hardness to Practical Success,” Communications of the ACM, 52(8):76-82, 2009.

K Manjula, Vinod G, and Anoop K. Saxena, Parameterized Request Cache Enhancements , Teradata Database Orange Book 541-0006539A02, 2007.

Michael V. Mannino, Paicheng Chu, and Thomas Sager, "Statistical Profile Estimation in Database Systems," ACM Computing Surveys, 20(3):191-221, 1988.

V. Markl, G.M. Lohman, and V. Raman, “LEO: An Autonomic Query Optimizer for DB2,” IBM Systems Journal, 42(1):98-106, 2003.

Volker Markl, Vijayshankar Raman, David Simmen, Guy Lohman, Hamid Pirahesh, and Miso Cilimdzic, “Robust Query Processing Through Progressive Optimization,” Proceedings of ACM SIGMOD 2004:659-670, 2004.

V. Markl, P.J. Haas, M. Kutsch, N. Megiddo, U. Srivastava, and T.M.Tran, “Consistent Selectivity Estimation Via Maximum Entropy,” VLDB Journal, 16:55-76, 2007.

Jack Minker (ed.) Foundations of Deductive Databases and Logic Programming, San Francisco, CA: Morgan Kaufmann Publishers, Inc., 1988.

Priti Mishra and Margaret H. Eich, “Join Processing in Relational Databases,” ACM Computing Surveys, 24(1):63-113, 1992.

Kiyoshi Ono and Guy M. Lohman, “Measuring the Complexity of Join Enumeration in Query Optimization,” Proceedings of 16th International Conference on Very Large Data Bases, 314-325, 1990.

Gregory Piatetsky-Shapiro and Charles Connell, “Accurate Estimation of the Number of Tuples Satisfying a Condition,” Proceedings of SIGMOD 1984, 256-276, 1984.

Viswanath Poosala and Yannis E. Ioannidis, “Selectivity Estimation Without the Attribute Value Independence Assumption,” Proceedings of 23rd International Conference on Very Large Data Bases, 486-495, 1997.

Viswanath Poosala, Peter J. Haas, Yannis E. Ioannidis, and Eugene J. Shekita, "Improved Histograms for Selectivity Estimation of Range Predicates," Proceedings of SIGMOD 1996, 294-305, 1996.

Tony Rollins and Ranjan Priyadarshi, OCES Type 2 Costing, Teradata Database Orange Book 541-0006384, 2007.

P.G. Selinger, M.M. Astrahan, D.D. Chamberlin, R.A. Lorie, and T.G. Price, "Access Path Selection in a Relational Database Management System," Proceedings of SIGMOD 1979, 23-34, 1979.

Praveen Seshadri, Joseph M. Hellerstein, Hamid Pirahesh, T.Y. Cliff Leung, Raghu Ramakrishnan, Divesh Srivastava, Peter J. Stuckey, and S. Sudarshan, “Cost-Based Optimization for Magic: Algebra and Implementation,” Proceedings of SIGMOD 1996, 435‑446, 1996.

Michael Sipser, Introduction to the Theory of Computation (2nd ed.), Boston, MA: Thomson Course Technology, 2005.

John Miles Smith and Philip Yen-Tang Chang, “Optimizing the Performance of a Relational Algebra Database Interface,” Communications of the ACM, 18(10):568-579, 1975.

Michael Stonebraker, “Retrospection on a Database System,” ACM Transactions on Database Systems, 5(2):225-240, 1980.

Michael Stonebraker, Eugene Wong, and Peter Kreps, “The Design and Implementation of INGRES,” ACM Transactions on Database Systems, 1(3):189-222, 1976.

Wei Tang and Ahmad Ghazal, Partial Group By Optimization, Teradata Database Orange Book 541-0005529A02, 2005.

S.J.P. Todd, “The Peterlee Relational Test Vehicle—A System Overview,” IBM Systems Journal, 15(4):285-308, 1976.

Richard J. Trudeau, Introduction to Graph Theory, Mineola, NY: Dover Publishing Co., 1994.
Corrected and enlarged edition of Kent, OH: The Kent State University Press, Dots and Lines, 1976.

Jeffrey D. Ullman, Principles of Database Systems (2nd ed.), Rockville, MD: Computer Science Press, 1982.

Jeffrey D. Ullman, Principles of Database and Knowledge‑Base Systems, Volume 1, Rockville, MD: Computer Science Press, 1989.

Jeffrey D. Ullman, Principles of Database and Knowledge‑Base Systems, Volume 2, Rockville, MD: Computer Science Press, 1989.

Tom Van Vleck, “Multics Relational Data Store (MRDS),” http://www.mcjones.org/System_R/mrds.html, no date.

James A. Weeldreyer and Oris D. Friesen. "Multics Relational Data Store: An Implementation of A Relational Data Base Manager" Proceedings of 11th Hawaii International Conference on Systems Sciences, Volume 1, (January 1978), pp. 52-66.

Eugene Wong and Karel Youssefi, “Decomposition—A Strategy for Query Processing,” ACM Transactions on Database Systems, 1(3):223-241, 1976.

Karel Youssefi and Eugene Wong, “Query Processing In a Relational Database Management System,” Proceedings of 5th International Conference on Very Large Data Bases, 409-417, 1979.

Clement T. Yu and Weiyi Meng, Principles of Database Query Processing for Advanced Applications, San Francisco, CA: Morgan Kaufmann Publishers, Inc., 1998.

Hansjörg Zeller and Jim Gray, “An Adaptive Hash Join Algorithm for Multiuser Environments,” Proceedings of 16th VLDB Conference, 186-197, 1990.