Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Сравнение СУБД Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 [2] 3 4 5 6   вперед  Ctrl      все
 Re: Способы реализации индексов  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 54784

pkarklin
Например, регистро- и акценто-нечувствительность\нечуствительность в MS SQL может быть
задана вплоть до уровня отдельного поля в таблице.

И как идёт регистронечувствительный поиск по покрывающему индексу? Каждая строка из
индекса приводится в верхний/нижний регистр перед сравнением с образцом?

Posted via ActualForum NNTP Server 1.4

30 мар 11, 13:06    [10444905]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
pkarklin
Member

Откуда: Москва (Муром)
Сообщений: 74930
Dimitry Sibiryakov
И как идёт регистронечувствительный поиск по покрывающему индексу? Каждая строка из
индекса приводится в верхний/нижний регистр перед сравнением с образцом?


Что за привычка отвечать вопросом на вопрос...

В следующем примере создано "нечуствительное поле" в чуствительной бд:

CREATE TABLE dbo.T1(col1 varchar(10) COLLATE Cyrillic_General_CI_AS)
GO

CREATE INDEX IX_T1_col1 ON dbo.T1(col1)
GO

INSERT dbo.T1 VALUES('ы')
GO

SET SHOWPLAN_TEXT ON
GO
SELECT * FROM dbo.T1 WHERE col1 = 'Ы'

SELECT * FROM dbo.T1 WHERE col1 = 'ы'
GO

SET SHOWPLAN_TEXT OFF

GO
DROP TABLE dbo.T1

(1 row(s) affected)
StmtText
-----------------------------------------
SELECT * FROM dbo.T1 WHERE col1 = 'Ы'

(1 row(s) affected)

StmtText
-------------------------------------------------------------------------------------------------------------------------------------------------
|--Index Seek(OBJECT:([test].[dbo].[T1].[IX_T1_col1]), SEEK:([test].[dbo].[T1].[col1]=CONVERT_IMPLICIT(varchar(8000),[@1],0)) ORDERED FORWARD)

(1 row(s) affected)

StmtText
-----------------------------------------

SELECT * FROM dbo.T1 WHERE col1 = 'ы'

(1 row(s) affected)

StmtText
-------------------------------------------------------------------------------------------------------------------------------------------------
|--Index Seek(OBJECT:([test].[dbo].[T1].[IX_T1_col1]), SEEK:([test].[dbo].[T1].[col1]=CONVERT_IMPLICIT(varchar(8000),[@1],0)) ORDERED FORWARD)

(1 row(s) affected)

Т.е. неявно конвертиться не "строка индекса", а строковый литерал, который по дефолту имеет такой же коллэйшен, как и у бд.

Результат:

(1 row(s) affected)
col1
----------
ы

(1 row(s) affected)

col1
----------
ы

(1 row(s) affected)

Сравните с:

CREATE TABLE dbo.T1(col1 varchar(10) COLLATE Cyrillic_General_CS_AS)
GO

CREATE INDEX IX_T1_col1 ON dbo.T1(col1)
GO

INSERT dbo.T1 VALUES('ы')
GO

SET SHOWPLAN_TEXT ON
GO
SELECT * FROM dbo.T1 WHERE col1 = 'Ы'

SELECT * FROM dbo.T1 WHERE col1 = 'ы'
GO

SET SHOWPLAN_TEXT OFF
GO
DROP TABLE dbo.T1

(1 row(s) affected)

StmtText
---------------------------------------------------------------------------------------------------------------
|--Index Seek(OBJECT:([test].[dbo].[T1].[IX_T1_col1]), SEEK:([test].[dbo].[T1].[col1]=[@1]) ORDERED FORWARD)

(1 row(s) affected)

StmtText
-----------------------------------------

SELECT * FROM dbo.T1 WHERE col1 = 'ы'

(1 row(s) affected)

StmtText
---------------------------------------------------------------------------------------------------------------
|--Index Seek(OBJECT:([test].[dbo].[T1].[IX_T1_col1]), SEEK:([test].[dbo].[T1].[col1]=[@1]) ORDERED FORWARD)

(1 row(s) affected)

Результат:

(1 row(s) affected)
col1
----------

(0 row(s) affected)

col1
----------
ы

(1 row(s) affected)
30 мар 11, 13:39    [10445194]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
ScareCrow
Member

Откуда: Белый город
Сообщений: 17472
Ivan Durak
А в оракле тоже непокрывающие чтоли? аки в фб?

нет. в Оракле версионность блоков, в ФБ версионность записей.
в блоке хранится номер версии, влазит меньше данных. но блок лежит ПОД индексами, и ни индексы ни данные про версии не знают.
30 мар 11, 13:51    [10445327]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 54784

