список в реляционной БД
В постгресе есть тип элементов массив и позволяет делать что-то вроде:
SELECT * FROM table WHERE 123 = ANY (array_field);
Но то ли я ламо и не нашёл как сделать индекс для таких запросов, то ли там такого ещё нет.
SELECT * FROM table WHERE 123 = ANY (array_field);
Но то ли я ламо и не нашёл как сделать индекс для таких запросов, то ли там такого ещё нет.
Из объяснения как-то не очень понятно, чего именно хочется 
Как я понял, хочется примерно такую табличку:
Также хочется иметь возможность быстро по key получать value и по value быстро находить key. Так? Нужно ли уметь по value находить номер строки и по номеру строки находить value (при условии, что таблица отсортирована по key)? Если не нужно, то все просто, достаточно присвоить key значения, идущие с некоторым интервалом (100, 200, 300, ... а при вставке в середину присваивать key незанятое значение из соответствующего интервала. А вот если нужно, то все будет несколько сложнее, и сильно зависит от объема данных, частоты и характера запросов на чтение и изменение данных.
Если объем данных небольшой, а изменения в таблице происходят редко, то варианты с перенумеровкой и пересозданием списка тоже неплохие, особенно, если ссылок на эту таблицу нет
Как я понял, хочется примерно такую табличку:
key | value
-----------
3 | value1
4 | value2
5 | value3
6 | value4
7 | value5
Также хочется иметь возможность быстро по key получать value и по value быстро находить key. Так? Нужно ли уметь по value находить номер строки и по номеру строки находить value (при условии, что таблица отсортирована по key)? Если не нужно, то все просто, достаточно присвоить key значения, идущие с некоторым интервалом (100, 200, 300, ... а при вставке в середину присваивать key незанятое значение из соответствующего интервала. А вот если нужно, то все будет несколько сложнее, и сильно зависит от объема данных, частоты и характера запросов на чтение и изменение данных.
Если объем данных небольшой, а изменения в таблице происходят редко, то варианты с перенумеровкой и пересозданием списка тоже неплохие, особенно, если ссылок на эту таблицу нет
Также хочется иметь возможность быстро по key получать value и по value быстро находить key. Так? Нужно ли уметь по value находить номер строки и по номеру строки находить value (при условии, что таблица отсортирована по key)?Не совсем. Если бы нужно было по key чего-то находить, то это уже был бы хеш.
Нужно находить только value. В таблице с массивом помимо значения мне нужна будет ещё ссылка на объект, которому этот массив "принадлежит". И для поиска всего 2 задачи - по значению найти какому объекту оно принадлежит (т.е. индекс по value) и по номеру объекта восстановить значение массива упорядоченном виде (индексирование ссылки на объект). И кроме поиска - ещё задачи изменения есть: вставить значение, удалить значение, ...
Собственно какие при этом будут key не особо важно, главное чтобы они задавали порядок.
Если не нужно, то все просто, достаточно присвоить key значения, идущие с некоторым интервалом (100, 200, 300, ... а при вставке в середину присваивать key незанятое значение из соответствующего интервала.А что делать когда он закончится - всё равно придётся проводить смещение когда-нибудь.
Если объем данных небольшой, а изменения в таблице происходят редко, то варианты с перенумеровкой и пересозданием списка тоже неплохие, особенно, если ссылок на эту таблицу нетНу в принципе в конкретной случае массивы будут не очень большими и я склоняюсь к варианту похерить-создать заново.
Кажется, понял, ты хочешь хранить в одной таблице упорядоченные массивы значений, соответствующих каким-то объектам, т.е. в таблице три столбца: идентификатор объекта-"хозяина", значение и порядок сортировки. И еще индексы (значение, идентификатор хозяина) и (идентификатор хозяина, порядковый номер, порядок сортировки).
Ну, это зависит от того, что у тебя за данные. В общем случае, конечно, придется пересчитывать. Но часто есть какие-то естественные ограничения (например, количество элементов в массиве заведомо не может быть больше какого-то числа, или, например, новые значения будут вставляться в основном в начало массива, или еще какие-то тогда может быть реальным подобрать удачное разбиение.
Но запариваться этим стоит только если в таблице данных много и важна производительность операций вставки. В противном случае проще удалить и вставить заново.
Вообще, реляционные БД не очень удачно подходят для работы с такого рода данными, ибо в них не определен порядок хранения записей в таблицах, поэтому приходится его реализовывать вручную.
А что делать когда он закончится - всё равно придётся проводить смещение когда-нибудь.
Ну, это зависит от того, что у тебя за данные. В общем случае, конечно, придется пересчитывать. Но часто есть какие-то естественные ограничения (например, количество элементов в массиве заведомо не может быть больше какого-то числа, или, например, новые значения будут вставляться в основном в начало массива, или еще какие-то тогда может быть реальным подобрать удачное разбиение.
Но запариваться этим стоит только если в таблице данных много и важна производительность операций вставки. В противном случае проще удалить и вставить заново.
Вообще, реляционные БД не очень удачно подходят для работы с такого рода данными, ибо в них не определен порядок хранения записей в таблицах, поэтому приходится его реализовывать вручную.
Вообще, реляционные БД не очень удачно подходят для работы с такого рода данными, ибо в них не определен порядок хранения записей в таблицах, поэтому приходится его реализовывать вручную.Это-то всё понятно. Понятно, что можно подогнать разреженные порядковые номера под ограничения так, чтобы они не сошлись никогда и т.п.
Не то чтобы я особо заморачиваюсь. Просто я вот задумался над этим вопросом, а он на столько общий, что наверняка не я один над этим задумывался. Вот я и подумал - а вдруг какие-то общие и элегантные решения этого придуманы.
В нормальных БД это элементарно. А для остальных, наверняка, что-нибудь есть в книге Joe Celko.
Позволь спросить, а что такое нормальная БД с твоей точки зрения?
Знаю, что бывают всякие частные расширения, с помощью которых задача решается относительно просто. Например, некоторые СУБД умеют индексировать столбцы с XML, и там можно список значений сохранять в нем.
А общее и элегантное решение, если оно существует, мне было бы и самому интересно услышать.
А общее и элегантное решение, если оно существует, мне было бы и самому интересно услышать.
В постгресе есть тип элементов массив и позволяет делать что-то вроде:Недавно на семинаре выступал девелопер постгреса, обещал, что есть такие индексы. Может, надо версию поновее поставить.
SELECT * FROM table WHERE 123 = ANY (array_field);
Но то ли я ламо и не нашёл как сделать индекс для таких запросов, то ли там такого ещё нет.
Хочется сохранить список (упорядоченный набор значений одного типа нефиксированной длины) в базе данных.А если положить индекс равным значению из предыдущей по порядку строчки? Для первой строчки - NULL или специальное значение -Inf.
Видится что-то вроде таблицы (индекс, значение).
однонаправленный список поверх реляционки?
зависимость между отдельными операциями становится больше,
атомарность операций - ниже
зы
у себя стараемся использовать float с последующей периодической переиндексацией
зависимость между отдельными операциями становится больше,
атомарность операций - ниже
зы
у себя стараемся использовать float с последующей периодической переиндексацией
однонаправленный список поверх реляционкии предыдущий, и следующий элемент находятся примерно одинаково легко
зависимость между отдельными операциями становится больше,периодическая переиндексация конечно очень атомарная операция
атомарность операций - ниже
зы
у себя стараемся использовать float с последующей периодической переиндексацией
Я делал как-то так…
Для добавления элемента откуда-то берём n=2:
Получилось:
lynn=> \d lists
Table "public.lists"
Column | Type
---------+-----------------------
list_id | integer
n | integer
value | character varying(10)
lynn=> select * from lists order by list_id, n;
list_id | n | value
---------+---+--------
1 | 1 | a
1 | 2 | b
1 | 3 | z
2 | 1 | d
2 | 2 | dx
2 | 3 | adx
Для добавления элемента откуда-то берём n=2:
lynn=> update lists set n = n+1 where list_id = 1 and n >= 2;
UPDATE 2
lynn=> insert into lists values(1,2,'new el');
INSERT 0 1
Получилось:
lynn=> select * from lists where list_id = 1 order by n;
list_id | n | value
---------+---+--------
1 | 1 | a
1 | 2 | new el
1 | 3 | b
1 | 4 | z
зависимость между отдельными операциями становится больше,Этот вариант - уж точно лучше, чем вся эта переиндексация и костыли со свободными 100 позициями.
атомарность операций - ниже
Раз список частный случай дерева, то можно использовать записи (id, parent_id, value а потом древовидными запросами делать выборки.
Параметры можно попробовать положить в xmltype и создать по нему индекс.
Параметры можно попробовать положить в xmltype и создать по нему индекс.
Позволь спросить, а что такое нормальная БД с твоей точки зрения?kdb+
Недавно на семинаре выступал девелопер постгреса, обещал, что есть такие индексы. Может, надо версию поновее поставить.А он не говорил каким SQL-заклинанием они делаются?
зыfloat в этом плане вроде не намного лучше "разреженного" int в плане разрядности. Хотя может разве удобнее только. А как проверяется, что индекс "сошёлся"?
у себя стараемся использовать float с последующей периодической переиндексацией
kdb+Не знаю что это такое - поэтому уточню: она реляционная, opensource?
она реляционная
Да, хотя не совсем похожа на привычные РСУБД.
opensource
Нет. Не open source и стоит хороших денег.
Да, хотя не совсем похожа на привычные РСУБД.А чем не похожа?
Ну я так сумбурно напишу, что сразу вспомню.
* Эта СУБД обычно использует много оперативной памяти (можно сказать, что это in-memory db).
* В таблицах определен порядок строк.
* Даные хранятся по колонкам, не по строкам.
* В СУБД встроен язык программирования q, родственник APL, позволяющий удобно работать с временными рядами. Насколько я понимаю все что можно выразить в sql, можно написать на q, обратное не верно.
В общем эта штука заточена под обработку временных рядов и применяется обработки котировок и подобного.
* Эта СУБД обычно использует много оперативной памяти (можно сказать, что это in-memory db).
* В таблицах определен порядок строк.
* Даные хранятся по колонкам, не по строкам.
* В СУБД встроен язык программирования q, родственник APL, позволяющий удобно работать с временными рядами. Насколько я понимаю все что можно выразить в sql, можно написать на q, обратное не верно.
В общем эта штука заточена под обработку временных рядов и применяется обработки котировок и подобного.
Ну да, не совсем реляционная получается.
Спасибо за небольшой ликбез.
Спасибо за небольшой ликбез.
Не open source и стоит хороших денег.хороших - это каких?
Ну да, не совсем реляционная получается.Она реляционная. Поддерживается SQL92 полностью (ну за исключением деталей). Просто sql только часть языка, q - полноценный функциональный векторный язык программирования, поэтому на нем удобно решать задачи, которые на тандемах типа SQL+PLSQL решаются через жопу.
хороших - это каких?40к за процессор, 4 процессора минимум.
Она реляционная.Ну либо там не фиксирован порядок строк, либо она немножко не реляционная всё же.
Слушайте, а что, в самом деле нет аналогичного трюка для списка? В смысле, как дерево можно эффективно хранить в реляционной базе, так и список, наверное?
Я поискал в интернетах и ничего не нашёл. Как правильно искать вообще?
Я поискал в интернетах и ничего не нашёл. Как правильно искать вообще?
если честно, я так и не понял, чем плохо стандартное представление списка (двунаправленного как
(id, value, next_id, prev_id)
если ограничиваться операциями вставки, и перехода к следующему/предыдущему, то быстрее придумать нельзя. IMHO
(id, value, next_id, prev_id)
если ограничиваться операциями вставки, и перехода к следующему/предыдущему, то быстрее придумать нельзя. IMHO
возможно автор хочет уметь не только итерироваться взад/вперед, но и иметь произвольный доступ по порядковому номеру?
это тогда уже называется массив, а не список 
В смысле, как дерево можно эффективно хранить в реляционной базе, так и список, наверное?А дерево можно "эффективно" хранить? Эффективность - она для всех разная. Это может по месту считаться, по времени конкретных операций, нужных в данной задаче.
возможно автор хочет уметь не только итерироваться взад/вперед, но и иметь произвольный доступ по порядковому номеру?Нет, в данном случае, произвольный доступ на основе порядкового номера не нужен. 2 необходимые операции поиска уже были описаны.
если честно, я так и не понял, чем плохо стандартное представление списка (двунаправленного какПро список с указателями уже упоминалось. Тут как всегда есть плюсы и минусы - быстрая вставка, но сравнительно геморройный поиск всех.
(id, value, next_id, prev_id)
если ограничиваться операциями вставки, и перехода к следующему/предыдущему, то быстрее придумать нельзя. IMHO
Получается, что ничего интереснее, чем то, что мы имеем в оперативной памяти, в реляционной модели для этого ещё не придумали (тут по крайней мере).
40к за процессор, 4 процессора минимум.Понятно. Просто год назад пришлось делать похожую (судя по описанию) с точки зрения функциональности нереляционную базу. Было бы обидно, если бы оказалось, что изобретали велосипед. Но 40 тонн - это не вариант
Оставить комментарий
tokuchu
Сейчас прошвырнулся по инету, но ничего путного не нашёл. Задача такая:Хочется сохранить список (упорядоченный набор значений одного типа нефиксированной длины) в базе данных.
Видится что-то вроде таблицы (индекс, значение). Значения в отдельных строках таблицы, т.к. хочется иметь индексирование по ним, упаковка значений в одно поле не катит. А индекс может быть любой - главное чтобы задавал порядок.
Но кроме всего этого ещё хочется, чтобы обычные операции над списком выполнялись просто - добавление и удаление элементов, в том числе в середину. Если с удалением проблем нет - индекс можно не трогать, то при добавлении, возможно, придётся перенумеровать. Или при каждом изменении "чистить" список и создавать его заново?
В общем есть ли какие известные решения данной задачи или мысли на эту тему?