Информатика · объяснение и практика

Чем группировка с подсчётом отличается от удаления повторяющихся строк

Различаем уникальные строки и агрегаты по группам, считаем частоты повторов и задаём порядок результата отдельно от DISTINCT и GROUP BY.

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Таблицы, базы данных и SQL · Учебная карта

Главная мысль

DISTINCT убирает повторяющиеся строки выбранного результата. GROUP BY формирует группы для агрегатов, например COUNT(*). Уникальные категории и категории с числом наблюдений — разные выходные данные.

Как одна таблица отвечает на два вопроса

В столбце class находятся А, А, Б, В, В, В. Запрос SELECT DISTINCT class возвращает три категории без повторов. Он не показывает, сколько учеников в каждой. Запрос SELECT class, COUNT(*) FROM pupils GROUP BY class возвращает категории с частотами 2,1,3. Группировка сохраняет информацию о количестве строк через агрегат.

Если выбрать DISTINCT class, score, уникальность относится к паре значений, а не к class отдельно. Одна категория с разными баллами останется несколькими строками. Поэтому состав выбранных столбцов является частью определения дубля. Нельзя добавлять столбец «для удобства вывода», ожидая прежнего числа уникальных категорий.

Как фильтры связаны с группировкой

WHERE ограничивает исходные строки до образования групп. HAVING может отфильтровать уже рассчитанные группы по агрегату. Для списка классов минимум с тремя строками используют HAVING COUNT(*) >= 3 после GROUP BY. Если сначала WHERE исключит часть учеников, частоты будут считаться по оставшимся, а не по всей таблице.

Например, в данных А, А, Б, В, В, В условие HAVING COUNT(*) >= 2 оставит А и В. Это не удаление дублей, а отбор категорий по размеру. Смысл запроса зависит от того, считаются все строки или только строки с определённым признаком. Название агрегата без описания базы может создать правдоподобную, но неверную статистику.

Пример

Столбец содержит X, X, Y. Что дают DISTINCT и GROUP BY с COUNT(*)?

DISTINCT даёт категории X и Y. Группировка с подсчётом даёт X:2 и Y:1. Точные порядок и оформление требуют отдельного ORDER BY и вывода.

Почему сортировка и выбор других полей отдельны

Ни DISTINCT, ни GROUP BY не следует использовать как обещание нужного порядка. Для стабильного результата задают ORDER BY явно. Без него изменение плана или индекса может переставить строки, сохранив их состав. Особенно важно фиксировать порядок перед пагинацией и при сравнении результатов теста.

При выборе неагрегированного столбца, не входящего в GROUP BY, разные системы ведут себя по-разному: одни отклоняют запрос, SQLite в ряде случаев допускает его со специальными правилами. Нельзя считать случайно выбранное имя ученика представителем группы без явной задачи. Лучше выбирать группирующие поля и обоснованные агрегаты. Тогда результат отвечает одному ясному вопросу, а не сочетает частоту класса с произвольными данными одной его строки.

От чтения к действию

А теперь — вы

Данные А, А, Б. Какой результат содержит и категорию, и число её строк?

Частые вопросы

DISTINCT по двум столбцам убирает повторы каждого отдельно?

Нет. Он сравнивает целые выбранные строки, то есть комбинации этих столбцов.

GROUP BY гарантирует алфавитный порядок?

Нет. Для нужного порядка нужно явно использовать ORDER BY.

Углублённый разбор

Отмена разных элементов в алгоритме Мисры — Гриса

Чтобы найти часто встречающиеся элементы потока, необязательно хранить все точные частоты. Мисра — Грис отменяет группы различных элементов и сохраняет небольшой набор кандидатов. Он гарантирует, что действительно тяжёлый элемент не исчезнет, но оставшийся счётчик обычно меньше настоящей частоты.

Перед началом: Частота элемента; Потоковый проход.

Алгоритм хранит не больше k−1 разных ключей

Выберем k≥2. При новом элементе увеличиваем его счётчик, если он уже хранится. Если ключа нет, но занято меньше k−1 мест, создаём счётчик 1. Иначе уменьшаем все k−1 счётчиков на1, удаляем нулевые и сам новый элемент в таблицу не добавляем. Именно последняя ветвь отменяет k различных вхождений: по одному у каждого сохранённого ключа и текущий новый.

