Здравствуйте, AndrewVK, Вы писали:
AVK>К тебе тот же вопрос — как обеспечить малое количество дисковых операций при добавлении или удалении элементов? Стандартная техника с бакетами, используемая в нетовских хештаблицах для диска мало подходит.
Если мне вернут моего Гарсиа-Молина, то я расскажу, как устроены хеш-индексы в СУБД. Там какая-то особенная хитрость применена для рехешинга при переполнении, благодаря чему вставки тоже ведут себя прилично. Конечно, никакие хеш-таблицы, реализованные c расчетом на произвольный доступ, в СУБД непригодны.

Здравствуйте, GlebZ, Вы писали:

GZ>То есть в случае 8 байтового значения индекс будет в два раза меньше. В случае guid'а еще больше.
Эффект от размра ключа вылезает только на очень больших таблицах, в несколько миллионов записей, а на маленьких его практически незаметно.
К тому же это PK, то есть вытягивание одной записи, а это одна из самых дешевых операций, тут нет необходимости выжимать максимальную производительность.

GZ> Как результат, у нас увеличивается вероятность что на мелких таблицах(коих иногда очень даже много) мы весь primary key уместим на одной странице. Это должно снизить нагрузку на кэш.
Плюс-минус пара страниц на кеш — болшой роли не играет, так что для малых размеров реально выигрыша практически не будет.

GZ> Во вторых, у нас в отличие от B дерева — нет надобности сравнивать значения. То есть в случае если все лежит в кэше, поиск значения мгновенный. Логарифметическая сложность поиска сохраняется, только в отличие от Nlog(N) получается log(N).
Если все в кеше, то это все просто другой порядок малости по сравнению с обращением к диску. К тому же, как я уже говорил, поиск одной записи не самая критичная ко времени операция.

GZ> Ну и еще мы получаем практически готовый эффективный join. Надо просто добавить сравнение.
К сожалению hash join эффективен далеко не всегда.

Здравствуйте, Serginio1, Вы писали:

AVK>>Он выгоднее в памяти. А вот работающий алгоритм для диска я пока не услышал.
S>http://zeus.sai.msu.ru:7000/programming/theory/sorting/sorting2.shtml#5_2
Из всего того что там сказано, к методам хэширования на диске относятся две фразы:
1.

Линейное хеширование: Если возникает потребность в расщеплении, то записи перераспределяются по блокам так, чтобы адресация осталась правильной.

Отпадает по понятным причинам — слишком дорогое это удовольствие.

2.

По базы данных: Тем не менее, похоже, что технология хэширования постепенно сольется с технологией B-деревьев и станет основной в мире баз данных.

Обнадеживает, но пока не актуально.

Здравствуйте, Merle, Вы писали:

M>К сожалению hash join эффективен далеко не всегда.

Это потому что он сначала строит хэш, а только потом его использует, а в слуаче хэш индекса он уже готов сразу.

Кстати, когда СУБД делает хеш-джоин, она ведь строит хэш, то есть где-то его хранит. А если он в память не помещается?

Здравствуйте, Sinclair, Вы писали:

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

Спасибо. Я как раз и интересуюсь статистикой: нужны ли произвольные джоины или достатоно только по ссылоным полям (FK). Это для проектирования языка запросов.

Здравствуйте, Merle, Вы писали:

M>Здравствуйте, Serginio1, Вы писали:

AVK>>>Он выгоднее в памяти. А вот работающий алгоритм для диска я пока не услышал.
S>>http://zeus.sai.msu.ru:7000/programming/theory/sorting/sorting2.shtml#5_2
M>Из всего того что там сказано, к методам хэширования на диске относятся две фразы:
M>1.

Линейное хеширование: Если возникает потребность в расщеплении, то записи перераспределяются по блокам так, чтобы адресация осталась правильной.

M>Отпадает по понятным причинам — слишком дорогое это удовольствие.
При фиксированнолм размере удовольствие бесплатное. Всё от задач.

А чем тебе не нравится Extendible Hashing. До миллиона элементов вполне приемлемая технология.
В этот размер умещается большинство справочников.
M>

По базы данных: Тем не менее, похоже, что технология хэширования постепенно сольется с технологией B-деревьев и станет основной в мире баз данных.

