[MSSQL] CROSS APPLY (avansert)

Kul drittunge · 22. april 2008

[LØST] Det er forskjell på outer og cross apply.

Hei godtfolk.

Har en sak her som min lille nøtt ikke helt takler.

For å være helt ærlig, tror jeg det er noe feil med kompilatoren for Microsoft SQL Server, hvor dem har tatt en mindre lur snarvei for implementeringen av CROSS APPLY.

I all korthet dreier det seg om at for to spørringer som gir samme resultat, så tar den enkleste 100 ganger mer tid enn den mer omstendelige.

Dette er da koden:

select dub.*
from
(
	select top 1 path
	from tblFamily
	where 0 = 0
		and lvl = 3
) as sub
cross apply
(	  
	select path
	from tblFamily
	where 0 = 0		  
		and id in
		(
			select number
			from dbo.util_list2tbl (sub.path)			  
		)	  
) as dub  

select lub.*
from
(
	select top 1 path
	from tblFamily
	where 0 = 0
		and lvl = 3
) as sub
cross apply
(
	select number
	from dbo.util_list2tbl (sub.path)	  
) as dub
cross apply
(
	select path
	from tblFamily
	where 0 = 0		  
		and id = dub.number
) as lub

Her er da path for tblFamily en kondensert sti, og primærnøkkel for tabellen.

util_list2tbl er bare en tabelverdi-funksjon som gjør om en kommaseparert liste til en tabell.

io og time gir:

SQL Server parse and compile time:
CPU time = 0 ms, elapsed time = 1 ms.

(3 row(s) affected)

Table '#1367E606'. Scan count 24422, logical reads 24422, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

Table 'tblFamily'. Scan count 2, logical reads 183, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

(1 row(s) affected)

SQL Server Execution Times:

CPU time = 82781 ms, elapsed time = 105673 ms.

(3 row(s) affected)

Table 'tblFamily'. Scan count 1, logical reads 13, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

Table '#1367E606'. Scan count 1, logical reads 1, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

(1 row(s) affected)

SQL Server Execution Times:

CPU time = 16 ms, elapsed time = 139 ms.

SQL Server parse and compile time:

CPU time = 0 ms, elapsed time = 1 ms.

SQL Server Execution Times:

CPU time = 0 ms, elapsed time = 1 ms.

Fornuftige betraktninger?

Endret 23. april 2008 av zY8pKPhR8XLJ

kaffenils · 22. april 2008

Nå har har jeg ingen SQL Server tilgjengelig så jeg får ikke gjort noen tester for å finne ut nøyaktig hva som skjer, men jeg gjetter at det har noe med hvordan SQL Server bruker (eller i dette tilfelle ikke bruker) index-statistikken for å lage en execution plan for ID IN (SELECT number...). I et WHERE clause med > < (større eller mindre enn) så vil SQL Server anta at 30% av radene vil returneres og kan ofte føre til en lite optimal execution plan. Jeg husker ikke om tilsvarende gjelder IN(), men jeg ser ikke bort fra at tilsvarende gjelder for dette.

Hvis du poster execution planen i XML for begge spørringene + antall rader som finnes i tabellen (og gjerne noe sample data hvis du kan) så skal jeg se om jeg får tid å se på det i morgen.

Kul drittunge · 23. april 2008

Nå er som sagt path primærnøkkel, og har clustered index.

Hvor mange rader det er i tblFamily er derfor klinkende likegyldig.

Spesielt med tanke på problemstillingen som her tas opp.

Det vi snakker om her, er rent konkret at:

select top 1 path
from tblFamily
where 0 = 0
and lvl = 3

path
------------------

-1,17707,8295,

(1 row(s) affected)

select number
from dbo.util_list2tbl ('-1,17707,8295,')

number
-----------

-1

17707

8295

(3 row(s) affected)

Nå har jo faktisk tabellen tblFamily 24422 rader.

Og vi ser av io at den blir lest 24422 ganger.

Noe som forsterker min mening om at her bæsjer kompilatoren på leggen.

<ShowPlanXML xmlns="http://schemas.microsoft.com/sqlserver/2004/07/showplan" Version="1.0" Build="9.00.3042.00"><BatchSequence><Batch><Statements><StmtSimple StatementText="select dub.*
from
(
	select top 1 path
	from tblFamily
	where 0 = 0
		and lvl = 3
) as sub
cross apply
(	  
	select path
	from tblFamily
	where 0 = 0		  
		and id in
		(
			select number
			from dbo.util_list2tbl (sub.path)			  
		)	  
) as dub  

