Immutable object - Философия программирования

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

V>>В вики не смотрел?
V>>В общем, второе определение я оставлю лишь недобросовестным фанам функционального программирования, бо оно неверно в общем случае.
S>И какое это имеет отношение к изобретённому вами определению?

Ну... попробуй как-то иначе расшифровать переход от "что" к "как", с интересом послушаю.

V>>Неодинаково. В общем случае одна операция РИ требует нескольких операций из базиса РА, обратное неверно.
S>Ну начинается. Вы собрались ещё и метрику "количества операций" вводить?

Мне уровень "как" представляется как уровень с большими подробностями, относительно уровня "что". Иначе пропадает сам смысл наличия уровня "что" над "как".

S>Это всё равно заведёт вас в тупик — именно поэтому ваша идея определения декларативности не получила широкого распространения.

Идея не моя, это первоначальное значение самого слова. Я наоборот возражал против тупика (вернее — необоснованности), который начинается там, где функциональную парадигму пытаются безусловно приписать к декларативной, и ты ту же мысль здесь повторил многократно. Вот более удачное определение декларативного ЯП:

Декларати́вные языки́ программи́рования — это языки программирования высокого уровня, в которых программистом не задается пошаговый алгоритм решения задачи ("как" решить задачу), а некоторым образом описывается, "что" требуется получить в качестве результата. Механизм обработки сопоставления с образцом декларативных утверждений уже реализован в устройстве языка. Типичным примером таких языков являются языки логического программирования (языки, основанные на системе правил).
В программах на языках логического программирования соответствующие действия выполняются только при наличии необходимого разрешающего условия.

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

V>>Опять же, операции базиса РА не описывают характер результата, а только лишь действия над ним.
S>Да ладно! Как раз характер результата они и описывают. Скажем, оператор "сигма" никаких действий не описывает. Он просто говорит "результат будет содержать только кортежи, удовлетворяющие указанному ограничению". Что это по-вашему, как не характер результата?

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

Основная концепция декларативной семантики заключается в том, что смысл каждого оператора не зависит от того, как этот оператор используется в программе.

Наример, любой объект пролога может быть использован как для непосредственных вычислений, так и для задания условия уравнения. Аннотация типов в статически-типизированных языках, независимо от императивности, это намного большая декларативность, чем высосанная из пальца декларативность функциональщиков в ф-ии "y x = x + 1", бо эту т.н. "декларативную ф-ию" нельзя использовать иначе как для непосредственного вычисления по ней. Эту ф-ию нельзя будет использовать как предикат, как цель или как ограничение внутри собственной программы, хотя несомненно она является целью для низлежащего механизма — компилятора, так же является декларативным ограничением для подсистемы вывода типов. Но декларативность аннотации типов работает аналогично в императивных языках, не хуже функциональных.

Для некоего низлежащего уровня реализации, перебирающего мн-во кортежей поэлементно, уровень сигмы РА будет несомненно декларативным (я на этой относительности настаиваю), бо операция РА будет задавать условие получения результата. Итого, на уровне РА операция считается "атомарной" и "безусловной", т.е. выполняемой независимо ни от чего, но на низлежащем уровне реализации некие действия над конкретными кортежами будут зависеть от истинности заданного условия.

К тому же, твоя сигма — это классический фильтр, используемый для преобразования информации, но этот фильтр на уровне РА нельзя использовать "наоборот", в кач-ве детектора, бо он описывает именно механику поэлементной фильтрации и не умеет быть детектором самостоятельно, в рамках одной операции. На уровне РИ, заметь, сигма используется как детектор.

V>>Мнэээ... Речь изначально была об O(M+N), если я ничего не пропустил. Сорри, не могу здесь поддержать твой очередной спор с самим собой.
S>К счастью, в форуме записаны все ходы. "Изначально" речь шла о том, что вы почему-то заложили O(N*M*K) в стоимость операции join трёх составляющих:
S>

S>Насчет порядка: если некая соединительная операция из 3-х (грубо) составляющий выполняется в 4 раза быстрее, что каждая в среднем стала выполняться быстрее в корень 3-й степени из 4.

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

Это и называется "общий случай", который правомернее любых частных. Даже когда по равенству атрибутов, но в отсутствии индексов, то сортировка (т.е. построение индексов на лету) по алгоритмам внешней сортировки для одного из аргументов даст похожую оценку сложности.

S>А для star-join с тремя составляющими стоимость будет O(N*log(M*K)).

А это при чем?

S>Так что если всё вместе выполняется в 4 раза быстрее, то каждая из операций ускорилась вовсе не в корень третьей степени из четырёх.

Тут можно вспомнить о кластерном индексе, из-за которого началось. Если мы выбираем данные не по кластерному индексу, то в общем случае каждая новая строка таблицы справа в каждом join будет требовать нового чтения всей страницы ради чтения одной записи, что приводит к немыслимому К при этих формулах. А если все строки участников физически отсортированы внутри страниц как надо для этого join, то вид формул будет совсем другой и K при них будет минимальный. Собсно, вот то предложение насчет избыточности ради дополнительных искусственных кластерных индексов я получил далеко не сразу. Была куча экспериментов на технике, на которой неоптимальное решение было видно невооруженным глазом, в отличие от сейчас.

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

Нормальная оценка джинов для боевого применения. А твои "более реальные условия" — это фактически минибазульки, а не "реальные условия". Для реляционных СУБД всегда надо исходить из данных, больших ОП, иначе стоит подумать о другой технологии.

S>Многие приложения, построенные по принципу select N+1 и client-side join, прекрасно работают на встроенных движках, и даже на тупом ISAM.
S>И, естественно, со страшной силой начинают сливать при переходе на клиент-серверную архитектуру, потому что там это честный roundtrip с парсингом и исполнением каждого запроса. Поэтому всякий раз, как я вижу упоминание тормозов при переходе с фокспра на оракл или с аксесса на MSSQL, я начинаю подозревать худшее.

Я че-то не понял объяснения, почему клиентский движок может выполнить select N+1 быстрее серверного? За счет чего именно? К тому же, тормоза были не там, а из-за многократно большего требования к размеру ОП (физическое уменьшение размера данных помогло) и чувствительности к организации кластерных индексов. И к тому же, SQL выдает первые данные раньше, чем закончивает полную выборку, т.е. по мере готовности, при чем тут roundtrip? Или неужели клиентский движок парсит запросы быстрее? А если это не текстовые запросы, а вызов процедур или view?

S>Но это, естественно, не единственное объяснение. Понятно, что, скажем, в линейном чтении с локального диска любой dBase порвёт любой сиквел как тузик грелку. Поэтому я и написал, что не могу делать выводы о вашем опыте, не глядя в исходники приложения.

Это бы еще куда ни шло... Неприятно, что технологии локальных движков рвут SQL-сервера, даже когда первые работали по сетевому диску до этого. И кстати, ORACLE тех времен смотрелся всяко получше MS SQL в отклике, хотя последний гораздо проще в обслуживании и программировании.

V>>Пока что согласился только насчет оценок быстродействия кластерного индекса, и то, там бабка на двое сказала. Бо даже лишняя страница по тем временам на том размере ОП (т.е. не та политика кеширования была), с теми скоростями жестки дисков и т.д., могла и дать такую ощутимую разницу.
S>Да-да, разницу в "десять-пятнадцать страниц". Я понял. Но я же говорю не о том, что ваш конкретный проект работал как-то не так. Я говорю ровно про то, что ваш подход к исследованию мира даёт вот такие вот результаты: вы увидели некий эффект, и вместо того, чтобы разобраться, поставили кластерные индексы на полочку "тормозное г".

Нет, было сказано, что для первичных ключей они оказались в большинстве сценариев нехороши. Справедливости ради, для справочных данных кластерные индексы для основного ключа таки хороши (это очевидно). Так же хороши везде для основных ключей, где сами таблицы невелики (влазят в единицы 1-2 физических страниц), независимо от сценариев, это тоже утверждалось. К тому же, ты пытаешься сфокусировать спор на сценарии выбора одной строки и сам же допускаешь одно лишнее логическое чтение на такую выборку. Где-нить в середине join это запросто может быть по лишней логической выборке на каждую включенную строку. Что на малой возможности буферирования из-за размеров ОП могло превращать приличную долю логических чтений в тормознутые физические на тех винтах с 30-50ms seek. Ты просто не понял, что я имел ввиду насчет сложности воспроизведения эффекта на современных машинах. Хотя, это зависит лишь от масштабов.

S>С тех пор и память стала другая, и диски несколько другие, но ментальная модель кластерных индексов в вашей голове изменений не претерпела — потому, что там монолит. Нет границы между архитектурой кластерных индексов и её реализацией.

Я лишь вижу, что те сценарии, которые я рассматривал как "очень некоторые", ты рассматриваешь как "почти все"...

Ес-но, отсюда разный взгляд на вещи.

V>>Боюсь, на современных ОС и современном железе воспроизвести сей эффект будет сложновато.
S>Боюсь, вы по-прежнему не понимаете предмета обсуждения. Количество логических чтений в MS SQL никак не зависит ни от ОС, ни от железа.

Эффект был не в логических чтениях, а в абсолютном быстродействии. Самая тяжеловесная операция, где всё вылизывалось — это полный перерасчет операционного дня. Много join, и в ширь и в глубь. Лишние прочитанные страницы на каждую строку где-нить в глубине join могли оказаться фатальными. Действительно заметно помогли вот те "искуственные индексы", т.е. банальная избыточность, где по каждой такой избыточности построен кластерный индекс именно под конкретный сценарий, чтобы к дереву индекса практически не обращались, а шел перебор связанного списка страниц.

Кстати, еще момент. В конечном итоге пришел к по-позиционному расчету в цикле. Почему в цикле, а не в виде одного запроса? В виде единого запроса работало в несколько раз медленней даже после всех игр с уровнями блокировок и даже с хинтами без блокировок вообще (что было недопустимо, но гонялось для экспериментов). К тому же, торможение единого запроса фактически не давало работать остальным, пока выполнялся запрос, а по-позиционный расчет в этом плане был более "легок" для базы, позволял работать остальным... и сам выполнялся в итоге быстрее! Т.е. сотни транзакций выполнялись быстрее одной транзакции. Тоже есть о чем подумать... Всего навсего в тот же самый запрос добавили ограничение на одну позицию и прогнали по всем задействованным за день позициям в цикле. Подозреваю, что тоже дело было в объемах промежуточных данных, что болезненно.

S>Всё правильно. Вот только я никаких противоречий и не декларировал. Я объяснял, что одних законов РА недостаточно для функционирования реальных СУБД.

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

S>И что нужно понимать, где начинаются "дополнительные подробности". Иначе можно запросто попасть впросак, написав бред типа "стоимость операции join пропорциональна O(N*M)".

Для декартового произведения это так по-определению. Другое дело, что ты сложность считаешь исключительно в логических чтениях, считая, что порождение результата затем бесплатно. А оно зависит от много чего, т.е. чтение является лишь частью от всей сложности. Ведь не читает же SQL Server с диска медленнее, чем локальный движок базы данных? Скорее, наоборот, бо его поставили на гораздо более мощную технику. Т.е. тормоза не только на чтении данных. Далее. Для несортированных N и M в пределе сложность можно считать близкой к такой, из-за стоимости алгоритмов внешней сортировки при построении индекса "на лету", и из-за более дорогой записи в сравнении с чтением. Понятно, что коль индекс строится не по всем полям, а лишь по части, то мы можем получить оч. низкий К при этой оценке, но сама полная сложность в пределе именно такова.

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

V>>Потому и напомнил. Что различия реализации и модели есть, а для 99% сценариев не помеха. А где помеха — там есть совсем простые паттерны обхода ограничения реализации.
S>В программировании все помехи — исключительно в голове. Именно поэтому так важно хорошо во всём разбираться.