pkarklin
Т.е. неявно конвертиться не "строка индекса", а строковый литерал

Для сравнения всегда нужны двое. Литерал ты проконвертил, отлично. С чем он теперь
сравнивается? Очевидно, что с неким ключом из индекса. Как сравнивается? Очевидно,
регистронечувствительно. Как такое сравнение вообще возможно? Сюрприз, но для этого оба
аргумента функции stricmp() принудительно приводятся к одному регистру, после чего
сравниваются двоично. Отсюда следует, что при поиске каждый ключ индекса преобразуется в
верхний регистр. И так при каждом поиске. А эта операция недешева. Хоть и дешевле
дискового В/В. Но при некотором (достаточно большом) количестве сравнений данный алгоритм
может проиграть тому, который в индексах хранит уже преобразованное значение и использует
только двоичное сравнение.

Posted via ActualForum NNTP Server 1.4

30 мар 11, 14:01    [10445424]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
pkarklin
Member

Откуда: Москва (Муром)
Сообщений: 74930
Dimitry Sibiryakov,

Если было бы так, как написано, то никакого бы seek не было. Был бы scan.
30 мар 11, 15:31    [10446232]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 54784

pkarklin
Если было бы так, как написано, то никакого бы seek не было. Был бы scan.

Ну а как тогда оно происходит у MS в брюхе?

Posted via ActualForum NNTP Server 1.4

30 мар 11, 15:36    [10446271]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
Индекс Способович
Guest
ScareCrow
Ivan Durak
А в оракле тоже непокрывающие чтоли? аки в фб?

нет. в Оракле версионность блоков, в ФБ версионность записей.
в блоке хранится номер версии, влазит меньше данных. но блок лежит ПОД индексами, и ни индексы ни данные про версии не знают.

Т.е. так же в FB данные берутся не из индексов, а из блоков(в FB из записей). И также как в FB для индекс скана могут использоваться одновременно несколько индексов?

А в IOT оракловом что позволят брать данные из индекса?
30 мар 11, 18:58    [10448085]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
Le Peace
Member

Откуда: Москва
Сообщений: 8969
Индекс Способович
А в IOT оракловом что позволят брать данные из индекса?

То, что все данные находятся на листовом уровне индекса.
30 мар 11, 19:02    [10448095]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
Индекс Способович
Guest
Le Peace
Индекс Способович
А в IOT оракловом что позволят брать данные из индекса?

То, что все данные находятся на листовом уровне индекса.

И записи о версиях там же?
А поля по которым построен индекса дублируются в листовом уровне индекса или беруться непосредственно из индекса?
30 мар 11, 19:17    [10448136]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
Индекс Способович
Guest
Gluk (Kazan)
Индекс Способович
пропущено...

ZXY<Zxy<abc и ZXY<ZXY<ABC )
Это называется коллизии, они так же не позволяют сохранять порядок.
Если не ограничивать пространство арбузов узкими рамками тыквины, а ещё и яблоки арбузами называть. Я не настаиваю, но я бы предпочел называть функции подходящие под определение хэш-функции.
Но не верьте мне, я просто беру частные случаи, на самом деле вы правы.

Кстати, а как в Oracle с этим дело обстоит, там данные берутся из индекса?


определение хэш функции соблаговолите представить :)
а то получается почти как про 7 красных линий

Про 7 линий шикарно )


Хэш-функцией называется односторонняя функция, предназначенная для получения дайджеста или "отпечатков пальцев" файла, сообщения или некоторого блока данных.
Хэш-код создается функцией Н:

h = H (M)

Где М является сообщением произвольной длины и h является хэш-кодом фиксированной длины.
Хэш-функция Н, которая используется для аутентификации сообщений, должна обладать следующими свойствами:
1. Хэш-функция Н должна применяться к блоку данных любой длины.
2. Хэш-функция Н создает выход фиксированной длины.
3. Н(М) относительно легко (за полиномиальное время) вычисляется для любого значения М.
4. Для любого данного значения хэш-кода h вычислительно невозможно найти M такое, что Н(M) = h.
5. Для любого данного х вычислительно невозможно найти y<>x, что H(y) = H(x).
6. Вычислительно невозможно найти произвольную пару (х,y) такую, что H(y) = H(x).

Хэш-функция, которая удовлетворяет первым пяти свойствам, называется простой или слабой хэш-функцией. Если кроме того выполняется шестое свойство, то такая функция называется сильной хэш-функцией.
30 мар 11, 19:38    [10448210]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
ScareCrow
Member

Откуда: Белый город
Сообщений: 17472
автор
И записи о версиях там же?
А поля по которым построен индекса дублируются в листовом уровне индекса или беруться непосредственно из индекса?