" StatementId="146534" StatementCompId="2" StatementType="SELECT" StatementSubTreeCost="0.40242" StatementEstRows="21979.8" StatementOptmLevel="FULL" StatementOptmEarlyAbortReason="GoodEnoughPlanFound"><StatementSetOptions QUOTED_IDENTIFIER="false" ARITHABORT="true" CONCAT_NULL_YIELDS_NULL="false" ANSI_NULLS="false" ANSI_PADDING="false" ANSI_WARNINGS="false" NUMERIC_ROUNDABORT="false"/><QueryPlan DegreeOfParallelism="1" CachedPlanSize="14" CompileTime="5" CompileCPU="5" CompileMemory="192"><RelOp NodeId="0" PhysicalOp="Nested Loops" LogicalOp="Left Semi Join" EstimateRows="21979.8" EstimateIO="0" EstimateCPU="0.102084" AvgRowSize="35" EstimatedTotalSubtreeCost="0.40242" Parallel="0" EstimateRebinds="0" EstimateRewinds="0"><OutputList><ColumnReference Database="[hjalla_v3]" Schema="[dbo]" Table="[tblFamily]" Column="path"/></OutputList><RunTimeInformation><RunTimeCountersPerThread Thread="0" ActualRows="3" ActualEndOfScans="1" ActualExecutions="1"/></RunTimeInformation><NestedLoops Optimized="0"><OuterReferences><ColumnReference Database="[hjalla_v3]" Schema="[dbo]" Table="[tblFamily]" Column="path"/><ColumnReference Database="[hjalla_v3]" Schema="[dbo]" Table="[tblFamily]" Column="ID"/></OuterReferences><RelOp NodeId="1" PhysicalOp="Nested Loops" LogicalOp="Inner Join" EstimateRows="24422" EstimateIO="0" EstimateCPU="0.102084" AvgRowSize="65" EstimatedTotalSubtreeCost="0.264191" Parallel="0" EstimateRebinds="0" EstimateRewinds="0"><OutputList><ColumnReference Database="[hjalla_v3]" Schema="[dbo]" Table="[tblFamily]" Column="path"/><ColumnReference Database="[hjalla_v3]" Schema="[dbo]" Table="[tblFamily]" Column="ID"/><ColumnReference Database="[hjalla_v3]" Schema="[dbo]" Table="[tblFamily]" Column="path"/></OutputList><RunTimeInformation><RunTimeCountersPerThread Thread="0" ActualRows="24422" ActualEndOfScans="1" ActualExecutions="1"/></RunTimeInformation><NestedLoops Optimized="0"><RelOp NodeId="2" PhysicalOp="Top" LogicalOp="Top" EstimateRows="1" EstimateIO="0" EstimateCPU="1e-007" AvgRowSize="35" EstimatedTotalSubtreeCost="0.00381278" Parallel="0" EstimateRebinds="0" EstimateRewinds="0"><OutputList><ColumnReference Database="[hjalla_v3]" Schema="[dbo]" Table="[tblFamily]" Column="path"/></OutputList><RunTimeInformation><RunTimeCountersPerThread Thread="0" ActualRows="1" ActualEndOfScans="1" ActualExecutions="1"/></RunTimeInformation><Top RowCount="0" IsPercent="0" WithTies="0"><TopExpression><ScalarOperator ScalarString="(1)"><Const ConstValue="(1)"/></ScalarOperator></TopExpression><RelOp NodeId="3" PhysicalOp="Clustered Index Scan" LogicalOp="Clustered Index Scan" EstimateRows="1" EstimateIO="0.286088" EstimateCPU="0.0270212" AvgRowSize="36" EstimatedTotalSubtreeCost="0.00379291" Parallel="0" EstimateRebinds="0" EstimateRewinds="0"><OutputList><ColumnReference Database="[hjalla_v3]" Schema="[dbo]" Table="[tblFamily]" Column="path"/></OutputList><RunTimeInformation><RunTimeCountersPerThread Thread="0" ActualRows="1" ActualEndOfScans="0" ActualExecutions="1"/></RunTimeInformation><IndexScan Ordered="0" ForcedIndex="0" NoExpandHint="0"><DefinedValues><DefinedValue><ColumnReference Database="[hjalla_v3]" Schema="[dbo]" Table="[tblFamily]" Column="path"/></DefinedValue></DefinedValues><Object Database="[hjalla_v3]" Schema="[dbo]" Table="[tblFamily]" Index="[IX_tblFamily_path]" TableReferenceId="1"/><Predicate><ScalarOperator ScalarString="[hjalla_v3].[dbo].[tblFamily].[lvl]=(3)"><Compare CompareOp="EQ"><ScalarOperator><Identifier><ColumnReference Database="[hjalla_v3]" Schema="[dbo]" Table="[tblFamily]" Column="lvl"/></Identifier></ScalarOperator><ScalarOperator><Const ConstValue="(3)"/></ScalarOperator></Compare></ScalarOperator></Predicate></IndexScan></RelOp></Top></RelOp><RelOp NodeId="5" PhysicalOp="Index Scan" LogicalOp="Index Scan" EstimateRows="24422" EstimateIO="0.131273" EstimateCPU="0.0270212" AvgRowSize="39" EstimatedTotalSubtreeCost="0.158294" Parallel="0" EstimateRebinds="0" EstimateRewinds="0"><OutputList><ColumnReference Database="[hjalla_v3]" Schema="[dbo]" Table="[tblFamily]" Column="ID"/><ColumnReference Database="[hjalla_v3]" Schema="[dbo]" Table="[tblFamily]" Column="path"/></OutputList><RunTimeInformation><RunTimeCountersPerThread Thread="0" ActualRows="24422" ActualEndOfScans="1" ActualExecutions="1"/></RunTimeInformation><IndexScan Ordered="0" ForcedIndex="0" NoExpandHint="0"><DefinedValues><DefinedValue><ColumnReference Database="[hjalla_v3]" Schema="[dbo]" Table="[tblFamily]" Column="ID"/></DefinedValue><DefinedValue><ColumnReference Database="[hjalla_v3]" Schema="[dbo]" Table="[tblFamily]" Column="path"/></DefinedValue></DefinedValues><Object Database="[hjalla_v3]" Schema="[dbo]" Table="[tblFamily]" Index="[IX_tblFamily_ID]" TableReferenceId="2"/></IndexScan></RelOp></NestedLoops></RelOp><RelOp NodeId="6" PhysicalOp="Table-valued function" LogicalOp="Table-valued function" EstimateRows="1" EstimateIO="0" EstimateCPU="1.157e-006" AvgRowSize="11" EstimatedTotalSubtreeCost="0.0244222" Parallel="0" EstimateRebinds="24421" EstimateRewinds="0"><OutputList/><RunTimeInformation><RunTimeCountersPerThread Thread="0" ActualRows="3" ActualRebinds="24422" ActualRewinds="0" ActualEndOfScans="24419" ActualExecutions="24422"/></RunTimeInformation><TableValuedFunction><DefinedValues/><Object Database="[hjalla_v3]" Schema="[dbo]" Table="[util_list2tbl]"/><Predicate><ScalarOperator ScalarString="[hjalla_v3].[dbo].[tblFamily].[ID]=[hjalla_v3].[dbo].[util_list2tbl].[number]"><Compare CompareOp="EQ"><ScalarOperator><Identifier><ColumnReference Database="[hjalla_v3]" Schema="[dbo]" Table="[tblFamily]" Column="ID"/></Identifier></ScalarOperator><ScalarOperator><Identifier><ColumnReference Database="[hjalla_v3]" Schema="[dbo]" Table="[util_list2tbl]" Column="number"/></Identifier></ScalarOperator></Compare></ScalarOperator></Predicate><ParameterList><ScalarOperator ScalarString="CONVERT_IMPLICIT(ntext,[hjalla_v3].[dbo].[tblFamily].[path],0)"><Convert DataType="ntext" Style="0" Implicit="1"><ScalarOperator><Identifier><ColumnReference Database="[hjalla_v3]" Schema="[dbo]" Table="[tblFamily]" Column="path"/></Identifier></ScalarOperator></Convert></ScalarOperator></ParameterList></TableValuedFunction></RelOp></NestedLoops></RelOp></QueryPlan></StmtSimple></Statements></Batch></BatchSequence></ShowPlanXML>

