Приблизительный план

• 19:00 – 19:50 Гриды: скрытая сложность (Иван Пономарёв)
• 19:50 – 20:00 Q&A
• 20:00 – 20:20 Celesta и Flute: что это и зачем? (Николай Поташников)
• 20:20 – 20:35 Чай с пирожками
• 20:35 – 21:35 Создание бизнес-логики на Celesta и Flute (Иван Пономарёв)
• 21:35 – 22:00 Q&A

​

​

1

Скрытая сложность повседневной задачи: отображение табличных данных

Иван Пономарёв, КУРС/МФТИ

​

@inponomarev

​

​

2

Чем мы занимаемся в КУРСе

• Course Orchestra для создания бизнес-приложений
• На Java — платформа, на Jython — код бизнес-логики
• Бизнес-решения на платформе (банки, госструктуры, коммерческие организации)
• PostgreSQL / MSSQL / Oracle

3

Все знают, что такое грид

4

Грид – это прокрутка…

5

Грид – это позиционирование…

6

Хороший грид должен

• Работать быстро (не грузить БД!)
• Работать удобно (не грузить пользователя!)
• Одинаково быстро и удобно на 10 записях �и на 1 млн записей.

7

��

8

— И разве нет готовых решений?

— А разве это сложно?

и вычитать данные таблицы в массив

​

9

Подход №1: просто взять

​

Подход №1: вычитать в массив

• Прокрутка: доступ к «окну» == доступ к N-ному элементу массива —О(1)
• Переход к записи: бинарный поиск в отсортированном массиве —O(log(N))

10

Проблемы:

• Первоначальная загрузка данных – O(N)

11

12

Проблемы:

• Первоначальная загрузка данных – O(N)
• «Тяжёлые» данные могут не «пролезть» �в пропускную способность канала
• Данные изменяются со временем – надо периодически обновлять массив

13

Подход №2: �Переложим задачу на СУБД?

• Хорошая новость: извлечение по ключу — «лёгкая» операция

SELECT … WHERE k >= … LIMIT …

​

Переход к записи по ключу работать будет быстро!

​

14

Подход №2: �Переложим задачу на СУБД?

Плохие новости:

• Позиционирование:

SELECT COUNT(*) WHERE k<… для определения диапазона полосы прокрутки и позиционирования.

• Прокрутка: выбираем записи с N-ной:

SELECT … OFFSET … LIMIT … 

15

Подход №2: �Переложим задачу на СУБД?

• Имитация ОFFSET:
• Oracle before 12: WITH a AS (YOUR_QUERY_HERE_WITH_ORDER_BY) �SELECT * FROM (SELECT a.*, ROWNUM rnum FROM a WHERE rownum <= limit) WHERE rnum >= offset ORDER BY rnum  

​

• MS SQL Server before 2012: WITH a AS (SELECT ROW_NUMBER() OVER (ORDER BY %s) AS [limit_row_number], %s FROM %s) SELECT * FROM a WHERE [limit_row_number] >= offset AND [limit_row_number] < offset + limit

16

Проблемы:

• COUNT и OFFSET — «дорогие» операции

​

17

“The rows skipped by an OFFSET clause still have to be computed inside the server; therefore a large OFFSET might be inefficient.”

— Но чем мы ближе к концу набора, тем больше OFFSET!

– А зачем нам вообще грид со всеми записями?!

• Пагинация

​

18

– А зачем нам вообще грид со всеми записями?!

• Пагинация
• Фильтрация и показ только лимитированного количества записей

​

19

– А зачем нам вообще грид со всеми записями?!

• Пагинация
• Фильтрация и показ только лимитированного количества записей
• “Load more”

​

20

Бывает и так:

21

А где полоса прокрутки?