Пусть D — число полных отмен. Каждая отмена потребляет k позиций исходного потока, поэтому kD≤N. Для любого ключа a остаточный счётчик ĉ_a, включая 0 при отсутствии, удовлетворяет f_a−D≤ĉ_a≤f_a. Одна отмена может убрать не больше одного вхождения данного ключа, а увеличение происходит только при реальном появлении. Эти неравенства детерминированы и не зависят от хеш-вероятностей.

Все частоты больше N/k остаются кандидатами

Если f_a>N/k, то f_a>D и ĉ_a>0. Значит любой строго тяжёлый элемент обязательно присутствует в конце. Обратное неверно: последние редкие элементы могут сохраниться после прежних отмен. Поэтому полученная таблица является набором кандидатов, а не готовым точным списком всех превышающих порог.

Второй проход подсчитывает точные частоты только сохранённых ключей и фильтрует условием kf_a>N. Это позволяет решить точную задачу с малой памятью при повторном доступе к потоку. Однопроходный результат имеет интервальную точность f_a∈[ĉ_a,ĉ_a+D]; нельзя использовать ĉ_a>N/k как необходимое условие тяжести, иначе часть настоящих тяжёлых элементов будет потеряна.

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

Гарантия относится к f>N/k. При точном равенстве элемент может исчезнуть, что не противоречит теореме. Для k=2 это отмена разных пар и поиск кандидата большинства. Произвольные удаления, отрицательные веса или повторное использование уже отменённых позиций не входят в доказательство группировки. Реализация также должна явно удалять нулевые записи, чтобы свободное место действительно отражало число активных счётчиков.

Счётчик три скрывает настоящую частоту шесть

Условие. Для k=3 обработайте поток a,b,a,c,a,b,a,d,a,b,a,c. Найдите финальных кандидатов, число полных отмен и точные элементы с частотой>N/3.

  1. До первого c счётчики a=2,b=1. При c таблица полна, поэтому отменяем тройку: остаётся a=1, D=1.
  2. Следующие a,b,a дают a=3,b=1. При d происходит вторая отмена, остаётся a=2. Затем a,b,a дают a=4,b=1.
  3. Последний c вызывает третью отмену. Финальная таблица содержит только a со счётчиком 3, D=3. Проверка массы:3+3·3=12=N.
  4. Второй проход даёт f_a=6,f_b=3,f_c=2,f_d=1. Порог N/3=4, поэтому точный тяжёлый набор равен{a}, хотя его остаточный счётчик 3 сам по себе меньше порога.

Ответ. Кандидат a:ĉ=3,D=3; после точного второго прохода тяжёлый элемент только a с частотой 6.

Проверка. Независимая таблица всех реальных частот подтверждает 6,3,2,1. Для каждого ключа проверены границы f−3≤ĉ≤f и условие отсутствующих f≤3; история отмен содержит непересекающиеся тройки разных ключей.

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

Проверьте понимание

Какие ключи потока имеют точную частоту строго больше 4?

Вопросы к этой главе

Почему новый c не вставляется сразу после общей отмены?

Его текущее вхождение уже использовано как k-й элемент отменённой группы. Повторная вставка посчитала бы одну позицию дважды и разрушила бы инвариант массового баланса.

Что означает отсутствие b при настоящей частоте 3?

При D=3 все три его вхождения могли быть отменены. Гарантия запрещает исчезновение только при частоте строго больше N/k=4, поэтому отсутствие b полностью допустимо.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Graham Cormode: Misra–Gries Summaries, Algorithm0.1

    Прочитаны k−1 счётчиков, отмена k разных элементов и гарантия для частоты>n/k. Определение approximate frequent из других частей не смешивается с точным вторым проходом. Собственный поток 12 элементов и все короткие контрольные потоки проверены отдельно.

Точный distinct в потоке: почему малой памяти недостаточно

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

Перед началом: Мощность множества и объединение; Биты памяти и число различимых состояний.

Фиксируем модель, к которой относится граница

Пусть универсум U содержит N известных элементов. Алгоритм делает один проход по потоку, в котором повторы разрешены, и по сигналу конца обязан выдать точное число различных элементов. Алгоритм детерминирован, а всё, что он помнит о прочитанном префиксе, входит в его рабочее состояние. Бесплатный внешний журнал ключей, неучтённый счётчик позиции или второй проход не предоставляются.