<ShowPlanXML xmlns="http://schemas.microsoft.com/sqlserver/2004/07/showplan" Version="1.0" Build="9.00.3042.00"><BatchSequence><Batch><Statements><StmtSimple StatementText="select lub.*
from
(
	select top 1 path
	from tblFamily
	where 0 = 0
		and lvl = 3
) as sub
cross apply
(
	select number
	from dbo.util_list2tbl (sub.path)	  
) as dub
cross apply
(
	select path
	from tblFamily
	where 0 = 0		  
		and id = dub.number
) as lub" StatementId="146542" StatementCompId="3" StatementType="SELECT" StatementSubTreeCost="0.00710539" StatementEstRows="1" StatementOptmLevel="FULL" StatementOptmEarlyAbortReason="GoodEnoughPlanFound"><StatementSetOptions QUOTED_IDENTIFIER="false" ARITHABORT="true" CONCAT_NULL_YIELDS_NULL="false" ANSI_NULLS="false" ANSI_PADDING="false" ANSI_WARNINGS="false" NUMERIC_ROUNDABORT="false"/><QueryPlan DegreeOfParallelism="1" CachedPlanSize="13" CompileTime="6" CompileCPU="6" CompileMemory="192"><RelOp NodeId="0" PhysicalOp="Nested Loops" LogicalOp="Inner Join" EstimateRows="1" EstimateIO="0" EstimateCPU="4.18e-006" AvgRowSize="35" EstimatedTotalSubtreeCost="0.00710539" Parallel="0" EstimateRebinds="0" EstimateRewinds="0"><OutputList><ColumnReference Database="[hjalla_v3]" Schema="[dbo]" Table="[tblFamily]" Column="path"/></OutputList><RunTimeInformation><RunTimeCountersPerThread Thread="0" ActualRows="3" ActualEndOfScans="1" ActualExecutions="1"/></RunTimeInformation><NestedLoops Optimized="0"><OuterReferences><ColumnReference Database="[hjalla_v3]" Schema="[dbo]" Table="[util_list2tbl]" Column="number"/></OuterReferences><RelOp NodeId="1" PhysicalOp="Nested Loops" LogicalOp="Inner Join" EstimateRows="1" EstimateIO="0" EstimateCPU="4.18e-006" AvgRowSize="11" EstimatedTotalSubtreeCost="0.00381811" Parallel="0" EstimateRebinds="0" EstimateRewinds="0"><OutputList><ColumnReference Database="[hjalla_v3]" Schema="[dbo]" Table="[util_list2tbl]" Column="number"/></OutputList><RunTimeInformation><RunTimeCountersPerThread Thread="0" ActualRows="3" ActualEndOfScans="1" ActualExecutions="1"/></RunTimeInformation><NestedLoops Optimized="0"><OuterReferences><ColumnReference Database="[hjalla_v3]" Schema="[dbo]" Table="[tblFamily]" Column="path"/></OuterReferences><RelOp NodeId="2" PhysicalOp="Top" LogicalOp="Top" EstimateRows="1" EstimateIO="0" EstimateCPU="1e-007" AvgRowSize="35" EstimatedTotalSubtreeCost="0.00381278" Parallel="0" EstimateRebinds="0" EstimateRewinds="0"><OutputList><ColumnReference Database="[hjalla_v3]" Schema="[dbo]" Table="[tblFamily]" Column="path"/></OutputList><RunTimeInformation><RunTimeCountersPerThread Thread="0" ActualRows="1" ActualEndOfScans="1" ActualExecutions="1"/></RunTimeInformation><Top RowCount="0" IsPercent="0" WithTies="0"><TopExpression><ScalarOperator ScalarString="(1)"><Const ConstValue="(1)"/></ScalarOperator></TopExpression><RelOp NodeId="3" PhysicalOp="Clustered Index Scan" LogicalOp="Clustered Index Scan" EstimateRows="1" EstimateIO="0.286088" EstimateCPU="0.0270212" AvgRowSize="36" EstimatedTotalSubtreeCost="0.00379291" Parallel="0" EstimateRebinds="0" EstimateRewinds="0"><OutputList><ColumnReference Database="[hjalla_v3]" Schema="[dbo]" Table="[tblFamily]" Column="path"/></OutputList><RunTimeInformation><RunTimeCountersPerThread Thread="0" ActualRows="1" ActualEndOfScans="0" ActualExecutions="1"/></RunTimeInformation><IndexScan Ordered="0" ForcedIndex="0" NoExpandHint="0"><DefinedValues><DefinedValue><ColumnReference Database="[hjalla_v3]" Schema="[dbo]" Table="[tblFamily]" Column="path"/></DefinedValue></DefinedValues><Object Database="[hjalla_v3]" Schema="[dbo]" Table="[tblFamily]" Index="[IX_tblFamily_path]" TableReferenceId="1"/><Predicate><ScalarOperator ScalarString="[hjalla_v3].[dbo].[tblFamily].[lvl]=(3)"><Compare CompareOp="EQ"><ScalarOperator><Identifier><ColumnReference Database="[hjalla_v3]" Schema="[dbo]" Table="[tblFamily]" Column="lvl"/></Identifier></ScalarOperator><ScalarOperator><Const ConstValue="(3)"/></ScalarOperator></Compare></ScalarOperator></Predicate></IndexScan></RelOp></Top></RelOp><RelOp NodeId="5" PhysicalOp="Table-valued function" LogicalOp="Table-valued function" EstimateRows="1" EstimateIO="0" EstimateCPU="1.157e-006" AvgRowSize="11" EstimatedTotalSubtreeCost="1.157e-006" Parallel="0" EstimateRebinds="0" EstimateRewinds="0"><OutputList><ColumnReference Database="[hjalla_v3]" Schema="[dbo]" Table="[util_list2tbl]" Column="number"/></OutputList><RunTimeInformation><RunTimeCountersPerThread Thread="0" ActualRows="3" ActualRebinds="1" ActualRewinds="0" ActualEndOfScans="1" ActualExecutions="1"/></RunTimeInformation><TableValuedFunction><DefinedValues><DefinedValue><ColumnReference Database="[hjalla_v3]" Schema="[dbo]" Table="[util_list2tbl]" Column="number"/></DefinedValue></DefinedValues><Object Database="[hjalla_v3]" Schema="[dbo]" Table="[util_list2tbl]"/><ParameterList><ScalarOperator ScalarString="CONVERT_IMPLICIT(ntext,[hjalla_v3].[dbo].[tblFamily].[path],0)"><Convert DataType="ntext" Style="0" Implicit="1"><ScalarOperator><Identifier><ColumnReference Database="[hjalla_v3]" Schema="[dbo]" Table="[tblFamily]" Column="path"/></Identifier></ScalarOperator></Convert></ScalarOperator></ParameterList></TableValuedFunction></RelOp></NestedLoops></RelOp><RelOp NodeId="7" PhysicalOp="Index Seek" LogicalOp="Index Seek" EstimateRows="1" EstimateIO="0.003125" EstimateCPU="0.0001581" AvgRowSize="35" EstimatedTotalSubtreeCost="0.0032831" Parallel="0" EstimateRebinds="0" EstimateRewinds="0"><OutputList><ColumnReference Database="[hjalla_v3]" Schema="[dbo]" Table="[tblFamily]" Column="path"/></OutputList><RunTimeInformation><RunTimeCountersPerThread Thread="0" ActualRows="3" ActualEndOfScans="0" ActualExecutions="3"/></RunTimeInformation><IndexScan Ordered="1" ScanDirection="FORWARD" ForcedIndex="0" NoExpandHint="0"><DefinedValues><DefinedValue><ColumnReference Database="[hjalla_v3]" Schema="[dbo]" Table="[tblFamily]" Column="path"/></DefinedValue></DefinedValues><Object Database="[hjalla_v3]" Schema="[dbo]" Table="[tblFamily]" Index="[PK_tblFamily_ID]" TableReferenceId="2"/><SeekPredicates><SeekPredicate><Prefix ScanType="EQ"><RangeColumns><ColumnReference Database="[hjalla_v3]" Schema="[dbo]" Table="[tblFamily]" Column="ID"/></RangeColumns><RangeExpressions><ScalarOperator ScalarString="[hjalla_v3].[dbo].[util_list2tbl].[number]"><Identifier><ColumnReference Database="[hjalla_v3]" Schema="[dbo]" Table="[util_list2tbl]" Column="number"/></Identifier></ScalarOperator></RangeExpressions></Prefix></SeekPredicate></SeekPredicates></IndexScan></RelOp></NestedLoops></RelOp></QueryPlan></StmtSimple></Statements></Batch></BatchSequence></ShowPlanXML>

