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

Откуда: 010100
Сообщений: 6642
К обсуждению изобретение нового велосипеда с ракетным двигателем.
Подходящего форума не подобрал

Оптимизатор SQL-запросов, основанный на нейронной сети

Основные постулаты:

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

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

Организация нейронной сети
1. Элементом нейронной сети является простая операция запроса, включая параметры и текущие условия на сервере. Элементы имеют взаимные связи.
2. Весом элемента является время выполнения операции (альтернативно оценка CBO или RBO).
3. Запрос, таким образом представляет собой дерево N элементов плюс M параметров. Простые условия уменьшают размерность многомерного пространства сети (максимум M+N).
4. Требуется решить с помощью нейросети «задачу коммивояжера».

Идеи реализации
1. Базовый (Rule-based или Cost-based) оптимизатор отсеивает очевидные вещи и оставляет набор планов запросов для проверки.
2. Ведется статистика выполнения запросов – оптимизировать нужно или часто выполняемые, или указанные вручную.
3. Тестовые или проверочные запросы могут выполняться не в ядре СУБД, а внешней утилитой.
4. Записываем результат выполнения тестовых запросов в конкретных условиях – количество коннектов, занятость памяти, количество выполняемых запросов.
5. Update не воспроизведешь – но их количество мало и они проще.
6. При явном преимуществе нового плана выполнения – выдаем хинт.
7. Следует учесть, что при различных условиях или ! при разных параметрах запроса преимущества могут иметь разные планы.

Поскольку идеи могут мне же в будущем пригодиться, например продам инвесторам в Сколково, авторское право застолблю за собой =)
P.S. Так как основная идея состоит в разбиении сложного запроса на атомарные части и их группировке и обучении сети частиц, алгоритм с полным правом может называться НАНООПТИМИЗАТОРОМ SQL-запросов.
20 апр 11, 13:13    [10541221]     Ответить | Цитировать Сообщить модератору
 Re: Идея. Оптимизатор SQL-запросов, основанный на нейронной сети  [new]
Gluk (Kazan)
Member

Откуда:
Сообщений: 9365
1 апреля вроде прошло?
или я за календарем не следил???
20 апр 11, 13:30    [10541396]     Ответить | Цитировать Сообщить модератору
 Re: Идея. Оптимизатор SQL-запросов, основанный на нейронной сети  [new]
Зайцев Фёдор
Member

Откуда: Лужки
Сообщений: 5308
ну да, требуется всего лишь решить задачу коммивояжера. всё просто ))
20 апр 11, 13:31    [10541403]     Ответить | Цитировать Сообщить модератору
 Re: Идея. Оптимизатор SQL-запросов, основанный на нейронной сети  [new]
Gluk (Kazan)
Member

Откуда:
Сообщений: 9365
Зайцев Фёдор
ну да, требуется всего лишь решить задачу коммивояжера. всё просто ))


нанокоммивояжера, ага
20 апр 11, 13:32    [10541415]     Ответить | Цитировать Сообщить модератору
 Re: Идея. Оптимизатор SQL-запросов, основанный на нейронной сети  [new]
Siemargl
Member

Откуда: 010100
Сообщений: 6642
Gluk (Kazan)
1 апреля вроде прошло?
или я за календарем не следил???
В этой области уже имеется:
-United States Patent 6108648
-масса научных работ (гуглится)
20 апр 11, 13:33    [10541424]     Ответить | Цитировать Сообщить модератору
 Re: Идея. Оптимизатор SQL-запросов, основанный на нейронной сети  [new]
pkarklin
Member

Откуда: Москва (Муром)
Сообщений: 74930
автор
5. Update не воспроизведешь – но их количество мало и они проще.


Везет Вам...
20 апр 11, 13:57    [10541670]     Ответить | Цитировать Сообщить модератору
 Re: Идея. Оптимизатор SQL-запросов, основанный на нейронной сети  [new]
Yo.!
Guest
пару дней назад читал, что пчел будут использовать вместо собак для поиска взрывчатки. короче пошел патентовать использование шмелей в SQL оптимизаторе

Шмели умеют решать задачу коммивояжера
http://iscience.ru/2010/10/26/shmeli-umeyut-reshat-zadachu-kommivoyazhera/
20 апр 11, 14:12    [10541808]     Ответить | Цитировать Сообщить модератору
 Re: Идея. Оптимизатор SQL-запросов, основанный на нейронной сети  [new]
Gluk (Kazan)
Member

Откуда:
Сообщений: 9365
Siemargl
Gluk (Kazan)
1 апреля вроде прошло?
или я за календарем не следил???
В этой области уже имеется:
-United States Patent 6108648
-масса научных работ (гуглится)


