book

Inside Microsoft® SQL Server® 2008: T-SQL Querying

by Lubor Kollar Itzik Ben-Gan Dejan Sarka, and Steve Kass

March 2009

Intermediate to advanced

832 pages

23h 49m

English

Microsoft Press

Read now

Unlock full access

Questions and Comments
Logical Query Processing Phases in Brief

Step 1: The FROM PhaseStep 1-J1: Perform Cartesian Product (Cross Join)Step 1-J2: Apply ON Filter (Join Condition)Step 1-J3: Add Outer RowsStep 2: The WHERE PhaseStep 3: The GROUP BY PhaseStep 4: The HAVING PhaseStep 5: The SELECT PhaseStep 5-1: Evaluate ExpressionsStep 5-2: Apply the DISTINCT ClauseStep 5-3: Apply the TOP OptionStep 6: The Presentation ORDER BY Phase
Table OperatorsAPPLYPIVOTUNPIVOTOVER ClauseSet Operators
Well-DefinednessDefinitionsUndefined TermsEquality, Identity, and SamenessMathematical ConventionsNumbersContextDatesAlphabetical OrderFunctions, Parameters, and VariablesInstructions and Algorithms
Notation for SetsEnumerationSet-Builder NotationWell-Definedness of SetsDomains of DiscourseDomains and Bad DataDomains and ModelingFaithfulnessNo REAL FaithfulnessRussell’s ParadoxOrdered Pairs, Tuples, and Cartesian ProductsOrdered Pairs and k-TuplesThe Cartesian ProductThe Empty Set(s)The Characteristic Function of a SetCardinalityFormal and Constructive Definitions of CardinalityOrderNumerical OrderAlphabetical OrderTrichotomyInduced OrderOrdinal NumbersSet OperatorsUnion and IntersectionSet DifferenceSet PartitionsGeneralizations of Set TheoryMultiset Theory
Logic-Like Features of Programming LanguagesThe Keyword IF in Control-of-Flow StatementsPropositions and PredicatesBoolean Expressions in T-SQLProposition or Predicate?Creating Propositions from PredicatesThe Law of Excluded MiddleAnd, Or, and NotWhat Not Is NotWhen And Means OrExclusive OrLogical EquivalenceDeMorgan’s LawsLogical ImplicationIf P, Then QThe ContrapositiveVacuous TruthsQuantificationNegating Quantified StatementsMultiple QuantificationAlternatives and GeneralizationsBoolean AlgebraThree-Valued LogicFuzzy Logic
The Reflexive, Symmetric, and Transitive PropertiesNot All < Operators Were Created Equal
Relations, Tuples and TypesThe Meaning of RelationsViews (and Other Virtual Relations)Naming ConventionsThe Relational Model: A Quick Summary
Basic OperatorsRelational AlgebraCodd’s Eight Original OperatorsAdditional Relational Algebra OperatorsPrimitive Relational Algebra OperatorsRelational CalculusT-SQL Support
Declarative ConstraintsEntity IntegrityReferential IntegrityDomain IntegrityOther Means of Enforcing IntegrityThe Good, the Bad, and the . . . Unknown!
Normal Forms Dealing with Functional DependenciesFirst Normal FormSecond Normal FormThird Normal FormBoyce-Codd Normal FormHigher Normal FormsFourth Normal FormFifth Normal FormAdditional Normal FormsDenormalizationGeneralization and SpecializationPrinciple of Orthogonal Design
Analyze Waits at the Instance LevelIsolating Top WaitsCollecting Wait InformationCorrelate Waits with QueuesDetermine Course of ActionDrill Down to the Database/File LevelDrill Down to the Process LevelTrace Performance WorkloadAnalyze Trace DataQuery StatisticsTune Indexes and Queries
Cached Query Execution PlansClearing the CacheDynamic Management ObjectsSTATISTICS IOMeasuring the Run Time of QueriesAnalyzing Execution PlansGraphical Execution PlansTextual ShowplansXML ShowplansHintsTraces/ProfilerDatabase Engine Tuning AdvisorData Collection and Management Data WarehouseUsing SMO to Clone Statistics
Table and Index StructuresPages and ExtentsTable OrganizationHeapClustered IndexNonclustered Index on a HeapNonclustered Index on a Clustered TableIndex Access MethodsTable Scan/Unordered Clustered Index ScanUnordered Covering Nonclustered Index ScanOrdered Clustered Index ScanOrdered Covering Nonclustered Index ScanThe Storage Engine’s Treatment of ScansAllocation Order Scans vs. Index Order ScansAllocation Order ScansIndex Order ScansNonclustered Index Seek + Ordered Partial Scan + LookupsUnordered Nonclustered Index Scan + LookupsClustered Index Seek + Ordered Partial ScanCovering Nonclustered Index Seek + Ordered Partial ScanIndex IntersectionFiltered Indexes and StatisticsIndexed ViewsAnalysis of Indexing StrategiesTable Scan (Unordered Clustered Index Scan)Unordered Covering Nonclustered Index ScanUnordered Nonclustered Index Scan + LookupsNonclustered Index Seek + Ordered Partial Scan + LookupsClustered Index Seek + Ordered Partial ScanCovering Nonclustered Index Seek + Ordered Partial ScanSummary of Analysis of Indexing StrategyFragmentationPartitioning
Data PreparationTABLESAMPLE
How to Retrieve a Quarter from a Coin JarSometimes the Jar Has No Quarters
An Example of Quadratic ScalingAn Algorithm with Linear ComplexityExponential and Superexponential ComplexityThe Factorial FunctionSublinear ComplexityBinary SearchConstant ComplexityTechnical Definitions of ComplexityBig Oh and related notationsPolynomial and Nonpolynomial ComplexityComparing Complexities
Algorithms for SortingQuadratic Sorting AlgorithmsInsertion sortSelection sortO(n log n) Sorting AlgorithmsMerge sortQuick sortFaster Sorting AlgorithmsUltra sortString Searching
Identifying Trends in Measurement DataIncreasing SubsequencesThe Algorithmic Complexity of LISLPHow Many Subsequences Are There?An Algorithm for LISLP with Θ(n log n) ComplexitySolving the Longest Increasing Subsequence Length Problem in T-SQL
Self-Contained SubqueriesCorrelated SubqueriesIsolating One Row Per Group and Applying a TiebreakerEXISTSEXISTS vs. INNOT EXISTS vs. NOT INMinimum Missing ValueReverse Logic Applied to Relational Division ProblemsMisbehaving SubqueriesUncommon Predicates
Derived TablesResult Column AliasesUsing ArgumentsNestingMultiple ReferencesCommon Table ExpressionsResult Column AliasesUsing ArgumentsMultiple CTEsMultiple ReferencesModifying DataCTEs in View and Inline Function DefinitionsRecursive CTEs
Row NumberThe ROW_NUMBER FunctionDeterminismPartitioningUsing Subqueries to Calculate Row NumbersUnique Sort ColumnNonunique Sort Column and TiebreakerNonunique Sort Column Without a TiebreakerPartitioningCursor-Based SolutionIDENTITY-Based SolutionNonpartitionedPartitionedPerformance ComparisonsPagingAd Hoc PagingMultipage AccessRank and Dense RankRANK and DENSE_RANK FunctionsSolutions Based on SubqueriesTile NumberThe Built-in NTILE FunctionOther Solutions to Tile Number
Missing Ranges (Gaps)Gaps, Solution 1: Using SubqueriesGaps, Solution 2: Using SubqueriesGaps, Solution 3: Using Ranking FunctionsGaps, Solution 4: Using CursorsReturning Individual Missing ValuesExisting Ranges (Islands)Islands, Solution 1: Using Subqueries and Ranking CalculationsIslands, Solution 2: Using Group Identifier Based on SubqueriesIslands, Solution 3: Using Group Identifier Based on Ranking CalculationsIslands, Solution 4: Using CursorsA Variation of the Islands Problem
Old Style vs. New StyleFundamental Join TypesCROSSINNEROUTERNonsupported Join TypesFurther Examples of JoinsSelf JoinsMultiple JoinsControlling the Physical Join Evaluation OrderControlling the Logical Join Evaluation OrderBushy PlansSemi JoinsSliding Total of Previous YearJoin AlgorithmsNested LoopsMergeHashBitmap Filters in Star Schema JoinsForcing a Join StrategySeparating Elements
UNIONUNION DISTINCTUNION ALLEXCEPTEXCEPT DISTINCTEXCEPT ALLINTERSECTINTERSECT DISTINCTINTERSECT ALLPrecedence of Set OperationsUsing INTO with Set OperationsCircumventing Unsupported Logical Phases
Cumulative AggregationsSliding AggregationsYear-to-Date (YTD)
Pivoting AttributesRelational DivisionAggregating Data
Custom Aggregations Using PivotingString Concatenation Using PivotingAggregate Product Using PivotingUser Defined Aggregates (UDA)Specialized SolutionsSpecialized Solution for Aggregate String ConcatenationDynamic PivotingSpecialized Solution for Aggregate ProductSpecialized Solutions for Aggregate Bitwise OperationsAggregate Bitwise ORAggregate Bitwise ANDAggregate Bitwise XORMedianMode
Sample DataThe GROUPING SETS SubclauseThe CUBE SubclauseThe ROLLUP SubclauseGrouping Sets AlgebraMultiplicationDivisionAdditionThe GROUPING_ID FunctionMaterialize Grouping SetsSorting
TOP and DeterminismTOP and Input ExpressionsTOP and ModificationsTOP on Steroids
TOP n for Each GroupMatching Current and Previous OccurrencesPagingFirst PageNext PagePrevious PageRandom RowsMedian
Enhanced VALUES ClauseSELECT INTOBULK Rowset ProviderMinimally Logged OperationsAnalyzing Logging BehaviorTesting Insert ScenariosScenario 1: SELECT INTO, FULL RecoveryScenario 2: SELECT INTO, Non-FULL RecoveryScenario 3: INSERT SELECT, Empty Heap, TABLOCKScenario 4: INSERT SELECT, Nonempty Heap, TABLOCKScenario 5: INSERT SELECT, Empty Heap, Without TABLOCKScenario 6: INSERT SELECT, Empty B-Tree, TABLOCKScenario 7: INSERT SELECT, Nonempty B-Tree, TABLOCK, TF-610 Off, New Key RangeScenario 8: INSERT SELECT, Nonempty B-Tree, TABLOCK, TF-610 On, New Key RangeScenario 9: INSERT SELECT, Nonempty B-Tree, TABLOCK, Merged Key RangeScenario 10: INSERT SELECT, Empty B-Tree, Without TABLOCK, TF-610 OffScenario 11: INSERT SELECT, Empty B-Tree, Without TABLOCK, TF-610 OnScenario 12: INSERT SELECT, Nonempty B-Tree, without TABLOCK, TF-610 Off, New Key RangeScenario 13: INSERT SELECT, Nonempty B-Tree, without TABLOCK, TF-610 On, New Key RangeScenario 14: INSERT SELECT, Nonempty B-Tree, without TABLOCK, Merged Key RangeSummary of Minimal LoggingINSERT EXECSequence MechanismsIdentity ColumnsCustom SequencesBlocking SequencesSingle Sequence ValueBlock of Sequence ValuesNonblocking SequencesGUIDs
TRUNCATE vs. DELETERemoving Rows with Duplicate DataDELETE Using Joins
UPDATE Using JoinsUpdating Large Value TypesSELECT and UPDATE Statement AssignmentsAssignment SELECTAssignment UPDATE
MERGE FundamentalsAdding a PredicateMultiple WHEN ClausesWHEN NOT MATCHED BY SOURCEMERGE ValuesMERGE and Triggers
INSERT with OUTPUTDELETE with OUTPUTUPDATE with OUTPUTMERGE with OUTPUTComposable DML
Partitioned ViewsComparing Partitioned Views and Partitioned TablesPartitioned TablesQuery Plans for Partitioned TablesStatistics on Partitioned TablesPartition EliminationPartitioning and Parallelism
GraphsTreesHierarchies
Employee Organizational ChartBill of Materials (BOM)Road System
SubordinatesAncestorsSubgraph/Subtree with Path EnumerationSortingCycles
Maintaining DataAdding Employees Who Manage No One (Leaves)Moving a SubtreeRemoving a SubtreeQuerying
Maintaining DataAdding EmployeesMoving a SubtreeQueryingSubtreePathDirect SubordinatesLeaf NodesPresentationFurther Aspects of Working with HIERARCHYIDNormalizing HIERARCHYID ValuesConvert Parent-Child Representation to HIERARCHYIDSorting Separated Lists of Values
Assigning Left and Right ValuesQuerying
Directed Acyclic GraphUndirected Cyclic Graph
Puzzle 1: RemaindersPuzzle 2: Round Manhole CoversPuzzle 3: Shaking HandsPuzzle 4: Then There Were Five?Puzzle 5: Arranging Soldiers in a RowPuzzle 6: Crossing the TunnelPuzzle 7: Escaping a CavePuzzle 8: Free TunaPuzzle 9: Naming an HeirPuzzle 10: The Next Element in a SeriesPuzzle 11: Same BirthdayPuzzle 12: Catching a TrainPuzzle 13: Prisoners and SwitchesPuzzle 14: Probabilities in ChinaPuzzle 15: Two MathematiciansPuzzle 16: Crazy SequencePuzzle 17: Minimum Number of WeightsPuzzle 18: Counting TrianglesPuzzle 19: Counterfeit CoinsPuzzle 20: Too Clever by HalfPuzzle 21: A Cat, a String, and the EarthPuzzle 22: Josephus ProblemPuzzle 23: Shipping AlgebraPuzzle 24: Equilateral Triangles Puzzle
Puzzle 1: RemaindersPuzzle 2: Round Manhole CoversPuzzle 3: Shaking HandsPuzzle 4: Then There Were Five?Puzzle 5: Arranging Soldiers in a RowPuzzle 6: Crossing the TunnelPuzzle 7: Escaping a CavePuzzle 8: Free TunaPuzzle 9: Naming an HeirPuzzle 10: The Next Element in a SeriesPuzzle 11: Same BirthdayPuzzle 12: Catching a TrainPuzzle 13: Prisoners and SwitchesPuzzle 14: Probabilities in ChinaPuzzle 15: Two MathematiciansPuzzle 16: Crazy SequencePuzzle 17: Minimum Number of WeightsPuzzle 18: Counting TrianglesPuzzle 19: Counterfeit CoinsPuzzle 20: Too Clever by HalfPuzzle 21: A Cat, a String, and the EarthPuzzle 22: Josephus ProblemPuzzle 23: Shipping AlgebraPuzzle 24: Equilateral Triangles Puzzle

Content preview from Inside Microsoft® SQL Server® 2008: T-SQL Querying

Chapter 5. Algorithms and Complexity

Steve Kass

This chapter contains a brief introduction to a central topic in computer science: algorithms and complexity. In theory, modern computers can solve nearly any problem that can be expressed precisely. In practice, however, we encounter two considerable obstacles: No computer can solve problems without valid strategies or methods for solving them, and valid problem-solving strategies and methods are useful only if they yield answers within a reasonable amount of time.

Strategies and methods for solving particular problems, given arbitrary input, are called algorithms. The computational complexity of a problem-solving algorithm measures the way in which the resources needed to execute the algorithm depend ...