в Оракле записи о версиях хранятся уровнем ниже. в блоках. ни индексы ни данные про версии не знают.
IOT это та же самая таблица, только завязанная в двунаправленный сортированный список по ключевым полям.
30 мар 11, 21:08    [10448437]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
ScareCrow
Member

Откуда: Белый город
Сообщений: 17472
автор
Т.е. так же в FB данные берутся не из индексов, а из блоков(в FB из записей).

в ФБ нельзя получить данные только из индекса, потому что прочитав индекс, ты не знаешь - видим ли элемент для твоей транзакции. в оракле ты это знаешь.
30 мар 11, 21:10    [10448441]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34709

On 30.03.2011 20:38, Индекс Способович wrote:

Какое-то дебильное определение хэш-функции.

> 4. Для любого данного значения хэш-кода h вычислительно невозможно найти M
> такое, что Н(M) = h.
> 5. Для любого данного х вычислительно невозможно найти y<>x, что H(y) = H(x).

Ну а это просто враньё. Как раз наоборот, таких разных M и разных y будет много,
которые дадут один и тот же h. В этом самая суть хэш-функции. Если этого нет --
это не хеш-функция, а свёртка.


> 6. Вычислительно невозможно найти произвольную пару (х,y) такую, что H(y) = H(x).
>
> Хэш-функция, которая удовлетворяет первым пяти свойствам, называется простой или
> слабой хэш-функцией.

Это вообще не хеш-функция. Конечно, может быть у тебя какая-то своя, другая
терминология, тогда уж укажи в начале послания, что, да как.


Posted via ActualForum NNTP Server 1.4

30 мар 11, 21:13    [10448452]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
Индекс Способович
Guest
MasterZiv
знаете что такое "вычислительно невозможно найти" )
И приведите своё правильное и четкое определение хэш-функции.
30 мар 11, 23:06    [10448765]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
Индекс Способович
Guest
ScareCrow
в Оракле записи о версиях хранятся уровнем ниже. в блоках. ни индексы ни данные про версии не знают.


ScareCrow
в ФБ нельзя получить данные только из индекса, потому что прочитав индекс, ты не знаешь - видим ли элемент для твоей транзакции. в оракле ты это знаешь.


Что-то я совсем запутался. Как индексы не зная про версии знают видим ли элемент для твоей транзакции?
30 мар 11, 23:10    [10448785]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
Индекс Способович
Guest
kdv
Sk1N.
Сначала ключей меньше чем версий, потом обратное: ключей не может быть меньше чем версий. Где описка? :)

ошибка во второй части.
количество записей <= количество ключей <= количество записей+версий

pkarklin
Я правильно понимаю, что в ФБ хранение в индексе хэша, а не данных Вы объясняете версионностью?

нет. И про "хэш в индексе" Сибиряков уже объяснил, что ОН имел в виду. Хранятся, конечно, данные, только из-за отсутствия в ключе информации о транзакции невозможно определить видимость ключа без определения видимости записи.

Т.е. именно данные хранятся в индексе?
А при Read Uncommited браться из индекса данные не смогут?
Учитывая что FB можно использовать как embedded.
31 мар 11, 01:34    [10449059]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 54784

Индекс Способович
А при Read Uncommited браться из индекса данные не смогут?

Не могут, поскольку во-первых, нет в FB Read Uncommitted. А во-вторых, то, что можно
достать из индекса это не то, что стоило бы показывать пользователю. Как я уже
неоднократно говорил, функция преобразования значения в ключ в общем случае необратима.

Posted via ActualForum NNTP Server 1.4

31 мар 11, 01:40    [10449064]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
kdv
Member

Откуда: iBase.ru
Сообщений: 30253
Индекс Способович
Т.е. именно данные хранятся в индексе?
А при Read Uncommited браться из индекса данные не смогут?
Учитывая что FB можно использовать как embedded.

блжад. Embedded, не Embedded, никакой разницы. Версионность движка неотключаема, и это хорошо, ибо базе по барабану, "выделенный" сервер с ней работает, или сервер в виде exe+embedded.
Далее, в ФБ нет Read Uncommitted в принципе. Более того, до версии 4.0 в InterBase не было Read Committed, был только Repeatable Read.
Ну и, наконец, данные из индекса браться никак не могут, я уже объяснял почему.

Пример1:
запись, столбец field имеет значение 1, столбец проиндексирован, в индексе хранится ключ 1 со ссылкой на запись.
новая транзакция модифицирует запись, но не меняет столбец field. Имеем 2 версии, при этом в индексе 1 ключ, ссылающийся на одну и ту же запись (у которой 2 версии).

