Предположим, мы хотим исправлять опечатки в поисковых запросах или сообщениях чата. Человек вводит «абривиатура», мы исправляем на «аббревиатура», «рассчет» → «расчет», «дороаг» → «дорога». Посмотрим, как решить такую задачу на SQL.

Я буду использовать SQLite. Но аналогичный подход сработает с любой СУБД или языком программирования (если интересно — дайте знать, сделаю примеры на Python).

1. Собираем словарь

Воспользуемся списком русских слов во всех морфологических формах из репозитория russian-words. Скачаем и сконвертируем в UTF-8:

$ wget https://github.com/danakt/russian-words/raw/master/russian.txt
$ iconv -f cp1251 russian.txt > russian.utf.csv

Загрузим в таблицу words:

$ sqlite3 dictionary.db
sqlite> create table words(word text);
sqlite> .mode csv
sqlite> .import russian.utf.csv words
sqlite> create unique index words_idx on words(word);
sqlite> select count(*) from words;
1532629

Словарь из 1.5 млн слов готов.

Когда человек ввел какое-то слово («абривиатура») — несложно проверить, есть ли оно в словаре:

select 1 from words where word = 'абривиатура';
-- <пусто>

Раз варианта в словаре нет — в слове наверняка опечатка. Чтобы предложить исправление, придется найти максимальное похожее слово в words.

2. Определяем похожесть слов

Человеку интуитивно понятно, что такое «похожее» или «непохожее» слово, но машине нужен формальный критерий.

Идеально, если бы мы умели измерять расстояние между словами. Функция расстояния принимает на входе два слова и возвращает некоторое число D, которое характеризует похожесть:

distance(w1, w1) = x

Чем меньше D, тем более похожи слова.

Приятно, что специалисты по компьютерным наукам уже придумали великое множество таких функций. Наиболее известная из них — расстояние Левенштейна. Она измеряет, сколько букв надо удалить, добавить или заменить, чтобы перейти от слова w1 к слову w2:

Расстояние Левенштейна считает количество элементарных замен, которыми можно превратить одно слово в другое.

# одна операция: удалить лишнюю С
levenshtein("рассчет", "расчет") = 1

# одна операция: добавить недостающую лишнюю Л
levenshtein("сонце", "солнце") = 1

# две операции: заменить А→Г, заменить Г→А
levenshtein("дороаг", "дорога") = 2

Пример с «дороаг» → «дорога» может показаться странным: очевидно же, что достаточно переставить буквы местами. Перестановка — одна операция, и расстояние должно быть 1, а не 2. Алгоритм Левенштейна не учитывает такие случаи, поэтому создали улучшенную и дополненную версию — расстояние Дамерау-Левенштейна:

dlevenshtein("дороаг", "дорога") = 1

Его и будем использовать.

-- в консоли sqlite
.load ./fuzzy

-- или через select
select load_extension('./fuzzy');

select translit('дорога');
-- doroga

select translit('дороаг');
-- doroag

select dlevenshtein(
  translit('дорога'),
  translit('дороаг')
);
-- 1

3. Ищем похожее слово в словаре

Чтобы исправить опечатку в слове, достаточно посчитать расстояние от него до каждого слова в словаре и выбрать слово с минимальным расстоянием.

Считаем расстояния между словом с опечаткой и остальными словами → получаем набор расстояний. Выбираем минимальное → получаем слово с исправленной опечаткой.

Отличный был бы алгоритм, если бы не сортировал каждый раз полтора миллиона слов.

На SQL:

select
  word,
  dlevenshtein(
    translit('абривиатура'),
    translit(word)
  ) as distance
from words
order by distance
limit 1;

┌──────────────┬──────────┐
│     word     │ distance │
├──────────────┼──────────┤
│ аббревиатура │ 2        │
└──────────────┴──────────┘
Run Time: real 8.145 user 8.055009 sys 0.051747

Отлично работает! Одна проблема: расчет занимает 8 секунд. Для исправления опечаток в онлайне не подходит. Нам желательно уложиться в 50–200 мс, чтобы для человека выглядело мгновенным. Исправим это.

4. Фонетическое кодирование

Проблема с расстоянием в том, что его нельзя посчитать заранее — мы же не знаем, какое слово введет человек. Здесь поможет фонетическое кодирование:

Фонетический алгоритм превращает произвольное слово (солнце) в фонетический код (SNTK). При этом созвучные слова получают одинаковые коды, а несозвучные — разные.

Теперь мы можем обойтись без расстояния вообще:

1. Заранее посчитать код для каждого слова в словаре.
2. Посчитать код для слова с опечаткой, которое ввел человек.
3. Найти слово в словаре по этому коду — это и будет правильный вариант.

Работать должно моментально, потому что по столбцу с кодами можно построить индекс, и искать по нему.

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

5. Ищем по фонетике

Фонетические алгоритмы придумывали для английского языка, и на русском они не работают. Нам придется прибегнуть к трюку с транслитерацией.