M>Обнадеживает, но пока не актуально.

Здравствуйте, Sinclair, Вы писали:

S>>Нас вообще-то должно волновать только "select folder.*, u.unreadSize".
S>Нет, это волнует прикладного программиста, который будет пользовать эту гипотетическую БД.

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

S>>Остальное, то что внутри запроса, как я понимаю, дело компилятора запроса.
S>А разработчиков БД как раз это и волнует. Точнее, волнует вообще возможность type inference.

А какие здесь проблемы. У любого выражения в типизированном языке (языке запросов) есть свой тип. И все.

S>>Имхо, оба способа должны присутствовать. И разве этого будет недостаточно?
S>Это ты здорово придумал. Вот только я не очень понял, на каком это языке. C# такого пока не позволяет. Я не очень внимательно слежу за тем, что будет позволено в C# 3.0.

Первый способ на текущем C# не сделать никак.
То есть вывод один: если хочется типизированного API, то необходимо явно объявлять указывать тип возвращаемой запросом строки.

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

S>В целом мне, конечно, идея нравится. Проблема только в том, что для обеспечения второго способа (точный именованный тип) тебе фактически нужен первый (а потом ты просто перекладываешь данные из анонимного типа в именованный путем явного вызова конструктора).

Блин. Каюсь. И так тоже не получится. Если только C# поддерживал бы C++ подобные шаблонные ужасы .

Здравствуйте, Sinclair, Вы писали:

S>Никто не собирается делать еще один компилятор C#-подобного языка.

Я вообще то этим как раз и занимаюсь . Для узкого круга задач (Системы, подобной 1С).

Здравствуйте, GlebZ, Вы писали:

AVK>>Ага, ты еще ТЗ попроси.
GZ>ТЗ нет. А вот vision — с удовольствием бы. Тогда было бы более понятно что строим и с кем конкурируем. И вообще границы задачи.

Если ты еще не понял — цель этого топика как раз и состоит в том, чтобы сформировать такой vision.

AVK>>На десктопе часто.
GZ>Никогда. Лучше я десять раз перекачаю лишние данные, чем каждый раз обращаться к серваку. А десктопами, особо не занимался.

С этого и надо начинать.

AVK>>Я серверные не использую, я использую клиентские. И здесь речь, ты еще не забыл, о настольной БД. Проблемы серверных БД меня в данном контексте не волнуют, особенно проблемы многопользовательского доступа.
GZ>Проблема серверных курсоров лежит в многопользовательском доступе, и только в нем. И больше нигде. Поэтому предлагаю размыть разницу между серверным и клиентским курсором. Тем более что у нас именно встроенная система.

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

AVK>>Еще как. А что, у тебя с этим какие то проблемы?
GZ>Я просто не понял, если ты держишь у себя результат join'a, то есть проекции от него, то каким образом ты его адресуешь? Или это только когда проекция одной таблицы?

Вместо джойна выбирается только таблица, которая содержит ключ. Например, в случае януса, самый тяжелый запрос джойнит таблицу сообщений с таблицей агрегатов по темам. Если использовать кейсет, то при выборке собственно кейсета этот джойн выкидывается и заменяется на банальный фильтр по форуму. А джойн при выборке данных уже не так страшен, потому что в 99% случаев дальше верхних двух десятков тем дело не идет.

GZ>На заключительном этапе мы пытаемся отрефакторить новое приложение так, чтобы пользователь хотя бы чайку при запросе не успел выпить. А достигается это рефакторингом запросов и схемы. А менять приложение в таком случае, не очень приятное занятие.

Спорно.

Здравствуйте, Merle, Вы писали:

M>1.

Линейное хеширование: Если возникает потребность в расщеплении, то записи перераспределяются по блокам так, чтобы адресация осталась правильной.

M>Отпадает по понятным причинам — слишком дорогое это удовольствие.

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

M>2.
M>

По базы данных: Тем не менее, похоже, что технология хэширования постепенно сольется с технологией B-деревьев и станет основной в мире баз данных.

M>Обнадеживает, но пока не актуально.

+1

Здравствуйте, Sinclair, Вы писали:

S>Вот такая вот петрушка. Надо копать в анонимные типы в третьем шарпе, чтобы понять, что там вообще можно сделать.