Пример2:
запись, столбец field имеет значение 1, --//---
новая транзакция модифицирует запись, меняет столбец field на 2. Имеем 2 версии, при этом в индексе 2 разных ключа, ссылающихся на одну и ту же запись, видимую разным транзакциям (2 версии).

Что для примера 1, что для примера 2, видимость конкретной версии для конкретной транзакции определяется только номером и состоянием транзакции, создавшей конкретную версию. В ключах индекса этой информации нет. Значит, хоть ключ и содержит данные, для определения видимости сервер должен считать конкретную версию, чтобы понять, какой транзацкции что можно видеть.
31 мар 11, 04:51    [10449115]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34709

On 31.03.2011 0:06, Индекс Способович wrote:

> знаете что такое "вычислительно невозможно найти" )
Не, не знаю. Я знаю, что такое "можно найти" и знаю, что
такое "нельзя найти". А "вычислительно невозможно найти"
это очень похоже на "немножко беременна".

Это как в EMC люди откровенно считают, что хэш-функция
даёю уникальный код для своего аргумента.

> И приведите своё правильное и четкое определение хэш-функции.

Я что тут в преподаватели нанялся ?
Найди литературу, почитай. Хопкрофта книга была хорошая.
Ахо etc тоже.

Posted via ActualForum NNTP Server 1.4

31 мар 11, 11:49    [10450289]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
SergSuper
Member

Откуда: SPb
Сообщений: 5488
MasterZiv
> знаете что такое "вычислительно невозможно найти" )
Не, не знаю. Я знаю, что такое "можно найти" и знаю, что
такое "нельзя найти". А "вычислительно невозможно найти"
это очень похоже на "немножко беременна".
если на поиск потребуется миллиард лет - это "можно найти" или "нельзя найти"?
31 мар 11, 12:21    [10450570]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34709

On 31.03.2011 13:21, SergSuper wrote:

> если на поиск потребуется миллиард лет - это "можно найти" или "нельзя найти"?

Это -- "можно найти". Нерешаемая задача и сложнорешаемая задача -- не одно и то же.

Posted via ActualForum NNTP Server 1.4

31 мар 11, 12:38    [10450712]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
SergSuper
Member

Откуда: SPb
Сообщений: 5488
MasterZiv
On 31.03.2011 13:21, SergSuper wrote:

> если на поиск потребуется миллиард лет - это "можно найти" или "нельзя найти"?

Это -- "можно найти". Нерешаемая задача и сложнорешаемая задача -- не одно и то же.
т.е. никакой разницы нет между задачами которые, решаются считанным количеством тактов и и которые решаются годами?
"вычислительно невозможно найти" и подразумевает что найти можно только теоретически, перебором, для использования получения данных не предназначено
31 мар 11, 14:17    [10451626]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
Siemargl
Member

Откуда: 010100
Сообщений: 6637
SergSuper
MasterZiv
On 31.03.2011 13:21, SergSuper wrote:

> если на поиск потребуется миллиард лет - это "можно найти" или "нельзя найти"?

Это -- "можно найти". Нерешаемая задача и сложнорешаемая задача -- не одно и то же.
т.е. никакой разницы нет между задачами которые, решаются считанным количеством тактов и и которые решаются годами?
"вычислительно невозможно найти" и подразумевает что найти можно только теоретически, перебором, для использования получения данных не предназначено

У "вычислительно невозможно найти" - граница меняется с каждым годом. Это нечеткое определение.

А ТС взял определение криптографического хэша и пытается присобачить его к СУБД. А тут никто не поймет,
зачем такие навороты в зоопарке БД.
31 мар 11, 17:02    [10453046]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
Bogdanov Andrey
Member

Откуда: Да уже и сам не знаю...
Сообщений: 2203
Siemargl
У "вычислительно невозможно найти" - граница меняется с каждым годом. Это нечеткое определение.
Вы действительно понятие "сложность вычислений" не слышали, или прикидываетесь? Почитайте про классы сложности. Все очень строго определено. Граница никуда не меняется и никак от быстродействия современных компьютеров не зависит. А вот от достижений математической мысли зависеть может :)
31 мар 11, 17:25    [10453218]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
Siemargl
Member

Откуда: 010100
Сообщений: 6637
Bogdanov Andrey,

В Вике все доступно объяснено на трех пальцах.
Но ТС наже в этом путается
Индекс Способович
3. Н(М) относительно легко (за полиномиальное время) вычисляется для любого значения М.
31 мар 11, 17:53    [10453468]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 [2] 3 4 5 6   вперед  Ctrl      все
Все форумы / Сравнение СУБД Ответить