alexhemp
Новичок
Wicked
1. Человек задает префикс, он может быть достаточно мал (2-3 символа) и группа соотв. ему - мала. Строки неравномерно распределяются по пространству возможных значений.
Проблема как раз выбрать алгоритм поиска не сильно от этого зависящий. т.е. одинаково быстро ищущий малые префиксы на малых группах, длинные префиксы на болшиих.
2. Именно. Но заранее я этого не знаю, поэтому нужно брать какой-то усредненный вариант. Все упирается как раз в выбор длинны этого префикса.
3. Это я понимаю, но сути дела это не меняет - упираемся в выбор размерности. (4 в твоем случае).
4. Вот именно, там используется индекс "слов". Инверсный индекс имеет смысл при большом количестве повторений этих "слов", тогда он дает выигрыш, опять-же за счет того, что список целых просмотреть быстрее чем сам текст. А у меня повторений не так много, хотя идея мне понятна. Опять - упираемся в выбор размера "слова". Спасибо, я над этим подумаю ;-)
5. Пока это большая таблица, грубо говоря
ID (INT autoincrement), CODE (char(50)) - код детали, SUPPLIER_ID (INT) - идентификатор поставщика, PRICE (FLOAT) - цена
Далее служебные поля
CLEAN_CODE (char(50)) - "очищенный" от мусора код (без пробелов, дефисов и т.п.), HASH (INT) - результат хеш-фции.
Пока хэш-фция - это битовая строка по 6 бит на символ + первые 4 бита - нули (потом возьму может 4 бита из следующего символа, пока для тестов и этого хватит).
Индекс - один - по HASH (ну и PRIMARY - хотя возможно от него откажусь, если не будет необходимости ссылаться на конкретную строку).
-~{}~ 13.12.06 16:57:
А, да я тут понял - индекс MySQL по первым 5-ти символам и есть инвертированный индекс для этих 5-ти символов, размерность просто элемента = 1 ;-)
-~{}~ 19.12.06 01:19:
Забыл написать - 8.5 миллионов записей, индекс занимает примерно 10% от объема данных
1.5 гига данные, 230 мегов индекс (из них половина - primary key)
LOAD DATA INFILE работает очень быстро, 10000 строк в секунду примерно - таблица MyISAM (оптимальное на мой взгляд решение для таблицы с редкой массовой вставкой).
Это без временного отключения индексов на время обновления.
Запрос на выборку колеблется в пределах 1-10 ms, считаю вполне удачное решение.
Ну что-же теперь купим production сервер и запустим на нем. Попробуем 100-150 миллионов записей
-~{}~ 19.12.06 14:57:
Поменял на varchar типы полей.
В итоге - занимаемый данными объем упал в 3 раза. ;-) Ну а скорость тоже упала, раз в 10. Все-таки скан таблицы с фиксированной длиной ряда - на порядок быстрее.
Думаю над декомпозицией ;-) Тогда вставка усложниться правда, но это не слишком страшно.
1. Человек задает префикс, он может быть достаточно мал (2-3 символа) и группа соотв. ему - мала. Строки неравномерно распределяются по пространству возможных значений.
Проблема как раз выбрать алгоритм поиска не сильно от этого зависящий. т.е. одинаково быстро ищущий малые префиксы на малых группах, длинные префиксы на болшиих.
2. Именно. Но заранее я этого не знаю, поэтому нужно брать какой-то усредненный вариант. Все упирается как раз в выбор длинны этого префикса.
3. Это я понимаю, но сути дела это не меняет - упираемся в выбор размерности. (4 в твоем случае).
4. Вот именно, там используется индекс "слов". Инверсный индекс имеет смысл при большом количестве повторений этих "слов", тогда он дает выигрыш, опять-же за счет того, что список целых просмотреть быстрее чем сам текст. А у меня повторений не так много, хотя идея мне понятна. Опять - упираемся в выбор размера "слова". Спасибо, я над этим подумаю ;-)
5. Пока это большая таблица, грубо говоря
ID (INT autoincrement), CODE (char(50)) - код детали, SUPPLIER_ID (INT) - идентификатор поставщика, PRICE (FLOAT) - цена
Далее служебные поля
CLEAN_CODE (char(50)) - "очищенный" от мусора код (без пробелов, дефисов и т.п.), HASH (INT) - результат хеш-фции.
Пока хэш-фция - это битовая строка по 6 бит на символ + первые 4 бита - нули (потом возьму может 4 бита из следующего символа, пока для тестов и этого хватит).
Индекс - один - по HASH (ну и PRIMARY - хотя возможно от него откажусь, если не будет необходимости ссылаться на конкретную строку).
-~{}~ 13.12.06 16:57:
А, да я тут понял - индекс MySQL по первым 5-ти символам и есть инвертированный индекс для этих 5-ти символов, размерность просто элемента = 1 ;-)
-~{}~ 19.12.06 01:19:
Забыл написать - 8.5 миллионов записей, индекс занимает примерно 10% от объема данных
1.5 гига данные, 230 мегов индекс (из них половина - primary key)
LOAD DATA INFILE работает очень быстро, 10000 строк в секунду примерно - таблица MyISAM (оптимальное на мой взгляд решение для таблицы с редкой массовой вставкой).
Это без временного отключения индексов на время обновления.
Запрос на выборку колеблется в пределах 1-10 ms, считаю вполне удачное решение.
Ну что-же теперь купим production сервер и запустим на нем. Попробуем 100-150 миллионов записей
-~{}~ 19.12.06 14:57:
Поменял на varchar типы полей.
В итоге - занимаемый данными объем упал в 3 раза. ;-) Ну а скорость тоже упала, раз в 10. Все-таки скан таблицы с фиксированной длиной ряда - на порядок быстрее.
Думаю над декомпозицией ;-) Тогда вставка усложниться правда, но это не слишком страшно.