Inside Microsoft® SQL Server® 2008: T-SQL Querying (Developer Reference)

Tackle the toughest set-based querying and query tuning problemsguided by an author team with in-depth, inside knowledge of T-SQL. Deepen your understanding of architecture and internalsand gain practical approaches and advanced techniques to optimize your codes performance. Discover how to: - Move from procedural programming to the language of sets and logic - Optimize query tuning with a top-down methodology - Assess algorithmic complexity to predict performance - Compare data-aggregation techniques, including new grouping sets - Manage data modificationinsert, delete, update, mergefor performance - Write more efficient queries against partitioned tables - Work with graphs, trees, hierarchies, and recursive queries - PlusUse pure-logic puzzles to sharpen your problem-solving skills Cover......Page 1 Copyright page......Page 2 Dedication......Page 4 Table of Contents......Page 6 Foreword......Page 14 Acknowledgments......Page 16 Introduction......Page 20 Companion Content and Sample Database......Page 23 Find Additional Content Online......Page 24 Questions and Comments......Page 25 Chapter 1: Logical Query Processing......Page 26 Logical Query Processing Phases......Page 27 Logical Query Processing Phases in Brief......Page 28 Sample Query Based on Customers/Orders Scenario......Page 30 Step 1: The FROM Phase......Page 32 Step 2: The WHERE Phase......Page 36 Step 3: The GROUP BY Phase......Page 37 Step 4: The HAVING Phase......Page 38 Step 5: The SELECT Phase......Page 39 Step 6: The Presentation ORDER BY Phase......Page 41 Table Operators......Page 45 OVER Clause......Page 54 Set Operators......Page 56 Conclusion......Page 58 An Example of English-to-Mathematics Translation......Page 60 Well-Definedness......Page 62 Mathematical Conventions......Page 64 Context......Page 66 Instructions and Algorithms......Page 68 Set Theory......Page 69 Notation for Sets......Page 70 Domains of Discourse......Page 71 Faithfulness......Page 74 Russell’s Paradox......Page 77 Ordered Pairs, Tuples, and Cartesian Products......Page 78 The Empty Set(s)......Page 79 The Characteristic Function of a Set......Page 80 Cardinality......Page 81 Order......Page 82 Set Operators......Page 86 Set Partitions......Page 88 Generalizations of Set Theory......Page 89 Logic-Like Features of Programming Languages......Page 90 Propositions and Predicates......Page 91 And, Or, and Not......Page 93 Logical Implication......Page 95 Quantification......Page 97 Alternatives and Generalizations......Page 98 The Refiexive, Symmetric, and Transitive Properties......Page 100 A Practical Application......Page 102 Conclusion......Page 106 Introduction to the Relational Model......Page 108 Relations, Tuples and Types......Page 109 The Relational Model: A Quick Summary......Page 114 Basic Operators......Page 115 Relational Algebra......Page 116 Relational Calculus......Page 127 T-SQL Support......Page 128 Data Integrity......Page 129 Declarative Constraints......Page 130 Other Means of Enforcing Integrity......Page 134 Normalization and Other Design Topics......Page 136 Normal Forms Dealing with Functional Dependencies......Page 137 Higher Normal Forms......Page 144 Denormalization......Page 147 Generalization and Specialization......Page 149 Conclusion......Page 151 Sample Data for This Chapter......Page 152 Tuning Methodology......Page 156 Analyze Waits at the Instance Level......Page 159 Correlate Waits with Queues......Page 168 Drill Down to the Database/File Level......Page 170 Drill Down to the Process Level......Page 173 Tune Indexes and Queries......Page 194 Clearing the Cache......Page 196 STATISTICS IO......Page 197 Measuring the Run Time of Queries......Page 198 Analyzing Execution Plans......Page 199 Hints......Page 210 Traces/Profiler......Page 211 Index Tuning......Page 212 Table and Index Structures......Page 213 Index Access Methods......Page 222 Analysis of Indexing Strategies......Page 269 Fragmentation......Page 281 Partitioning......Page 283 Data Preparation......Page 284 TABLESAMPLE......Page 290 An Examination of Set-Based vs. Iterative/Procedural Approaches and a Tuning Exercise......Page 293 Conclusion......Page 301 Chapter 5: Algorithms and Complexity......Page 302 Do You Have a Quarter?......Page 303 How Algorithms Scale......Page 304 An Algorithm with Linear Complexity......Page 305 Exponential and Superexponential Complexity......Page 306 Sublinear Complexity......Page 307 Technical Definitions of Complexity......Page 308 Comparing Complexities......Page 310 Classic Algorithms and Algorithmic Strategies......Page 311 Algorithms for Sorting......Page 312 String Searching......Page 314 A Practical Application......Page 315 The Algorithmic Complexity of LISLP......Page 316 Solving the Longest Increasing Subsequence Length Problem in T-SQL......Page 317 Conclusion......Page 320 Chapter 6: Subqueries, Table Expressions, and Ranking Functions......Page 322 Self-Contained Subqueries......Page 323 Correlated Subqueries......Page 327 Misbehaving Subqueries......Page 339 Uncommon Predicates......Page 341 Derived Tables......Page 343 Common Table Expressions......Page 346 Analytical Ranking Functions......Page 355 Row Number......Page 357 Rank and Dense Rank......Page 377 Tile Number......Page 379 Auxiliary Table of Numbers......Page 384 Missing and Existing Ranges (Also Known as Gapsand Islands)......Page 388 Missing Ranges (Gaps)......Page 391 Existing Ranges (Islands)......Page 400 Conclusion......Page 412 Old Style vs. New Style......Page 414 Fundamental Join Types......Page 415 Further Examples of Joins......Page 427 Sliding Total of Previous Year......Page 442 Join Algorithms......Page 446 Separating Elements......Page 454 Set Operations......Page 460 UNION......Page 461 EXCEPT......Page 462 INTERSECT......Page 464 Precedence of Set Operations......Page 465 Circumventing Unsupported Logical Phases......Page 466 Conclusion......Page 468 OVER Clause......Page 470 Tiebreakers......Page 473 Running Aggregations......Page 476 Cumulative Aggregations......Page 478 Sliding Aggregations......Page 482 Year-to-Date (YTD)......Page 484 Pivoting Attributes......Page 485 Relational Division......Page 490 Aggregating Data......Page 491 Unpivoting......Page 495 Custom Aggregations......Page 498 Custom Aggregations Using Pivoting......Page 499 User Defined Aggregates (UDA)......Page 501 Specialized Solutions......Page 512 Histograms......Page 524 Grouping Factor......Page 528 Grouping Sets......Page 531 Sample Data......Page 532 The GROUPING SETS Subclause......Page 533 The CUBE Subclause......Page 536 The ROLLUP Subclause......Page 537 Grouping Sets Algebra......Page 539 The GROUPING_ID Function......Page 543 Materialize Grouping Sets......Page 546 Sorting......Page 549 Conclusion......Page 550 SELECT TOP......Page 552 TOP and Determinism......Page 554 TOP and Input Expressions......Page 555 TOP and Modifications......Page 556 TOP on Steroids......Page 559 APPLY......Page 560 TOP n for Each Group......Page 562 Matching Current and Previous Occurrences......Page 568 Paging......Page 572 Random Rows......Page 577 Median......Page 579 Logical Transformations......Page 581 Conclusion......Page 584 Enhanced VALUES Clause......Page 586 SELECT INTO......Page 588 BULK Rowset Provider......Page 590 Minimally Logged Operations......Page 592 INSERT EXEC......Page 615 Sequence Mechanisms......Page 620 GUIDs......Page 625 Removing Rows with Duplicate Data......Page 626 DELETE Using Joins......Page 628 UPDATE Using Joins......Page 631 Updating Large Value Types......Page 635 SELECT and UPDATE Statement Assignments......Page 636 Merging Data......Page 641 MERGE Fundamentals......Page 642 Adding a Predicate......Page 646 Multiple WHEN Clauses......Page 648 WHEN NOT MATCHED BY SOURCE......Page 649 MERGE Values......Page 651 MERGE and Triggers......Page 652 OUTPUT Clause......Page 653 INSERT with OUTPUT......Page 654 DELETE with OUTPUT......Page 655 UPDATE with OUTPUT......Page 657 MERGE with OUTPUT......Page 659 Composable DML......Page 661 Conclusion......Page 663 Partitioned Views......Page 664 Partitioned Tables......Page 665 Conclusion......Page 682 Graphs......Page 684 Trees......Page 685 Employee Organizational Chart......Page 686 Bill of Materials (BOM)......Page 688 Road System......Page 691 Iteration/Recursion......Page 695 Subordinates......Page 696 Ancestors......Page 706 Subgraph/Subtree with Path Enumeration......Page 710 Sorting......Page 713 Cycles......Page 716 Materialized Path......Page 719 Maintaining Data......Page 720 Querying......Page 726 Materialized Path with the HIERARCHYID Data Type......Page 731 Maintaining Data......Page 733 Querying......Page 740 Further Aspects of Working with HIERARCHYID......Page 744 Nested Sets......Page 755 Assigning Left and Right Values......Page 756 Querying......Page 762 Directed Acyclic Graph......Page 765 Conclusion......Page 780 Puzzle 2: Round Manhole Covers......Page 782 Puzzle 6: Crossing the Tunnel......Page 783 Puzzle 9: Naming an Heir......Page 784 Puzzle 14: Probabilities in China......Page 785 Puzzle 16: Crazy Sequence......Page 786 Puzzle 19: Counterfeit Coins......Page 787 Puzzle 23: Shipping Algebra......Page 788 Puzzle 1: Remainders......Page 789 Puzzle 5: Arranging Soldiers in a Row......Page 790 Puzzle 7: Escaping a Cave......Page 791 Puzzle 9: Naming an Heir......Page 792 Puzzle 12: Catching a Train......Page 793 Puzzle 14: Probabilities in China......Page 794 Puzzle 15: Two Mathematicians......Page 795 Puzzle 17: Minimum Number of Weights......Page 796 Puzzle 18: Counting Triangles......Page 797 Puzzle 20: Too Clever by Half......Page 798 Puzzle 21: A Cat, a String, and the Earth......Page 799 Puzzle 22: Josephus Problem......Page 800 Puzzle 24: Equilateral Triangles Puzzle......Page 801 Conclusion......Page 803 A......Page 804 B,C......Page 805 D......Page 807 E......Page 808 F,G,H......Page 809 I......Page 810 J,K......Page 811 L,M......Page 812 N......Page 813 O......Page 814 P......Page 815 Q......Page 816 R......Page 817 S......Page 818 T......Page 821 U,V,W......Page 822 X,Y......Page 823 Dejan Sarka......Page 824 Steve Kass......Page 825 Cover 1 Copyright page 2 Dedication 4 Table of Contents 6 Foreword 14 Acknowledgments 16 Introduction 20 Hardware and Software Requirements 23 Companion Content and Sample Database 23 Find Additional Content Online 24 Support for These Books 25 Questions and Comments 25 Chapter 1: Logical Query Processing 26 Logical Query Processing Phases 27 Logical Query Processing Phases in Brief 28 Sample Query Based on Customers/Orders Scenario 30 Logical Query Processing Phase Details 32 Step 1: The FROM Phase 32 Step 2: The WHERE Phase 36 Step 3: The GROUP BY Phase 37 Step 4: The HAVING Phase 38 Step 5: The SELECT Phase 39 Step 6: The Presentation ORDER BY Phase 41 Further Aspects of Logical Query Processing 45 Table Operators 45 OVER Clause 54 Set Operators 56 Conclusion 58 Chapter 2: Set Theory and Predicate Logic 60 An Example of English-to-Mathematics Translation 60 Well-Definedness 62 Equality, Identity, and Sameness 64 Mathematical Conventions 64 Numbers 66 Context 66 Functions, Parameters, and Variables 68 Instructions and Algorithms 68 Set Theory 69 Notation for Sets 70 Well-Definedness of Sets 71 Domains of Discourse 71 Faithfulness 74 Russell’s Paradox 77 Ordered Pairs, Tuples, and Cartesian Products 78 The Empty Set(s) 79 The Characteristic Function of a Set 80 Cardinality 81 Order 82 Set Operators 86 Set Partitions 88 Generalizations of Set Theory 89 Predicate Logic 90 Logic-Like Features of Programming Languages 90 Propositions and Predicates 91 The Law of Excluded Middle 93 And, Or, and Not 93 Logical Equivalence 95 Logical Implication 95 Quantification 97 Alternatives and Generalizations 98 Relations 100 The Refiexive, Symmetric, and Transitive Properties 100 A Practical Application 102 Conclusion 106 Chapter 3: The Relational Model 108 Introduction to the Relational Model 108 Relations, Tuples and Types 109 The Relational Model: A Quick Summary 114 Relational Algebra and Relational Calculus 115 Basic Operators 115 Relational Algebra 116 Relational Calculus 127 T-SQL Support 128 Data Integrity 129 Declarative Constraints 130 Other Means of Enforcing Integrity 134 Normalization and Other Design Topics 136 Normal Forms Dealing with Functional Dependencies 137 Higher Normal Forms 144 Denormalization 147 Generalization and Specialization 149 Conclusion 151 Chapter 4: Query Tuning 152 Sample Data for This Chapter 152 Tuning Methodology 156 Analyze Waits at the Instance Level 159 Correlate Waits with Queues 168 Determine Course of Action 170 Drill Down to the Database/File Level 170 Drill Down to the Process Level 173 Tune Indexes and Queries 194 Tools for Query Tuning 196 Cached Query Execution Plans 196 Clearing the Cache 196 Dynamic Management Objects 197 STATISTICS IO 197 Measuring the Run Time of Queries 198 Analyzing Execution Plans 199 Hints 210 Traces/Profiler 211 Database Engine Tuning Advisor 212 Data Collection and Management Data Warehouse 212 Using SMO to Clone Statistics 212 Index Tuning 212 Table and Index Structures 213 Index Access Methods 222 Analysis of Indexing Strategies 269 Fragmentation 281 Partitioning 283 Preparing Sample Data 284 Data Preparation 284 TABLESAMPLE 290 An Examination of Set-Based vs. Iterative/Procedural Approaches and a Tuning Exercise 293 Conclusion 301 Chapter 5: Algorithms and Complexity 302 Do You Have a Quarter? 303 How Algorithms Scale 304 An Example of Quadratic Scaling 305 An Algorithm with Linear Complexity 305 Exponential and Superexponential Complexity 306 Sublinear Complexity 307 Constant Complexity 308 Technical Definitions of Complexity 308 Comparing Complexities 310 Classic Algorithms and Algorithmic Strategies 311 Algorithms for Sorting 312 String Searching 314 A Practical Application 315 Identifying Trends in Measurement Data 316 The Algorithmic Complexity of LISLP 316 Solving the Longest Increasing Subsequence Length Problem in T-SQL 317 Conclusion 320 Chapter 6: Subqueries, Table Expressions, and Ranking Functions 322 Subqueries 323 Self-Contained Subqueries 323 Correlated Subqueries 327 Misbehaving Subqueries 339 Uncommon Predicates 341 Table Expressions 343 Derived Tables 343 Common Table Expressions 346 Analytical Ranking Functions 355 Row Number 357 Rank and Dense Rank 377 Tile Number 379 Auxiliary Table of Numbers 384 Missing and Existing Ranges (Also Known as Gapsand Islands) 388 Missing Ranges (Gaps) 391 Existing Ranges (Islands) 400 Conclusion 412 Chapter 7: Joins and Set Operations 414 Joins 414 Old Style vs. New Style 414 Fundamental Join Types 415 Further Examples of Joins 427 Sliding Total of Previous Year 442 Join Algorithms 446 Separating Elements 454 Set Operations 460 UNION 461 EXCEPT 462 INTERSECT 464 Precedence of Set Operations 465 Using INTO with Set Operations 466 Circumventing Unsupported Logical Phases 466 Conclusion 468 Chapter 8: Aggregating and Pivoting Data 470 OVER Clause 470 Tiebreakers 473 Running Aggregations 476 Cumulative Aggregations 478 Sliding Aggregations 482 Year-to-Date (YTD) 484 Pivoting 485 Pivoting Attributes 485 Relational Division 490 Aggregating Data 491 Unpivoting 495 Custom Aggregations 498 Custom Aggregations Using Pivoting 499 User Defined Aggregates (UDA) 501 Specialized Solutions 512 Histograms 524 Grouping Factor 528 Grouping Sets 531 Sample Data 532 The GROUPING SETS Subclause 533 The CUBE Subclause 536 The ROLLUP Subclause 537 Grouping Sets Algebra 539 The GROUPING_ID Function 543 Materialize Grouping Sets 546 Sorting 549 Conclusion 550 Chapter 9: TOP and APPLY 552 SELECT TOP 552 TOP and Determinism 554 TOP and Input Expressions 555 TOP and Modifications 556 TOP on Steroids 559 APPLY 560 Solutions to Common Problems Using TOP and APPLY 562 TOP n for Each Group 562 Matching Current and Previous Occurrences 568 Paging 572 Random Rows 577 Median 579 Logical Transformations 581 Conclusion 584 Chapter 10: Data Modification 586 Inserting Data 586 Enhanced VALUES Clause 586 SELECT INTO 588 BULK Rowset Provider 590 Minimally Logged Operations 592 INSERT EXEC 615 Sequence Mechanisms 620 GUIDs 625 Deleting Data 626 TRUNCATE vs. DELETE 626 Removing Rows with Duplicate Data 626 DELETE Using Joins 628 Updating Data 631 UPDATE Using Joins 631 Updating Large Value Types 635 SELECT and UPDATE Statement Assignments 636 Merging Data 641 MERGE Fundamentals 642 Adding a Predicate 646 Multiple WHEN Clauses 648 WHEN NOT MATCHED BY SOURCE 649 MERGE Values 651 MERGE and Triggers 652 OUTPUT Clause 653 INSERT with OUTPUT 654 DELETE with OUTPUT 655 UPDATE with OUTPUT 657 MERGE with OUTPUT 659 Composable DML 661 Conclusion 663 Chapter 11: Querying Partitioned Tables 664 Partitioning in SQL Server 664 Partitioned Views 664 Partitioned Tables 665 Conclusion 682 Chapter 12: Graphs, Trees, Hierarchies, and Recursive Queries 684 Terminology 684 Graphs 684 Trees 685 Hierarchies 686 Scenarios 686 Employee Organizational Chart 686 Bill of Materials (BOM) 688 Road System 691 Iteration/Recursion 695 Subordinates 696 Ancestors 706 Subgraph/Subtree with Path Enumeration 710 Sorting 713 Cycles 716 Materialized Path 719 Maintaining Data 720 Querying 726 Materialized Path with the HIERARCHYID Data Type 731 Maintaining Data 733 Querying 740 Further Aspects of Working with HIERARCHYID 744 Nested Sets 755 Assigning Left and Right Values 756 Querying 762 Transitive Closure 765 Directed Acyclic Graph 765 Conclusion 780 Appendix A: Logic Puzzles 782 Puzzles 782 Puzzle 1: Remainders 782 Puzzle 2: Round Manhole Covers 782 Puzzle 3: Shaking Hands 783 Puzzle 4: Then There Were Five? 783 Puzzle 5: Arranging Soldiers in a Row 783 Puzzle 6: Crossing the Tunnel 783 Puzzle 7: Escaping a Cave 784 Puzzle 8: Free Tuna 784 Puzzle 9: Naming an Heir 784 Puzzle 10: The Next Element in a Series 785 Puzzle 11: Same Birthday 785 Puzzle 12: Catching a Train 785 Puzzle 13: Prisoners and Switches 785 Puzzle 14: Probabilities in China 785 Puzzle 15: Two Mathematicians 786 Puzzle 16: Crazy Sequence 786 Puzzle 17: Minimum Number of Weights 787 Puzzle 18: Counting Triangles 787 Puzzle 19: Counterfeit Coins 787 Puzzle 20: Too Clever by Half 788 Puzzle 21: A Cat, a String, and the Earth 788 Puzzle 22: Josephus Problem 788 Puzzle 23: Shipping Algebra 788 Puzzle 24: Equilateral Triangles Puzzle 789 Puzzle Solutions 789 Puzzle 1: Remainders 789 Puzzle 2: Round Manhole Covers 790 Puzzle 3: Shaking Hands 790 Puzzle 4: Then There Were Five? 790 Puzzle 5: Arranging Soldiers in a Row 790 Puzzle 6: Crossing the Tunnel 791 Puzzle 7: Escaping a Cave 791 Puzzle 8: Free Tuna 792 Puzzle 9: Naming an Heir 792 Puzzle 10: The Next Element in a Series 793 Puzzle 11: Same Birthday 793 Puzzle 12: Catching a Train 793 Puzzle 13: Prisoners and Switches 794 Puzzle 14: Probabilities in China 794 Puzzle 15: Two Mathematicians 795 Puzzle 16: Crazy Sequence 796 Puzzle 17: Minimum Number of Weights 796 Puzzle 18: Counting Triangles 797 Puzzle 19: Counterfeit Coins 798 Puzzle 20: Too Clever by Half 798 Puzzle 21: A Cat, a String, and the Earth 799 Puzzle 22: Josephus Problem 800 Puzzle 23: Shipping Algebra 801 Puzzle 24: Equilateral Triangles Puzzle 801 Conclusion 803 Index 804 Symbols and Numbers 804 A 804 B,C 805 D 807 E 808 F,G,H 809 I 810 J,K 811 L,M 812 N 813 O 814 P 815 Q 816 R 817 S 818 T 821 U,V,W 822 X,Y 823 About the Authors 824 Itzik Ben-Gan 824 Lubor Kollar 824 Dejan Sarka 824 Steve Kass 825 Master the mechanics behind advanced querying and tuning - for faster, more scalable code. Tackle the toughest set-based querying and query tuning problems - guided by an author team with in-depth, inside knowledge of T-SQL. Deepen your understanding of architecture and internals - and gain practical approaches and advanced techniques to optimize your code's performance. Discover how to: move from procedural programming to the language of sets and logic, optimize query tuning with a top-down methodology, assess algorithmic complexity to predict performance, compare data-aggregation techniques, including new grouping sets, manage data modification - insert, delete, update, merge - for performance, write more efficient queries against partitioned tables, work with graphs, trees, hierarchies, and recursive queries, and use pure-logic puzzles to sharpen your problem-solving skills

Tackle the toughest set-based querying and query tuning problems-guided by an author team with in-depth, inside knowledge of T-SQL. Deepen your understanding of architecture and internals-and gain practical approaches and advanced techniques to optimize your code’s performance.

Discover how to:

• Move from procedural programming to the language of sets and logic
• Optimize query tuning with a top-down methodology
• Assess algorithmic complexity to predict performance
• Compare data-aggregation techniques, including new grouping sets
• Manage data modification-insert, delete, update, merge-for performance
• Write more efficient queries against partitioned tables
• Work with graphs, trees, hierarchies, and recursive queries
• Plus-Use pure-logic puzzles to sharpen your problem-solving skills