Endret 23. april 2008 av zY8pKPhR8XLJ

kaffenils · 23. april 2008

Jeg ser jo selvfølgelig nå hva som skjer.

Siden funksjonen util_list2tbl tar et paramater så kalles den en gang per rad for hver av de 24422 radene i tblFamily.

Dette gjøres selv om verdien av parameteret faktisk ikke settes av denne sub-querien, men derimot fra den første sub-querien (sub). Kan være enig i at query optimizeren bør oppdage at ingen av parameterverdier settes av den andre sub-querien og at funksjonen kun kjøres en gang per rad i den ytre tabellen definert for CROSS APPLY.

Det er jo nettopp dette som skjer i den andre (og raske) spørringen.

Så min konklusjon er vel som jeg allerede har sagt at query optimizeren kunne oppdaget at funksjonens parameterverdier ikke settes av den andre sub-querien og det det dermed ikke er nødvendig å kalle funksjonen 24422 ganger.

Men til en helt annen ting. Nå vet jeg ikke hva tblFamily egentlig inneholder, men det virker heller snodig at primærnøkkelen din er en kommaseparert liste som logisk refererer til en kolonne ved navn Id. Virker på meg som et klassisk tilfelle som bør løses med en mange-til-mange releasjon. Men igjen, jeg vet ikke hva tabellen inneholder eller hvordan du bruker den. Godt mulig at den denormaliserte formen er mest effektiv til ditt bruk.