(Обсуждение темы:

https://habrahabr.ru/post/280157/)

— Может, строить «честный грид» �и не надо?

22

— Надо, Федя!

23

Почему нужен «честный» грид?

1. Пользователи любят «простыни» данных

24

Почему нужен «честный» грид?

1. Пользователи любят «простыни» данных
2. Нужно видеть соседние записи

​

25

Почему нужен «честный» грид?

1. Пользователи любят «простыни» данных
2. Нужно видеть соседние записи
3. Переход к связанному списку

​

26

27

Как справляются другие ребята?

— С переменным успехом.

• PgAdmin3 — виснет
• SQL Server Management Studio — по умолчанию ограничивает число строк
• инструменты DB2, ERP Microsoft Navision �(ок. 2003 г.) — сразу открывают и «крутят» любые таблицы

28

Наше решение

• Disclaimer:
• Не «серебряная пуля»
• Не всё просто с сортировкой и фильтрацией
• Нужны правильные индексы, LIKE с осторожностью

​

• Но:
• Неплохой компромисс между скоростью и удобством

29

Временное упрощение задачи�(потом ограничения снимем!)

1. Первичный ключ таблицы состоит �из одного поля k с типом INT
2. Сортировка по первичному ключу

30

CREATE TABLE test (

k INT NOT NULL PRIMARY KEY,

descr VARCHAR(20)

);

Мысленный эксперимент

1. У 1-й записи k = 0.
2. У 1 000-й записи k = 10 000.
3. Записи отсортированы по k.
1. Вопрос: какое примерно значение k�будет иметь запись с номером 500? �

31

Идея

«Угадаем» взаимосвязь между ключом записи k�и её порядковым номером λ при помощи линейной интерполяции?

32

Насколько хороша линейная интерполяция? (50 из 200)

33

порядковый номер записи

значение ключа

Случай 10 из 200 — похуже…

34

значение ключа

порядковый номер записи

Вероятность наличия �ровно λ записей с ключом <k

35

Теоретическая оценка границ, �мат. ожидания и СКО

36

Неравномерное распределение ключей�— кусочная интерполяция!

37

Снимаем ограничения

• Ключ составной

— нумеруем возможные комбинации так, чтобы описывались (большим) целым числом

• Нужна сортировка

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

• Ключ содержит не только INT-поля

— нумеруем значения (большими) целыми!

38

39

интерполяционная

таблица

Компоненты алгоритма

нумератор

интер-�полятор

генератор�запросов

Пример

• Справочник улиц КЛАДР
• 1 175 430 записей
• ORDER BY name, code
• CREATE INDEX ix_street ON kladr.street (name, code)

40

Пользователь прокрутил записи…

41

изменилась�позиция бегунка

вычисление

порядкового номера

вычисление

ключа

запрос

ближайшей записи

БД

Нумератор

Интерполятор

Полоса �прокрутки

Интерполяцией находим порядковый номер ключа

42

изменилась�позиция бегунка

вычисление

порядкового номера

вычисление

ключа

запрос

ближайшей записи

БД

Нумератор

Интерполятор

Полоса �прокрутки

Вычисляем примерные значения �полей ключа по примерному номеру

43

изменилась�позиция бегунка

вычисление

порядкового номера

вычисление

ключа

запрос

ближайшей записи

БД

Нумератор

Интерполятор

Полоса �прокрутки

Запрашиваем записи, ближайшие �к найденным примерным значениям полей

44

изменилась�позиция бегунка

вычисление

порядкового номера

вычисление

ключа

запрос

ближайшей записи

БД

Нумератор

Интерполятор

Полоса �прокрутки

name: Мд‘Ukp ®$-'•ДЫ9uj?¦АОZ‡У›:"ZG818*$‰9Ювэ‘

code: я$зec§}0,&-»гФ4%эR

SELECT ... FROM ... WHERE

("name", "code") >= (?, ?) LIMIT ...

Прокрутка в реальном времени

45

Асинхронное уточнение позиции

46

запрос

ближайшей записи

запрос реального�номера записи

SELECT COUNT(*) FROM kladr.street WHERE ("name", "code") < (?, ?)

586038

(А хотели 584600!)

Позиционирование

47

Позиционирование

48

обращение �к таблице по ключу

вычисление

порядкового номера

позиция бегунка

(обр. интерп.)

изменение позиции�бегунка

БД

Нумератор

Интерполятор

Полоса �прокрутки

запрос реального�номера записи

SELECT ... FROM ... WHERE

("name", "code") >= (?, ?) LIMIT ...

SELECT COUNT(*) FROM ...

