Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 4 [5]      все
 Re: Работа с большими данными  [new]
mayton
Member

Откуда: loopback
Сообщений: 41382
schi
mayton
DBMS умеет по другому. Он бъет сложным и универсальным ударом который
называется B+Tree. Это дерево. Но особое. Оптимизированное для дисковых
блочных операций. И разумеется оно нелетает без прослойки LRU-подобного
кеша блоков.


Первый раз такую трактовку слышу, про оптимизацию с дисками. Не поделитесь источником ?

1) Ваша постановка вопроса меня удивляет. Если вы из сегмента It - то вы должны были проходить
курс алгоритмы и структуры данных. Там - дают вводную по деревьям (красные-чорные, бинарные,
тернарные, АВЛ) и в том числе B+Tree, N-того порядка. Последние просто являются
частным случаем предыдущих деревьев при условии что группа узлов (Nodes)
объединяются в дисковый блок (2/4/8/16K) массив и все операции с узлами
делаются в рамках блока. Это дает оптимальное использование I/O.

Один из производителей DBMS их описывает так.
B-tree indexes are the standard index type. They are excellent for highly selective indexes (few rows correspond to each index entry) and primary key indexes. Used as concatenated indexes, a B-tree index can retrieve data sorted by the indexed columns.

Далее по ссылке отрисовывается вся внутренняя структура.

https://docs.oracle.com/database/122/CNCPT/indexes-and-index-organized-tables.htm#CNCPT88834

Детально об этом пишут разные писатели. Джонатан Льюис. Том Кайт.

Решение нашей задачи в рамках DBMS я вижу так:

create table FuckenWordsDictionary(word VARCHAR2(2000) primary key) organization index;


Далее - наполняем этот справочник insert-ами и игнорируем ошибку ORA-00001. Отбрасываем дубли.

Profit.

2) По кешам.

Механизм кеша - это я сказал ниочом и обо всем. Практически все современные
DBMS используют разные варианты кешей. IBM DB2, Postgres e.t.c. А кто не использует
тот дурак и у того нет перформанса.

Поэтому моя фраза о кешах - это попадание пальцем в небо. Так-же как и
"Волга Впадает в Каспийское море".
20 авг 17, 22:01    [20737423]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
schi
Member

Откуда: Москва
Сообщений: 2601
mayton

Первый раз такую трактовку слышу, про оптимизацию с дисками. Не поделитесь источником ?

1) Ваша постановка вопроса меня удивляет. Если вы из сегмента It - то вы должны были проходить
курс алгоритмы и структуры данных. Там - дают вводную по деревьям (красные-чорные, бинарные,
тернарные, АВЛ) и в том числе B+Tree, N-того порядка. Последние просто являются
частным случаем предыдущих деревьев при условии что группа узлов (Nodes)
объединяются в дисковый блок (2/4/8/16K) массив и все операции с узлами
делаются в рамках блока. Это дает оптимальное использование I/O.

Один из производителей DBMS их описывает так.
B-tree indexes are the standard index type. They are excellent for highly selective indexes (few rows correspond to each index entry) and primary key indexes. Used as concatenated indexes, a B-tree index can retrieve data sorted by the indexed columns.

Далее по ссылке отрисовывается вся внутренняя структура.

https://docs.oracle.com/database/122/CNCPT/indexes-and-index-organized-tables.htm#CNCPT88834

Детально об этом пишут разные писатели. Джонатан Льюис. Том Кайт.

[/quot]

Ничего не понял. Кайта и Льюиса читал, с деревьями знаком несколько раньше, чем вышли книги Кайта и Льюиса же, и ни разу не слышал про оптимизацию использования деревьев с точки зрения ввода-вывода, поэтому и заитересовался.
20 авг 17, 22:09    [20737449]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mayton
Member

Откуда: loopback
Сообщений: 41382
schi
Ничего не понял. Кайта и Льюиса читал, с деревьями знаком несколько раньше, чем вышли книги Кайта и Льюиса же, и ни разу не слышал про оптимизацию использования деревьев с точки зрения ввода-вывода, поэтому и заитересовался.

Вся дисковая оптимизация для дисков старого поколения (магнитных) базируется
на уменьшении количества чтений и записей блоков (db_blocks). Сам по себе блок может
варьироваться от 512 байт до 64к. Это зависит от ОС и архитектуры. Поэтому
все структуры данных такие как таблицы и индексы бьются на блоки и читаются
и сериализуются кусками кратными блоку. Это считается ТруЪ для всех DBMS.
20 авг 17, 22:23    [20737485]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
schi
Member

Откуда: Москва
Сообщений: 2601
mayton
schi
Ничего не понял. Кайта и Льюиса читал, с деревьями знаком несколько раньше, чем вышли книги Кайта и Льюиса же, и ни разу не слышал про оптимизацию использования деревьев с точки зрения ввода-вывода, поэтому и заитересовался.