У транслитерированных слов фонетика сильно отличается от «родной» английской, поэтому многие фонетические алгоритмы плохо работает с транслитом. Мы возьмем функцию caverphone — она на удивление недурна, несмотря на австралийское происхождение:

caverphone(translit("рассчет")) = "RSKT111111"
caverphone(translit("расчет"))  = "RSKT111111"

caverphone(translit("сонце"))  = "SNTK111111"
caverphone(translit("солнце")) = "SNTK111111"

caverphone(translit("абривиатура"))  = "APRFTRA111"
caverphone(translit("аббревиатура")) = "APRFTRA111"

Рассчитаем коды для слов из словаря и построим индекс:

alter table words add column hash text;
update words set hash = caverphone(translit(word));
create index words_hash_idx on words(hash);

Исправим опечатку в слове абривиатура:

select word
from words
where hash = caverphone(translit('абривиатура'))
limit 3;

┌───────────────┐
│     word      │
├───────────────┤
│ аббревиатура  │
│ аббревиатурой │
│ аббревиатурою │
└───────────────┘
Run Time: real 0.002 user 0.000130 sys 0.000391

Замечательно! Запрос выполнился мгновенно и вернул подходящие слова из словаря.

6. Ищем по фонетике и расстоянию

Как удачно все получилось с «аббревиатурой». Проверим на «расчете»:

select word
from words
where hash = caverphone(translit('рассчет'))
limit 3;

┌────────────┐
│    word    │
├────────────┤
│ разжигает  │
│ разжигаете │
│ разжигайте │
└────────────┘

Эээ. Совсем не то, чего мы ожидали. Проблема в том, что у «расчета» фонетически похожих слов довольно много:

select count(*)
from words
where hash = caverphone(translit('рассчет'));
-- 50

Нам бы как-то найти среди этих пятидесяти самое похожее. Хорошо, что мы уже знаем как это сделать — с помощью расстояния Дамерау-Левенштейна! Будем выбирать слова-кандидаты по фонетическому коду, а наиболее подходящего из кандидатов — по расстоянию:

-- кандидаты по фонетическому коду
with candidates as (
  select word
  from words
  where hash = caverphone(translit('рассчет'))
)

-- выбираем кандидата с минимальным расстоянием
select
  word,
  dlevenshtein(
    translit('рассчет'),
    translit(word)
  ) as distance
from candidates
order by
  distance,
  abs(length(word) - length('рассчет')),
  length(word)
limit 3;

┌──────────┬──────────┐
│   word   │ distance │
├──────────┼──────────┤
│ расчет   │ 1        │
│ расчёт   │ 1        │
│ рассечет │ 1        │
└──────────┴──────────┘
Run Time: real 0.014 user 0.000729 sys 0.003712

То что надо! Поиск остался моментальным (благодаря выборке кандидатов по индексу), но стал точным (благодаря честному сравнению расстояния между кандидатами).

7. Учитываем нефонетические опечатки

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

дорога
дороаг

Фонетический алгоритм посчитает такие слова разными (и будет прав):

caverphone("doroga") = "TRKA111111"
caverphone("doroag") = "TRK1111111"

В результате на нефонетических опечатках наш алгоритм будет работать плохо. Для дороаг вернет:

┌────────┬──────────┐
│  word  │ distance │
├────────┼──────────┤
│ дорог  │ 1        │
│ дороге │ 2        │
│ драг   │ 2        │
└────────┴──────────┘

Часть нефонетических опечаток можно исправить. Например, выбирать не по строгому равенству фонетических кодов, а по префиксу (первые 3 символа в данном случае):

-- диапазон допустимых фонетических кодов
with bounds as (
  select
    substr(caverphone(translit('дороаг')), 1, 3) || '1' as left,
    substr(caverphone(translit('дороаг')), 1, 3) || 'Z' as right
),

-- кандидаты по фонетическому коду
-- из числа допустимых
candidates as (
  select word
  from words, bounds
  where hash between bounds.left and bounds.right
)

-- выбираем кандидата с минимальным расстоянием
select
  word,
  dlevenshtein(translit('дороаг'), translit(word)) as distance
from candidates
order by distance, abs(length(word) - length('дороаг')), length(word)
limit 3;

┌────────┬──────────┐
│  word  │ distance │
├────────┼──────────┤
│ дорога │ 1        │
│ дорог  │ 1        │
│ дороге │ 2        │
└────────┴──────────┘
Run Time: real 0.032 user 0.030312 sys 0.000339

Такой запрос находит на порядки больше кандидатов (6633 вместо 81 для «дороги»). Из-за этого он намного медленнее работает (хотя 32 мс — все еще очень быстро с точки зрения человека).

Префиксный подход не сработает, если опечатка в самом начале слова. Запрос по одрога не найдет слово дорога:

┌────────┬──────────┐
│  word  │ distance │
├────────┼──────────┤
│ отрога │ 1        │
│ отроге │ 2        │
│ отроги │ 2        │
└────────┴──────────┘

Хоть мой айфон такую опечатку тоже не исправляет, так что может и ничего.

8. Готовое решение для SQLite