Спрашивай что конкретно интересует, я расскажу.

Здравствуйте, vdimas, Вы писали:

AVK>>Мало. Потому что GUID обладает замечательной особенностью — отпадает необходимость в генераторах или автоинкременторах в движке БД и операциях его считывания после добавления записи. Грубо говоря — я могу знать PK объекта даже не обращаясь к БД.

V>Собсно, я для этого использую счетчики в программе. И я тоже знаю ПК объекта заранее и даже могу понасоздавать в памяти графы связанных объектов и затем в один присест сохранить. Думаешь, дело упирается в генерацию ПК???

C Guid проще, связанность меньше. В твоем же случае придется передавать при создании внутрь объектов какой то контекст, содержащтй счетчики. Опять же заморочки с многопоточностью.

V>В одном из проектов, когда я оптимизировал ПК, то бишь уменьшил где только это возможно ширину данных (с 32 до 16 или даже 8 бит) у меня быстродействие базы выросло более чем вдвое. Ты же не забывай, что таблицы, которые хранят наибольшее число строк (сотни тысяч и миллионы), обычно представляют из себя некие "движения"

Ты не забывай, что речь идет не о БД для всяких ERP-подобных программ. Там другие решения, с другими требованиями.

V>Для того, чтобы не страдать переполнением малоразрядных счетчиков, я использую кеш удаленных ключей, для повторного их использования на новых объектах. В общем, все ради сужения типа, представляющего ключ, ибо это в разы повышает эффективность.

Насчет разов я сильно сомневаюсь. Я в свое время делал много тестов на эту тему — переход с int на guid в mssql отжирал максимум 20% производительности на очень мелких операциях.

Здравствуйте, Serginio1, Вы писали:

S> При фиксированнолм размере удовольствие бесплатное. Всё от задач.
Во-во, а задачи такие, что фиксированный размер только по большим праздникам.

S>А чем тебе не нравится Extendible Hashing.

требует наличия в основной памяти справочного дерева.

S>До миллиона элементов вполне приемлемая технология.
А после миллиона что делать?

S> В этот размер умещается большинство справочников.
А не справочников? А что делать если не уместится?

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

Здравствуйте, Merle, Вы писали:

M>Здравствуйте, Serginio1, Вы писали:

S>> При фиксированнолм размере удовольствие бесплатное. Всё от задач.
M>Во-во, а задачи такие, что фиксированный размер только по большим праздникам.

S>>А чем тебе не нравится Extendible Hashing.
M>

M>требует наличия в основной памяти справочного дерева.

S>>До миллиона элементов вполне приемлемая технология.
M>А после миллиона что делать?

S>> В этот размер умещается большинство справочников.
M>А не справочников? А что делать если не уместится?

M>Проблема в том что такой подход не обладает должной универсальностью и требует довольно серьезного расхода ресурсов, что в настольной системе вряд ли можно себе позволить.

Да??? На все если есть определённые кабы. Кроме того речь шла о не универсальности а возможности. Возможность такая есть.
Кроме того после определенного размера, не все дерево можно хранить в памяти. Все от реализации. В любом случае количество обращений к диску и вычислений двоичного поиска можно существенно снизить.А это для настольных систем более чем нужно.

Здравствуйте, Merle, Вы писали:

M>Здравствуйте, Serginio1, Вы писали:

S>> При фиксированнолм размере удовольствие бесплатное. Всё от задач.
M>Во-во, а задачи такие, что фиксированный размер только по большим праздникам.

S>>А чем тебе не нравится Extendible Hashing.
M>

M>требует наличия в основной памяти справочного дерева.

S>>До миллиона элементов вполне приемлемая технология.
M>А после миллиона что делать?

Вот не разобрался в сути алгоритма, а начинаешь критиковать.
Мы имеем дерево страниц. Алгортм таков сначало всй хранится в одной странице. При переполнении выделяется еще одна страница
в которую перемещаются данные с первым битом равным 1.
Так имеем дерево с разветвлением по первому биту. Затем при переполнении страницы она опять расчепляется на 2 и в дереве появляется узел но раздляет уже по 2 биту итд. Держать же само дерево можно на диске, первая страница так или иначе будет кэшировано вот и вся память. А выигрыш за счет дисковых операций очевиден.
S>> В этот размер умещается большинство справочников.
M>А не справочников? А что делать если не уместится?
Смотри выше
M>Проблема в том что такой подход не обладает должной универсальностью и требует довольно серьезного расхода ресурсов, что в настольной системе вряд ли можно себе позволить.
Обладает универсальностью. Просто надо уметь готовить.