Угу, возвращаемся к самому началу. "Хорошо" — означает подробно? Означает знать как все устроено или хотя бы как устроено аналогичное или таки неважно?

V>>И я показал, что таки не очень мешает. И оценка в 1% от таких сценариев — это еще очень оптимистично, бо я с переполнениями борюсь даже далеко не в каждом проекте, где многие тысячи целочисленных переменных.
S>Ну я рад за ваши проекты. Это всего лишь означает, что ваши программы — некорректны, просто вас не везде поймали за руку ваши QA.

Нет, это означает, что были взяты нужные типы данных для нужных платформ. Это в C# интерфейсы коллекций завязали на платформенно-независимый int, что есть большая грабля сама по себе, а в С++ используется платформенно-зависимый тип size_t. И вообще, беззнаковая арифметика в почете, бо позволяет делать на одно сравнение меньше для выяснения соответствия требуемому диапазону.

S>И, кстати, из двух предоженных вами решений проблемы с переполнением при построении компаратора одно не работает.

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

V>>Ну-ну, не разгоняйся так быстро. Я такими аппаратами пользуюсь, что поверь, придумать их самому, специально под реализации вещественных чисел — ну просто никак. Например, в области обнаружения и обработки сигналов. Всего навсего погрешности округлений представляют как аддитивный шум, поэтому всё несоответствие реализации и модели сводится к оценке шума (тем более достоверно известен его спектральный состав), т.е. к достижению требуемого отношения сигнал/шум. И для этого тоже аппарат есть — "энтропийный": H + Y = 1 (Взаимосвязь энтропии и информации). А формула самой энтропии физику по образованию должна быть известна. Точно так же как должны быть известны правила сложения источников белого шума, например. Всё решаемо, не надо паники. Фактически выводится на кончике пера для каждого оператора/преобразователя для конкретной разрядности и соотношения граничной интересующей частоты и частоты квантования.
S>Ну вот видите, как здорово. Я же не говорю, что нерешаемо. Я говорю, что надо понимать, что "чистая" математика, где все сигналы без шумов, тут неприменима. И вы это понимаете, т.к. пользуетесь специальными моделями, куда входят разрядности и частоты квантования.

Нет, применима. Математика — это уже модель сама по себе, она не существует как объективная реальность. Более того, это ср-во построения моделей. Какую захотим построить модель, такую и построим. (вернее, которая подойдет — такую и пользуем). Где отношение сигнал-шум не так уж важно, а важна лишь вероятность срабатывания, например, (распознавание DTMF, например), то там вообще погрешность вычислений может доходить до 75% (свертка с прямоугольным сигналом, т.е. выполнение простых +- вместо сложения ряда, умноженного на отсчеты синусоиды). Но этого оказалось достаточно для нужной вероятности обнаружения сигнала, бо сам алгоритм такой, что работает даже тогда, когда сигнал в 4 раза меньшей мощности, чем белый фоновый шум. Вот тебе объективный случай, когда заведомо грубая реализация математической модели с погрешностью до 75% вполне подходит, потому что удовлетворяет требованиям алгоритма. Потому что после фильтрации почти равномерный спектральный состав мощности шума этой погрешности оказывается крайне незначительным в нужной полосе.

(на остальное потом)

Здравствуйте, vdimas, Вы писали:
V>Мне уровень "как" представляется как уровень с большими подробностями, относительно уровня "что". Иначе пропадает сам смысл наличия уровня "что" над "как".
Это достаточно наивное представление, равно как и попытки располагать "что" над "как". В связи с теоремой Чёрча, бывает всякое — в том числе, и описание "как", более компактное, чем "что".

V>Идея не моя, это первоначальное значение самого слова.
Ну щас прямо.

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

V>>>Опять же, операции базиса РА не описывают характер результата, а только лишь действия над ним.
S>>Да ладно! Как раз характер результата они и описывают. Скажем, оператор "сигма" никаких действий не описывает. Он просто говорит "результат будет содержать только кортежи, удовлетворяющие указанному ограничению". Что это по-вашему, как не характер результата?

V>Нет инвариантности использования, обязательного для декларативности, т.е. ты эти действия не можешь использовать "наоборот", например как задание для уравнения.
V>

V>Основная концепция декларативной семантики заключается в том, что смысл каждого оператора не зависит от того, как этот оператор используется в программе.

Вы очень ловко одной рукой критикуете википедию, а другой тут же ссылаетесь на неё же. Статья, на которую вы ссылаетесь, это всего лишь заглушка, в которой написано несколько бессмысленных фраз. Перейдите в англоязычную версию — там очень внятно написано, что такое декларативное программирование и чем оно отличается от императивного.
Никакой "основной концепции" там, естественно, нет.

V>Для некоего низлежащего уровня реализации, перебирающего мн-во кортежей поэлементно, уровень сигмы РА будет несомненно декларативным (я на этой относительности настаиваю), бо операция РА будет задавать условие получения результата.
Ну вот видите. Всё-таки декларативна.

V>К тому же, твоя сигма — это классический фильтр, используемый для преобразования информации, но этот фильтр на уровне РА нельзя использовать "наоборот", в кач-ве детектора, бо он описывает именно механику поэлементной фильтрации и не умеет быть детектором самостоятельно, в рамках одной операции. На уровне РИ, заметь, сигма используется как детектор.
А можно пояснить подробнее, что значит "использовать наоборот"?

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

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

V>Даже когда по равенству атрибутов, но в отсутствии индексов, то сортировка (т.е. построение индексов на лету) по алгоритмам внешней сортировки для одного из аргументов даст похожую оценку сложности.
Непохожую. Учите матчасть.

V>Тут можно вспомнить о кластерном индексе, из-за которого началось. Если мы выбираем данные не по кластерному индексу, то в общем случае каждая новая строка таблицы справа в каждом join будет требовать нового чтения всей страницы ради чтения одной записи, что приводит к немыслимому К при этих формулах.
При каких формулах? Мы говорим о K при логарифме, и ничего немыслимого в нём нет. В любом случае это не K при N, как вам кажется.

V>Нормальная оценка джинов для боевого применения. А твои "более реальные условия" — это фактически минибазульки, а не "реальные условия".
Вы не читаете то, что я вам пишу. Дело не в размере базы, а в том, какие индексы применяются. Получение O(N*M) на джойне по равенству атрибутов, при произвольном размере базы — это признак кривых рук у DBA.

V>Я че-то не понял объяснения, почему клиентский движок может выполнить select N+1 быстрее серверного? За счет чего именно?
За счёт того, вестимо, что все данные для него локальны, зачастую еще и лежат прямо в ОП, а транзакции — это условность. Поэтому ему всё равно, что выполнять — один селект на 100 записей или 100 селектов по одной записи. А для честного сервера, который принимает запросы по сети, 100 селектов по одной записи сильно хуже, чем один селект на 100 записей. Ваш К.О.

V>Нет, было сказано, что для первичных ключей они оказались в большинстве сценариев нехороши. Справедливости ради, для справочных данных кластерные индексы для основного ключа таки хороши (это очевидно). Так же хороши везде для основных ключей, где сами таблицы невелики (влазят в единицы 1-2 физических страниц), независимо от сценариев, это тоже утверждалось. К тому же, ты пытаешься сфокусировать спор на сценарии выбора одной строки и сам же допускаешь одно лишнее логическое чтение на такую выборку. Где-нить в середине join это запросто может быть по лишней логической выборке на каждую включенную строку.
То, что я фокусируюсь на сценарии выбора одной строки — это я вам одолжение делаю. В сценариях с join кластерный индекс порвёт некластерный вообще в мелкие ошмётки. Ну и, опять же, ваше утверждение было именно про выборку одного значения.

V>Я лишь вижу, что те сценарии, которые я рассматривал как "очень некоторые", ты рассматриваешь как "почти все"...

Я привёл свои соображения про то, какие факторы влияют на выбор кластерных/некластерных индексов. Вы подняли их на смех, не дав труда задуматься, какие случаи — "почти все", а какие — "очень некоторые".
V>Ес-но, отсюда разный взгляд на вещи.
Разный взгляд на вещи у нас оттого, что я понимаю, как устроены кластерные индексы, и как работает движок в MS SQL, а вы — нет.

V>Эффект был не в логических чтениях, а в абсолютном быстродействии. Самая тяжеловесная операция, где всё вылизывалось — это полный перерасчет операционного дня. Много join, и в ширь и в глубь. Лишние прочитанные страницы на каждую строку где-нить в глубине join могли оказаться фатальными. Действительно заметно помогли вот те "искуственные индексы", т.е. банальная избыточность, где по каждой такой избыточности построен кластерный индекс именно под конкретный сценарий, чтобы к дереву индекса практически не обращались, а шел перебор связанного списка страниц.
Ой, как интересно. А в прошлый раз вы рассказывали ровно наоборот — вы заменяли кластерные индексы на некластерные, и сокращали размер ключа с 4х байт до 2х.
Видите, как заметно меняется прошлое, стоит разобраться в вопросе, да?

V>Подозреваю, что тоже дело было в объемах промежуточных данных, что болезненно.
А не надо подозревать. Надо пользоваться SQL Profiler и вдумчиво читать документацию. Ваши подозрения приводят к чудовищным заблуждениям.

S>>Всё правильно. Вот только я никаких противоречий и не декларировал. Я объяснял, что одних законов РА недостаточно для функционирования реальных СУБД.

V>Ты утверждал, что им нет места. Более всего категорично при выборе, какой индекс использовать для физического плана и как. Я потому и зацепился, что аж стало интересно — а какой же теоретический аппарат тогда используют???
Оценки размеров результатов запросов — распределение Зипфа; информацию о статистиках; семантическую информацию (например, наличие constraints). Именно это и используют. А с точки зрения РА все планы запросов одинаковы. Выбрать ничего не получится.

S>>И что нужно понимать, где начинаются "дополнительные подробности". Иначе можно запросто попасть впросак, написав бред типа "стоимость операции join пропорциональна O(N*M)".

V>Для декартового произведения это так по-определению.
Ну так join — это не декартово произведение. Ваш К.О.

V>Другое дело, что ты сложность считаешь исключительно в логических чтениях, считая, что порождение результата затем бесплатно. А оно зависит от много чего, т.е. чтение является лишь частью от всей сложности. Ведь не читает же SQL Server с диска медленнее, чем локальный движок базы данных?
Конечно же читает медленнее. У него архитектура движка другая. Учите матчасть. Для того, чтобы приблизиться к скорости чтения ФС, движок MS SQL пришлось сильно переработать. RTFM по слову FILESTREAM. ISAM-движки при линейном чтении приближаются к скорости чистого чтения с ФС.

V>Скорее, наоборот, бо его поставили на гораздо более мощную технику. Т.е. тормоза не только на чтении данных. Далее. Для несортированных N и M в пределе сложность можно считать близкой к такой, из-за стоимости алгоритмов внешней сортировки при построении индекса "на лету", и из-за более дорогой записи в сравнении с чтением.
V>Понятно, что коль индекс строится не по всем полям, а лишь по части, то мы можем получить оч. низкий К при этой оценке, но сама полная сложность в пределе именно такова.
Ок, давайте оценим стоимость построения индекса "на лету" и посмотрим, какая получится оценка. Если вам лень — подсмотрите в учебнике. Я чувствую, вас ждёт неожиданное открытие.

S>>В программировании все помехи — исключительно в голове. Именно поэтому так важно хорошо во всём разбираться.
V>Угу, возвращаемся к самому началу. "Хорошо" — означает подробно? Означает знать как все устроено или хотя бы как устроено аналогичное или таки неважно?
Конечно. Чем лучше разбираешься — тем лучше. Но тут важен такой момент: знать всё — нереально. Поэтому важно эффективно применять те знания, которые уже есть. И вот тут очень важно понимать границы применимости того или иного.

