Всем Привет. В КХ появился тип MAP, в котором пара

Question

Всем Привет. В КХ появился тип MAP, в котором пара

ключ/значение хранятся как кортежи (tuple) в массиве, они не отсортированы по ключу, поэтому поиск занимает линейное время. Я хочу понять, почему так было сделано? Есть какая-то причина не делать бинарный поиск по отсортированым ключам (типа как flat_map в boost)?

#backend #clickhouse #database #devops #programming #russian

0

09.11.2021

9 ответов

22 просмотра

sdev E Автор вопроса

Dmitry [Altinity] Titov
Потому что так сделать было достаточно просто. А в...

Спасибо. А не в курсе, делает ли это кто-нибудь? У нас есть задача, которой нужен быстрый поиск по ключу/значению. MAP демонстрирует лучшую производительность, чем 2xArray, похоже за счет лучшей локальности. Бинарный поиск бы ее улучшил еще больше.

0

09.11.2021

Dmitry [Altinity] Titov

sdev E
Спасибо. А не в курсе, делает ли это кто-нибудь? У...

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

0

09.11.2021

sdev E Автор вопроса

Dmitry [Altinity] Titov
Наверное никто, большие у вас мапы выходят?

У нас большой QPS и большие объемы сканирования.

0

09.11.2021

Dmitry [Altinity] Titov

sdev E
У нас большой QPS и большие объемы сканирования.

Это не ответ :) Какого размера у вас мапы в среднем?

0

09.11.2021

Denny [Altinity]

так нету смысла в этом никакого потому что это все лежит в 2 двух запакованых .bin файлах, все строки подряд, внутри строк неотсортированные Key толку-то сортировать, даже чтобы найти конкретную строку надо прочитать 8192 строки целиком, все KEY, все VALUE

0

09.11.2021

sdev E Автор вопроса

Denny [Altinity]
так нету смысла в этом никакого потому что это все...

Оно будет загружено в память, да. Но если сканирование ищет конкретный ключ, разве бинарный поиск не будет быстрее (если ключи отсортированы). Т.е. select id from mapped_table where map_field[‘key_string’] = ‘value’

0

09.11.2021

Denny [Altinity]

sdev E
Оно будет загружено в память, да. Но если сканиров...

ну да все так, мы потратили 10 минут на чтение и распаковку .bin и поиск строки вы предлагает 3 сек. сэкономить, мудро в итоге все будет переделано вот так https://kb.altinity.com/altinity-kb-schema-design/best-schema-for-storing-many-metrics-registered-from-the-single-source/#2e-several-baskets-of-arrays это уже все переделано

0

09.11.2021

Denny [Altinity]

sdev E
Спасибо. А не в курсе, делает ли это кто-нибудь? У...

это странное поведение. В чем разница MAP и 2 Array ? Вы как к Array обращаетесь? В общем я получил ускорение в 20 раз, сделав 20 пар Array, вместо 1 пары

0

09.11.2021

Dmitry [Altinity] Titov · Accepted Answer

Dmitry [Altinity] Titov

Потому что так сделать было достаточно просто. А всякие оптимизации вроде на потом запланированы были

0

09.11.2021

184 похожих чатов

Всем Привет. В КХ появился тип MAP, в котором пара

9 ответов

Похожие вопросы