Здравствуйте, Serginio1, Вы писали:

S> Да???
Да.

S>Кроме того речь шла о не универсальности а возможности. Возможность такая есть.
Нету, потому как не подходит под условие задачи.

S> В любом случае количество обращений к диску и вычислений двоичного поиска можно существенно снизить.
Каким образом? Если не все дерево в памяти хранить?

Здравствуйте, Serginio1, Вы писали:

S>Вот не разобрался в сути алгоритма, а начинаешь критиковать.
Я просто процитировал слова автора, где оговорено условие не подходящее под нашу задачу.

S> Держать же само дерево можно на диске, первая страница так или иначе будет кэшировано вот и вся память.
И чем это будет отличаться от B+?

S> А выигрыш за счет дисковых операций очевиден.
Очевиден лишний геморрой, и очевидно что выигрыша нет, так как все равно получаем B-дерево частично лежащее на диске. Та же конструкция, только в профиль, и ради чего спрашивается?
К тому же пойми, даже если мы получим здесь небольшой выигрыш, затраченных усилий это не оправдает, так как доставание одной записи не самая критичная операция.

S> Просто надо уметь готовить.
Во-во.

Здравствуйте, Merle, Вы писали:

M>Здравствуйте, Serginio1, Вы писали:

S>>Вот не разобрался в сути алгоритма, а начинаешь критиковать.
M>Я просто процитировал слова автора, где оговорено условие не подходящее под нашу задачу.

S>> Держать же само дерево можно на диске, первая страница так или иначе будет кэшировано вот и вся память.
M>И чем это будет отличаться от B+?

S>> А выигрыш за счет дисковых операций очевиден.
M>Очевиден лишний геморрой, и очевидно что выигрыша нет, так как все равно получаем B-дерево частично лежащее на диске. Та же конструкция, только в профиль, и ради чего спрашивается?
Не совсем. Это модификация и не Б дереват, бинарного дерева по хэшу. Внути страницы понятно может сортироваться.
А насчет гемороя и лишних усилий, то алгоритм такой хэш таблицы, намного проще. Правжа нужно учитывать возможную вырожденность.
Опять же всё зависит от задач.
M>К тому же пойми, даже если мы получим здесь небольшой выигрыш, затраченных усилий это не оправдает, так как доставание одной записи не самая критичная операция.


Во первых я сам не являюсь сторонником, но выступаю за возможность и определённые бенефиты при использовании. Чем больше способов, тем больше гибкость. А категоричность не мой подход.
S>> Просто надо уметь готовить.
M>Во-во.

Здравствуйте, Merle, Вы писали:

M>Здравствуйте, Serginio1, Вы писали:

M>К тому же пойми, даже если мы получим здесь небольшой выигрыш, затраченных усилий это не оправдает, так как доставание одной записи не самая критичная операция.

А для меня, например, критичная. Я вот ORM делаю, и там есть две основные оптимизации: подгрузка ассоциированных объектов батчем в отдельном запросе, т.е. where id in (:p0, :p1, ...), и подгрузка ассоциироваых объектов джоинами в том же запросе. И первый вариант работает в Oracle откровенно плохо. Намного хуже чем ждоины, хотя вроде почему бы...

Здравствуйте, Serginio1, Вы писали:

S> Не совсем. Это модификация и не Б дереват, бинарного дерева по хэшу. Внути страницы понятно может сортироваться.
И в чем разница?

S> А насчет гемороя и лишних усилий, то алгоритм такой хэш таблицы, намного проще.
Проще чем B+?

S> Правжа нужно учитывать возможную вырожденность. Опять же всё зависит от задач.
Понимаеш, тут как бы не стоит задачи разработать Оракл, чтобы на каждый сценарий свой тип индекса держать... Нужен подход +/- с одинаковым успехом решающий максимально широкий круг задач.