ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Сравнение СУБД [игнор отключен] [закрыт для гостей] / Способы реализации индексов
25 сообщений из 150, страница 2 из 6
  2  все
Способы реализации индексов
    #37190020
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
pkarklinНапример, регистро- и акценто-нечувствительность\нечуствительность в MS SQL может быть
задана вплоть до уровня отдельного поля в таблице.

И как идёт регистронечувствительный поиск по покрывающему индексу? Каждая строка из
индекса приводится в верхний/нижний регистр перед сравнением с образцом?
Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
30.03.2011, 13:06
| Ответить | Цитировать | Написать  
Способы реализации индексов
    #37190112
pkarklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
pkarklin
Участник
Dimitry SibiryakovИ как идёт регистронечувствительный поиск по покрывающему индексу? Каждая строка из
индекса приводится в верхний/нижний регистр перед сравнением с образцом?


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

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

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
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

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
(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)

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

Результат:

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
(1 row(s) affected)
col1
----------
ы

(1 row(s) affected)

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

(1 row(s) affected)

Сравните с:

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
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

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
(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)

Результат:

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
(1 row(s) affected)
col1
----------

(0 row(s) affected)

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

(1 row(s) affected)
...
Рейтинг: 0 / 0
30.03.2011, 13:39
| Ответить | Цитировать | Написать  
Способы реализации индексов
    #37190154
Фотография ScareCrow
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ScareCrow
Участник
Ivan DurakА в оракле тоже непокрывающие чтоли? аки в фб?
нет. в Оракле версионность блоков, в ФБ версионность записей.
в блоке хранится номер версии, влазит меньше данных. но блок лежит ПОД индексами, и ни индексы ни данные про версии не знают.
...
Рейтинг: 0 / 0
30.03.2011, 13:51
| Ответить | Цитировать | Написать  
Способы реализации индексов
    #37190180
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
pkarklinТ.е. неявно конвертиться не "строка индекса", а строковый литерал

Для сравнения всегда нужны двое. Литерал ты проконвертил, отлично. С чем он теперь
сравнивается? Очевидно, что с неким ключом из индекса. Как сравнивается? Очевидно,
регистронечувствительно. Как такое сравнение вообще возможно? Сюрприз, но для этого оба
аргумента функции stricmp() принудительно приводятся к одному регистру, после чего
сравниваются двоично. Отсюда следует, что при поиске каждый ключ индекса преобразуется в
верхний регистр. И так при каждом поиске. А эта операция недешева. Хоть и дешевле
дискового В/В. Но при некотором (достаточно большом) количестве сравнений данный алгоритм
может проиграть тому, который в индексах хранит уже преобразованное значение и использует
только двоичное сравнение.
Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
30.03.2011, 14:01
| Ответить | Цитировать | Написать  
Способы реализации индексов
    #37190436
pkarklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
pkarklin
Участник
Dimitry Sibiryakov,

Если было бы так, как написано, то никакого бы seek не было. Был бы scan.
...
Рейтинг: 0 / 0
30.03.2011, 15:31
| Ответить | Цитировать | Написать  
Способы реализации индексов
    #37190451
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
pkarklinЕсли было бы так, как написано, то никакого бы seek не было. Был бы scan.

Ну а как тогда оно происходит у MS в брюхе?
Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
30.03.2011, 15:36
| Ответить | Цитировать | Написать  
Способы реализации индексов
    #37191000
Индекс Способович
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Индекс Способович
Гость
ScareCrowIvan DurakА в оракле тоже непокрывающие чтоли? аки в фб?
нет. в Оракле версионность блоков, в ФБ версионность записей.
в блоке хранится номер версии, влазит меньше данных. но блок лежит ПОД индексами, и ни индексы ни данные про версии не знают.
Т.е. так же в FB данные берутся не из индексов, а из блоков(в FB из записей). И также как в FB для индекс скана могут использоваться одновременно несколько индексов?

А в IOT оракловом что позволят брать данные из индекса?
...
Рейтинг: 0 / 0
30.03.2011, 18:58
| Ответить | Цитировать | Написать  
Способы реализации индексов
    #37191009
