malyj_gorgan | маленька SQL задачка

Виплила задача. Зрозумів, що я отак одразу не знаю, як її розвʼязати. Правда, я ще толком не думав, але чого я маю думати сам? Думайте і ви теж!

Власне, задача: Таблиця TBL має текст і метадані повідомлень, які відсилають юзери мережі. Нас цікавлять три колонки: user_id, message_text, _time. До таблички треба додати ще одну колонку, яка буде описувати скільки таких повідомлень підряд було/буде відіслано цим юзером. Тобто, допустимо, юзер stepan відіслав, по-порядку, ось такі повідомлення: hi, hi, hello, hi, hi, hi, hi, huilo, huilo, hi. Ці повідомлення повинні відповідати цифрам: 2,2,1,4,4,4,4,2,2,1.

У мене поки що в голові лише якісь неелєґантні розвʼязки з двома проходами з віконною функцією плюс одною агрегацією, пхе. Чи я чогось не знаю?
Кому цікаво, очевидний неелеґантний розвʼязок:

WITH
cte1 AS (
  SELECT user_id, message_text, _time,
         IFF(message_text=LEAD(message_text) OVER 
          (PARTITION BY user_id ORDER BY _time, 0,1) 
          AS x
  FROM tbl
),

cte2 AS (
 SELECT user_id, message_text, _time, 
        SUM(x) OVER (PARTITION BY user_id 
                     ORDER BY _time ROWS BETWEEN 
                     UNBOUNDED PRECEDING AND CURRENT ROW) 
            AS y
  FROM cte1
),

cte3 AS (
  SELECT user_id, y, COUNT(1) AS window_length
  FROM cte2
  GROUP BY user_id, y
)

SELECT user_id, message_text, _time, window_length
FROM cte2 INNER JOIN cte3 USING(user_id, y)

UPDATE: Ви казали, нема такого рішення, а воно є!. Дякую шановному

aklepatc за розвʼязок. Ось тут відформатована версія.

Flat | Top-Level Comments Only

From:

sassa_nf

У нас схожу задачку десь так і розв'язували.

Думаю, можна обійтися без inner join, а просто ще одне вікно. (count(1) over (partition by user_id, y rows between unbounded preceding and unbounded following))

From:

malyj_gorgan

Можна і вікно, точно.
Я б джойн написав всередині останнього SELECT'а, чогось мені джойнʼи подобаються більше, ніж вікна. Вікна мені Windows'ом віддають...

From:

sassa_nf

А мені заходить ліпше. Бо це ж очевидно par do. Джойни розпорошують логіку, а коректність деяких речей важче довести.

From:

kondybas

"..Джойни розпорошують логіку.."

З процедурної точки зору - можливо, але в реляційній алгебрі то єдино правильний підхід. Ну, і в продуктивності буде суттєва різниця.

From:

sassa_nf

Про продуктивність можна подробиці, бо я не розумію, що саме джойн може поліпшити?

Джойн: partition by [O(N log N) because of the preceding group by], а потім key lookup [N * O(log N) = O(N log N) for large keysets].

Window: partition by [O(N log N)], then compute one value in a running fashion [N * O(1) = O(N)] (for expressions that touch rows until current row), or compute one constant for entire partition [1 * O(N)] (for expressions that touch all rows - unbounded preceding and unbounded following)

Additionally, windows can be fused, if they are partitioned using conditions that are subsets or supersets of each other. So subsequent partitioning is also O(M log M), but for (much) smaller M.

Edited Date: 2025-10-16 11:54 am (UTC)

From:

kondybas

а як тут можна елегантно? ну, в мусклі/марії ще можна СТЕ та вікна замінить на фокуси з UDF. але ж все одно треба складати словника токенів і робити повторний прохід по таблиці для внесення відомостей про майбутнє.

From:

malyj_gorgan

Ось вона -- різниця між SQL i мовою-мовою, навіть якоюсь пандою в Пітоні -- там спочатку сортуєш все за юзером і часом, а потім один раз проходиш масив, памʼятаючи індекс початку вікна однакових значень, щоби, як тільки значення міняється, заповнити шматок стовпчика відповідним значенням.
Може, воно мені здається елегантнішим виключно як артефакт молодості, яку я провів програмуючи обчислення на Сі :)

From:

kondybas

Бо SQL то не мова програмування, то мова запитів. Якщо готових даних в базі нема, тоді ой.
В таких випадках оптимальним є препроцесинг. Ну, тобто, на момент інсерту в таблицю одразу писати ше й інкрементований лічильник. А потім проходити таблицю в зворотньому порядку.

From:

sassa_nf

Ну, і? Зекономиш один прохід, бо двічі все одно треба.

From:

malyj_gorgan