Для каждого подмножества S⊆U подадим его элементы по одному в заранее фиксированном порядке. Получим некоторое состояние после этого префикса. Если алгоритм использует b битов, разных рабочих состояний не больше 2^b. Мы покажем, что все 2^N подмножеств должны давать различные состояния, даже когда два множества имеют одинаковую текущую мощность.

Суффикс различает любую пару прошлых множеств

Предположим разные S, T привели к одному состоянию. После возможной перестановки названий выберем x∈S∖T. Продолжим оба потока одним и тем же суффиксом, содержащим каждый элемент U∖{x}. В первом случае итоговое множество равно U, потому что x уже встречался. Во втором x не было ни в T, ни в суффиксе, поэтому итог равен U∖{x}.

Истинные ответы равны N и N−1. Из одинакового внутреннего состояния на одинаковом продолжении детерминированный алгоритм выдаёт одинаковые ответы, что противоречит требованию точности. Следовательно, состояния для S, T различны. Так как пара была произвольной,2^b≥2^N и b≥N. Это информационное доказательство, а не оценка времени конкретной хеш-таблицы.

Что меняется при ослаблении задачи

Для U={a, b, c, d}, S={a, c}, T={b, c} возьмём x=a. Оба префикса содержат по два различных элемента, поэтому один счётчик не различает их. Суффикс b, c, d даёт четыре различных элемента после S и только три после T. Хранить сведения о предыдущих ключах нужно именно ради будущих повторов, а не только ради текущего значения ответа.

Граница относится к точному ответу на любом потоке в выбранной модели. Вероятностная погрешность, ограниченный класс входов или дополнительная внешняя память меняют постановку. Скетчи мощности экономят память за счёт допустимой ошибки; их нельзя считать контрпримером приведённой границе. Доказательство также не утверждает, что N битов всегда достаточно для всех представлений самого универсума: здесь его элементы и нумерация известны заранее.

Одинаковые текущие счётчики, разные будущие ответы

Условие. U={a, b, c, d}. После префиксов S={a, c} и T={b, c} подайте одинаковый суффикс b, c, d. Используйте пример для объяснения общей нижней границы памяти точного distinct.

  1. Оба префикса имеют мощность 2, но отличаются наличием a и b.
  2. После S суффикс дополняет множество до{a, b, c, d}; ответ 4.
  3. После T тот же суффикс оставляет{b, c, d}; ответ 3. Совпадающие внутренние состояния не смогли бы дать разные ответы.
  4. Для любой различной пары подмножеств аналогично выбирается x из одной разности и суффикс U∖{x}. Все 2^N состояний должны различаться, поэтому требуется не меньше N битов.

Ответ. Пример требует различать S и T; общий аргумент даёт b≥N для точного детерминированного однопроходного счётчика.

Проверка. Для N=4 можно перебрать все 16 подмножеств и каждую из 120 различных пар. Для каждой пары находится общий суффикс, дающий конечные мощности 4 и 3.

Где легко ошибиться. Не переносите нижнюю границу для точного детерминированного ответа на другую модель без проверки её условий.

Проверьте понимание

Какая постановка доказана в этой главе?

Вопросы к этой главе

Почему недостаточно хранить только текущее число distinct?

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

Противоречит ли маленький вероятностный скетч этой границе?

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

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

Вычитаемая хеш-таблица восстанавливает небольшую разность множеств

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

Перед началом: XOR и знаковые счётчики; Разность множеств.

Общие ключи уничтожаются при вычитании таблиц

Разность двух множеств без повторов. Учебная XOR-вариация IBLT хранит знаковый счётчик, XOR ключей и XOR контрольных значений; вероятность коллизий не считается нулевой.

Каждый ключ направляется в несколько разных ячеек. При добавлении увеличивают их счётчики и применяют XOR к ключевому и контрольному полям. Для разности A−B счётчики вычитают, а XOR-поля объединяют тем же XOR. Общий ключ из двух множеств даёт нулевой суммарный вклад во всех своих ячейках.

Знак оставшегося ключа хранится в счётчике: +1 означает A без B, −1 — B без A. В XOR знак не виден, поскольку ключ, применённый дважды, уничтожается. Эта упрощённая схема рассчитана на множества с единственным вхождением ключа. Многократные вставки и произвольные кратности требуют иной модели агрегатов.

Кандидат снимается сразу со всех своих адресов