Kul drittunge · 23. april 2008

Jeg ser jo selvfølgelig nå hva som skjer.

Siden funksjonen util_list2tbl tar et paramater så kalles den en gang per rad for hver av de 24422 radene i tblFamily.

Dette gjøres selv om verdien av parameteret faktisk ikke settes av denne sub-querien, men derimot fra den første sub-querien (sub).

Ah. Nettopp. Barnslig.

Men det er vel ikke først gang jeg oppdager at kompilatoren ikke er helt lur.

Men til en helt annen ting. Nå vet jeg ikke hva tblFamily egentlig inneholder, men det virker heller snodig at primærnøkkelen din er en kommaseparert liste som logisk refererer til en kolonne ved navn Id.
...

Godt mulig at den denormaliserte formen er mest effektiv til ditt bruk.

"Materialized path" er faktisk ganske så snedig.

Da kan man nemlig foreta set-baserte spørringer for å hente ut hierarkier, istedenfor iterative / rekursive.

Eksempelvis, for å hente ut alt av innhold under en gitt id:

select *
from tblFamily
where 0 = 0
and path like
(
	select path
	from tblFamily
	where 0 = 0
		and id = 8303
) + '_%'

Skal man ha ut alt fra flere hierarkier om gangen, blir det cross apply.

Uansett, takker for hjelpen.

kaffenils · 23. april 2008

"Materialized path" er faktisk ganske så snedig.

Da kan man nemlig foreta set-baserte spørringer for å hente ut hierarkier, istedenfor iterative / rekursive.