Теперь вы знаете, как быстро искать похожие слова в стиле «сделай сам». Описанный алгоритм можно реализовать в любой СУБД, где есть фонетические функции и функции расстояний. Но даже если в вашей базе их нет — то же самое можно сделать на Python, JS или C#, для которых уж точно найдутся подходящие библиотеки.

Если же работаете в SQLite — можно сэкономить время и воспользоваться готовым расширением spellfix. Под капотом у него фонетика + расстояния, как мы обсуждали, но внешний интерфейс сильно проще:

.load ./spellfix

create virtual table dictionary using spellfix1;

insert into dictionary(word)
select word from words;

select word from dictionary
where word match 'абривиатура'
limit 1;

┌──────────────┐
│     word     │
├──────────────┤
│ аббревиатура │
└──────────────┘
Run Time: real 0.182 user 0.112689 sys 0.014142

Работает медленнее и местами хуже, чем наше DIY-решение, зато гибче настраивается. Можно добавлять синонимы слов и тюнить расстояние — см. разделы «Dealing With Unusual And Difficult Spellings» и «Configurable Edit Distance» в документации.

9. Итоги

Теперь вы умеете:

• Считать расстояние между словами, чтобы понять, насколько они отличаются.
• Использовать фонетические алгоритмы, чтобы искать созвучные слова.
• Сочетать фонетику и расстояние, чтобы моментально находить похожие слова в миллионном словаре.

Конечно, есть и альтернативные подходы к исправлению опечаток. Например:

• Для каждого слова из словаря заранее сгенерить возможные варианты опечаток и сохранить их в отдельной таблице. Словарь увеличится в десятки, если не сотни раз — зато не нужны фонетика и расстояния.
• Обучить нейросеть предсказывать правильное слово по тому, что ввел человек. Заодно получится предиктивно предлагать варианты еще до того, как пользователь дописал слово — так работает ввод в айоси и андроиде.

Но это уже совсем другая история ツ А фонетика и расстояния могут вам пригодиться.

Извлек их и сделал нормальные наборы данных в CSV. Например:

Атрибутика:

• word — слово
• pos — часть речи
• level — уровень (A1, A2, B1, B2, C1)
• definition_url — ссылка на подробное определение
• voice_url — ссылка на озвучку в ogg

Посмотреть и скачать:
github.com/nalgeon/words

Возможно, теперь SQLite перестанут называть «джаваскриптом в мире СУБД» ツ Но давайте по порядку.

подробности на Хабре

Константное время, O(1)

Самый лучший вариант, скорость алгоритма не зависит от количества котиков.

🐾 Пример

Вы — счастливый обладатель N котиков. Каждый котик знает, как его зовут. Если позвать «Клёпа!», то прибежит только он, а остальным N-1 жопкам пофиг.

Логарифмическое время, O(log n)

На N котиках алгоритм отрабатывает за log(N) шагов. Это быстро! 1 000 000 котиков → всего 20 операций.

🐾 Пример

Мисочки у котиков расставлены по алфавиту. Когда у вас появляется новый котик, место для его мисочки находится за log(N) шагов.

Линейное время, O(n)

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

🐾 Пример

Котики взбунтовались и перестали отзываться на клички. Теперь приходится обходить N шубок, чтобы найти нужного.

Линейно-логарифмическое время, O(n log n)

На N котиках алгоритм отрабатывает за N × log(N) шагов. Это дольше, чем за линейное время, но ненамного (логарифм N сильно меньше N, помните?).

🐾 Пример

К приходу гостей вы решили рассадить котиков по размеру. Алгоритм quick sort справится с этим за N × log(N) шагов.

На очереди у нас неторопливые полиномиальные котики и совсем улиточки — суперполиномиальные.

Квадратичное время O(n²)

На N котиках алгоритм отрабатывает за N² шагов. Ме-е-едленно.

🐾 Пример

Конкурент утверждает, что его N котиков более гладкие и довольные, чем ваши. Специальная комиссия попарно сравнит хвостатых и вынесет справедливый вердикт. Понадобится ~ N² сравнений.

Полиномиальное время, O(nᵏ)

На N котиках алгоритм отрабатывает за N³ шагов, N⁴ шагов, N⁵ шагов, или ещё дольше. Фу таким быть.

🐾 Пример

Фотосессия! Каждого из N котиков надо попарно отфоткать с другими, причем фотограф делает N снимков на каждую пару. N × N × N ≃ N³ шагов.

Хоть полиномиальные алгоритмы и не славятся быстротой, по сравнению с суперполиномиальными они стремительны как Флеш. Из «суперского» у суперполиномиальных только название, увы. Сейчас покажу.

Экспоненциальное время, O(2ⁿ)

На N котиках алгоритм отрабатывает за 2ⁿ шагов. Это долго, вы вряд ли дождетесь.

🐾 Пример

Котики отправляются на выставку. Каждого взвесили и оценили в звездах. Но перевозка рассчитана максимум на X килограмм. Как выбрать самый звездный состав? Ответ потребует 2ⁿ шагов.

Факториальное время, O(n!)