Фотография Le Peace
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Le Peace
Участник
Индекс СпособовичА в IOT оракловом что позволят брать данные из индекса?
То, что все данные находятся на листовом уровне индекса.
...
Рейтинг: 0 / 0
30.03.2011, 19:02
| Ответить | Цитировать | Написать  
Способы реализации индексов
    #37191030
Индекс Способович
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Индекс Способович
Гость
Le PeaceИндекс СпособовичА в IOT оракловом что позволят брать данные из индекса?
То, что все данные находятся на листовом уровне индекса.
И записи о версиях там же?
А поля по которым построен индекса дублируются в листовом уровне индекса или беруться непосредственно из индекса?
...
Рейтинг: 0 / 0
30.03.2011, 19:17
| Ответить | Цитировать | Написать  
Способы реализации индексов
    #37191050
Индекс Способович
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Индекс Способович
Гость
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).

Хэш-функция, которая удовлетворяет первым пяти свойствам, называется простой или слабой хэш-функцией. Если кроме того выполняется шестое свойство, то такая функция называется сильной хэш-функцией.
...
Рейтинг: 0 / 0
30.03.2011, 19:38
| Ответить | Цитировать | Написать  
Способы реализации индексов
    #37191159
Фотография ScareCrow
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ScareCrow
Участник
авторИ записи о версиях там же?
А поля по которым построен индекса дублируются в листовом уровне индекса или беруться непосредственно из индекса?
в Оракле записи о версиях хранятся уровнем ниже. в блоках. ни индексы ни данные про версии не знают.
IOT это та же самая таблица, только завязанная в двунаправленный сортированный список по ключевым полям.
...
Рейтинг: 0 / 0
30.03.2011, 21:08
| Ответить | Цитировать | Написать  
Способы реализации индексов
    #37191163
Фотография ScareCrow
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ScareCrow
Участник
авторТ.е. так же в FB данные берутся не из индексов, а из блоков(в FB из записей).
в ФБ нельзя получить данные только из индекса, потому что прочитав индекс, ты не знаешь - видим ли элемент для твоей транзакции. в оракле ты это знаешь.
...
Рейтинг: 0 / 0
30.03.2011, 21:10
| Ответить | Цитировать | Написать  
Способы реализации индексов
    #37191170
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
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
...
Рейтинг: 0 / 0
30.03.2011, 21:13
| Ответить | Цитировать | Написать  
Способы реализации индексов
    #37191335
Индекс Способович
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Индекс Способович
Гость
MasterZiv
знаете что такое "вычислительно невозможно найти" )
И приведите своё правильное и четкое определение хэш-функции.
...
Рейтинг: 0 / 0
30.03.2011, 23:06
| Ответить | Цитировать | Написать  
Способы реализации индексов
    #37191344
Индекс Способович
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Индекс Способович
Гость
ScareCrowв Оракле записи о версиях хранятся уровнем ниже. в блоках. ни индексы ни данные про версии не знают .


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

Что-то я совсем запутался. Как индексы не зная про версии знают видим ли элемент для твоей транзакции?
...
Рейтинг: 0 / 0
30.03.2011, 23:10
| Ответить | Цитировать | Написать  
Способы реализации индексов
    #37191487
Индекс Способович
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Индекс Способович
Гость
kdvSk1N.Сначала ключей меньше чем версий, потом обратное: ключей не может быть меньше чем версий. Где описка? :)
ошибка во второй части.
количество записей <= количество ключей <= количество записей+версий

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

Т.е. именно данные хранятся в индексе?
А при Read Uncommited браться из индекса данные не смогут?
Учитывая что FB можно использовать как embedded.
...
Рейтинг: 0 / 0
31.03.2011, 01:34
| Ответить | Цитировать | Написать  
Способы реализации индексов
    #37191490
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
Индекс СпособовичА при Read Uncommited браться из индекса данные не смогут?

Не могут, поскольку во-первых, нет в FB Read Uncommitted. А во-вторых, то, что можно
достать из индекса это не то, что стоило бы показывать пользователю. Как я уже
неоднократно говорил, функция преобразования значения в ключ в общем случае необратима.
Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
31.03.2011, 01:40
| Ответить | Цитировать | Написать  
Способы реализации индексов
    #37191532