V>Нет, это означает, что были взяты нужные типы данных для нужных платформ. Это в C# интерфейсы коллекций завязали на платформенно-независимый int, что есть большая грабля сама по себе, а в С++ используется платформенно-зависимый тип size_t. И вообще, беззнаковая арифметика в почете, бо позволяет делать на одно сравнение меньше для выяснения соответствия требуемому диапазону.

Ок, не будем копать в эту сторону.

V>Оно даже не компилируется, если ты про приведение к Int64... писал поздно и быстро. Ожидал сие возражение там же сразу, оно было очевидным после отправки без предварительного просмотра...
Даже если бы компилировалось — там сам подход неверен.

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

V>>Мне уровень "как" представляется как уровень с большими подробностями, относительно уровня "что". Иначе пропадает сам смысл наличия уровня "что" над "как".
S>Это достаточно наивное представление, равно как и попытки располагать "что" над "как".

"Что" и "как" — это вполне интуитивные понятия, имеющие однозначную языковую семантику, а вовсе не наивные. Тебя че-то несет не в ту степь. Так нам придется предварительно договариваться о смысле слов, из которых будут состоять наши посты... правда я не знаю, в каком алфавите...

S>В связи с теоремой Чёрча, бывает всякое — в том числе, и описание "как", более компактное, чем "что".

Есть такая теорема, которая прямо определяет где у неё "что", а где "как"? Или ты как обычно решил подменить слово "декларативный" на "функциональный"?

V>>Идея не моя, это первоначальное значение самого слова.
S>Ну щас прямо.

Т.е. таки разногласия в понимании взаимоотношений понятий "как" и "что"?

V>>Нет инвариантности использования, обязательного для декларативности, т.е. ты эти действия не можешь использовать "наоборот", например как задание для уравнения.
V>>

V>>Основная концепция декларативной семантики заключается в том, что смысл каждого оператора не зависит от того, как этот оператор используется в программе.

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

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

S>Никакой "основной концепции" там, естественно, нет.

Знака равенства м/у ортогональными понятиями тоже нет. Да и видел я твои ссылки на английскую википедию по РА — большей путаницы, недосказанности, отсутствия последовательности и прочей каши еще поискать. Писатели-любители составляли, через поиск по гуглу, а не специалисты в описываемой области.

V>>Для некоего низлежащего уровня реализации, перебирающего мн-во кортежей поэлементно, уровень сигмы РА будет несомненно декларативным (я на этой относительности настаиваю), бо операция РА будет задавать условие получения результата.
S>Ну вот видите. Всё-таки декларативна.

printf("%d", x); — точно так же декларативен для некоей низлежащей системы, как и сигма. Эти спекуляции ведут в никуда, ведь ты сначала отвергаешь взаимоотношение РИ и РА как уровней с разными степенями подробностей, а потом пытаешься исопльзовать еще более низкий уровень как некое док-во декларативности более высокого по-отношению к нему. Не выйдет. Мы способов реализации формул РА не обсуждали и не будем.

V>>К тому же, твоя сигма — это классический фильтр, используемый для преобразования информации, но этот фильтр на уровне РА нельзя использовать "наоборот", в кач-ве детектора, бо он описывает именно механику поэлементной фильтрации и не умеет быть детектором самостоятельно, в рамках одной операции. На уровне РИ, заметь, сигма используется как детектор.
S>А можно пояснить подробнее, что значит "использовать наоборот"?

Чем фильтрация сигнала от обнаружения отличается? Тем, что фильтрация в общем случае налагает лишь некоторые ограничения, которыми должен обладать сигнал, но реальная конструкция сигнала может быть гораздо сложнее, чем возможно выделить одним фильтром или даже несколькими фильтрами, т.к. кодирование информации может случается разное, она может быть закодирована как статические или даже динамические х-ки, получаемые сразу по многим фильтрам. Поэтому каждый фильтр "просто делает своё дело", не подозревая, как будут использоваться результаты его труда. Например, все структурные формулы РИ приводимы к одному квантору EXISTS, который использует сигму как детектор по своему определению, но после перевода конкретного квантора EXISTS в формулу РА, состоящую из продукций, проекций и ограничений, ты не можешь по каждой отдельной выделенной операции судить, какой же был вид исходного (целевого) квантора. Т.е. в каждом отдельном операторе РА непонятно, как же было сформулировано "что" в исходном операторе РИ.

V>>Тут можно вспомнить о кластерном индексе, из-за которого началось. Если мы выбираем данные не по кластерному индексу, то в общем случае каждая новая строка таблицы справа в каждом join будет требовать нового чтения всей страницы ради чтения одной записи, что приводит к немыслимому К при этих формулах.
S>При каких формулах? Мы говорим о K при логарифме, и ничего немыслимого в нём нет. В любом случае это не K при N, как вам кажется.

Эта К будет при каждой операции чтения, т.е. при N, независимо от затрат на обход индекса. Эти логарифмические затраты просто не видны обычно на фоне чтения страниц "вразнобой".

V>>Нормальная оценка джинов для боевого применения. А твои "более реальные условия" — это фактически минибазульки, а не "реальные условия".
S>Вы не читаете то, что я вам пишу. Дело не в размере базы, а в том, какие индексы применяются. Получение O(N*M) на джойне по равенству атрибутов, при произвольном размере базы — это признак кривых рук у DBA.

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

V>>Я че-то не понял объяснения, почему клиентский движок может выполнить select N+1 быстрее серверного? За счет чего именно?
S>За счёт того, вестимо, что все данные для него локальны, зачастую еще и лежат прямо в ОП, а транзакции — это условность. Поэтому ему всё равно, что выполнять — один селект на 100 записей или 100 селектов по одной записи. А для честного сервера, который принимает запросы по сети, 100 селектов по одной записи сильно хуже, чем один селект на 100 записей. Ваш К.О.

Фи, как низкопробно. Т.е. ты считаешь, что основная лишняя нагрузка на СУБД — это работа по обслуживанию запросов, передачи по сети каждый раз заново заголовков таблиц вместе с данными и т.д.?

Тогда действительно, относительные тормоза SQL-серверов проявлялись бы там, где размер служебной передаваемой информации превышает полезную. Ну и еще вспомним, что по named-pipes народ не часто подключает MS SQL, а про работу нагиля в TCP забывает и не конфигурит TCP-соединение, чтобы нагиль не мешал, и не умеет выполнить более 5-ти запросов в секунду на одном соединении... и потом рассуждают на таком печальном уровне о roundtrip-ах. Кароч, это всё детский сад, а не объяснение. MS SQL сливает даже там, где требуются просто тяжеловесные вычисления по сложному запросу, а не "куча мелких запросов". ИМХО от того, что локальные базы агрессивно юзают маппинг файлов и более эффективно (в плане обработки) располагают свои данные. По крайней мере, не надо читать конец страницы, чтобы пройтись бинарным поиском по данным. Попробуй ради прикола нарисуй на C++ программу, которая будет перебирать строки внутри страницы по смещению, указанному в конце страницы, как ты показал для MS SQL, то бишь использовать банально +1 косвенности к адресации... Да это пипец полный для пробежки по данным, таким макаром. И ко всему прочему добавляется копирование в отдельный участок памяти целой страницы и обратно, даже если нам надо изменить всего байт...

S>То, что я фокусируюсь на сценарии выбора одной строки — это я вам одолжение делаю. В сценариях с join кластерный индекс порвёт некластерный вообще в мелкие ошмётки.

И как он порвет, если редко бывает так, что по одной таблице выполняется join только по одному и тому же индексу? Кластерный же один только. Т.е. для одного сценария порвет, а другие сольют.

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

Ну и ты сам увидел на лишнее чтение на строку. Поэтому если делается join не по кластерному, то имеем лишнее логическое чтение на каждую строку.

V>>Я лишь вижу, что те сценарии, которые я рассматривал как "очень некоторые", ты рассматриваешь как "почти все"...

S>Я привёл свои соображения про то, какие факторы влияют на выбор кластерных/некластерных индексов. Вы подняли их на смех, не дав труда задуматься, какие случаи — "почти все", а какие — "очень некоторые".

ИМХО, случай, когда для некоей таблицы во всех сценариях выборки, происходящих вокруг нее встречается только один вид join, это таки "очень некоторые".

V>>Ес-но, отсюда разный взгляд на вещи.
S>Разный взгляд на вещи у нас оттого, что я понимаю, как устроены кластерные индексы, и как работает движок в MS SQL, а вы — нет.

Я рассказал о внешних эффектах, которые были обнаружены и обкатаны многократно во всех вариантах. Стоит вернуться и попытаться соотнести свое представление о кишках этой СУБД и причин производимых ими эффектов.

V>>Эффект был не в логических чтениях, а в абсолютном быстродействии. Самая тяжеловесная операция, где всё вылизывалось — это полный перерасчет операционного дня. Много join, и в ширь и в глубь. Лишние прочитанные страницы на каждую строку где-нить в глубине join могли оказаться фатальными. Действительно заметно помогли вот те "искуственные индексы", т.е. банальная избыточность, где по каждой такой избыточности построен кластерный индекс именно под конкретный сценарий, чтобы к дереву индекса практически не обращались, а шел перебор связанного списка страниц.

S>Ой, как интересно. А в прошлый раз вы рассказывали ровно наоборот — вы заменяли кластерные индексы на некластерные, и сокращали размер ключа с 4х байт до 2х.
S>Видите, как заметно меняется прошлое, стоит разобраться в вопросе, да?

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

V>>Подозреваю, что тоже дело было в объемах промежуточных данных, что болезненно.
S>А не надо подозревать. Надо пользоваться SQL Profiler и вдумчиво читать документацию. Ваши подозрения приводят к чудовищным заблуждениям.

Гы, профайлер от 7-ки и был основным инструментом. Только он не объяснит, почему несколько транзакций в процедуре в цикле с доп. условием к запросу дешевле одной транзакции без условий. Показал он тебе больше промахов кеша, дальше что? Проведя несколько построчных запросов тоже кеш смениться многократно... Просто было интересно следующее: почему надо делать искусственный построчный прогон для уменьшения промахов кеша, если он должен нечто аналогичное делать сам? Ну и, конечно, сам факт работы одновременно других людей с базой вносит свои коррективы, для более короткой транзакции зачистка кеша каким-нить конкурирующим запросом не так болезненна. Да и размер изолированных данных и всяких их реплик начинает играть рояль... Это я все пишу насчет того, что измерять производительность теоретически, одними только логическими чтениями, фактически бесполезно в реальных условиях. Твой подход работает только там, где остальными описанными факторами можно пренебречь, например, когда имеем многократный запас в производительности и памяти относительно окучиваемых задач.

Ну и конфигурация самого сервака — это было нечто...сейчас толком никто не парится, оставляют значения по умолчанию. Например, чего стоил один только ключ располагать временные таблицы в памяти. В зависимости от сценариев это могло как добавить резко эффективности, так и наоборот.

Ну и во всех гайдлайнах настоятельно MS советует отделять оперативные данные от исторических первой строчкой рекомендаций. Причем, и даже разносить их по разным серверам. Дык, а в твоей системе координат, коль речь идет о разных таблицах, какая фиг разница, не правда ли? Ведь количество логических чтений независимо для независимых запросов...

В общем, картинка ясна. Упоминая зачем-то термин "промышленные СУБД", ты, тем не менее, не особо сталкивался с "промышленными" соотношениями объемов данных, уровня конкурентности соединений и возможностей техники. Да еще небось база работает в тепличных условиях трехзвенки, коль идут нелепые рассуждения о roundtrip... нелепые для случая, когда >90% логики программы выполняется внутри SQL-сервера, т.е. когда у нас почти всегда один запрос и один ответ, даже если сервер в ответ возвращает последовательность из сотни различных рекордсетов.