На N котиках алгоритм отработает за N × (N-1) × (N-2) ×… × 1 шагов. Это жесть! Всего 20 котиков уже дадут нам пару квинтиллионов операций.

🐾 Пример

Котики расселись по квартире. Вам хочется пожамкать каждого, но ходить лень. Какой кратчайший маршрут, чтобы обойти всех шерстяных жопок? Это ~ N! сравнений.

Резюме

Вот какие алгоритмы мы рассмотрели:

• Константные O(1)
• Логарифмические O(log n)
• Линейные O(n)
• Линейно-логарифмические O(n log n)
• Квадратичные O(n²)
• Полиномиальные O(nᵏ)
• Экспоненциальные O(2ⁿ)
• Факториальные O(n!)

Константный алгоритм — всегда лучший вариант, а логарифмический — почти всегда. С линейными и полиномиальными сложнее — тут все зависит от задачи. Где-то стыдно выбирать O(n), а где-то и O(n²) будет большим успехом.

O(2ⁿ) и O(n!) безумно медленные, поэтому на практике вместо них обычно используют неоптимальные, но быстрые алгоритмы.

Всем котиков! И подписывайтесь на @nalgeon в твитере, чтобы не пропустить новые заметки 🚀

Все знают, как работать со списком в питоне:

>>> guests = ["Френк", "Клер", "Зоя"]
>>> guests[1]
'Клер'

Наверняка вы знаете, что выборка элемента по индексу — guests[idx] — отработает очень быстро даже на списке из миллиона элементов. Более точно, выборка по индексу работает за константное время O(1) — то есть не зависит от количества элементов в списке.

А знаете, за счет чего так быстро работает? Если да — вы в меньшинстве:

Давайте разбираться.

Список = массив?

В основе списка лежит массив. Массив — это набор элементов ① одинакового размера и ② расположенных в памяти подряд друг за другом, без пропусков.

Раз элементы одинаковые и идут подряд, получить элемент массива по индексу несложно — достаточно знать адрес самого первого элемента («головы» массива).

Допустим, голова находится по адресу 0×00001234, а каждый элемент занимает 8 байт. Тогда элемент с индексом idx находится по адресу 0×00001234 + idx*8:

Поскольку операция «получить значение по адресу» выполняется за константное время, то и выборка из массива по индексу выполняется за O(1).

Грубо говоря, список в питоне именно так и устроен. Он хранит указатель на голову массива и количество элементов в массиве. Количество хранится отдельно, чтобы функция len() тоже отрабатывала за O(1), а не считала каждый раз фактическое количество элементов списка.

Все хорошо, но есть пара проблем:

• все элементы массива одного размера, а список умеет хранить разные (true/false, числа, строки разной длины);
• массив имеет фиксированную длину, а в список можно добавить сколько угодно элементов.

Чуть позже посмотрим, как их решить.

Ну очень примитивный список

Лучший способ освоить структуру данных — реализовать ее с нуля. К сожалению, питон плохо подходит для таких низкоуровненых структур как массив, потому что не дает явно работать с указателями (адресами в памяти).

Но кое-что можно сделать:

class OhMyList:
    def __init__(self):
        self.length = 0
        self.capacity = 8
        self.array = (self.capacity * ctypes.py_object)()

    def append(self, item):
        self.array[self.length] = item
        self.length += 1

    def __len__(self):
        return self.length

    def __getitem__(self, idx):
        return self.array[idx]

Наш самописный список имеет фиксированную вместимость (capacity = 8 элементов) и хранит элементы в массиве array.

Модуль ctypes дает доступ к сишным структурам, на которых построена стандартная библиотека. В даннам случае мы используем его, чтобы создать массив размером в capacity элементов.

Список = массив указателей

Список моментально выбирает элемент по индексу, потому что внутри у него массив. А массив такой быстрый, потому что все элементы у него одинакового размера.

Но при этом в списке элементы могут быть очень разные:

guests = ["Френк", "Клер", "Зоя", True, 42]

Чтобы решить эту задачку, придумали хранить в массиве не сами значения, а указатели на них. Элемент массива — адрес в памяти, а если обратиться по адресу — получишь настоящее значение:

Поскольку указатели фиксированного размера (8 байт на современных 64-битных процессорах), то все прекрасно работает. Да, получается, что вместо одной операции (получить значение из элемента массива) мы делаем две:

1. Получить адрес из элемента массива.
2. Получить значение по адресу.

Но это все еще константное время O(1).

Список = динамический массив

Если в массиве под списком остались свободные места, то метод .append(item) выполнится за константное время — достаточно записать новое значение в свободную ячейку и увеличить счетчик элементов на 1:

def append(self, item):
    self.array[self.length] = item
    self.length += 1

Но что делать, если массив уже заполнен?

Приходится выделять память под новый массив, побольше, и копировать все элементы старого массива в новый:

Примерно так:

def append(self, item):
    if self.length == self.capacity:
        self._resize(self.capacity*2)
    self.array[self.length] = item
    self.length += 1

