Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Сравнение СУБД Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
 Интересный (?) результат.  [new]
shuklin
Member

Откуда: Харьков
Сообщений: 799
По поводу навигаций. Если трактовать навигацию как переход от текущего объекта к следующему - предыдущему в пределах некоторого упорядоченного списка (коллекции объектов), то такую навигацию поддерживать ядром ОБД так же неэффективно как и ядром РБД.
- если мы реализуем упорядоченный список в виде array of pointers то в перспективе некторого времени выполнения процесса ядра БД это повлечет проблемы. Определить заранее максимальное колличество элементов в массиве не эффективно - так как большую часть времени массив будет содержать nulls. Проводить изменение размеров этого списка повлечет значительную дефрагментацию памяти (как RAM так и HD).
- реализовать одно, либо дву-связный список так же неэффективно, так как время доступа к некоторому N элементу списка будет зависить от этого N (в отличие от предыдущего случая, в котором время константно)

В результате я вижу только одну эффективную реализацию членства объекта в некоторой коллекции - с использованием древовидного индекса (хэштаблицы). Но, такой индекс не может обеспечить эффективную реализацию порядка в пределах коллекции.
Если в качестве ключа для объекта использовать его порядковый номер в коллекции, то после удаления объектов в дереве возникнут дыры, и придется проводить переиндексацию (балансировку), что опять повлечет потерю производительности. Таким образом отказавшись поддерживать некоторый определенный порядок объектов в коллекции, кроме "случайного", заданного деталями реализации индекса получим возможность эффективной реализации коллекций в ядре ОБД.

Так же как и в РБД в ОБД будет иметь место придание некоторого порядка объектам в процессе материализации результатов запроса. Это может быть либо "случайный" порядок определяемый реализацией индекса либо порядок определяемый дополнительной сортировкой.

Говорить о наличии порядка у объектов в смысле наличия следующего и предыдущего, без явного задания такового (любым эффективном с точки зрения приложения способом) будет некорректно, так как порядок, определяемый деталями реализации индекса будет в большинстве случаев полностью бесполезен для приложения, а приложение, опирающееся на такой порядок, при любой оптимизации или изменении алгоритма индексирования перестанет адекватно функционировать.
17 окт 05, 14:11    [1975128]     Ответить | Цитировать Сообщить модератору
 Re: Интересный (?) результат.  [new]
vadiminfo
Member

Откуда: Обнинск
Сообщений: 4802
shuklin

навигацию поддерживать ядром ОБД так же неэффективно как и ядром РБД.

Вы думаете, что ядру РБД нужно поддерживать навигацию, потому что отношение якобы соответствует строке таблицы? Или почему? Ить раньше думали, что ядро РМД поддерживает ассоциативный доступ к данным.
17 окт 05, 15:34    [1975644]     Ответить | Цитировать Сообщить модератору
 Re: Интересный (?) результат.  [new]
mod
Member

Откуда:
Сообщений: 2318
Учите Perl, коллега...
17 окт 05, 15:45    [1975721]     Ответить | Цитировать Сообщить модератору
 Re: Интересный (?) результат.  [new]
shuklin
Member

Откуда: Харьков
Сообщений: 799
vadiminfo
Вы думаете, что ядру РБД нужно поддерживать навигацию,


Я думаю, что ядру ОБД не нужно поддерживать упорядоченность объектов в коллекции так же как ядру РБД поддерживать упорядоченность строк в таблице.
17 окт 05, 17:20    [1976325]     Ответить | Цитировать Сообщить модератору
 Re: Интересный (?) результат.  [new]
shuklin
Member

Откуда: Харьков
Сообщений: 799
mod
Учите Perl, коллега...

А а какое имеет отношение перл к деталям реализации ядра субд? Просветите, коллега.
17 окт 05, 17:21    [1976335]     Ответить | Цитировать Сообщить модератору
 Re: Интересный (?) результат.  [new]
aZm
Member

Откуда:
Сообщений: 2357
shuklin, order by спасет церебрум :) ибо, выполнять физическую пересортировку на каждой вставке... а если эта вставка массовая... да на табличку с парой сотен мильёнов записей... одумайтесь пока не поздно :)

---
Vae victis!
17 окт 05, 17:25    [1976357]     Ответить | Цитировать Сообщить модератору
 Re: Интересный (?) результат.  [new]
shuklin
Member