В общем, мне сложно работать К.О. для сценариев, которых не видел... приводить как аргумент сценарии из 100 коротких запросов к СУБД, которая работает как отдельный процесс или как отдельная машина — это рассуждения о кривизне рук, более ни о чем...

V>>Ты утверждал, что им нет места. Более всего категорично при выборе, какой индекс использовать для физического плана и как. Я потому и зацепился, что аж стало интересно — а какой же теоретический аппарат тогда используют???
S>Оценки размеров результатов запросов — распределение Зипфа; информацию о статистиках; семантическую информацию (например, наличие constraints). Именно это и используют. А с точки зрения РА все планы запросов одинаковы. Выбрать ничего не получится.

Какая разница, как конкретно устроена оценочная ф-ия? Чем дальше, тем больше будет методик составления сей оценочной ф-ии и способов представления статистики для нее. Мы уже давно договорились, что ее вид f(x1, x2, x3, ...), т.е. обычный черный ящик. Я утверждал, что породить всевозможные комбинации последовательностей операций для последующей оценки весовой ф-ией можно как раз с помощью аппарата РА. Вот это ты и отрицаешь до сих пор, и я хочу таки услышать, какой для этого исопльзуется аппарат. Мне плевать на конкретную оценочню ф-ю, расскажи, как строиться и модифицируется план запросов, который потом оценивается. Ты спорил лишь потому, что не считаешь индексы за декомпозицию исходной таблицы и всё еще продолжаешь рядом приводить нелепые примеры, подтверждая свое непонимание происходящего:

V>Суть я уловил, но мне любопытен был хоть какой-нить пример на пальцах. В голову только пока приходит предположение, что операция сравнения по какому-нить атрибуту "тяжелая", т.е. начинает заметно влиять на результат, чтобы имело смысл выполнить эти сравнения как можно позже, жертвуя взамен минимальной мощностью промежуточных результатов.
На пальцах — у нас часть предиката может соответствовать некоторому индексу, поэтому имеет смысл сначала сделать выборку по ней, а потом уже выполнять по оставшейся части.
При этом индексов может быть много, и надо выбирать, как именно резать предикат.

Такого рода ответы уже просто лень комментировать. Ведь это и есть тот самый перебор вариантов формул РА. Я фиг его знает почему ты решил, что для этих вещей исопльзуется какая-то особая, недоступная простым смертным, технология... Хотя в деле организации индексов мало что поменялось с выхода первых СУБД.

S>>>И что нужно понимать, где начинаются "дополнительные подробности". Иначе можно запросто попасть впросак, написав бред типа "стоимость операции join пропорциональна O(N*M)".

V>>Для декартового произведения это так по-определению.
S>Ну так join — это не декартово произведение. Ваш К.О.

Это смотря какой join и как организованы данные.

V>>Другое дело, что ты сложность считаешь исключительно в логических чтениях, считая, что порождение результата затем бесплатно. А оно зависит от много чего, т.е. чтение является лишь частью от всей сложности. Ведь не читает же SQL Server с диска медленнее, чем локальный движок базы данных?
S>Конечно же читает медленнее. У него архитектура движка другая. Учите матчасть. Для того, чтобы приблизиться к скорости чтения ФС, движок MS SQL пришлось сильно переработать. RTFM по слову FILESTREAM. ISAM-движки при линейном чтении приближаются к скорости чистого чтения с ФС.

Какой нах FILESTREAM, когда речь идет о страницах с обычными данными? Насчет "приближаются к скорости чистого чтения" — это иди учи матчасть сам... Не приближаются, а в точности равны, бо работают через memory-mapped file. Дело, конечно, в неумении автоматически детектить моменты, когда требуется конкурентность, от моментов, когда не особо требуется. Это я намекаю, что уровней изоляции во встроенных движках обычно поменьше, а сценарий простой полной блокировки очень дешевы в условиях малого кол-ва одновременных запросов, но когда сами запросы относительно тяжелы. Но MS SQL, похоже, всегда создает копии страниц в ОП (хотя сами страницы, скорее всего читает так же через memory-mapped file), и работает уже с ними... ИМХО, если стоимость запроса была известна заранее, то вполне мог бы быть некий "порог" конкурентности для конкретной таблицы или целого файла данных, чтобы работать с данными по месту.

V>>Понятно, что коль индекс строится не по всем полям, а лишь по части, то мы можем получить оч. низкий К при этой оценке, но сама полная сложность в пределе именно такова.
S>Ок, давайте оценим стоимость построения индекса "на лету" и посмотрим, какая получится оценка. Если вам лень — подсмотрите в учебнике. Я чувствую, вас ждёт неожиданное открытие.

Построение индекса — это и есть сортировка, чего там смотреть-то? В общем случае построение индекса выливается во внешнюю сортировку, а ее стоимость зависит от соотношения размеров буферов в ОП и общего объема данных. Осталось учесть, что стоимость записи многократно больше стоимости чтения... А если временные таблицы расположены на том же диске, что и данные, и головка диска дергается то на чтение исходных данных, то на запись промежуточных, то там вообще труба выходит... И эту "трубу", что характерно, ты не увидишь в SQL Profiler, бо он не покажет проседание производительности от дергания головки жесткого диска. И там такое может выйти, что любыми оценками в терминах логических чтений можно пренебречь как незначащими... Вы хоть раз замеряли эффект от установки SORT_IN_TEMPDB? Я чувствую, тебя ждёт неожиданное открытие.

V>>Нет, это означает, что были взяты нужные типы данных для нужных платформ. Это в C# интерфейсы коллекций завязали на платформенно-независимый int, что есть большая грабля сама по себе, а в С++ используется платформенно-зависимый тип size_t. И вообще, беззнаковая арифметика в почете, бо позволяет делать на одно сравнение меньше для выяснения соответствия требуемому диапазону.
S>

Ок, не будем копать в эту сторону.

Ну и зря... бо в C# действительно приходится бодаться с переполнениями, странно что народ так редко возмущается. Отсутствие банального typedef размножает какую-нить простейшую проблему многократно по коду, вместо того, чтобы дать возможность справиться с ней раз и навсегда в одном месте.

V>>Оно даже не компилируется, если ты про приведение к Int64... писал поздно и быстро. Ожидал сие возражение там же сразу, оно было очевидным после отправки без предварительного просмотра...
S>Даже если бы компилировалось — там сам подход неверен.

Приведение к Int64 было обязательно для выяснения знака операции через вычитание. Мы просто решали не ту проблему и не с того конца. Проблема-то в том, что генерики не поддерживают статические ф-ии, поэтому нужен интерфейс компаратора, но результат работы компаратора, в свою очередь, надо зафиксировать в некоем типе, не зависящем от типа аргумента. Почему там int, а не enum {less/before, equal, greater/after}? Вот тебе любезно подложенная грабля by design, которая своим происхождением вовсе не обязана тому, что ты пытался на ее примере показать.

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

V>"Что" и "как" — это вполне интуитивные понятия, имеющие однозначную языковую семантику, а вовсе не наивные.
Наивно представление о том, что "как" обязательно предоставляет больше информации, чем "что".

V>Т.е. таки разногласия в понимании взаимоотношений понятий "как" и "что"?
Разногласия в понимании того, чем отличаются декларативное представление программ от императивного.

V>Ты утверждал, что иммутабельное означает декларативное.
Нет. Я утверждал, что отсутствие побочных эффектов означает декларативное. Причём, естественно, не случайное отсутствие побочных эффектов, а такое, которое с гарантией.

V>printf("%d", x); — точно так же декларативен для некоей низлежащей системы, как и сигма.
Ничего подобного. printf() работает с консолью и меняет её состояние. Поэтому порядок вызова printf-ов важен, и printf — императивен на 100%.

V>Эти спекуляции ведут в никуда, ведь ты сначала отвергаешь взаимоотношение РИ и РА как уровней с разными степенями подробностей,
Да нет там никаких разных степеней подробностей. РА и РИ взаимно однозначно отображаются друг на друга — см. теорему Кодда.

S>>А можно пояснить подробнее, что значит "использовать наоборот"?

V>Чем фильтрация сигнала от обнаружения отличается? Тем, что фильтрация в общем случае налагает лишь некоторые ограничения, которыми должен обладать сигнал, но реальная конструкция сигнала может быть гораздо сложнее, чем возможно выделить одним фильтром или даже несколькими фильтрами, т.к. кодирование информации может случается разное, она может быть закодирована как статические или даже динамические х-ки, получаемые сразу по многим фильтрам. Поэтому каждый фильтр "просто делает своё дело", не подозревая, как будут использоваться результаты его труда. Например, все структурные формулы РИ приводимы к одному квантору EXISTS, который использует сигму как детектор по своему определению, но после перевода конкретного квантора EXISTS в формулу РА, состоящую из продукций, проекций и ограничений, ты не можешь по каждой отдельной выделенной операции судить, какой же был вид исходного (целевого) квантора. Т.е. в каждом отдельном операторе РА непонятно, как же было сформулировано "что" в исходном операторе РИ.
Ок, это понятно. Непонятно только, при чём тут декларативность vs императивность. Вместо них противопоставляется декомпозированное описание и монолитное.

V>Эта К будет при каждой операции чтения, т.е. при N, независимо от затрат на обход индекса. Эти логарифмические затраты просто не видны обычно на фоне чтения страниц "вразнобой".
Эти логарифмические затраты обычно и определяют количество чтений страниц.

V>Еще раз, эта сложность у операции декартова произведения по-определению.
Join — это не декартово произведение.
V>Я знаю, что ты настаиваешь на оценке исключительно логического чтения. Но, логические не значат физические и не только на чтение с диска нужны ресурсы.
Я вас разочарую — CPU-затраты на join ведут себя с той же асимптотикой, что и на логические чтения. Вот только K при этих O там совсем другой.

V>Фи, как низкопробно. Т.е. ты считаешь, что основная лишняя нагрузка на СУБД — это работа по обслуживанию запросов, передачи по сети каждый раз заново заголовков таблиц вместе с данными и т.д.?

Основная лишняя нагрузка — это парсинг запроса, построение плана, использование метаданных. Для интереса, попробуйте замерить, сколько стоит выполнить select 0 на удалённом MS SQL.

Рассуждения про внутреннее устройство СУБД я поскипаю, т.к. не могу без слёз их читать.

V>И как он порвет, если редко бывает так, что по одной таблице выполняется join только по одному и тому же индексу? Кластерный же один только. Т.е. для одного сценария порвет, а другие сольют.
Ну, то есть другими словами, если в join придётся таки применять некластерный индекс, то всё резко станет плохо. Отлично, вы постепенно начинаете понимать, как всё работает.

V>Ну и ты сам увидел на лишнее чтение на строку. Поэтому если делается join не по кластерному, то имеем лишнее логическое чтение на каждую строку.
Правильно. Это и есть основной недостаток некластерных индексов.

V>ИМХО, случай, когда для некоей таблицы во всех сценариях выборки, происходящих вокруг нее встречается только один вид join, это таки "очень некоторые".
Угу. А теперь попробуйте мне доказать, что для этой таблицы кластерный индекс вовсе не нужен. Вы же такой их противник, нет?

V>Я рассказал о внешних эффектах, которые были обнаружены и обкатаны многократно во всех вариантах. Стоит вернуться и попытаться соотнести свое представление о кишках этой СУБД и причин производимых ими эффектов.
У вас рассказы о внешних эффектах волшебным образом меняются по ходу беседы. Из этого можно сделать банальный вывод, что применяемая вами методика исследования мира не даёт полезных результатов, зато даёт вредные.

S>>Ой, как интересно. А в прошлый раз вы рассказывали ровно наоборот — вы заменяли кластерные индексы на некластерные, и сокращали размер ключа с 4х байт до 2х.
S>>Видите, как заметно меняется прошлое, стоит разобраться в вопросе, да?