def _resize(self, new_cap):
    new_arr = (new_cap * ctypes.py_object)()
    for idx in range(self.length):
        new_arr[idx] = self.array[idx]
    self.array = new_arr
    self.capacity = new_cap

._resize() — затратная операция, так что новый массив создают с запасом. В примере выше новый массив в два раза больше старого, а в питоне используют более скромный коэффициент — примерно 1.12.

Если удалить из списка больше половины элементов через .pop(), то питон его скукожит — выделит новый массив поменьше и перенесет элементы в него.

Таким образом, список все время жонглирует массивами, чтобы это не приходилось делать нам ツ

Добавление элемента в конец списка

Выборка из списка по индексу работает за O(1) — с этим разобрались. Метод .append(item) тоже отрабатывает за O(1), пока не приходится расширять массив под списком. Но любое расширение массива — это операция O(n). Так за сколько же в итоге отрабатывает .append()?

Оценивать отдельную операцию вставки было бы неправильно — как мы выяснили, она иногда выполняется за O(1), а иногда и за O(n). Поэтому используют амортизационный анализ — оценивают общее время, которое займет последовательность из K операций, затем делят его на K и получают амортизированное время одной операции.

Так вот. Не вдаваясь в подробности скажу, что амортизированное время для .append(item) получается константным — O(1). Так что вставка в конец списка работает очень быстро.

1 + 2 + 4 + ... log(n) = 
= 2**log(n) * 2 - 1 =
= 2n - 1

Получается, у списка есть такие гарантированно быстрые операции:

# O(1)
lst[idx]

# O(1)
len(lst)

# амортизированное O(1)
lst.append(item)
lst.pop()

Итоги

Как мы выяснили, у списка работают за O(1):

• выборка по индексу lst[idx]
• запрос длины len(lst)
• добавление элемента в конец списка .append(item)
• удаление элемента из конца списка .pop()

Остальные операции — «медленные»:

• Вставка и удаление из произвольной позиции — .insert(idx, item) и .pop(idx) — работают за линейное время O(n), потому что сдвигают все элементы после целевого.
• Поиск и удаление элемента по значению — item in lst, .index(item) и .remove(item) — работают за линейное время O(n), потому что перебирают все элементы.
• Выборка среза из k элементов — lst[from:to] — работает за O(k).

Значит ли это, что «медленные» операции нельзя использовать? Конечно, нет. Если у вас список из 1000 элементов, разница между O(1) и O(n) для единичной операции незаметна.

С другой стороны, если вы миллион раз выполняете «медленную» операцию на списке из 1000 элементов — это уже заметно. Или если список из миллиона элементов — тоже.

Поэтому полезно знать, что у списка работает за константное время, а что за линейное — чтобы осознанно принимать решение в конкретной ситуации.

Проблема

Допустим, у нас есть таблица продаж по месяцам за два года:

┌──────┬───────┬───────┬──────────┬─────────┐
│ year │ month │ price │ quantity │ revenue │
├──────┼───────┼───────┼──────────┼─────────┤
│ 2019 │ 1     │ 60    │ 200      │ 12000   │
│ 2019 │ 2     │ 60    │ 660      │ 39600   │
│ 2019 │ 3     │ 60    │ 400      │ 24000   │
│ 2019 │ 4     │ 60    │ 300      │ 18000   │
│ 2019 │ 5     │ 60    │ 440      │ 26400   │
│ 2019 │ 6     │ 60    │ 540      │ 32400   │
│ 2019 │ 7     │ 60    │ 440      │ 26400   │
│ 2019 │ 8     │ 60    │ 440      │ 26400   │
│ 2019 │ 9     │ 60    │ 250      │ 15000   │
│ 2019 │ 10    │ 60    │ 420      │ 25200   │
│ ...  │ ...   │ ...   │ ...      │ ...     │
└──────┴───────┴───────┴──────────┴─────────┘

песочница

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

Для начала посчитаем среднемесячную выручку по годам:

select
  year,
  avg(revenue) as avg_rev
from sales
group by year;

┌──────┬─────────┐
│ year │ avg_rev │
├──────┼─────────┤
│ 2019 │ 25125.0 │
│ 2020 │ 48625.0 │
└──────┴─────────┘

Теперь можно выбрать только те записи, revenue в которых не уступает avg_rev:

select
  sales.year,
  sales.month,
  sales.revenue,
  round(totals.avg_rev) as avg_rev
from sales
  join (
    select
      year,
      avg(revenue) as avg_rev
    from sales
    group by year
  ) as totals
  on sales.year = totals.year
where sales.revenue >= totals.avg_rev;

┌──────┬───────┬─────────┬─────────┐
│ year │ month │ revenue │ avg_rev │
├──────┼───────┼─────────┼─────────┤
│ 2019 │ 2     │ 39600   │ 25125.0 │
│ 2019 │ 5     │ 26400   │ 25125.0 │
│ 2019 │ 6     │ 32400   │ 25125.0 │
│ 2019 │ 7     │ 26400   │ 25125.0 │
│ ...  │ ...   │ ...     │ ...     │
└──────┴───────┴─────────┴─────────┘