Откуда: Харьков
Сообщений: 799
aZm
shuklin, order by спасет церебрум :) ибо, выполнять физическую пересортировку на каждой вставке... а если эта вставка массовая... да на табличку с парой сотен мильёнов записей... одумайтесь пока не поздно :)


Именно. Хотя вопрос ставился шире. Похоже что данная ситуация характерна для любых СУБД а не только РБД или ОБД.

По поводу Cerebrum - в текущей доступной для довнлоада версии в качестве ключа в индексе для объекта используется его порядковый номер в коллекции. С инсертами проблем нет. а вот при удалении нужно или перестроить индекс или допускать дырки в дереве. И то и то неприемлимо. Так что да. Следующую версию будет спасать order by.
17 окт 05, 18:21    [1976666]     Ответить | Цитировать Сообщить модератору
 Re: Интересный (?) результат.  [new]
pavelvp
Member

Откуда:
Сообщений: 673
shuklin
С инсертами проблем нет. а вот при удалении нужно или перестроить индекс или допускать дырки в дереве. И то и то неприемлимо.

А какой же индекс используется?
Так что да. Следующую версию будет спасать order by.

Т.е. постоянные сортировки приемлемы?
17 окт 05, 18:44    [1976752]     Ответить | Цитировать Сообщить модератору
 Re: Интересный (?) результат.  [new]
pavelvp
Member

Откуда:
Сообщений: 673
aZm
shuklin, order by спасет церебрум :) ибо, выполнять физическую пересортировку на каждой вставке... а если эта вставка массовая... да на табличку с парой сотен мильёнов записей... одумайтесь пока не поздно :)

Правильно! Долой индексы!
17 окт 05, 18:49    [1976767]     Ответить | Цитировать Сообщить модератору
 Re: Интересный (?) результат.  [new]
shuklin
Member

Откуда: Харьков
Сообщений: 799
pavelvp

Правильно! Долой индексы!


Почему долой, я их собираюсь "инвертировать". ;-)
17 окт 05, 19:25    [1976822]     Ответить | Цитировать Сообщить модератору
 Re: Интересный (?) результат.  [new]
shuklin
Member

Откуда: Харьков
Сообщений: 799
pavelvp
А какой же индекс используется?

в Cerebrum я применил 3х уровневое дерево - позволяет находить узел за три операции доступа к узлам. Сейчас я поддерживаю только индексацию по ObjectId поэтому любой объект можно найти за 3 относительно затратные по времени операции. JOIN двух объектов требует 6 таких операций. Итого получаем константное время выборки объекта независимо от объема БД.
pavelvp
Т.е. постоянные сортировки приемлемы?

Сейчас - да. В будущем врядли. Как получится. Проблем с ними больше чем пользы.
17 окт 05, 19:30    [1976832]     Ответить | Цитировать Сообщить модератору
 Re: Интересный (?) результат.  [new]
pavelvp
Member

Откуда:
Сообщений: 673
Забавный ответ. Какое-то странное, безымянное, 3-х уровневое дерево... Почему именно три уровня? Как оно организовано? Узлы могут содержать произвольное количество ключей? Как оно хранится на диске?

Ниже привожу цитату, которая вызвала первоначальный вопрос:
shuklin
С инсертами проблем нет. а вот при удалении нужно или перестроить индекс или допускать дырки в дереве.

Странное дерево какое-то...
17 окт 05, 21:00    [1976956]     Ответить | Цитировать Сообщить модератору
 Re: Интересный (?) результат.  [new]
Andreww
Member [заблокирован]

Откуда:
Сообщений: 1752
2 pavelvp

>Какое-то странное, безымянное, 3-х уровневое дерево

При этом время затраченное на поиск элемента в нём не зависит от кол-ва элементов.

Это ещё более странное свойство, тут дело пахнет нехилым открытием в области дискретной математики и премией Тьюринга как минимум.

У известных структур всё же зависит, у B*tree - O(logN) и т.д., но зависимость от кол-ва есть .....
17 окт 05, 21:11    [1976978]     Ответить | Цитировать Сообщить модератору
 Re: Интересный (?) результат.  [new]
Gluk (Kazan)
Member

Откуда:
Сообщений: 9365
Andreww
У известных структур всё же зависит, у B*tree - O(logN) и т.д., но зависимость от кол-ва есть .....


Если число уровней константно, то константно количество обращений к каждому уровню. Неконстантно время поиска на уровне, либо есть ограничение на количество хранимых узлов. Так что премия Тьюринга накрылась.

2 Шуклин

БГ, кстати, советует молодым программистам прежде чем искать сотрудничества с ним любимым