Вся дисковая оптимизация для дисков старого поколения (магнитных) базируется
на уменьшении количества чтений и записей блоков (db_blocks). Сам по себе блок может
варьироваться от 512 байт до 64к. Это зависит от ОС и архитектуры. Поэтому
все структуры данных такие как таблицы и индексы бьются на блоки и читаются
и сериализуются кусками кратными блоку. Это считается ТруЪ для всех DBMS.


Да, я знаю, что Волга впадает в Каспийское море, но причем тут B-деревья ? :)
На уменьшении количества операций ввода-вывода направлена любая оптимизация, пока диски не быстрее памяти, увы.

Ждем автора, от него должна информация поступать, а то, может, ему и оптимизация не нужна вовсе.
21 авг 17, 10:49    [20737990]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
Bred eFeM
Member

Откуда:
Сообщений: 525
mayton
Как вы любите сортировать! ... табличка 4Гб ключей ...
это на 1*10^9 или на 4*10^9 ключей?

Считаем сколько будет чанков.
там слова? - а значит буквы - 32*2+1 будет достаточно.
Итого, максимум 1,5*10^9 слова из 20 разных первых символов длиной 5 (байт), которые на основании свойств моей волшебной функции сортируются с выбрасыванием копий не дольше 2х(чтение-запись) диска.

И никакой сортировки. Как вам?
И что с этим неупорядоченным 150G "как вам" делать дальше? Индексы строить, хеши считать...
21 авг 17, 11:50    [20738157]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mayton
Member

Откуда: loopback
Сообщений: 41382
Я своё мнение кажется сказал в первом посте. Грузить в базу.

А все остальное в топика - это игры разума. И я поддерживаю их ради дискурса.
21 авг 17, 13:45    [20738617]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mayton
Member

Откуда: loopback
Сообщений: 41382
В продолжение топика. Для 150Гб файла в качестве метрики эффективности
алгоритма КМК мы должны брать за основу т.н. Full-Table-Scan (это в терминологии БД).

Или грубо говоря 1 проход чтением по нашему файлу. Full-File-Scan (если мы работаем
со своими самописными алгоритмами). Для краткости - FFS.

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

Как я уже говорил - ленточная сортировка - это сразу более чем несколько FFS.
Ванговать не буду. Это количество зависит от оперативы у вас на борту.
26 авг 17, 12:09    [20750928]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1748
Можно предложить симбиоз оптимистичного и пессимистичного 20737243 алгоритма.

Сначала оптимистично грузим данные в хеш-таблицу пока не накопится некоторое предельное количество различных ключей, например, 2*10^6.

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

Если же различных ключей много, например, 128*10^6, то мы рано или поздно достигнем лимит. В этом случае выгружаем промежуточные результаты в 128 файлов, расслоив данные по хеш-коду. Затем очищаем таблицу, загружаем новую порцию, снова расслаиваем и дописываем в те же файлы. Продолжаем до исчерпания исходных данных. На второй фазе алгоритма поочередно грузим каждый из 128 промежуточных файлов в хеш-таблицу (с другой хеш-функцией) и дописываем из нее данные в результирующий файл.
26 авг 17, 12:52    [20750974]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mayton
Member

Откуда: loopback
Сообщений: 41382
Aleksandr Sharahov, +1

Я тоже об этом думал. Но у меня была идея такая. Мы (к примеру) имеем не 1 а аж минимум 3 разных
алгоритма унификации большого толстого грёбаного файла (big-fat-ugly-file (BFUF)).

И во всех трех алгоритмах всегда присутствует первая фаза FFS. Что мы будем делать в эту фазу?
Сразу много всего.
- анализировать сведенья (число строк. средняя длина. количество уникальных на тек.момент,
гистограммы и прочие характеристики текста. Языки кодировки.)
- параллельно строить hash-table или другую структуру данных полезную для distinct of BFUF.
- если при параллельной постройке hash-table мы вышли за какие-то разумные границы
расходов памяти - то процесс анализа продолжаем до конца.
26 авг 17, 13:03    [20750983]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
Alibek B.
Member

Откуда:
Сообщений: 3153
Андрей Александрович.
Есть текстовые данные - порядка 2 тб в виде набора файлов ( файлы от 200 мб до 150 гб )
Задача проверить все файлы и удалить дубликаты ( а так же скомпоновать данные )

Что является записью (по которой выявляются дубликаты)?
Весь файл? Строка? Слово?
Если строка или слово, то необходимости использования БД я пока не вижу.
Нужно проиндексировать записи в имеющихся файлах, упорядочив их по языку и алфавиту.
При наличии индексов работать с этими файлами или выгрузить обработанные и отсортированные данные будет легче.
А удалять из середины 150ГБ файла несколько строк-дубликатов может быть накладно.
26 авг 17, 13:37    [20751007]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mayton
Member

Откуда: loopback
Сообщений: 41382
Alibek B.
А удалять из середины 150ГБ файла несколько строк-дубликатов может быть накладно.
26 авг 17, 14:25    [20751050]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mayton
Member

Откуда: loopback
Сообщений: 41382
Всем заинтересованным.

Тема имеет логическое продолжение здесь Тяпничная унификация
9 сен 17, 17:27    [20783917]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 4 [5]      все
Все форумы / Программирование Ответить