Решили с помощью подзапроса:

• внутренний запрос считает среднемесячную выручку;
• внешний соединяется с ним и фильтрует результаты.

Запрос в целом получился сложноват. Если вернетесь к нему спустя месяц — наверняка потратите какое-то время на «распутывание». Проблема в том, что такие вложенные запросы приходится читать наоборот:

• найти самый внутренний запрос, осознать;
• мысленно присоединить к более внешнему;
• присоединить к следующему внешнему, и так далее.

Хорошо, когда вложенных уровня два, как в нашем примере. На практике же я часто встречаю трех- и четырехуровневые подзапросы. Форменное издевательство над читателем.

Решение

Вместо подзапроса можно использовать табличное выражение (common table expression, CTE). Любой подзапрос X:

select a, b, c
from (X)
where e = f

Механически превращается в CTE:

with cte as (X)
select a, b, c
from cte
where e = f

В нашем примере:

with totals as (
  select
    year,
    avg(revenue) as avg_rev
  from sales
  group by year
)

select
  sales.year,
  sales.month,
  sales.revenue,
  round(totals.avg_rev) as avg_rev
from sales 
  join totals on totals.year = sales.year
where sales.revenue >= totals.avg_rev;

С табличным выражением запрос становится одноуровневым — так воспринимать его намного проще. Кроме того, табличное выражение можно переиспользовать в пределах запроса, как будто это обычная таблица:

with totals as (...)
select ... from sales_ru join totals ...
union all
select ... from sales_us join totals ...

Табличные выражения SQL чем-то похожи на функции в обычном языке программирования — они уменьшают общую сложность:

• Можно написать нечитаемую простыню кода, а можно разбить код на понятные отдельные функции и составить программу из них.
• Можно возвести башню из пяти этажей подзапросов, а можно вынести подзапросы в CTE и составить общий запрос из них.

CTE против подзапроса

Существует миф, что «CTE медленные». Он пришел из старых версий PostgreSQL (11 и раньше), которые всегда материализовали CTE — вычисляли полный результат табличного выражения и запоминали до конца запроса.

Обычно это хорошо: один раз вычислил результат, и дальше используешь его несколько раз по ходу основного запроса. Но иногда материализация мешала движку оптимизировать запрос:

with cte as (select * from foo)
select * from cte where id = 500000;

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

PostgreSQL 12+ и другие современные СУБД поумнели и больше так не делают. Материализация применяется, когда от нее больше пользы, чем вреда. Плюс, многие СУБД позволяют явно управлять этим поведением через инструкции MATERIALIZED / NOT MATERIALIZED.

Так что CTE не медленнее подзапросов. А если сомневаетесь, всегда можно сделать два варианта — подзапрос и табличное выражение — и сравнить план и время выполнения.

Как понять, когда использовать подзапрос, а когда CTE? Я вывел для себя простое правило, которое пока ни разу не подвело:

Всегда использовать CTE

Чего и вам желаю.

Справочник адресов называется «ФИАС» (федеральная информационная адресная система) или «ГАР» (государственный адресный реестр) — это одно и то же. Раньше назывался «КЛАДР» (классификатор адресов). Технически поддерживает его налоговая, а данные о домах и улицах вносят местные чиновники по всей стране. У справочника даже есть сайт (не читайте его): fias.nalog.ru

Вот как видит нашу родину налоговая служба:

• 86 регионов
• 3 тыс. городов
• 300 тыс. населённых пунктов
• 1 млн улиц
• 31 млн домов
• 52 млн квартир

У каждого адреса есть тип и название. Скажем, тип = «город», название = «Самара». Или тип = «республика», название = «Бурятия». Но если вам повезло жить в республике Чувашия, то тип = «Чувашия», название = «Чувашская республика». Потому что пошёл ты нахер, вот почему.

ФИАС — истина в последней инстанции для всех гос. органов. Если вы живёте в Кабардино-Балкарии на Моздокской улице, а у налоговой она значится как «МосдоГская» (в честь знаменитых кабардино-балкарских догов, видимо), то ни одному чиновнику вы свою правоту не докажете.

Или ещё был случай. В 2018 году питерским чиновникам стало скучно, и они домам приделали «литеру А». Был «Невский проспект, дом 41», а стал «дом 41 литер А». И так со всеми домами в городе. На табличках нормально написано, а в голове у чиновников — с литерами. Deal with it.

Справочник полон милых идиотизмов. Однажды перестали помещаться гаражи и садовые товарищества, и налоговая додумалась добавить новый «уровень» адреса для них. Загадочно назвали его «планировочная структура». Но забыли рассказать местным чиновникам, что это такое и зачем. Поэтому теперь в «планировочных структурах» лежит всё от жилых кварталов до районов городов и международных трасс. Бадум-тсс!

Ах да. Если вы думаете, что живёте в городе, то разочарую. На самом деле это не «город», а «городской округ». Это называется «муниципальное деление»: городские округа вместо городов, сельские поселения вместо сёл, и так далее. Ну, чтобы никто не догадался.