Мені воно _виглядає_ краще, не треба шукати тут раціо :) Я розсортовану табличку уявляю як штуковину, де в один бік індекси юзерів від нуля догори, в другий -- індекси часу від нуля до якогось максимума, який різний для кожного юзера. Тоді в псевдокоді логічно хороше рішення мені виглядає так:

for(u=0; u<Umax; u++) {
  i = j = 0;
  val = tbl[u][j] ;
  for(i=1; i<Imax[u]; i++) {
    if(val != tbl[u][i]){
      memset(&out[u][j], i-j, (i-j)*sizeof(int));
      val = tbl[u][i];
      j = i;}
    memset(&out[u][j], i-j, (i-j)*sizeof(int));}}

Де out -- int структура такої самої розмірності, як tbl.
І от розумію, що з точки зору абстрактних компʼютер сайєнтістів це може виглядати некрасиво, але це -- то, як як думаю про розрахунки. (Перших 20 років свого досвіду програмування я не знав нічого, крім вибраних розділів Numerical Recipes in C.... Наступних скільки-там-було років свого досвіду програмування я перестав знати навіть то :))

Edited Date: 2025-10-16 03:58 pm (UTC)

From:

ichthuss

"Як краще денормалізувати базу".

From:

kondybas

Денормалізація - то не гріх. Зрештою, тюрингова машина добре працює із списками, і зовсім не працює з множинами. Тому доводиться множини емулювати на списках, а це породжує неприємні побіжні ефекти, які за розумний час інакше, як денормалізацією, не подолати.

From:

ichthuss

Не гріх, але завжди морока (як і з будь-якими інваріантами стану).

From:

kondybas

Чесно кажучи, після запровадження типу `JSON` із доступом до елементів об'єкту, що прямо порушує 1NF, я вже нічому не дивуюся. Зрештою, мені тільки більше роботи буде.

From:

aklepatc

How about something like this?

Sorry, not sure how to format code properly here... Calculated grp column seems to do trick.

WITH numbered_messages AS (
-- Assign a group number that changes whenever msg_txt changes for a user
SELECT
user_id,
msg_txt,
_time,
ROW_NUMBER() OVER (PARTITION BY user_id ORDER BY _time)
- ROW_NUMBER() OVER (PARTITION BY user_id, msg_txt ORDER BY _time) AS grp
FROM tbl
) SELECT
user_id,
msg_txt,
_time,
COUNT(*) OVER (PARTITION BY user_id, msg_txt, grp ORDER BY _time) AS consecutive_count
FROM numbered_messages
ORDER BY user_id, _time;

Edited Date: 2025-10-16 09:42 pm (UTC)

From:

malyj_gorgan

O! Супер!
Правда, в останньому вікні треба забрати ORDER BY _time, деякі бази даних, якщо для функції COUNT() вказати порядок сортування, автоматично вважають, що там ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW. Ну, принаймні, Snowflake так вважає, як я тільки що переконався, швидко підставивши пару прикладів. Достатньо забрати сортування і все працює.
Дякую! Це саме те, що я назву елеґантним sql рішенням! Шкода, ми зараз data scientist'ів не шукаємо, я би позицію запропонував ;)

Форматувати код можна простим htmlʼним теґом <pre>(код)</pre> Давайте, я переформатую для нащадків:

WITH
numbered_messages AS (
  SELECT user_id, msg_txt, _time,
        ROW_NUMBER() OVER (PARTITION BY user_id ORDER BY _time)
        - ROW_NUMBER() OVER (PARTITION BY user_id, msg_txt ORDER BY _time) AS grp
  FROM tbl
) 
SELECT _time, user_id, msg_txt,
       COUNT(*) OVER (PARTITION BY user_id, msg_txt, grp) AS window_length
FROM numbered_messages
ORDER BY user_id, _time;

From:

aklepatc

Half of the credit goes to Claude. It gave me a much more complex CTE (relative to what I posted above). Still, the row number subtraction trick was a part of it.

And thank you for the order by _time correction!

Edited (Clarification , punctuation ) Date: 2025-10-16 11:34 pm (UTC)

From:

aklepatc

Also, special thank you for "pre". Will try it next time.

Edited (Punctuation, style) Date: 2025-10-16 11:56 pm (UTC)

From:

sassa_nf

А у вас pipe syntax використовують? Я трохи покористувався і підсів. Менше отаких хитромудрих cte, ближче до справи.

FROM tbl
|> EXTEND ROW_NUMBER() OVER (same_user) - ROW_NUMBER() OVER (same_message) AS grp
   WINDOW same_user AS (PARTITION BY user_id ORDER BY _time),
          same_message AS (PARTITION BY user_id, msg_txt ORDER BY _time)
|> EXTEND COUNT(1) OVER (same_group) AS window_length
   WINDOW same_group AS (PARTITION BY user_id, msg_txt, grp)
|> SELECT _time, user_id, msg_txt, window_length
|> ORDER BY user_id, _time;

From:

malyj_gorgan

Виглядає дивно, сходу не розумію (disclaimer: я пишу по дорозі в ліжко, ніч уже). Мені, правду кажучи, cte не хитромудрі, а природні. Я, навпаки, намагаюся співробітників відучати від, принаймні, looped SELECTs на користь читабельних cte's.
Плюс, не знаю, чи воно є на snoflake'у. Принаймні, можливості окремо визначати WINDOW, як в BigQuery точно нема. Ок, точно не було навесні, коли я останній раз пробував, так-то Snowflake досить непогано розвивається, точно швидше за RedShift

From:

sassa_nf

Ну, іменовані вікна тут щоб ліпше видно intent, так то можна прямо в over записати.

Я коли на SQL дивлюсь, то саме у такій послідовності: звідки беремо, що ми робимо, куди далі передаємо. Різниця суто синтаксична, план виконання не відрізняється.

EXTEND це SELECT * із новими колонками. |> це заміна SELECT у попереднього CTE та FROM наступного.

From:

malyj_gorgan

Яка краса, я би і сам таке використовував! На жаль, в Snowflake оператора EXTEND ще нема :(
Пайп є, правда, пишеться інакше, отак: ->>
Додали його недавно, тому я не знав. Виглядає зручно, буду вчитися.

Edited Date: 2025-10-17 04:19 pm (UTC)

From:

aklepatc

Sorry for the late afterthought...

Yes, I am on the market now. AFAICT market sucks with capital S. So I might be still here in (the early) 2026.

If you were able to make a good intro or even have a good lead in the comming months I would very much appreciate it. Backend programmer or SMLT... Can DM my LinkedIn profile if it makes any sense.

From:

malyj_gorgan

Hmmm.
For non-DS positions we actually have a few openings. Our backend is all in Go, which afaik is somewhat obscure as skillsets go. Here: https://www.textnow.com/careers
If anything fits, please DM me

From:

aklepatc

I have 8 years of Go exp. Including ~4 years building low latency/high frequency data intensive systems.

DM-ed my profile...

Edited (Addition ) Date: 2025-10-18 09:45 pm (UTC)

From:

sassa_nf

~~Does it work though?~~ hmm OK

Partition by user_id, msg_txt order by time is going to produce a different ~~grp~~ number for every message. But grp will be the same, if both orders by time increments by 1 - i.e. consecutive messages.

Edited Date: 2025-10-17 06:05 am (UTC)

From:

aklepatc

Looks like the magic trick does what's needed. I am still chewing on it though...

From:

aklepatc

The 2nd row number "resets" every time msg_txt changes.

Edited Date: 2025-10-17 11:44 am (UTC)

From:

aklepatc

grp remains the same and is unique within every group/span.

_Maybe_ the easiest explanation for uniqueness is that the 1st row number grows at least as fast as the 2nd one or even faster.

Also, uniqueness is per user_id. grp can be the same (i think) across different users but this would not be an issue.

Edited (Clarification, addition) Date: 2025-10-17 12:48 pm (UTC)

From:

sassa_nf

Yes, that's exactly why.

Since we use grp together with msg_txt, we need to consider only groups of identical messages.

Message B follows A as part of one contiguous group, if B is next after A in the contiguous group and B is next after A in total order in time. In terms of integer row numbers this means both B's row numbers are greater than A's by 1, and the difference is the same for all messages in one contiguous group.

Similarly the uniqueness of grp follows from the fact that for group B following group A in time the first message of B will have row number greater than the last message of A by 1, but the row number in time is greater by more than 1.

From:

malyj_gorgan

Мені для того, щоби переварити, достатньо фокусуватися на двох фактах: 1. номер рядку у вікні за юзером ніколи не менший, ніж номер рядку у вікні за юзером + ще чимось. 2. Різниця номерів рядків у двох вікнах для того ж юзера не міняється, поки він відсилає ті самі повідомлення.
Далі очевидно-тривіально

From:

sassa_nf

Так, це воно і є. Різниця лише в тому, що факт (1) треба ще довести, а у моєму формулюванні ми відштовхуємось від визначення. Ми користуємось саме цим визначенням, коли формулюємо логіку за допомогою LEAD або LAG.

From:

malyj_gorgan

> факт (1) треба ще довести
Та ні, він за визначенням такий, якщо u позначає юзера, m месидж, R_um і R_u -- номер рядка для юзера з у без врахування мессиджа, то за принципом побудови:
R_u = ∑_m R_um
Відповідно, оскільки всі вони невідʼємні,
R_u ≥ R_um