V>Я упоминал каждый из способов, который давал прибавки к эффективности, многократно. Нигде ничего не меняется. Да, заменял кластерные индексы по уникальному ключу на некластерные, а кластерные оставлял для неуникальных (внешних, например, или индексов для поиска).
Ну вот это уже больше похоже на правду. И прекрасно согласуется с теми критериями, которые я приводил 40 постов назад, а вы смеялись.

V>Ну и во всех гайдлайнах настоятельно MS советует отделять оперативные данные от исторических первой строчкой рекомендаций. Причем, и даже разносить их по разным серверам. Дык, а в твоей системе координат, коль речь идет о разных таблицах, какая фиг разница, не правда ли? Ведь количество логических чтений независимо для независимых запросов...

Вы уже один раз посмеялись над моими знаниями в СУБД. Предлагаю не продолжать — опять ведь в лужу сядете.

V>Какая разница, как конкретно устроена оценочная ф-ия?
Как бы устройство оценочной функции принципиально — именно оно определяет способность СУБД выбрать оптимальный план.

V>Чем дальше, тем больше будет методик составления сей оценочной ф-ии и способов представления статистики для нее. Мы уже давно договорились, что ее вид f(x1, x2, x3, ...), т.е. обычный черный ящик.
Я не знаю, с кем и о чём вы договорились. Вижу только, что никакой литературы об устройстве оптимизаторов запросов вы не читали, и для вас эта область помечена "тут живут драконы".

V>Я утверждал, что породить всевозможные комбинации последовательностей операций для последующей оценки весовой ф-ией можно как раз с помощью аппарата РА.
Используется расширенный аппарат РА — в нём отношения аннотированы дополнительной информацией. В частности, есть информация о том, какие отношения эквивалентны, и насколько они эквивалентны. Что и позволяет оптимизатору запрос по таблице превращать в запрос по индексу.

V>Вот это ты и отрицаешь до сих пор, и я хочу таки услышать, какой для этого исопльзуется аппарат. Мне плевать на конкретную оценочню ф-ю, расскажи, как строиться и модифицируется план запросов, который потом оценивается.
V>Я фиг его знает почему ты решил, что для этих вещей исопльзуется какая-то особая, недоступная простым смертным, технология... Хотя в деле организации индексов мало что поменялось с выхода первых СУБД.
Почему недоступная-то? Всё доступно. Я ссылку на учебник дал. То, чего там нет, легко найти в публикациях. Просто применяемый аппарат шире, чем классическая РА.

V>Это смотря какой join и как организованы данные.

V>Какой нах FILESTREAM, когда речь идет о страницах с обычными данными?
Ну вот "страницы с обычными данными" никогда вам не дадут скорость чтения, близкую к ФС. Попробуйте сами сравнить скорость отдачи данных со скоростью чтения с диска — это нетрудно.

V>Насчет "приближаются к скорости чистого чтения" — это иди учи матчасть сам... Не приближаются, а в точности равны, бо работают через memory-mapped file.
Ну вы же только что сами мне рассказывали про то, что логические чтения — не единственные затраты?
V>Дело, конечно, в неумении автоматически детектить моменты, когда требуется конкурентность, от моментов, когда не особо требуется. Это я намекаю, что уровней изоляции во встроенных движках обычно поменьше, а сценарий простой полной блокировки очень дешевы в условиях малого кол-ва одновременных запросов, но когда сами запросы относительно тяжелы. Но MS SQL, похоже, всегда создает копии страниц в ОП (хотя сами страницы, скорее всего читает так же через memory-mapped file), и работает уже с ними...
Нет, не создаёт. Зачем вы продолжаете оперировать домыслами, когда можно просто пойти в документацию и почитать?
Кстати, вы же вроде бы исходники смотрели? Я понимаю, что это враньё, но вы уж врите согласованно. Неужто вы бы не заметили копирования страниц, если смотрели даже на выравнивание данных внутри страницы?

V>ИМХО, если стоимость запроса была известна заранее, то вполне мог бы быть некий "порог" конкурентности для конкретной таблицы или целого файла данных, чтобы работать с данными по месту.
Ну, расскажите мне, для чего MS SQL будет копировать страницы.

V>Построение индекса — это и есть сортировка, чего там смотреть-то?
Вы зря не выполняете домашние задания. Так вы ничему не научитесь.

V>В общем случае построение индекса выливается во внешнюю сортировку, а ее стоимость зависит от соотношения размеров буферов в ОП и общего объема данных.
Пренебрежём тем, что у нас есть ОП. Стоимость построения индекса — это O(N log N).
V>Осталось учесть, что стоимость записи многократно больше стоимости чтения...
И всё равно это будет O(N log N), только коэффициент будет учитывать и записи, и чтения.
V>А если временные таблицы расположены на том же диске, что и данные, и головка диска дергается то на чтение исходных данных, то на запись промежуточных, то там вообще труба выходит...
Да не будет никакой трубы. Будет O(N log N) c плохим коэффициентом. Ничего военного. Наличие большой ОП и разнесение на разные диски способны всего лишь улучшить коэффициенты, но не могут повлиять на асимптотику.

V>Ну и зря... бо в C# действительно приходится бодаться с переполнениями, странно что народ так редко возмущается. Отсутствие банального typedef размножает какую-нить простейшую проблему многократно по коду, вместо того, чтобы дать возможность справиться с ней раз и навсегда в одном месте.
Как раз в C# проблема с переполнениями детектируется элементарно. В отличие от менее удачных языков.

V>Приведение к Int64 было обязательно для выяснения знака операции через вычитание.
Но обратное приведение к int тут же теряет знак обратно.

V>Мы просто решали не ту проблему и не с того конца. Проблема-то в том, что генерики не поддерживают статические ф-ии, поэтому нужен интерфейс компаратора, но результат работы компаратора, в свою очередь, надо зафиксировать в некоем типе, не зависящем от типа аргумента. Почему там int, а не enum {less/before, equal, greater/after}? Вот тебе любезно подложенная грабля by design, которая своим происхождением вовсе не обязана тому, что ты пытался на ее примере показать.
Правильные соображения. Конечно лучше не иметь таких ловушек вовсе. Однако попадание в ловушку — именно следствие непонимания того, что школьная арифметика не работает в компьютере.

DG>>2. присвоение переменной эквивалентно присвоение полю
DG>>3. получение значения переменной эквивалентно получению значения поля
S>И это чушь. Я это не использовал. Что бы делать утверждения относительно кода с сахаром, нужно знать, во что он разворачивается. Я произвел соответствующее преобразование. Все. Никаких спекуляций об эквивалентности и идентичности.

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

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

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

в c#-е переменная и поле того же типа полностью эквиваленты (за исключением времени жизни). и переменную можно считать частным случаем поля.
вот эквивалентность поля и простого свойства в .net-е страдает намного сильнее (мало того, что они не полиморфны с точки зрения реализации (хотя полиморфны с точки зрения поведения)), так есть еще такие операции как ref и out, которые поддерживают поля, но не поддерживают свойства. хотя эквивалентность поведения и здесь сохраняется, ref может быть заменен на два сообщения(две операции) get/set в виде двух делегатов или интерфейса с двумя методами, а out заменен на одно сообщение set (в виде интерфейса с одним методом или делегатом)

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

DG>>>2. присвоение переменной эквивалентно присвоение полю
DG>>>3. получение значения переменной эквивалентно получению значения поля
S>>И это чушь. Я это не использовал. Что бы делать утверждения относительно кода с сахаром, нужно знать, во что он разворачивается. Я произвел соответствующее преобразование. Все. Никаких спекуляций об эквивалентности и идентичности.

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

DG>второй подход плох тем, что в твоей карте мира не остается возможности делать утверждения: преобразования компилятора правильные или нет и при каких условиях
Утверждения относительно правильности преобразований компилятора в контексте корректности программы, компилируемой этим компилятором неинтересны. Даже если бы компилятор микрософт делал все неправильно, имело бы смысл использовать именно его преобразования для того что бы делать утверждения относительно программы.

DG>в том-то и дело, что в данном случае замена переменной на объект делается на основе имеющейся эквивалентности переменной и поля объекта, и ничего нового придумано не было.
Кроме эквивалентности этих понятий.

DG>в c#-е переменная и поле того же типа полностью эквиваленты (за исключением времени жизни). и переменную можно считать частным случаем поля.
Так же полностью эквивалентны как совок и экскаватор. И экскаватор можно считать частным случаем совка.

DG>вот эквивалентность поля и простого свойства в .net-е страдает намного сильнее (мало того, что они не полиморфны с точки зрения реализации (хотя полиморфны с точки зрения поведения)), так есть еще такие операции как ref и out, которые поддерживают поля, но не поддерживают свойства. хотя эквивалентность поведения и здесь сохраняется, ref может быть заменен на два сообщения(две операции) get/set в виде двух делегатов или интерфейса с двумя методами, а out заменен на одно сообщение set (в виде интерфейса с одним методом или делегатом)

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

Но все-таки. Есть или нет такая эквивалентность — неважно при использовании конкретного компилятора. Он делает такую замену и не спрашивает тебя, считаешь ли ты ее корректной. Для корректности результата работы твоей программы имеет значение только факт такого преобразования. И уволь меня от рассуждений о корректности твоей программы согласно твоим понятиям об эквивалентности преобразований абстрактным компилятором.

S>Само ООП в вашем расширении совершенно не нуждается, и прекрасно работает без него. С возможностью расширять модель ООП никто не спорил с самого начала. Вы пытались доказать, что можно получить ООП, ослабив требования к одной из составляющих модели. Увы.

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

например, ОТО расширяет классическую механику, ослабляя базовые требования классической механики

1.время абсолютно, то есть промежутки времени между любыми двумя событиями одинаковы во всех произвольно движущихся системах отсчёта;
2.пространство абсолютно, то есть расстояние между двумя любыми материальными точками одинаково во всех произвольно движущихся системах отсчёта.

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

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

ООП, как минимум, расширяется по трем направлениям:
1. понятие объект не обязано соответствовать физическому воплощению в виде объекта из ООП языка программирования
2. инкапсуляция рассматривается для относительного наблюдателя, а не абсолютного
3. время квантованное. и квант времени рассмотрения может не один к одному соответствовать атомарному кванту времени изменения состояния программы

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

V>>"Что" и "как" — это вполне интуитивные понятия, имеющие однозначную языковую семантику, а вовсе не наивные.
S>Наивно представление о том, что "как" обязательно предоставляет больше информации, чем "что".

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

V>>Т.е. таки разногласия в понимании взаимоотношений понятий "как" и "что"?
S>Разногласия в понимании того, чем отличаются декларативное представление программ от императивного.

V>>Ты утверждал, что иммутабельное означает декларативное.
S>Нет. Я утверждал, что отсутствие побочных эффектов означает декларативное. Причём, естественно, не случайное отсутствие побочных эффектов, а такое, которое с гарантией.

Гарантия — это атрибут модели, придуманный тобой. И правильно придуманый, бо я бы возразил, что без проблем на декларативном ЯП писать без побочных эффектов. А гарантии в том же С++ можно обеспечить через const, например. Получим декларативный подход?

V>>printf("%d", x); — точно так же декларативен для некоей низлежащей системы, как и сигма.
S>Ничего подобного. printf() работает с консолью и меняет её состояние. Поэтому порядок вызова printf-ов важен, и printf — императивен на 100%.

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

V>>Эти спекуляции ведут в никуда, ведь ты сначала отвергаешь взаимоотношение РИ и РА как уровней с разными степенями подробностей,
S>Да нет там никаких разных степеней подробностей. РА и РИ взаимно однозначно отображаются друг на друга — см. теорему Кодда.