О патент это конечно вешч !!! и работы тоже научные, ага
Но по мне так лучше стабильный ПЛАН
20 апр 11, 14:15    [10541832]     Ответить | Цитировать Сообщить модератору
 Re: Идея. Оптимизатор SQL-запросов, основанный на нейронной сети  [new]
MasterZiv
Member

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

On 20.04.2011 14:13, Siemargl wrote:

> /Недостатки нового подхода:/

Недостаток (главный) -- как я понимаю, в том,
что сервер СУБД для оптимизации должен будет хранить
в каком -то виде нейронные сети для ВСЕХ КОГДА-ЛИБО
ВЫПОЛНЯВШИХСЯ ЗАПРОСОВ.

> Поскольку идеи могут мне же в будущем пригодиться, например продам инвесторам
> в Сколково, авторское право застолблю за собой =)

Кажется, ты с этим уже опоздал. Кажется, где-то уже используются НС в оптимизаторах.

Posted via ActualForum NNTP Server 1.4

20 апр 11, 15:26    [10542376]     Ответить | Цитировать Сообщить модератору
 Re: Идея. Оптимизатор SQL-запросов, основанный на нейронной сети  [new]
Siemargl
Member

Откуда: 010100
Сообщений: 6642
Gluk (Kazan), конечно ты помнишь про Oracle ADDM =)

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

Кроме того - ничего не мешает мониторинг и анализ вести на отдельном сервере.
20 апр 11, 16:16    [10542811]     Ответить | Цитировать Сообщить модератору
 Re: Идея. Оптимизатор SQL-запросов, основанный на нейронной сети  [new]
MasterZiv
Member

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

On 20.04.2011 17:16, Siemargl wrote:

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

ВСЕХ_КОГДА_ЛИБО_ВЫПОЛНЯВШИХСЯ_ЗАПРОСОВ ?

Posted via ActualForum NNTP Server 1.4

20 апр 11, 16:31    [10542928]     Ответить | Цитировать Сообщить модератору
 Re: Идея. Оптимизатор SQL-запросов, основанный на нейронной сети  [new]
interesting
Guest
Siemargl
изобретение нового велосипеда с ракетным двигателем.


А в качестве тормоза якорь выбрасывать бум , или как ?




Кроме взаимоисключающих параграфов ничего не увидел


Siemargl



- CBO требует константного обновления статистики, иногда очень долго выбирает план

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



Проверенные долго

проверенные основаны на
http://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BC%D0%B1%D0%B8%D0%BD%D0%B0%D1%82%D0%BE%D1%80_%D0%BD%D0%B5%D0%BF%D0%BE%D0%B4%D0%B2%D0%B8%D0%B6%D0%BD%D0%BE%D0%B9_%D1%82%D0%BE%D1%87%D0%BA%D0%B8

( Упрощенно это рекурсия )

и
http://ru.wikipedia.org/wiki/%D0%9A%D0%BB%D0%B0%D1%81%D1%81_P

и очень навороченные ( типа генетических) еще на :

http://ru.wikipedia.org/wiki/%D0%9A%D0%BB%D0%B0%D1%81%D1%81_NP

А на чем вы хотите обосновать свою идею ,
на каком основании у вас получится быстрее и при каких условиях?


Siemargl
6. При явном преимуществе нового плана выполнения – выдаем хинт.

1. Элементом нейронной сети является простая операция запроса, включая параметры и текущие условия на сервере. Элементы имеют взаимные связи.


Как в этом случае спасет хинт ?

А никак , Вам в соотвествии с требованием
http://ru.wikipedia.org/wiki/%D0%90%D1%81%D0%B8%D0%BC%D0%BF%D1%82%D0%BE%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D1%83%D1%81%D1%82%D0%BE%D0%B9%D1%87%D0%B8%D0%B2%D0%BE%D1%81%D1%82%D1%8C

придется планы персчитывать заново,
если текущие условия на сревере изменились достаточно сильно.

Если вес текущих условий недостаточен для пересчета, то зачем вся эта затея ?



Siemargl
- большинство запросов в продакшн-системах повторяются и их набор конечен

3. Запрос, таким образом представляет собой дерево N элементов плюс M параметров. Простые условия уменьшают размерность многомерного пространства сети (максимум M+N).



Для наихудшего случая M*N факториал , тоже конечная влечина
Не забываем про текущие условия на сервере и их вес в принятии решения о пересчете .

В моем понимании ИМХО вы хотите получить бесконечные ресурсы для решения конечного набора задач.




Siemargl
P.S. Так как основная идея состоит в разбиении сложного запроса на атомарные части и их группировке и обучении сети частиц, алгоритм с полным правом может называться НАНООПТИМИЗАТОРОМ SQL-запросов.



Откатопригодная идея
20 апр 11, 16:43    [10543016]     Ответить | Цитировать Сообщить модератору
 Re: Идея. Оптимизатор SQL-запросов, основанный на нейронной сети  [new]