ПОЧИТАТЬ КНУТА
18 окт 05, 09:46    [1977517]     Ответить | Цитировать Сообщить модератору
 Re: Интересный (?) результат.  [new]
aZm
Member

Откуда:
Сообщений: 2357
pavelvp
aZm
shuklin, order by спасет церебрум :) ибо, выполнять физическую пересортировку на каждой вставке... а если эта вставка массовая... да на табличку с парой сотен мильёнов записей... одумайтесь пока не поздно :)

Правильно! Долой индексы!


индекс - отнюдь не обязательная весч. он может быть, его может не быть.
18 окт 05, 09:54    [1977557]     Ответить | Цитировать Сообщить модератору
 Re: Интересный (?) результат.  [new]
mod
Member

Откуда:
Сообщений: 2318
shuklin
mod
Учите Perl, коллега...

А а какое имеет отношение перл к деталям реализации ядра субд? Просветите, коллега.

А как Perl работает с массивами?
18 окт 05, 10:20    [1977715]     Ответить | Цитировать Сообщить модератору
 Re: Интересный (?) результат.  [new]
Andreww
Member [заблокирован]

Откуда:
Сообщений: 1752
2 Gluk (Kazan)

>>Неконстантно время поиска на уровне

Ну дык ! Я о чём и толкую.