WHERE ("name", "code") < (?, ?)

Вычисляем порядковый номер ключа

49

обращение �к таблице по ключу

вычисление

порядкового номера

позиция бегунка

(обр. интерп.)

изменение позиции�бегунка

БД

Нумератор

Интерполятор

Полоса �прокрутки

name: Чаадаева

code: 42000010000057000

Интерполяцией находим примерную позицию бегунка

50

обращение �к таблице по ключу

вычисление

порядкового номера

позиция бегунка

(обр. интерп.)

изменение позиции�бегунка

БД

Нумератор

Интерполятор

Полоса �прокрутки

Выставляем бегунок на позицию

51

обращение �к таблице по ключу

вычисление

порядкового номера

позиция бегунка

(обр. интерп.)

изменение позиции�бегунка

БД

Нумератор

Интерполятор

Полоса �прокрутки

запрос реального�номера записи

Осталось разобраться в одном вопросе…

Как работает нумератор?

52

Функция нумератора

53

• С BIT и INT всё просто — они нумеруют сами себя
• Даты сводимы к целому типу

​

• Составные ключи?
• Строки?

54

Составной ключ/сортировка:�ORDER BY X, Y

55

Составной ключ

Если умеем работать �с парами значений —

�

56

Составной ключ

Если умеем работать �с парами значений —

�— то можем работать �и с произвольными N-ками значений

57

Как отыскивать записи �от составного ключа?

​

• where (k1, k2) >= (K1, K2)

(работает только в PostgreSQL)

​

• where k₁ > K₁ or (k₁ = K₁ and (k₂ >= K₂))

не использует индекс!

​

• where k₁ >= K₁ and (k₁ > K₁ or (k₂ >= K₂))

58

Нумерация строк

59

Интерполяция строк

60

61

Пустая строка, строка из одной буквы, из двух букв…

62

‘’ — 0, ‘а’ — 1, ‘б’ — ?

2 — неправильный ответ: ‘абак’, ‘араб’, ‘арка’…

63

64

• Общая формула:

• Постаравшись, можно найти алгоритм обратного вычисления строки

Ничего не упустили?.. �Пишем тест:

ИЖЕВСК 297544850130486

ИРКУТСК 309090873152681

ЙОШКАР-ОЛА 343626219328684

Реальность: �SELECT name FROM city ORDER BY name�(PostgreSQL с настройками по умолчанию)

66

Правила сортировки (collation rules)

Результат «подгонки» правил к PostgreSQL:

…<в,В<г,Г<д,Д<е,Е;ё,Ё<ж,Ж<з,З<и,И;й,Й<к,К<л,Л…�

67

java.text.RuleBasedCollator extends java.text.Collator

java.text.CollationKey

Строка с точки зрения Collation Rule

68

Насколько всё это быстро?

JMH-замер:

• 10000 ops/sec — для 200 символов
• 30000 ops/sec — для 50 символов

69

Первоначальное заполнение интерполяционной таблицы

70

А также не упомянуты…

• Отработка и сортировка NULL-значений
• Режим прокрутки на малый шаг
• Анализ «качества» интерполяционных точек

…и другие мелкие, но важные детали

“God is in the detail.”

71

Выводы

1. Создавать фреймворк — дело трудное�и неблагодарное

72

Выводы

2. Всегда помните�про О-оценку сложности алгоритмов

73

Выводы

3. По возможности, избегайте COUNT �и OFFSET

74

Выводы

4. SQL не всемогущ. Ему можно и нужно «помогать»
5. Помните, что сортировка строк существенно зависит от Collation. Следите за текущим Collation.
6. «Приблизительное» решение бывает намного быстрее «точного» и практически столь же хорошо

​

​

75

Ссылки

• Демо-пример: https://github.com/inponomarev/lyragrid-demo
• Платформа C-Orchestra: http://corchestra.ru «Реализация грида»
• https://habrahabr.ru/post/278773/
• https://habrahabr.ru/post/279083/
• «Быстро/неудобно — медленно/удобно»
• https://habrahabr.ru/post/280157/

​

76

Вопросы?

​

ponomarev@corchestra.ru

@inponomarev

​

77