Налоговая любит внезапно менять справочник. То все дома в городе потеряет, то битых улиц насыпет, то просто два месяца не обновляет. Объяснений и анонсов, конечно же, никто не делает. Сами разберётесь, не маленькие.

Но. Хоть я и ворчу, ФИАС — большое благо! Это структурированный, регулярно обновляемый справочник адресов, доступный всем желающим. У большинства стран такого нет, так что пусть завидуют 👌

Подписывайтесь на @nalgeon в твитере, чтобы не пропустить новые заметки

Вы являетесь держателем продуктов Тинькофф Банка. При входе по номеру телефона, в целях безопасности, введите пароль.

Я, конечно, не UX-писатель, но это жуть какая кривая формулировка. Давайте попробуем улучшить.

1. Формулируем по-человечески

Меняем суконный язык банковских безопасников на нормальную речь.

Вы являетесь держателем продуктов Тинькофф Банка. При входе по номеру телефона, в целях безопасности, введите пароль.
↓

Вы — клиент Тинькофф Банка. Введите пароль, чтобы войти.

2. Убираем лишнее

Зачем писать человеку, что он клиент? Я и так это знаю, потому и пытаюсь войти в интернет-банк. Убираем.

Вы — клиент Тинькофф Банка. Введите пароль, чтобы войти.
↓

Введите пароль, чтобы войти.

3. Убираем очевидное

На этой же форме огроменное поле ПАРОЛЬ и кнопка ВОЙТИ. Спорим, человек догадается, чего от него хотят?

Введите пароль, чтобы войти.
↓

Ø

Что осталось:

Q&A

А это не юридический затык? У Тинькофа вроде всё хорошо с ux-райтингом во всех других местах.

У Тинькова есть некоторое количество сотрудников, которые умеют писать нормальный текст, и огромная армия тех, кто делать этого не умеет и не желает. Вторые иногда прорываются. Хотя первые в целом отлично справляются, да.

Мне кажется, предполагать, что человек сразу поймет, куда он входит, слишком смело.

Действительно, он зашел на сайт Тинькова, нажал на «Войти», указал номер телефона. Конечно, он понятия не имеет, что делает.

А может это было сделано по требованиям accessibility? Чтобы читалка озвучила, например.

Это делается иначе.

Не уверен, что насчет этого можно сразу рассуждать предположениями. Как реально юзеры реагируют на такую форму можно понять только через исследования.

Не надо проводить исследования, чтобы исправить очевидные проблемы. Исследования не заменяют головной мозг, пользуйтесь им.

Вот чего хотелось:

• Возможность загрузить готовую базу, а не писать SQL для создания таблиц.
• Подключать как локальные базы, так и удаленные (по url).
• Сохранять базу и запросы в облаке.
• Бесплатно и без регистрации.
• Свежайшая версия SQLite.
• Минимализм.

В итоге сделал такую песочницу сам:

• демка с пустой базой;
• пример заполненной базы;
• исходники.

подробности на Хабре

1. Куки

Первые инженеры, едва переодевшись из шкур в неопрятные свитера, попытались использовать родной и привычный HTTP-протокол. Проблема в том, что он не хранит состояние (stateless) — пять запросов от Алисы выглядят точно так же, как пять запросов от пяти разных людей.

Что же делать? В любой непонятной ситуации придумывай костыль! Так появились куки (cookie). Это пары строк (ключ — значение), которые браузер гоняет на сервер с каждым запросом. Таким образом stateless протокол внезапно становится немножко stateful.

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

Куку может установить не только тот сайт, на котором вы находитесь, но и вообще любой (так называемые third-party cookies). Этим немедленно воспользовались хитрозадые рекламодатели. Если на сайте магазина подключен фейсбук, а вы купили ботинки — теперь до конца жизни будете видеть рекламу ботинок на всех сайтах, подключенных к фейсбуку.

Third-party cookies можно отключить в настройках браузера, а в Сафари они даже отключены по умолчанию. Рекомендую это сделать. Правда, некоторые особенно кривые сайты при этом перестанут работать — но оно и к лучшему, как по мне.

Работа с куками в JS реализована традиционно для веба — максимально неудобно. document.cookie — это все куки, склеенные в одну строку через точку с запятой. Наслаждайтесь парсингом.

Вообще, о куках можно еще много плохого рассказать. Делать этого я, конечно, не буду.

Куки на MDN

2. Web Storage

Постепенно разработчики поняли, что надо оставить HTTP в покое и сделать нормальное API хранения данных в браузере. Так появились localStorage и sessionStorage с очень простым интерфейсом:

• получить значение по ключу,
• записать значение по ключу,
• удалить значение по ключу.

localStorage хранит данные вечно, а sessionStorage — только пока открыта вкладка браузера. local свой у каждого домена, чужие данные посмотреть не получится. А session отдельный у каждой вкладки. Максимальный размер базы — несколько мегабайт.

И ключи, и значения — только строки, так что числа, массивы и объекты приходится превращать в строку перед сохранением. И парсить из строки при выборке. Обычно не заморачиваются и используют JSON.stringify / JSON.parse.