Фотография kdv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kdv
Участник
Индекс СпособовичТ.е. именно данные хранятся в индексе?
А при 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, видимость конкретной версии для конкретной транзакции определяется только номером и состоянием транзакции, создавшей конкретную версию. В ключах индекса этой информации нет. Значит, хоть ключ и содержит данные, для определения видимости сервер должен считать конкретную версию, чтобы понять, какой транзацкции что можно видеть.
...
Рейтинг: 0 / 0
31.03.2011, 04:51
| Ответить | Цитировать | Написать  
Способы реализации индексов
    #37191973
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
On 31.03.2011 0:06, Индекс Способович wrote:

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

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

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

Я что тут в преподаватели нанялся ?
Найди литературу, почитай. Хопкрофта книга была хорошая.
Ахо etc тоже.
Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
31.03.2011, 11:49
| Ответить | Цитировать | Написать  
Способы реализации индексов
    #37192071
Фотография SergSuper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SergSuper
Участник
MasterZiv> знаете что такое "вычислительно невозможно найти" )
Не, не знаю. Я знаю, что такое "можно найти" и знаю, что
такое "нельзя найти". А "вычислительно невозможно найти"
это очень похоже на "немножко беременна".
если на поиск потребуется миллиард лет - это "можно найти" или "нельзя найти"?
...
Рейтинг: 0 / 0
31.03.2011, 12:21
| Ответить | Цитировать | Написать  
Способы реализации индексов
    #37192115
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
On 31.03.2011 13:21, SergSuper wrote:

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

Это -- "можно найти". Нерешаемая задача и сложнорешаемая задача -- не одно и то же.
Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
31.03.2011, 12:38
| Ответить | Цитировать | Написать  
Способы реализации индексов
    #37192438
Фотография SergSuper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SergSuper
Участник
MasterZivOn 31.03.2011 13:21, SergSuper wrote:

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

Это -- "можно найти". Нерешаемая задача и сложнорешаемая задача -- не одно и то же.
т.е. никакой разницы нет между задачами которые, решаются считанным количеством тактов и и которые решаются годами?
"вычислительно невозможно найти" и подразумевает что найти можно только теоретически, перебором, для использования получения данных не предназначено
...
Рейтинг: 0 / 0
31.03.2011, 14:17
| Ответить | Цитировать | Написать  
Способы реализации индексов
    #37192855
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Siemargl
Участник
SergSuperMasterZivOn 31.03.2011 13:21, SergSuper wrote:

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

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

А ТС взял определение криптографического хэша и пытается присобачить его к СУБД. А тут никто не поймет,
зачем такие навороты в зоопарке БД.
...
Рейтинг: 0 / 0
31.03.2011, 17:02
| Ответить | Цитировать | Написать  
Способы реализации индексов
    #37192918
Bogdanov Andrey
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bogdanov Andrey
Участник
SiemarglУ "вычислительно невозможно найти" - граница меняется с каждым годом. Это нечеткое определение.Вы действительно понятие "сложность вычислений" не слышали, или прикидываетесь? Почитайте про классы сложности. Все очень строго определено. Граница никуда не меняется и никак от быстродействия современных компьютеров не зависит. А вот от достижений математической мысли зависеть может :)
...
Рейтинг: 0 / 0
31.03.2011, 17:25
| Ответить | Цитировать | Написать  
Способы реализации индексов
    #37193006
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Siemargl
Участник
Bogdanov Andrey,

В Вике все доступно объяснено на трех пальцах.
Но ТС наже в этом путается Индекс Способович3. Н(М) относительно легко (за полиномиальное время) вычисляется для любого значения М.
...
Рейтинг: 0 / 0
31.03.2011, 17:53
| Ответить | Цитировать | Написать  
25 сообщений из 150, страница 2 из 6
  2  все
Форумы / Сравнение СУБД [игнор отключен] [закрыт для гостей] / Способы реализации индексов
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=35&startmsg=37190020&tid=1552702]:
 0ms
get settings:
 10ms
get forum list:
 10ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 31ms
get topic data:
 9ms
get forum data:
 3ms
get page messages:
 53ms
get tp. blocked users:
 1ms
others: 12ms
total:  135ms
созд. / загр.: 135ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]