Дык, сам смотри внимательней. И смотри на реальные примеры тоже. В общем случае один оператор РИ требует много операторов РА, обратное неверно. Т.е. насчет взаимно-однозначного отображения... реверс-инжениринг работает по такому-же принципу, но из этого никто не делает далекоидущие выводы о равенстве декларативности условия и его решения. Бо из решения не всегда очевидно условие. А теорема Кодда доказывает нечто иное, что на РА можно выразить любые операторы РИ, т.е. РА обладает достаточной полнотой, чтобы являться инструментом реализации РИ. (справедливости ради в теореме доказывается не достаточность полноты РА для РИ, а эквивалентность, т.е. в РА были включены те и только те операции, которые требуются для выражения операторов РИ и никакие больше... это и было сутью теоремы)

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

S>Ок, это понятно. Непонятно только, при чём тут декларативность vs императивность.

При том, что изменяющееся состояние приписали "императивному" исторически. Императивность — это последовательность инструкций, факт обязательности побочных эффектов не является неоспоримым. Даже при взгляде на дерево вычислений математического выражения, в каждом узле этого дерева хранятся именно инструкции/операторы, которые вычисляются по направлению к корню. Ну и... даже в императивном программировании 99% математических вычислений абсолютно чисты. Отсюда и до бесконечности можно опять начинать спекулировать про те самые гарантии... но такой спор априори неинтересен.

V>>Эта К будет при каждой операции чтения, т.е. при N, независимо от затрат на обход индекса. Эти логарифмические затраты просто не видны обычно на фоне чтения страниц "вразнобой".
S>Эти логарифмические затраты обычно и определяют количество чтений страниц.

Это чтение одной строки в случае индекса имеет логарифмическую вид сложности некий K1 * O(log N), а чтение N страниц "вразнобой", а не подряд, имеет сложность O(N) cо своим совершенно другим К2, бо степень упорядоченность страниц данных обычно отличается от степени упорядоченности страниц индекса. Итого, логарифмический вид будет при малом K1, но прямо пропорционально при большем (обычно) K2.

V>>Еще раз, эта сложность у операции декартова произведения по-определению.
S>Join — это не декартово произведение.

О, решил повториться?

inner/outer/right/left/cross/full... не?

V>>Я знаю, что ты настаиваешь на оценке исключительно логического чтения. Но, логические не значат физические и не только на чтение с диска нужны ресурсы.
S>Я вас разочарую — CPU-затраты на join ведут себя с той же асимптотикой, что и на логические чтения. Вот только K при этих O там совсем другой.

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

V>>Фи, как низкопробно. Т.е. ты считаешь, что основная лишняя нагрузка на СУБД — это работа по обслуживанию запросов, передачи по сети каждый раз заново заголовков таблиц вместе с данными и т.д.?

S>Основная лишняя нагрузка — это парсинг запроса, построение плана, использование метаданных. Для интереса, попробуйте замерить, сколько стоит выполнить select 0 на удалённом MS SQL.

Речь шла об отличиях. И там и там есть как парсинг запроса, так и построение плана и использование метаданных. Для интереса попробуй замерить сам, только не через TCP и не на удаленном, а на локальном... бо измерять плохосконфигурированный TCP я, пожалуй, не стану, select 0 не будет ответом, почему сервер тормозит даже тогда, когда все дополнительные действия составляют мизер от общих затрат.

V>>ИМХО, случай, когда для некоей таблицы во всех сценариях выборки, происходящих вокруг нее встречается только один вид join, это таки "очень некоторые".
S>Угу. А теперь попробуйте мне доказать, что для этой таблицы кластерный индекс вовсе не нужен. Вы же такой их противник, нет?

Откуда "противник"? Я описал свои наблюдения относительно использования их в кач-ве уникальных ключей, где они хорошо работают, а где не очень. И как выяснилось в твоих же экспериментах, для "широких" таблиц кластерный индекс начинает работать как некластерный на чтении. Так зачем его тартить на это? Далее говорилось, что для небольших по-объему данных и "узкого" ключа основной ключ имеет смысл делать таки кластерным, невзирая ни на что. Т.е. я получал прирост эффективности для таких данных, невзирая на всевозможные join по совсем другим индексам. Возможно, хорошо начинают сказываться всякие политики упреждающего чтения, которые меньше промахиваются на малых объемах данных или еще что-нить, о чем можно только гадать. Т.е. возможны всякие эффекты, которые хрен увидишь в логических чтениях, но хорошо увидишь по возросшей отзывчивости основных операций после того как база немного "разогреется". Факт "разогрева" тоже простой асимптотикой логических чтений хрен опишешь...

V>>Я рассказал о внешних эффектах, которые были обнаружены и обкатаны многократно во всех вариантах. Стоит вернуться и попытаться соотнести свое представление о кишках этой СУБД и причин производимых ими эффектов.
S>У вас рассказы о внешних эффектах волшебным образом меняются по ходу беседы. Из этого можно сделать банальный вывод, что применяемая вами методика исследования мира не даёт полезных результатов, зато даёт вредные.

Гы, исследовать эффективность программных продуктов можно только на тестах в конкретном аппаратном окружении для конкретного характера данных... Остальное — грубая профанация.

S>Ну вот это уже больше похоже на правду. И прекрасно согласуется с теми критериями, которые я приводил 40 постов назад, а вы смеялись.

Те критерии совершенно не объясняют устойчиво наблюдаемых эффектов. А в Санта-Клауса я не верю.

V>>Ну и во всех гайдлайнах настоятельно MS советует отделять оперативные данные от исторических первой строчкой рекомендаций. Причем, и даже разносить их по разным серверам. Дык, а в твоей системе координат, коль речь идет о разных таблицах, какая фиг разница, не правда ли? Ведь количество логических чтений независимо для независимых запросов...

S>Вы уже один раз посмеялись над моими знаниями в СУБД. Предлагаю не продолжать — опять ведь в лужу сядете.

Таки это действительно MS настойчиво пишет в гайдах, и я не понял этот финт в кач-ве комментария. Ты точно на этот абзац отвечал, не промахнулся случаем?
Характерно, что мы пришли к тому же довольно быстро, еще до того, как был выпущен блестящий BOL к 7-ке и множество наработанных практик/советов от самой же MS. И неприятно поразило то, что для предыдущего варианта файлового движка СУБД мы могли позволить себе куда как больший оперативный период на той же технике.

V>>Какая разница, как конкретно устроена оценочная ф-ия?
S>Как бы устройство оценочной функции принципиально — именно оно определяет способность СУБД выбрать оптимальный план.

Для алгоритма перебора вариантов это не играет рояли.

V>>Чем дальше, тем больше будет методик составления сей оценочной ф-ии и способов представления статистики для нее. Мы уже давно договорились, что ее вид f(x1, x2, x3, ...), т.е. обычный черный ящик.
S>Я не знаю, с кем и о чём вы договорились. Вижу только, что никакой литературы об устройстве оптимизаторов запросов вы не читали, и для вас эта область помечена "тут живут драконы".

Разве? Наоборот видно, что я всяко лучше понимаю, как именно рождаются варианты планов запросов. Относительно оптимизаций мне достаточно знать, для чего нужна статистика и как именно она исопльзуется с весовой ф-ией. Устройство весовой ф-ии не интересует, разумеется, бо сам писал такие же многократно, и это дело зависит от совсем уж конкретики конкретной СУБД. Сколько разных СУБД увидишь, столько будет разных оценочных ф-ий, это непереносимые/неуниверсальные знания.

V>>Я утверждал, что породить всевозможные комбинации последовательностей операций для последующей оценки весовой ф-ией можно как раз с помощью аппарата РА.
S>Используется расширенный аппарат РА — в нём отношения аннотированы дополнительной информацией. В частности, есть информация о том, какие отношения эквивалентны, и насколько они эквивалентны.

Давай конкретней, где ты это берешь? Эта информация (зависимости) есть на уровне реляционной модели by design, ничего расширять не надо. Конкретная декомпозиция — то и есть набор отношений. При известной исходной схеме и зависимостях любые отношения даже проверять на эквивалентность не надо, достаточно посмотреть на мн-во атрибутов, входящих в отношение. И речь не об одноименности атрибутов, которую легко получить в SQL, а именно о мн-ве уникальных атрибутов конкретной схемы в рамках реляционной модели. Разумеется, индексы по некоей таблице априори оперируют уникальными атрибутами, т.е. колонками этой таблицы. Расширения, конечно, есть, но оно малость в другом — в использовании вычислимых полей. Но и это слабо тянет на расширения, бо вычислимые поля порождаются простой операцией проекции и переименования. Я потому и подбивал тебя на конкретику относительно твоих планов запросов, чтобы уже обсудить наконец хоть что-то по делу и попунктно. Жаль, что ты продолжаешь вилять.

Конечно, я в спешке написал малость некорректно относительно именно РА, бо РА не умеет составлять собственные формулы. Это очевидно. (кроме преобразования уже готовых, ссылку на примеры преобразований ты давал). Речь именно о применимости реляционной модели в деле составления плана запросов, то бишь перебора и оценки вариантов. Ведь тут придется вернуться к самому началу и вспомнить, как именно происходит оценка плана запроса и заново взглянуть на твои попытки выставить "bookmark lookup" как некую совершенно особую операцию.

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

S>Что и позволяет оптимизатору запрос по таблице превращать в запрос по индексу.

Так что же это "что"?

S>Почему недоступная-то? Всё доступно. Я ссылку на учебник дал. То, чего там нет, легко найти в публикациях. Просто применяемый аппарат шире, чем классическая РА.

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

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

Я вижу нереляционные расширения языка SQL (если отбросить хинты, операции конфигурирования или DDL) в основном в виде императивных конструкций вокруг курсоров. Неуникальность строк таблиц мы уже обсуждали, только не до конца. Так и не было показано, что твои же преобразования из РА, будучи примененным к таким неуникальным данным, вдруг станут неверными.

Один из самых мощных и наиболее часто используемый оператор SELECT реализует все операции реляционной алгебры.

Не могу не согласиться. И только по нему составляется обcуждаемый нами план запроса. Собс-но, реляционная алгебра именно выборкой и занимается. Поэтому мне и странно рассуждать о других возможностях SQL, коль речь идет о выборке. Мало ли, что есть в некоем языке программирования... они сейчас сплошь мультипарадигменные.

V>>Насчет "приближаются к скорости чистого чтения" — это иди учи матчасть сам... Не приближаются, а в точности равны, бо работают через memory-mapped file.
S>Ну вы же только что сами мне рассказывали про то, что логические чтения — не единственные затраты?
V>>Дело, конечно, в неумении автоматически детектить моменты, когда требуется конкурентность, от моментов, когда не особо требуется. Это я намекаю, что уровней изоляции во встроенных движках обычно поменьше, а сценарий простой полной блокировки очень дешевы в условиях малого кол-ва одновременных запросов, но когда сами запросы относительно тяжелы. Но MS SQL, похоже, всегда создает копии страниц в ОП (хотя сами страницы, скорее всего читает так же через memory-mapped file), и работает уже с ними...
S>Нет, не создаёт. Зачем вы продолжаете оперировать домыслами, когда можно просто пойти в документацию и почитать?
S>Кстати, вы же вроде бы исходники смотрели? Я понимаю, что это враньё, но вы уж врите согласованно.

Разбирать их целиком было невозможно принципиально, так что использовались в основном для непонятных моментов и эффектов, примерно как Reflector для дотнета. Исходники 6-ки таки были для гос-конторы.

S>Неужто вы бы не заметили копирования страниц, если смотрели даже на выравнивание данных внутри страницы?

Похоже, ты не понял, что есть копирование страниц в сравнении с работой через memory-mapping.
http://msdn.microsoft.com/en-us/library/aa337560.aspx
http://msdn.microsoft.com/en-us/library/aa337525.aspx

Например:

The buffer manager manages the functions for reading data or index pages from the database disk files into the buffer cache and writing modified pages back to disk.