interesting
Guest
MasterZiv
On 20.04.2011 17:16, Siemargl wrote:

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

ВСЕХ_КОГДА_ЛИБО_ВЫПОЛНЯВШИХСЯ_ЗАПРОСОВ ?


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

( Конкурентная среда , CPU, память , скорость ввода вывода)

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

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

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

В конечном итоге он остановится на ограниченном количестве колес удовлетоворящих
[8,9][0-9]% факторов.
Вернется к класической модели велосипеда , но затратиn при этом очень много ресурсов .
20 апр 11, 17:18    [10543287]     Ответить | Цитировать Сообщить модератору
 Re: Идея. Оптимизатор SQL-запросов, основанный на нейронной сети  [new]
interesting
Guest
автор
4. Требуется решить с помощью нейросети «задачу коммивояжера».



Пока противник ( комивояжер) рисует карту наступления,
мы ( условия на сервере) меняем ландшафты.....

( С) ДМБ
20 апр 11, 17:58    [10543649]     Ответить | Цитировать Сообщить модератору
 Re: Идея. Оптимизатор SQL-запросов, основанный на нейронной сети  [new]
Siemargl
Member

Откуда: 010100
Сообщений: 6642
Нейросеть и предназначена для выбора решения при неполных входных данных.

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

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

Пока нейросеть не обучена, нужно использовать старые привычные оптимизаторы.
А пробы вариантов предлагается проводить в фоне - отдельными задачами.
20 апр 11, 19:03    [10544002]     Ответить | Цитировать Сообщить модератору
 Re: Идея. Оптимизатор SQL-запросов, основанный на нейронной сети  [new]
interesting
Guest
Siemargl
Нейросеть и предназначена для выбора решения при неполных входных данных.

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

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

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


Хорошо, давайте зайдем с другой стороны

http://ru.wikipedia.org/wiki/%D0%A1%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B0_%D0%BC%D0%B0%D1%81%D1%81%D0%BE%D0%B2%D0%BE%D0%B3%D0%BE_%D0%BE%D0%B1%D1%81%D0%BB%D1%83%D0%B6%D0%B8%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F

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


http://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%BC%D0%B0%D1%81%D1%81%D0%BE%D0%B2%D0%BE%D0%B3%D0%BE_%D0%BE%D0%B1%D1%81%D0%BB%D1%83%D0%B6%D0%B8%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F

автор
рассматриваются только моменты времени поступления заявок, т.е. факты заявок без уточнения деталей каждой конкретной заявки.
........
Пуассоновский поток заявок удобен при решении задач ТМО. Строго говоря простейшие потоки редки на практике, однако многие моделируемые потоки допустимо рассматривать как простейшие



Приведите пример факторов работы оптмизатора , которые

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


То есть

http://ru.wikipedia.org/wiki/NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0

автор
В теории алгоритмов NP-полная задача — задача из класса NP, к которой можно свести любую другую задачу из класса NP за полиномиальное время. Таким образом, NP-полные задачи образуют в некотором смысле подмножество «самых сложных» задач в классе NP; и если для какой-то из них будет найден «быстрый» алгоритм решения, то и любая другая задача из класса NP может быть решена так же «быстро».


Ваша машина за достаточно быстрое время , относительно времени потраченной на ее создание ,
найдет ограниченное число решений соизмеримое ( находящееся в уже извстной для создателей оптимизаторов зависимости )
с
Siemargl
- большинство запросов в продакшн-системах повторяются и их набор конечен


И дальше будет работать в пустую в поисках непонятно чего.

Если не найдет , то тем более никому не будет интересна
20 апр 11, 19:45    [10544206]     Ответить | Цитировать Сообщить модератору
 Re: Идея. Оптимизатор SQL-запросов, основанный на нейронной сети  [new]
interesting
Guest
В отличие от генетических алгоритмов у нейронной сети в текущих автономных ( без подсказок) реализациях
очень слаба обратная связь для поиска вариантов обхода локальных экстремумов.

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

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

То есть если вы ей этих данных не предоставите , то она ( если качественной получится) ,
нагенерирует их вам методом проб и ошибок.
20 апр 11, 20:35    [10544334]     Ответить | Цитировать Сообщить модератору
 Re: Идея. Оптимизатор SQL-запросов, основанный на нейронной сети  [new]
-2-
Member

Откуда:
Сообщений: 15330
interesting
нагенерирует их вам методом проб и ошибок.
Рано или поздно на любой сколь угодно сложный запрос система незамедлительно будет давать ответ 42
20 апр 11, 21:25    [10544431]     Ответить | Цитировать Сообщить модератору
 Re: Идея. Оптимизатор SQL-запросов, основанный на нейронной сети  [new]
Siemargl
Member