sessionStorage редко используют, а вот localStorage весьма популярен. Простой, удобный, быстрый — что еще надо:

let obj = { a: 42 };
let objStr = JSON.stringify(obj);
localStorage.setItem("q", objStr);

let objStr = localStorage.getItem("q");
JSON.parse(objStr);
// {a: 42}

Ребята из команды Chrome рекомендуют вместо Web Storage использовать более новый механизм — IndexedDB. Это, мягко говоря, странный совет — но о своеобразном подходе разработчиков браузеров мы еще поговорим.

Web Storage на MDN

3. Web SQL

Постепенно разработчики дозрели до полноценной базы данных в браузере. Надо сказать, что абсолютно во всех браузерах — что мобильных, что десктопных — уже встроена отличная СУБД, которая реализует стандарт SQL-92 (и большой кусок более поздних стандартов) — SQLite.

Казалось бы, придумай удобный интерфейс поверх SQLite, согласуй со всеми и вперед — что может быть логичнее? Собственно, в конце нулевых так и сделали — новый стандарт Web SQL поддержали Apple (Safari), Google (Chrome) и Opera (еще популярная тогда). А Mozilla (Firefox) — нет.

Замечательные люди из Мозиллы заявили, что:

1. Использовать SQL в вебе некрасиво, у веба свой путь.
2. Где это видано, всем использовать SQLite, вместо того, чтобы каждый браузер напилил свой велосипед.

Классные аргументы, да? Очень характерно для веба.

В результате Web SQL убили, использовать его сейчас нельзя. А элегантное решение, которое гении из Мозиллы породили ему на замену (IndexedDB), я вам скоро покажу.

Документация по Web SQL (для полноты картины)

4. Indexed Database

Ну уж тут-то разработчики браузеров развернулись. IndexedDB — это настоящая NoSQL-база данных у вас в браузере. Можно сделать полноценное приложение, которое шустро ворочает сотнями мегабайт данных, не обращаясь к серверу. Прямо на вашем айфоне, мухаха.

Начнем с хорошего в IndexedDB:

• есть коллекции (аналог таблиц в реляционных БД), индексы и транзакции;
• без проблем хранит массивы и объекты;
• поддерживает версионирование схемы данных;
• (условно) неограниченный размер базы;
• работает асинхронно.

А теперь о плохом:

всё очень сложно

Никаких вам get / set, будьте любезны освоить многочисленные концепции, приемы и особенности работы, чтобы записать свой несчастный объект в базу и получить его обратно. Уверен, вы просто мечтали освоить еще одну СУБД. Ваши мечты сбылись.

Ах, и еще. В вебе есть стандарт асинхронной работы — механизм промисов (promise) и async / await. Так вот, IndexedDB его не поддерживает. Потому что fuck you, that’s why. Используйте костылики (idb) — это ведь так элегантно.

IndexedDB на MDN

5. Cache API

Допустим, у вас веб-приложение для заметок. Было бы здорово, чтобы оно работало даже когда нет сети, верно?

Сами заметки можно хранить в localStorage или IndexedDB. Но что делать, если человек обновит страницу, а сети нет? Тут и пригодится Cache API.

Cache API создан, чтобы хранить не данные приложения, а сетевые запросы и ответы. Обычно это файлы приложения — все ваши *.html, *.css и *.js

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

Cache API простой и асинхронный, одно удовольствие:

const cache = await caches.open("app");
await cache.add("/app.js");
const resp = await cache.match("/app.js");

.add() сам запросит указанный файл и сложит ответ в кеш, такой заботливый.

Возможно, вы ожидаете, что Cache API умеет очищать старые или редко используемые записи (на то он и кеш). Но нет! Это веб, так что решите вопрос как-нибудь самостоятельно.

На самом деле, никто не мешает использовать кеш и для данных приложения. Но так обычно не делают:

const data = { a: 42 };
let resp = new Response(JSON.stringify(data));
await cache.put("data.json", resp);

resp = await cache.match("data.json");
await resp.json();
// { a: 42 }

Cache API на MDN

6. Storage API

Storage API на самом деле ничего не хранит (обожаю веб). Вместо этого оно сообщает, сколько места занято вашим барахлом и сколько всего доступно.

const {usage, quota} = await navigator.storage.estimate();

usage и quota считаются суммарно по всем видам хранилищ — Web Storage, IndexedDB и CacheAPI.

А ещё можно сообщить браузеру, что ваши данные ну очень ценные, и молча удалять их никак нельзя, только с разрешения человека:

navigator.storage.persist()

Storage API пока не работает в Safari. Увы.

Storage API на MDN

7. File (whatever) API

Пара замечательных API с интуитивно понятными названиями: File System Access API и File and Directory Entries API.

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

Очень краткие выводы

• Web Storage для мелочевки
• IndexedDB для серьезных данных
• Cache API для файлов и запросов

Куки оставьте Цукербергу, Web SQL погиб молодым, File * API ещё не родились, а Storage API считает место.

И подписывайтесь на @nalgeon в твитере, чтобы не пропустить новые заметки 🚀