Synes ikke det er noen god måte i det hele tatt. Og hva hjelper det om det blir rene set-baserte spørringer når det mest sannsynlig også kjøres sammen med en index scan. Og hva med endringer i hierakiet? Hvor mange path verdier må oppdateres hvis du flytter, legger inn eller sletter en node?

Dessuten har du jo nettopp bevist at spørringene dine IKKE er set-basert da du må kalle en UDF for å gjøre spørringer i hierarkiet.

Jeg er sikker på at rekursiv CTE vil være mye mer effektiv enn din måte som medfører index scan. i alle fall den vil den skalere bedre når mengde med data og brukere øker.

Kul drittunge · 23. april 2008

"Materialized Path" er beskrevet i "Inside Microsoft SQL Server 2005: T-SQL Querying", fra side 505.

Har bittelitt dødtid nå etter lunsjen, så her har du litt mer nyttig info:

set ANSI_NULLS ON
set QUOTED_IDENTIFIER ON
GO
CREATE TABLE [dbo].[tblFamily](
[ID] [int] IDENTITY(1,1) NOT NULL,
[Parent_ID] [int] NULL,
[path] [varchar](900) NOT NULL CONSTRAINT [DF_tblFamily_path]  DEFAULT (newid()),
[lvl] [tinyint] NOT NULL CONSTRAINT [DF_tblFamily_lvl]  DEFAULT ((0)),
CONSTRAINT [PK_tblFamily_ID] PRIMARY KEY NONCLUSTERED 
(
[ID] ASC
)WITH (IGNORE_DUP_KEY = OFF) ON [PRIMARY]
) ON [PRIMARY]
GO
create trigger  [trg_a_i_tblFamily] on [dbo].[tblFamily] after insert
as 
declare @n_rows int
set @n_rows = @@rowcount

if @n_rows = 0 return 
else 
begin try  
	select inserted.id
		, inserted.path as old_path
		, f.path as parent_path
		, coalesce (f.path, '') + cast (inserted.id as varchar (max)) + ',' as new_path
		, inserted.lvl as old_lvl
		, f.lvl as parent_lvl
		, coalesce (f.lvl, 0) + 1 as new_lvl
	into #mod
	from inserted
		left outer join tblFamily f on f.id = inserted.parent_id

	update tblFamily
	set path = sub.new_path
		, lvl = sub.new_lvl
	from
		(
			select id, new_path, new_lvl
			from #mod
		) as sub
	where 0 = 0
		and tblFamily.id = sub.id
end try
begin catch
return
end catch
go
create trigger  [trg_u_tblFamily] on [dbo].[tblFamily] for update
as 
declare @n_rows int
set @n_rows = @@rowcount

if @n_rows = 0 return 
else 
begin try  
		select f.id
			, f.path as old_path
			, f.lvl as old_lvl
			, stuff (f.path, 1, len (sub.old_path), sub.new_path) as new_path
			, (f.lvl - sub.old_lvl) + sub.new_lvl as new_lvl
		into #mod
		from	
			(
				select deleted.id
					, deleted.path as old_path
					, deleted.lvl as old_lvl
					, f.path + cast (deleted.id as varchar (max)) + ',' as new_path
					, f.lvl + 1 as new_lvl
				from deleted
					inner join inserted on inserted.id = deleted.id
					inner join tblFamily f on f.id = inserted.parent_id
				where 0 = 0
					and deleted.parent_id <> inserted.parent_id
			) as sub
			inner join tblFamily f on f.path like sub.old_path + '%'		

		update tblFamily
		set path = sub.new_path
			, lvl = sub.new_lvl
		from			
			(	
				select *
				from #mod
			) as sub
		where 0 = 0 
			and tblFamily.id = sub.id					
end try
begin catch
return
end catch

Ryddet ut ting som ikke angår dette, så håper det ikke mangler noe.

Du må jo gjerne selv teste det litt, om du ønsker.

Her har du det jeg måler:

set statistics time on
set statistics io on
go

select *
from tblFamily
where 0 = 0
and path like
(
	select path
	from tblFamily
	where 0 = 0
		and id = 17713
) + '_%'

;with crawler as 
(
select id		
from tblFamily
where 0 = 0
	and id = 17713
union all
select f.id 		
from tblFamily f
	inner join crawler as c on c.id = f.parent_id
)
select *
from crawler c

SQL Server parse and compile time:
CPU time = 0 ms, elapsed time = 1 ms.

SQL Server Execution Times:

CPU time = 0 ms, elapsed time = 1 ms.

SQL Server Execution Times:

CPU time = 0 ms, elapsed time = 1 ms.

SQL Server parse and compile time:

CPU time = 31 ms, elapsed time = 46 ms.

(2338 row(s) affected)

Table 'Worktable'. Scan count 8, logical reads 0, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

Table 'tblFamily'. Scan count 3, logical reads 603, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

Table 'Worktable'. Scan count 0, logical reads 0, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

SQL Server Execution Times:

CPU time = 156 ms, elapsed time = 214 ms.

(2339 row(s) affected)

Table 'Worktable'. Scan count 2, logical reads 13324, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

Table 'tblFamily'. Scan count 2339, logical reads 16992, physical reads 1, read-ahead reads 46, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

SQL Server Execution Times:

CPU time = 141 ms, elapsed time = 1281 ms.

Her er riktignok primærnøkkelen path, og ikke id, men du kan jo utmerket godt endre dette og bare kjøre noen inserts med tilfeldig genererte id'er.

Endret 23. april 2008 av zY8pKPhR8XLJ

kaffenils · 23. april 2008

Snodige IO resultater du fikk på CTEen. Er Id indexert? Det virker jo ikke slik pga. den enormt høye antall med logical reads.

Og angående det jeg sa om index scans i forrige post, bare glem det. Ser jo at løsningen din gir range scans som er meget effektivt.

Ulempen er jo, som jeg sa, at insert, updates og deletes veldig ressurskrevende pga at hele hierarkiet må oppdateres, både level og path. Men hvis det er svært få skriveoperasjoner så har jo ikke det så mye å si.

Dessuten er det en begrensing på antall nivåer du kan ha siden path ikke kan overskrive 900 tegn, men det skal vel litt til å nå denne med mindre du skal registrere et slektstre flere tusen år tilbake i tid

Kul drittunge · 23. april 2008

ID er primærnøkkel og har nonclustered index. Path er ikke primærnøkkel, men har clustered index.

Tok det samme på hovedserveren, hvor det er null fragmentering på indekser, oppdatert statistikk, og *host* droppet alle cacher.

Med kald cache (ventet litt til *host* en plutselig høyere aktivitet på serveren roet seg *host*):

SQL Server parse and compile time:
CPU time = 0 ms, elapsed time = 1 ms.

SQL Server Execution Times:

CPU time = 0 ms, elapsed time = 1 ms.

SQL Server parse and compile time:

CPU time = 0 ms, elapsed time = 1 ms.

SQL Server Execution Times:

CPU time = 0 ms, elapsed time = 1 ms.

SQL Server Execution Times:

CPU time = 0 ms, elapsed time = 1 ms.

SQL Server parse and compile time:

CPU time = 0 ms, elapsed time = 1 ms.

(2332 row(s) affected)

Table 'Worktable'. Scan count 16, logical reads 0, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

Table 'tblFamily'. Scan count 5, logical reads 588, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

Table 'Worktable'. Scan count 0, logical reads 0, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

SQL Server Execution Times:

CPU time = 94 ms, elapsed time = 46 ms.

(2333 row(s) affected)

Table 'Worktable'. Scan count 2, logical reads 13289, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

Table 'tblFamily'. Scan count 2333, logical reads 16956, physical reads 2, read-ahead reads 81, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

SQL Server Execution Times:

CPU time = 79 ms, elapsed time = 499 ms.

Varm cache:

SQL Server parse and compile time:
CPU time = 0 ms, elapsed time = 1 ms.

SQL Server Execution Times:

CPU time = 0 ms, elapsed time = 2 ms.

SQL Server parse and compile time:

CPU time = 0 ms, elapsed time = 1 ms.

SQL Server Execution Times:

CPU time = 0 ms, elapsed time = 1 ms.

SQL Server Execution Times:

CPU time = 0 ms, elapsed time = 1 ms.

SQL Server parse and compile time:

CPU time = 0 ms, elapsed time = 1 ms.

(2332 row(s) affected)

Table 'Worktable'. Scan count 16, logical reads 0, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

Table 'tblFamily'. Scan count 5, logical reads 588, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

Table 'Worktable'. Scan count 0, logical reads 0, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

SQL Server Execution Times:

CPU time = 125 ms, elapsed time = 40 ms.

(2333 row(s) affected)

Table 'Worktable'. Scan count 2, logical reads 13289, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

Table 'tblFamily'. Scan count 2333, logical reads 16956, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

SQL Server Execution Times:

CPU time = 93 ms, elapsed time = 169 ms.

Så jo, rekursivitet er kostbart.

kaffenils · 23. april 2008

Så jo, rekursivitet er kostbart.

Det er jo logisk at det medfører mye mer logical reads og scans, men at det var så kostbart i forhold til å lagre path innbilte jeg meg ikke. Har en del parent-child relasjoner selv, men disse er for det meste mange-til-mange og da fungerer jo ikke path prinsippet siden en node vil kunne ha flere paths, eller har du noen smarte løsninger for det også?

Takk for god ide i alle fall. Må få tak boken du refererer til, sikkert mye interesant å lese der. Har andre i "Inside SQL Server 2005" serien og det er mye nyttig å plukke med seg derfra.

Kul drittunge · 23. april 2008

Har en del parent-child relasjoner selv, men disse er for det meste mange-til-mange og da fungerer jo ikke path prinsippet siden en node vil kunne ha flere paths, eller har du noen smarte løsninger for det også?

Vel, det blir enten en graf, og ikke et tre, eller et tre med symbolske lenker.

Vår løsning benytter det sistnevnte, hvor vi bare sier at en node ligger utenfor hierarkiet, og kan være oppført i hierarkiet under flere parent_id'er. Samtidig flagger vi hver oppføring i hierarkiet som original, dvs. opprinnelig / faktisk plassering, eller ei.

Takk for god ide i alle fall. Må få tak boken du refererer til, sikkert mye interesant å lese der. Har andre i "Inside SQL Server 2005" serien og det er mye nyttig å plukke med seg derfra.

Mye lurt og praktisk i den ja, anbefales i den serien.

kaffenils · 23. april 2008

Bok bestilt, i tillegg til Query Tuning and Optimization (samme serie) og Joe Celko's Trees and Hierarchies.

:thumbup:

Kul drittunge · 23. april 2008

Har en del parent-child relasjoner selv, men disse er for det meste mange-til-mange og da fungerer jo ikke path prinsippet siden en node vil kunne ha flere paths, eller har du noen smarte løsninger for det også?

Forstod ikke helt hva du mente med en gang, men tror jeg er med nå.

create table #tmp
(
id int identity (1,1) 
, real_parent_id int
, fake_parent_ids varchar (900)
, real_path varchar (900)
)

select lub.*
from 
(
	select id
		, fake_parent_ids
	from #tmp
) as sub
outer apply
(
	select sub.id
		, fakes.number as fake_id
	from dbo.util_list2tbl (sub.fake_parent_ids) as fakes			
) as dub
outer apply
(
	select t.real_path 
		, fake_paths.*
	from #tmp t
		, (
			select t.real_path
			from #tmp t
			where 0 = 0
				and t.id = dub.fake_id
		) as fake_paths
	where 0 = 0
		and t.id = dub.id
) as lub

Her har du da et tre som later som om den er en graf.

kaffenils · 23. april 2008

Takker. Er for sent på dagen til at jeg klarer skjønne hva spørringen gjør i detalj, så jeg må se mer på det i morgen.

Det jeg mente med "en node vil ha flere paths" var at den kan ha flere parent noder, f.eks. i en BOM (Bill of Material) struktur. Et material kan være child til en eller flere andre materialer og kan bestå av et eller flere materialer (child nodes). Altså en mange til mange relasjon. Da vil jo ikke et material (node) ha bare én sti til topp-noden, men flere, siden materialet (noden) kan inngå i flere andre materialer (parent nodes).

Det må vel løses med en ny tabell som inneholder alle path og parent_path som eksistere for et material...? kanskje..? Jeg er ikke altfor bevandret innen denne type problemstillinger på SQL Server og har derfor brukt rekursive CTEs, men det ser jeg jo nå at er veldig ressurskrevende.

Kul drittunge · 23. april 2008

Gav et noe bedre eksempel her: https://www.diskusjon.no/index.php?showtopic=943267

Og ja, vi har sett at rekursive ting bærer GALT hen, _VELDIG_ raskt.

Det skumle er at det går helt greit så lenge du ikke har nevneverdig med data i tabellene, og så plutselig smeller det.

Endret 23. april 2008 av zY8pKPhR8XLJ

kaffenils · 23. april 2008

Gav et noe bedre eksempel her: https://www.diskusjon.no/index.php?showtopic=943267

Og ja, vi har sett at rekursive ting bærer GALT hen, _VELDIG_ raskt.

Det skumle er at det går helt greit så lenge du ikke har nevneverdig med data i tabellene, og så plutselig smeller det.

Interessant eksempel du postet. Skal få sett mer i detlaj på det i morgen.

Jeg har heldigvis ikke støtt på problemer med mine rekursive spørringer enda, men dette skyldes nok at vi kjører på relativt kraftiger servere, at treene vi spør mot ikke er mer en 5-6 nivåer dype og hver node sjelden har mer en 20-30 child noder, og at det er lite rader i tabellene som definerer hierarkiene (~2.000.000).

Har forresten glemt å ønske deg velkommen til forumet. Alltid hyggelig med dyktige folk

Logg inn

[MSSQL] CROSS APPLY (avansert)

Anbefalte innlegg

Kul drittunge

Lenke til kommentar

Videoannonse

kaffenils

Lenke til kommentar

Kul drittunge

Lenke til kommentar

kaffenils

Lenke til kommentar

Kul drittunge

Lenke til kommentar

kaffenils

Lenke til kommentar

Kul drittunge

Lenke til kommentar

kaffenils

Lenke til kommentar

Kul drittunge

Lenke til kommentar

kaffenils

Lenke til kommentar

Kul drittunge

Lenke til kommentar

kaffenils

Lenke til kommentar

Kul drittunge

Lenke til kommentar

kaffenils

Lenke til kommentar

Kul drittunge

Lenke til kommentar

kaffenils

Lenke til kommentar

Opprett en konto eller logg inn for å kommentere

Opprett konto

Logg inn

Hvem er aktive 0 medlemmer