Откуда: 010100
Сообщений: 6642
interesting, ты перевозбудился ))

Во-первых, это только идея, а не ответ поисков Святого Грааля.

Во-вторых, сравнивать детерминированные алгоритмы (NP- итд) с и алг.с нечеткой логикой неправильно.

В-третьих, еще ничего не даже не опробовано, а ты уже знаешь ответ (про локальные экстремумы итд)!? )))))
20 апр 11, 22:42    [10544625]     Ответить | Цитировать Сообщить модератору
 Re: Идея. Оптимизатор SQL-запросов, основанный на нейронной сети  [new]
нейросети
Guest
Новые MS SQL Profiler с Tuning Wizard и Oracle AWR, только на фантастических алгоритмах.
Эти нейросети хоть где-то удачно используются кроме научных изысканий?
20 апр 11, 22:50    [10544656]     Ответить | Цитировать Сообщить модератору
 Re: Идея. Оптимизатор SQL-запросов, основанный на нейронной сети  [new]
interesting
Guest
Siemargl
interesting, ты перевозбудился ))



Попал 100% , я действительно был на психологическом взводе :)

[quot Siemargl]

Во-вторых, сравнивать детерминированные алгоритмы (NP- итд) с и алг.с нечеткой логикой неправильно.

Вам шашечки или ехать ?
Если ехать , нет там необходимости в нечеткой логике.
Она в некоторых случаях может даже вредить.

Siemargl
В-третьих, еще ничего не даже не опробовано,
а ты уже знаешь ответ (про локальные экстремумы итд)!? )))))


Попадание в экстремум можно описать простым примером из жизни.
Вы когда нибудь медкомисию на права или в армию проходили ?
У окулиста есть такая книжечка, с цифрами и геометрическими фигрурами
нарисованными с помощью мозаики разноцветных кружечков.
с ее помощью окулист однозначно диагностирует проблемы с цветовостприятием испытуемого.
Если есть проблемы с цветовосприятием ( искажена часть потока входящих данных) ,
испытемый будет видеть вместо тройки квадрат , или вместо семерки двойку.
И никакими разумными доводами ( диагноз врача в том числе) , испытуемого невозможно
переубедить в том что прочие окружающие видят не то что видит он.
Он в принятиях своих решений будет основываться на том что видит
он а не на том что говорят ему окружающие ( другие нейронные сети).
Если сеть самостоятельно не способа пройти окулиста
( у оптимизатора не будет возможности дать пользователю на лапу) ,
то можете посчитать во сколько для сети обойдется выход из такого экстремума ,
и за каждой новой допущенной лажей , вероятность ухода в полный
перебор факториала вариантов становится все выше и выше.
21 апр 11, 10:32    [10545864]     Ответить | Цитировать Сообщить модератору
 Re: Идея. Оптимизатор SQL-запросов, основанный на нейронной сети  [new]
interesting
Guest
нейросети
Новые MS SQL Profiler с Tuning Wizard и Oracle AWR, только на фантастических алгоритмах.
Эти нейросети хоть где-то удачно используются кроме научных изысканий?


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

От этого будет зависеть что в конечном итоге получится из сети ,
дерево ( овощь) , курица , овца, собака или человек.
21 апр 11, 10:59    [10546040]     Ответить | Цитировать Сообщить модератору
 Re: Идея. Оптимизатор SQL-запросов, основанный на нейронной сети  [new]
interesting
Guest
interesting
то можете посчитать во сколько для сети обойдется выход из такого экстремума ,
и за каждой новой допущенной лажей , вероятность ухода в полный
перебор факториала вариантов становится все выше и выше.


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

Этот алгоритм работает около 500 млн лет , и до сих пор считает ответ на вопрос
о главном смысле жизни.

:)
21 апр 11, 11:25    [10546282]     Ответить | Цитировать Сообщить модератору
 Re: Идея. Оптимизатор SQL-запросов, основанный на нейронной сети  [new]
interesting
Guest
Если у вас нет детей , торопитесь.
Только в этом случае можно будет однозначно сказать , что вы приняли активное участие
в поиске смысла жизни. ( есть полезной конфигурацией нейронной сети)
с точки зрения алгоритмики заложенной ее создателем.
Если кто то, по каким то причинам не хочет заводить детей - его конфигурация будет выбракована,
так как это тоже локальный экстремум.

зы Все завязываю с философским офтопиком.
21 апр 11, 11:49    [10546524]     Ответить | Цитировать Сообщить модератору
 Re: Идея. Оптимизатор SQL-запросов, основанный на нейронной сети  [new]
факториал
Guest
interesting
... вероятность ухода в полный
перебор факториала вариантов становится все выше и выше.

Очень полезный пост, появляется новая возможность послать в факториал.
21 апр 11, 16:09    [10548735]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
Все форумы / Сравнение СУБД Ответить