Просто невнимательно прочитал :(

Скорость поиска узла - константа. Но толку от этого чуть, если в каждом узле придётся перелопачивать список.
18 окт 05, 10:25    [1977739]     Ответить | Цитировать Сообщить модератору
 Re: Интересный (?) результат.  [new]
shuklin
Member

Откуда: Харьков
Сообщений: 799
Gluk (Kazan)
Если число уровней константно, то константно количество обращений к каждому уровню. Неконстантно время поиска на уровне, либо есть ограничение на количество хранимых узлов.


Все правильно. Система 32 битная. Больше чем 4 млрд объектов в одном хранилище разместить не сможет. (Если спортирую на 64 бита, принципиально ситуация не изменится). Дерево 3х уровневое (для 64 бит будет 4х уровневое). На первом уровне хранятся узлы для первых 10 бит. На втором - для вторых 10 бит и на последнем - для младших 12 бит. Каждый узел является array из указателей на дочерние узлы. Поиск указателя на кажом уровне занимает один такт процессорного времени. + переходы с уровня на уровень. Вобщем затраты весьма невелеки и действительно не зависят от конкретного колличества объектов в бд, который в текущей 32 битной версии не может быть более чем 2 млрд (так как старший бит я зарезервировал про запас). На самом деле максимальное колличество объектов может оказаться еще меньше, но точно оценить трудно, так как это зависит от их размера - от того сколько кластеров уровня VCRM будет отведено в среднем под один объект, но в VCRM старший бит не зарезервирован, так что по два кластера на объект ничему не помешают.
18 окт 05, 12:44    [1978628]     Ответить | Цитировать Сообщить модератору
 Re: Интересный (?) результат.  [new]
shuklin
Member

Откуда: Харьков
Сообщений: 799
mod
shuklin
mod
Учите Perl, коллега...

А а какое имеет отношение перл к деталям реализации ядра субд? Просветите, коллега.

А как Perl работает с массивами?


А там что, есть некий новый механизм, отсутствующий у господина Кнута?
Просто если есть, и действительно решает описанную проблему эффективно, я с удовольствием позаимствую идею. Хотя шото меня смутные сомнения терзают, что ничего там нового нету (((
18 окт 05, 12:47    [1978645]     Ответить | Цитировать Сообщить модератору
 Re: Интересный (?) результат.  [new]
Gluk (Kazan)
Member

Откуда:
Сообщений: 9365
Извини друк, но фундаментализма в изобретении велосипедов я не понимаю.
Почему ты так не любишь Кнута ???
18 окт 05, 12:48    [1978651]     Ответить | Цитировать Сообщить модератору
 Re: Интересный (?) результат.  [new]
shuklin
Member

Откуда: Харьков
Сообщений: 799
pavelvp
Забавный ответ. Какое-то странное, безымянное, 3-х уровневое дерево... Почему именно три уровня? Как оно организовано? Узлы могут содержать произвольное количество ключей? Как оно хранится на диске?

Ничего сверх необычного. Каждый узел представляет собой массив из фиксированного для этого уровня колличества указателей на дочерние узлы. Можете для аналогии посмотреть синхронизированное линейное дерево - таже идея но в применении к нейронным сетям и распознающим автоматным грамматикам http://www.shuklin.com/ai/ht/ru/ai00008f.aspx Поэтому поиск указателя дочернего узла в пределах текущего узла занимает примерно один такт процессорного времени (если конвейером пренебречь. а то и меньше). Основное время занимает переключение между уровнями (узлами), так как даже в случае полного попадания в кэш все равно пару условных переходов выполнить придется. Как оно на диске организованно - извините вопрос сложный и требует развернутого ответа. Статья на эту тему готова примерно на 30%, может в следующем году и опубликую. Гляньте для начала http://www.shuklin.com/ai/ht/ru/ke01050f.aspx VnpiCIDL используется при сериализации на диск самым активным образом.

pavelvp
Ниже привожу цитату, которая вызвала первоначальный вопрос:
shuklin
С инсертами проблем нет. а вот при удалении нужно или перестроить индекс или допускать дырки в дереве.

Странное дерево какое-то...


А тут смешаны несколько уровней. Собственно индексы и их использование при моделировании РБД средсвами Cerebrum http://www.shuklin.com/ai/ht/ru/cerebrum/lessons/Cerebrum.Samples.Streams-01.aspx Проблемы возникают при удалении уже созданного в БД объекта в виде строки из таблицы. Таблица на данный момент (в той версии что доступна для свободного довнлоада http://www.shuklin.com/ai/ht/ru/cerebrum/) моделируется в виде двух деревьев индексов - колонки и строки. В качестве ключа в этом индексе выступает порядковый номер строки в таблице соответсвующий данному объекту. Если удалить объект из таблицы, то в индексе останется дырка, которую надо заштопать проводя переиндексацию строк начиная с удаленной строки. Переиндексацию мне реализовывать просто в лом. Поэтому следующая версия будет лишена этого недостатка путем инвертирования дерева - это не большая работа, пару классов на C# перепедалить.
18 окт 05, 13:05    [1978772]     Ответить | Цитировать Сообщить модератору
 Re: Интересный (?) результат.  [new]
shuklin
Member

Откуда: Харьков
Сообщений: 799
Gluk (Kazan)
Извини друк, но фундаментализма в изобретении велосипедов я не понимаю.
Почему ты так не любишь Кнута ???


Это реплика ко мне по поводу "Хотя шото меня смутные сомнения терзают, что ничего там нового нету"? Если так, то сорри, выразился действительно неточно.

Следует читать

Я сомневаюсь что в perl применяются методы работы с массивами являющиеся более эффективными чем те что описаны у Кнута. Если это действительно так, то я буду рад использовать идею.
18 окт 05, 13:08    [1978795]     Ответить | Цитировать Сообщить модератору
 Re: Интересный (?) результат.  [new]
mod
Member

Откуда:
Сообщений: 2318
shuklin вот тебе про массивы в Perl
http://www.computerbooks.ru/books/Programming/Book-Perl/3/Index3.htm
И уж точно никто там заранее количество элеменитов в массиве не определяет - ибо в Perl массивы динамические, помимо того, что ты прочтёшь в статье - не обязательно все элементы массива в Perl одного типа - типы в Perl не описываются, а определяются по содержимому переменной...
А ассоциированные (хэш) массивы в perl это ваще отдельная песня!
18 окт 05, 13:26    [1978917]     Ответить | Цитировать Сообщить модератору
 Re: Интересный (?) результат.  [new]
mod
Member

Откуда:
Сообщений: 2318
Gluk (Kazan)
Извини друк, но фундаментализма в изобретении велосипедов я не понимаю.
Почему ты так не любишь Кнута ???

Не брат, ты прикинь как круто сделать квадратные колёса у велосипеда, а к ним механизмы для того чтобы колёса с грани на грань могли вращатся придумать и рессоры чтобы не укачивало. Это же супер! Ибо круглые колёса как-то примитивно, не современно(вон ещё в каких веках до нашей эры придумали)...
18 окт 05, 13:30    [1978947]     Ответить | Цитировать Сообщить модератору
 Re: Интересный (?) результат.  [new]
mod
Member

Откуда:
Сообщений: 2318
На вон тебе ещё про ассоциативные массивы
http://docs.h1.ru/perldocs/perl8x.html.
http://web.opennet.ru/docs/RUS/perl_hash/index.html
Як грится РМД форевер!
18 окт 05, 13:35    [1978985]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
Все форумы / Сравнение СУБД Ответить