Запись целиком страницы обратно говорит о том, что, во первых это хреново, записывать 8k, если поменялся всего один байт (неважно, lazy там или еще что), а во вторых, что сама страница не отображена как участок memory-mapped file, т.е. таки используется копия страницы в памяти. Хотя при BULK заливке или для твоих каких-то новых FILESTREAM (никогда не работал с ними) таки используется маппинг памяти на файлы (это видно по кодам ошибок), но при этом в журнал ничего не пишется и транзакционность не особо обеспечивается.

И да, подсмотренному вопросу выравнивания данных внутри страницы абсолютно фиолетово, с помощью какой именно технологии чтения эта страница была получена.

V>>ИМХО, если стоимость запроса была известна заранее, то вполне мог бы быть некий "порог" конкурентности для конкретной таблицы или целого файла данных, чтобы работать с данными по месту.
S>Ну, расскажите мне, для чего MS SQL будет копировать страницы.

Чтение и запись в стиле обычного IO — это и есть копирование, в сравнении с непосредственой работой memory-mapped files. Как, по-твоему, работает кеш страниц в MS SQL?

V>>Построение индекса — это и есть сортировка, чего там смотреть-то?
S>Вы зря не выполняете домашние задания. Так вы ничему не научитесь.

Ах, не сортировка? Что-то новое открыли в науке индексов? Или построение упорядоченной коллекции, типа сбалансированного дерева — это не сортировка? Как любопытно-то...

V>>В общем случае построение индекса выливается во внешнюю сортировку, а ее стоимость зависит от соотношения размеров буферов в ОП и общего объема данных.
S>Пренебрежём тем, что у нас есть ОП. Стоимость построения индекса — это O(N log N).
V>>Осталось учесть, что стоимость записи многократно больше стоимости чтения...
S>И всё равно это будет O(N log N), только коэффициент будет учитывать и записи, и чтения.

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

V>>А если временные таблицы расположены на том же диске, что и данные, и головка диска дергается то на чтение исходных данных, то на запись промежуточных, то там вообще труба выходит...
S>Да не будет никакой трубы. Будет O(N log N) c плохим коэффициентом. Ничего военного. Наличие большой ОП и разнесение на разные диски способны всего лишь улучшить коэффициенты, но не могут повлиять на асимптотику.

Могут, ты ведь сам настаиваешь, что асимптотика по логическим чтениям такова для многих операций, что остальными компонентами асимптотики можно пренебречь. Так и здесь. Кол-во операций записи на самом деле будет O(N). Стоимость слияния после сортировки — тоже O(N). В случае дергания головки будет лишь страшное К.

V>>Ну и зря... бо в C# действительно приходится бодаться с переполнениями, странно что народ так редко возмущается. Отсутствие банального typedef размножает какую-нить простейшую проблему многократно по коду, вместо того, чтобы дать возможность справиться с ней раз и навсегда в одном месте.
S>Как раз в C# проблема с переполнениями детектируется элементарно. В отличие от менее удачных языков.

Например? В С++ в компиляторах есть опция — проверять признак переполнения или нет.
Но не в этом суть, почему используют вычитание. Суть в том, чтобы попытаться убежать от лишнего if, бо в современных процах при неудачном предсказании ветвление может стоить столько же, сколько десятки целочисленных операций. Я думал это и так понятно для коллег, иначе никто бы не ломал голову над вариантами с вычитанием, а тупо написали бы на if.

V>>Приведение к Int64 было обязательно для выяснения знака операции через вычитание.
S>Но обратное приведение к int тут же теряет знак обратно.

Спасибо, просто открыл глаза...

V>>Мы просто решали не ту проблему и не с того конца. Проблема-то в том, что генерики не поддерживают статические ф-ии, поэтому нужен интерфейс компаратора, но результат работы компаратора, в свою очередь, надо зафиксировать в некоем типе, не зависящем от типа аргумента. Почему там int, а не enum {less/before, equal, greater/after}? Вот тебе любезно подложенная грабля by design, которая своим происхождением вовсе не обязана тому, что ты пытался на ее примере показать.
S>Правильные соображения. Конечно лучше не иметь таких ловушек вовсе. Однако попадание в ловушку — именно следствие непонимания того, что школьная арифметика не работает в компьютере.

Я уже объяснил, откуда потенциальное попадание в ловушку — из-за специальной попытки избежать if. Дело в том, что хоть С/С++ меняется медленно и очень консервативен, но стандартная библиотека удивительно целостностна в плане возможных косяков и принятых инженерных решений, в отличие от либ дотнета. Например, результат сравнения как int есть только для ф-ии над цепочкой char, т.е. никакая грабля в тот прототип, который был взят потом в дотнет, не была заложена. Грабля появилась после обобщения. А по мне — так экономия на спичках, бо виртуальный вызов метода компаратора "съест" любые сэкономленные спички.

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

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

V>>>printf("%d", x); — точно так же декларативен для некоей низлежащей системы, как и сигма.
S>>Ничего подобного. printf() работает с консолью и меняет её состояние. Поэтому порядок вызова printf-ов важен, и printf — императивен на 100%.

V>Нет никакого порядка вызова printf() внутри реализации этой ф-ии, есть только одна эта задача на своем уровне, которая понятия не имеет о вызовах других printf().
Эта задача есть инструкция control flow. printf не учавствует в вычислении, в описании того что нужно получить.
V>И есть некий низлежащий слой ОС. И эта задача вполне может быть выполнена без побочных эффектов на своем уровне, передавая данные "куда-то дальше"...
Передача данных "куда-то дальше" — это и есть императив. И нет никаких уровней побочных эффектов. Побочный эффект либо есть либо нет.
V>В чистых функциональных языках тоже ведь как-то ввод-вывод делают, просто разграничивают, что это делает "кто-то другой" через библиотеки.
В случае хаскеля, например, ввод-вывод не делают (не выполняют). Вместо этого результатом функции main является комбинация императивных действий и вычислений. Такая комбинация получается с помощью декларативного описания, именно она является целью декларативных вычислений. Выполнение ввода-вывода остается таким образом за бортом ФЯ.

В сравнении с таким подходом, результатом выполнения main у C-подобных языков является int или void. И printf для вычисления этого значения не нужен.

Здравствуйте, DarkGray, Вы писали:
DG>в большинстве случаев, расширение происходит через ослабление ряда исходных требований.
Нет. Вы неправильно понимаете, что такое "требование".
DG>при этом классическая механика становится вырожденным случаем ОТО.
Всё как раз наоборот. Появляется требование ограниченности скорости передачи информации, из которого выводится всё остальное. В том числе и изменённые требования к метрическому тензору. Если просто убрать требования, которые вы предлагаете, получится вовсе не ОТО.

DG>тоже самое, например, при переходе от действительных чисел к комплексным: ослабляется требование, что из отрицательных чисел нельзя брать корень, и происходит расширение: действительные числа становятся вырожденным случаем комплексных.
Нет. Всё как раз наоборот: появляется требование замкнутости множества относительно операций возведения в произвольную степень, и из него выводится всё остальное.
Требования "нельзя брать корень из отрицательных чисел" в определении действительных чисел нет.

DG>ООП, как минимум, расширяется по трем направлениям:
DG>1. понятие объект не обязано соответствовать физическому воплощению в виде объекта из ООП языка программирования
Это не расширение. Базовое ООП ничего не говорит о физическом воплощении.
DG>2. инкапсуляция рассматривается для относительного наблюдателя, а не абсолютного
Инкапсуляция с самого начала не рассматривается для абсолютного наблюдателя.
DG>3. время квантованное. и квант времени рассмотрения может не один к одному соответствовать атомарному кванту времени изменения состояния программы
Время в ООП и так квантованное. Мы с вами это уже обсуждали.

DG>>в большинстве случаев, расширение происходит через ослабление ряда исходных требований.
S>Нет. Вы неправильно понимаете, что такое "требование".

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

DG>>при этом классическая механика становится вырожденным случаем ОТО.
S>Всё как раз наоборот. Появляется требование ограниченности скорости передачи информации, из которого выводится всё остальное. В том числе и изменённые требования к метрическому тензору. Если просто убрать требования, которые вы предлагаете, получится вовсе не ОТО.

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

DG>>тоже самое, например, при переходе от действительных чисел к комплексным: ослабляется требование, что из отрицательных чисел нельзя брать корень, и происходит расширение: действительные числа становятся вырожденным случаем комплексных.
S>Нет. Всё как раз наоборот: появляется требование замкнутости множества относительно операций возведения в произвольную степень, и из него выводится всё остальное.

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

S>Требования "нельзя брать корень из отрицательных чисел" в определении действительных чисел нет.

DG>>ООП, как минимум, расширяется по трем направлениям:
DG>>1. понятие объект не обязано соответствовать физическому воплощению в виде объекта из ООП языка программирования
S>Это не расширение. Базовое ООП ничего не говорит о физическом воплощении.

значит ты согласен, что переменная, свойство, группа объектов могут рассматриваться как отдельный объект?

DG>>2. инкапсуляция рассматривается для относительного наблюдателя, а не абсолютного
S>Инкапсуляция с самого начала не рассматривается для абсолютного наблюдателя.

переформулируй это конструктивно (без "не"): с точки зрения чего инкапсуляция рассматривается?

DG>>3. время квантованное. и квант времени рассмотрения может не один к одному соответствовать атомарному кванту времени изменения состояния программы
S>Время в ООП и так квантованное. Мы с вами это уже обсуждали.

а что со второй частью — можно ли в качестве кванта рассмотрения брать произвольный промежуток времени?

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

V>Тем не менее, считается что сами уровни, подходящие под "как" и "что" находятся в односторонней зависимости, например, одному и тому же "что" может соответствовать много вариантов "как", каждый со своими лишними подробностями, не требуемыми на уровне "что". Мои рассуждения исходили из того, что на любом из вариантов уровня "как" видны примитивы уровня "что" (являются целью, "точкой входа" и т.д.), т.е. уровень "как" владеет одновременно своими подробностями и подробностями вышестоящей системы, в то время с уровня "что" подробности уровня "как" являются лишними.
Это интересное мнение. Откуда тогда так популярны соревнования типа "что делает эта программа", если на любом из вариантов уровня "как" видны примитивы уровня "что"?

V>Гарантия — это атрибут модели, придуманный тобой. И правильно придуманый, бо я бы возразил, что без проблем на декларативном ЯП писать без побочных эффектов. А гарантии в том же С++ можно обеспечить через const, например. Получим декларативный подход?
Ну, мы же знаем, что гарантиям const в C++ — грош цена. Но если вы обеспечите такие гарантии — то, конечно же, мы получим декларативный подход.

V>>>printf("%d", x); — точно так же декларативен для некоей низлежащей системы, как и сигма.
S>>Ничего подобного. printf() работает с консолью и меняет её состояние. Поэтому порядок вызова printf-ов важен, и printf — императивен на 100%.

V>Нет никакого порядка вызова printf() внутри реализации этой ф-ии,
При чём тут реализация? Вы что, всеръёз полагаете, что результат

printf("hello, ");
printf("world");

и результат

printf("hello, ");
printf("world");

— одинаковы?
V>есть только одна эта задача на своем уровне, которая понятия не имеет о вызовах других printf(). И есть некий низлежащий слой ОС. И эта задача вполне может быть выполнена без побочных эффектов на своем уровне, передавая данные "куда-то дальше"...
Нет, она не может быть выполнена без побочных эффектов. Она целиком и полностью опирается на определённое поведение разделяемого состояния.
V>В чистых функциональных языках тоже ведь как-то ввод-вывод делают, просто разграничивают, что это делает "кто-то другой" через библиотеки.
А вы поинтересуйтесь, как же так в чистых функциональных языках делают ввод-вывод. Там ведь нет ничего сложного — просто вместо неявного состояния вычислителя, на котором работают императивные программы, вводится явное состояние аргумента. Грубо говоря, вместо void printf(...) у нас появляется