Если абсолютное значение счётчика равно одному, keyXOR рассматривают как кандидат k. Проверяют допустимость его диапазона, соответствие текущей ячейки одному из адресов k и равенство checkXOR=H(k). При успешной проверке выводят пару (знак,k), затем вычитают её вклад из всех адресованных ячеек. Так могут появиться новые снимаемые кандидаты.

Контрольное поле существенно: смесь нескольких положительных и отрицательных ключей тоже способна иметь счётчик один. Однако конечная контрольная функция не делает ложное совпадение невозможным. В вероятностной реализации выбирают подходящее случайное хеширование; в нашем маленьком примере H(k)=k² служит только наглядной проверкой заданных ключей, а не обещанием криптографической защиты.

Остаток без снимаемой ячейки ещё не равен пустому множеству

Peeling — последовательное удаление известных вкладов. Если все ячейки обнулены и проверки не дали ложных кандидатов, найденные элементы объясняют таблицу разности. Если остался ненулевой остаток без подходящих ячеек, перечисление не завершено. Из этого нельзя заключить ни равенство исходных множеств, ни отсутствие дополнительных различий.

Например, при двух ячейках и двух адресах на каждый ключ элементы 1 и 4 попадают в обе ячейки. Для A={1},B={4} каждый счётчик нулевой, но keyXOR=5 и checkXOR=17. Начать снятие не с чего. Дополнительная память или другой набор хешей меняет граф декодирования; простое округление агрегатов утраченные возможности не возвращает.

Четыре ячейки восстанавливают три различия

Условие. A={1,2},B={4}. Ключи находятся в диапазоне 1,…,15; адреса h₁(k)=k mod 4 и h₂(k)=(k+1) mod 4, контроль H(k)=k². Постройте XOR-таблицу A−B и снимите различия.

  1. Ключ 1 добавляется в ячейки 1,2; ключ 2 — в 2,3; ключ 4 вычитается из 0,1. Первичные тройки (count,keyXOR,checkXOR): 0:(−1,4,16),1:(0,5,17),2:(2,3,5),3:(1,2,4).
  2. Ячейка 0 указывает −4: контроль 16=H(4), адрес 0 верен. Убираем этот отрицательный вклад, прибавив единицу к счётчикам 0,1 и повторив XOR с 4 и 16.
  3. Ячейка 1 теперь содержит (1,1,1) и даёт +1. Снимаем ключ 1 со счётчиков 1,2 и соответствующих XOR-полей.
  4. Ячейка 2 становится (1,2,4) и даёт +2. Снятие из 2,3 обнуляет все оставшиеся поля.
  5. Получены A\B={1,2} и B\A={4}. Прямое сравнение исходных множеств подтверждает каждый знак и элемент; случайного обещания безошибочности контрольной функции для всех входов здесь не делается.

Ответ. Знаковая разность равна {+1,+2,−4}; после трёх снятий таблица нулевая.

Проверка. Обратная сборка таблицы только из найденных трёх вкладов восстанавливает все четыре исходные тройки. Отдельный двухъячеечный контрпример оставляет ненулевой остаток без кандидатов, поэтому успешный пример не превращается в общую гарантию декодирования.

Где легко ошибиться. Счётчик ±1 сам по себе не доказывает, что ячейка содержит один ключ. А отсутствие снимаемых ячеек не доказывает равенства множеств: нужно проверить остаток и условия контрольного хеша.

Проверьте понимание

Каковы два направления разности в разобранном примере A={1,2},B={4}?

Вопросы к этой главе

Почему ключ из B снимается добавлением к счётчику?

Его вклад в разности отрицательный. Чтобы убрать −1, вычитают этот вклад, то есть прибавляют 1. Для XOR повторное применение ключа одинаково отменяет как положительное, так и отрицательное вхождение.

Можно применять эту XOR-вариацию прямо к спискам с повторами?

Нет без отдельного преобразования или изменения схемы. Два одинаковых ключа уничтожатся в XOR, хотя счётчик изменится на два. Здесь предполагаются множества; модель с кратностями использует другие проверяемые агрегаты.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Goodrich and Mitzenmacher: Invertible Bloom Lookup Tables, §§3–4

    Прочитаны контрольные суммы, знаковые удаления и оговорка о применении XOR без многократных ключей. Наши четыре ячейки, функция k² и двухъячеечная неудача — самостоятельные конечные примеры, не оценка вероятностных порогов статьи.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться