B-деревья, базы данных, последовательные и случайные вставки и скорость. Случайный выигрыш

Question

EDIT

@Remus исправил мою тестовую модель. Вы можете увидеть исправленную версию своего ответа ниже.

Я принял предложение заменить INT с DECIMAL (29,0), и результаты были:

Decimal: 2133
GUID: 1836

Случайные вставки по-прежнему побеждает, даже с дробно большей строкой.

Несмотря на объяснения, указывающие, что случайные вставки медленнее, чем последовательные, эти тесты показывают, что они, по-видимому, быстрее. Объяснения, которые я получаю, не согласуются с эталонами. Поэтому мой вопрос остается сосредоточенным на b-деревьях, последовательных вставках и скорости.

...

Я знаю по опыту, что б дерева имеют ужасную производительность, когда данные добавляются к ним последовательно (независимо от направления). Однако, когда данные добавляются случайным образом, достигается наилучшая производительность.

Это легко продемонстрировать с подобными RB-Tree. Последовательная запись вызывает максимальное количество балансов деревьев.

Я знаю, что очень немногие базы данных используют двоичные деревья, а скорее используют сбалансированные деревья n-порядка. Я логически предполагаю, что они страдают подобной судьбой от бинарных деревьев, когда речь идет о последовательных входах.

Это вызвало мое любопытство.

Если это так, можно было бы сделать вывод, что запись последовательных идентификаторов (например, в IDENTITY (1,1)) приведет к возникновению нескольких повторных балансов дерева. Я видел много сообщений утверждают против GUID как «они вызовут случайную запись». Я никогда не использовал GUID, но мне показалось, что эта «плохая» точка была фактически хорошей точкой.

Так что я решил проверить его. Вот мой код:

SET ANSI_NULLS ON 
GO 
SET QUOTED_IDENTIFIER ON 
GO 
CREATE TABLE [dbo].[T1](
    [ID] [int] NOT NULL 
CONSTRAINT [T1_1] PRIMARY KEY CLUSTERED ([ID] ASC) 
) 
GO 

CREATE TABLE [dbo].[T2](
    [ID] [uniqueidentifier] NOT NULL 
CONSTRAINT [T2_1] PRIMARY KEY CLUSTERED ([ID] ASC) 
) 

GO 

declare @i int, @t1 datetime, @t2 datetime, @t3 datetime, @c char(300) 

set @t1 = GETDATE() 
set @i = 1 

while @i < 2000 begin 
    insert into T2 values (NEWID(), @c) 
    set @i = @i + 1 
end 

set @t2 = GETDATE() 
WAITFOR delay '0:0:10' 
set @t3 = GETDATE() 
set @i = 1 

while @i < 2000 begin 
    insert into T1 values (@i, @c) 
    set @i = @i + 1 
end 

select DATEDIFF(ms, @t1, @t2) AS [Int], DATEDIFF(ms, @t3, getdate()) AS [GUID] 

drop table T1 
drop table T2 

Обратите внимание, что я не вычитая любое время для создания GUID ни для значительно увеличения размера строки. Результаты на моей машине были следующие:

Int: 17,340 мс GUID: 6,746 мс

Это означает, что в этом тесте, случайные вставки из 16 байт был почти в 3 раза быстрее чем последовательного вставки из 4 байтов.

Хотели бы вы прокомментировать это?

Ps. Я понимаю, что это не вопрос. Это приглашение к обсуждению, и это актуально для обучения оптимальному программированию.

Answer 1

переверните операцию, и int быстрее .. вы учли учет и рост файла данных? Запуск каждой отдельно

declare @i int, @t1 datetime, @t2 datetime 

set @t1 = GETDATE() 
set @i = 1 

while @i < 10000 begin 
    insert into T2 values (NEWID()) 
    set @i = @i + 1 
END 


set @t2 = GETDATE() 
set @i = 1 

while @i < 10000 begin 
    insert into T1 values (@i) 
    set @i = @i + 1 
end 



select DATEDIFF(ms, @t1, @t2) AS [UID], DATEDIFF(ms, @t2, getdate()) AS [Int] 

проблемы с UUID, когда кластеризация на них, а не с помощью NEWSEQUENTIALID() является то, что они вызывают разрывы страниц и фрагментацию таблицы

теперь попробуйте, как это, и вы видите, что это почти то же самое

declare @i int, @t1 datetime, @t2 datetime 

set @t1 = GETDATE() 
set @i = 1 

while @i < 10000 begin 
    insert into T2 values (NEWID()) 
    set @i = @i + 1 
END 
select DATEDIFF(ms, @t1, getdate()) 

set @t1 = GETDATE() 
set @i = 1 

while @i < 10000 begin 
    insert into T1 values (@i) 
    set @i = @i + 1 
end 



select DATEDIFF(ms, @t1, getdate()) 

И обратная

declare @i int, @t1 datetime, @t2 datetime 



set @t1 = GETDATE() 
set @i = 1 

while @i < 10000 begin 
    insert into T1 values (@i) 
    set @i = @i + 1 
end 

set @t1 = GETDATE() 
set @i = 1 

while @i < 10000 begin 
    insert into T2 values (NEWID()) 
    set @i = @i + 1 
END 
select DATEDIFF(ms, @t1, getdate()) 

Answer 2

Я ожидаю в реальной ребалансировке базы данных индекс является второстепенной проблемой, поскольку множество записей индекса будет вписываться в один блок и до тех пор.

Что может стать более серьезной проблемой, можно утверждать, что этот единственный блок содержит все новые записи. У Oracle есть функция для хранения байтов ключа в обратном порядке для распространения новых записей по всем блокам: http://oracletoday.blogspot.com/2006/09/there-is-option-to-create-index.html Не знаю о других базах данных.

Answer 3

Вы не измеряете скорость INSERT. Вы измеряете эффективность работы с журналом. Поскольку вы фиксируете после каждого INSERT, все эти тесты работают, ожидая фиксации, чтобы закрепить журнал. Это вряд ли имеет значение для производительности INSERT. И, пожалуйста, не публикуйте измерения «производительность», когда SET NOCOUNT является OFF ...

Так давайте попробуют это без ненужного клиент-сервера болтовни, с правильно подобранными данными, партия совершает и предварительно выращены базы данных:

:setvar dbname testdb 
:setvar testsize 1000000 
:setvar batchsize 1000 

use master; 
go 

if db_id('$(dbname)') is not null 
begin 
    drop database [$(dbname)]; 
end 
go 

create database [$(dbname)] 
    on (name='test_data', filename='c:\temp\test_data.mdf', size=10gb) 
    log on (name='test_log', filename='c:\temp\test_log.ldf', size=100mb); 
go 

use [$(dbname)]; 
go 

CREATE TABLE [dbo].[T1](
    [ID] [int] NOT NULL 
CONSTRAINT [T1_1] PRIMARY KEY CLUSTERED ([ID] ASC) 
) 
GO 

CREATE TABLE [dbo].[T2](
    [ID] [uniqueidentifier] NOT NULL 
CONSTRAINT [T2_1] PRIMARY KEY CLUSTERED ([ID] ASC) 
) 
GO 

set nocount on; 
go 

declare @i int, @t1 datetime, @t2 datetime 

set @t1 = GETDATE() 
set @i = 1 

begin transaction; 
while @i < $(testsize) begin 
    insert into T1 values (@i) 
    set @i = @i + 1 
    if @i % $(batchsize) = 0 
    begin 
     commit; 
     begin transaction; 
    end 
end 
commit 

set @t2 = GETDATE() 
set @i = 1 
begin transaction 
while @i < $(testsize) begin 
    insert into T2 values (NEWID()) 
    set @i = @i + 1 
    if @i % $(batchsize) = 0 
    begin 
     commit; 
     begin transaction; 
    end 
end 
commit 

select DATEDIFF(ms, @t1, @t2) AS [Int], DATEDIFF(ms, @t2, getdate()) AS [UID] 

drop table T1 
drop table T2 

INTS: 18s
GUIDs: 23s

КЭД