Console printf(this Console in, String text);

Сама printf здесь не имеет побочных эффектов — её можно вызывать на одном и том же аргументе сколько угодно раз, и результат всегда будет одинаковым.
Чтобы задать порядок, надо явно писать

console.printf("Hello").printf("World")

V>При том, что изменяющееся состояние приписали "императивному" исторически. Императивность — это последовательность инструкций, факт обязательности побочных эффектов не является неоспоримым.
Вы, я вижу, не понимаете простой вещи. Если нет побочных эффектов, то "последовательность" инструкций — фикция. Единственный способ принудить инструкции исполняться последовательно — ввести зависимость их друг от друга. В императивном программировании зависимость вводится через побочные эффекты. В декларативном программировании все зависимости — явные, поэтому можно делать всякие интересные трансформации с порядком выполнения (и с выполнением вообще). В частности, можно вычислить первые N чисел Фибоначчи не за N^2, а за N, несмотря на явно рекурсивное определение этой функции.

V>Даже при взгляде на дерево вычислений математического выражения, в каждом узле этого дерева хранятся именно инструкции/операторы, которые вычисляются по направлению к корню.
Ну да, есть отношения частичного порядка, заданные зависимостями. Но для дерева с N листьями у нас есть минимум 2^N вариантов последовательности выполнения, если нет побочных эффектов. Если побочные эффекты есть, то у нас есть ровно 1 вариант последовательности, который даст заданный результат.

V>Это чтение одной строки в случае индекса имеет логарифмическую вид сложности некий K1 * O(log N), а чтение N страниц "вразнобой", а не подряд, имеет сложность O(N) cо своим совершенно другим К2, бо степень упорядоченность страниц данных обычно отличается от степени упорядоченности страниц индекса. Итого, логарифмический вид будет при малом K1, но прямо пропорционально при большем (обычно) K2.
Вы путаете разные N. Стоимость поиска одной строки — O(log N), где N — количество строк в отношении, в котором мы ищем.
Стоимость поиска M строк, соответственно, равна O(M*log(N)).

V>Это бред сивой кобылы. Одну асимптотику можно выражать через другую, только если твой "другой" K постоянен, а если он зависит от того, сколько необходимых данных будут на каждой странице, то выражать одну сложность через другую бесполезно. В итоговую сложность надо будет включать отношения размеров доступного кеша и данных.
Прекратите пороть чушь. Вся прелесть логических чтений — в том, что они дают пессимистичную оценку. То есть наличие кэша всего лишь означает, что часть логических чтений удастся выполнить без физического обращения к диску. Вы сами предложили рассматривать случай, когда данные многократно превышают размер ОП — в этом случае сache hit ratio можно пренебречь, и считать, что он нулевой.
В этом случае у нас все коэффициенты станут фиксированными, их зависимостью от N и M можно будет пренебречь. И, конечно же, O(K1*M*logN+K2*M*logN) всё ещё сведётся к O(M*logN). Вы где вообще учились, что вам такие вещи приходится разжёвывать?

V>Откуда "противник"? Я описал свои наблюдения относительно использования их в кач-ве уникальных ключей, где они хорошо работают, а где не очень. И как выяснилось в твоих же экспериментах, для "широких" таблиц кластерный индекс начинает работать как некластерный на чтении. Так зачем его тартить на это? Далее говорилось, что для небольших по-объему данных и "узкого" ключа основной ключ имеет смысл делать таки кластерным, невзирая ни на что. Т.е. я получал прирост эффективности для таких данных, невзирая на всевозможные join по совсем другим индексам. Возможно, хорошо начинают сказываться всякие политики упреждающего чтения, которые меньше промахиваются на малых объемах данных или еще что-нить, о чем можно только гадать. Т.е. возможны всякие эффекты, которые хрен увидишь в логических чтениях, но хорошо увидишь по возросшей отзывчивости основных операций после того как база немного "разогреется". Факт "разогрева" тоже простой асимптотикой логических чтений хрен опишешь...

Ваши наблюдения как были некорректными, так и остались. Вернитесь в начало и перечитайте критерии уместности применения кластерных индексов, которые я вам написал. Если у вас после этих сорока постов всё ещё остались вопросы про то, как работают кластерные индексы, и как они используются в джойнах — пишите, не стесняйтесь.

V>Гы, исследовать эффективность программных продуктов можно только на тестах в конкретном аппаратном окружении для конкретного характера данных... Остальное — грубая профанация.
S>>Ну вот это уже больше похоже на правду. И прекрасно согласуется с теми критериями, которые я приводил 40 постов назад, а вы смеялись.
V>Те критерии совершенно не объясняют устойчиво наблюдаемых эффектов. А в Санта-Клауса я не верю.
Ооо, начинается. Какие именно эффекты, необъяснимые приведёнными критериями, вы смогли получить? Не стесняйтесь — приведите код эксперимента.

V>Таки это действительно MS настойчиво пишет в гайдах, и я не понял этот финт в кач-ве комментария. Ты точно на этот абзац отвечал, не промахнулся случаем?
Я отвечал на тот, где пачка смайликов, и вы пытаетесь смеяться над моим подходом. Объясню подробнее: вы уже две недели упорно демонстрируете непонимание простейших фактов из архитектуры MS SQL. В процессе объяснения этих элементарных фактов вы успели неоднократно сделать совершенно необоснованные предположения относительно моей квалификации, нарываясь на п.5. правил, и много смеялись. Теперь элементарные факты мы выяснили, несмотря на ваше активное сопротивление.
Вы продолжаете наезжать на моё понимание и опыт в СУБД, теперь переходя к эффектам следующего порядка. Вы что, после всего этого разговора, ещё надеетесь где-то в этой области меня подколоть? Ну-ну.

V>Для алгоритма перебора вариантов это не играет рояли.
О да. Интересное заблуждение.

V>Разве? Наоборот видно, что я всяко лучше понимаю, как именно рождаются варианты планов запросов.

V>Давай конкретней, где ты это берешь?
Я дал вам ссылки на учебники по устройству СУБД. Читайте.
V>Эта информация (зависимости) есть на уровне реляционной модели by design, ничего расширять не надо.
Покажите мне, где эта информация есть на уровне реляционной модели. В реляционной модели понятие "отношения" достаточно чётко определено, и что там есть, и чего нету, написано очень подробно.

S>>Почему недоступная-то? Всё доступно. Я ссылку на учебник дал. То, чего там нет, легко найти в публикациях. Просто применяемый аппарат шире, чем классическая РА.

V>Разбирать их целиком было невозможно принципиально, так что использовались в основном для непонятных моментов и эффектов, примерно как Reflector для дотнета. Исходники 6-ки таки были для гос-конторы.
В прошлый раз это было "вплоть до 2000".

V>Похоже, ты не понял, что есть копирование страниц в сравнении с работой через memory-mapping.
V>http://msdn.microsoft.com/en-us/library/aa337560.aspx
V>http://msdn.microsoft.com/en-us/library/aa337525.aspx

V>Например:
V>

V>The buffer manager manages the functions for reading data or index pages from the database disk files into the buffer cache and writing modified pages back to disk.

V>Запись целиком страницы обратно говорит о том, что, во первых это хреново, записывать 8k, если поменялся всего один байт (неважно, lazy там или еще что),
А вот конкретно это говорит о том, что вы не имеете представления о том, как работает чтение/запись в современных устройствах хранения (включая HDD и SSD).
Потому что записать меньше страницы на диск вообще нельзя. В теории СУБД традиционно принято оценивать характеристики в логических чтениях, а в практике — в IOPS. Современной аппаратуре всё равно, записать 1 байт или 1 екстент в 64кб.

V>а во вторых, что сама страница не отображена как участок memory-mapped file, т.е. таки используется копия страницы в памяти. Хотя при BULK заливке или для твоих каких-то новых FILESTREAM (никогда не работал с ними) таки используется маппинг памяти на файлы (это видно по кодам ошибок), но при этом в журнал ничего не пишется и транзакционность не особо обеспечивается.

Вы сваливаете в одну кучу механику взаимодействия с файлом данных и с файлом журнала, а также понятие транзакционности. Там у вас тоже монолит, да?

V>>>ИМХО, если стоимость запроса была известна заранее, то вполне мог бы быть некий "порог" конкурентности для конкретной таблицы или целого файла данных, чтобы работать с данными по месту.
S>>Ну, расскажите мне, для чего MS SQL будет копировать страницы.

V>Чтение и запись в стиле обычного IO — это и есть копирование, в сравнении с непосредственой работой memory-mapped files. Как, по-твоему, работает кеш страниц в MS SQL?

V>Ах, не сортировка? Что-то новое открыли в науке индексов? Или построение упорядоченной коллекции, типа сбалансированного дерева — это не сортировка? Как любопытно-то...
Сортировка. Но вы же поленились посмотреть стоимость этой сортировки.

S>>И всё равно это будет O(N log N), только коэффициент будет учитывать и записи, и чтения.

V>Только один коэф не сможет учесть-то, так что надо больше составляющих, и при каждой поставить свой коэф.
Вот у нас формула вида K1*N*logN + K2*N*logN. Вы правда думаете, что это не равно (K1+K2)*N*logN? Или у вас какое-то другое мнение о составляющих этой формулы?

V>>>А если временные таблицы расположены на том же диске, что и данные, и головка диска дергается то на чтение исходных данных, то на запись промежуточных, то там вообще труба выходит...
S>>Да не будет никакой трубы. Будет O(N log N) c плохим коэффициентом. Ничего военного. Наличие большой ОП и разнесение на разные диски способны всего лишь улучшить коэффициенты, но не могут повлиять на асимптотику.

V>Могут, ты ведь сам настаиваешь, что асимптотика по логическим чтениям такова для многих операций, что остальными компонентами асимптотики можно пренебречь.
Так и здесь. Кол-во операций записи на самом деле будет O(N). Стоимость слияния после сортировки — тоже O(N). В случае дергания головки будет лишь страшное К.
Ок, если вам хочется отбросить младшие члены ряда — пусть будет O(N). Несортированная сторона Join даст ещё M. Итого, имеем линейную асимптотику — O(N+M).
А вы, помнится, пугали меня O(N*M). Почувствуйте разницу.

S>>Как раз в C# проблема с переполнениями детектируется элементарно. В отличие от менее удачных языков.
V>Например? В С++ в компиляторах есть опция — проверять признак переполнения или нет.
Это в каких конкретно компиляторах? Или вы имеете в виду опции "отключить warning при возможном переполнении"?
В С# рекомендую курить ключевое слово checked.

V>Спасибо, просто открыл глаза...

Пожалуйста. Вы обращайтесь, если что.

V>Я уже объяснил, откуда потенциальное попадание в ловушку — из-за специальной попытки избежать if.
Да неважно, откуда появилось потенциальное попадание.
Это же был просто пример кода, который на первый взгляд кажется корректным. Не нужно высасывать из пальца историю, стоящую за этим кодом.

От:	Sinclair	https://github.com/evilguest/
Дата:	30.12.11 08:46
Оценка:

	От:	vdimas
	Дата:	30.12.11 14:53
	Оценка:

От:	Sinclair	https://github.com/evilguest/
Дата:	31.12.11 04:49
Оценка:

	От:	vdimas
	Дата:	31.12.11 10:12
	Оценка:

От:	Sinclair	https://github.com/evilguest/
Дата:	03.01.12 16:44
Оценка:

От:	DarkGray	http://blog.metatech.ru/post/ogni-razrabotki.aspx
Дата:	04.01.12 11:45
Оценка:

От:	samius	http://sams-tricks.blogspot.com
Дата:	04.01.12 18:53
Оценка:	+1