Temu Duga SQL: Cari Rentetan Log Masuk Berturut-turut Terpanjang Setiap Pengguna

Gesaan dan Konteks yang Berkenaan

Anda diberi jadual peristiwa PostgreSQL:

CREATE TABLE user_logins (
  user_id bigint NOT NULL,
  login_at timestamptz NOT NULL
);

Bagi setiap pengguna, kembalikan setiap jujukan terpanjang bagi tarikh kalendar America/New_York berturut-turut di mana pengguna tersebut log masuk sekurang-kurangnya sekali. Lajur output ialah user_id, streak_start, streak_end, dan streak_days. Pelbagai peristiwa pada tarikh tempatan yang sama dikira sebagai satu hari aktif. Sebarang tarikh tempatan yang hilang memutuskan rentetan. Jika pengguna mempunyai dua rentetan terpanjang dengan panjang yang sama, kembalikan kedua-duanya. Pengguna tanpa sebarang peristiwa tidak akan dipaparkan.

Ini ialah masalah temu duga data dan SQL, bukan permintaan untuk mengira tempoh 24 jam yang telah berlalu. Hari tempatan sekitar peralihan waktu jimat siang (daylight saving) mungkin mengandungi 23 atau 25 jam dan masih merupakan satu tarikh kalendar. Oleh itu, soalan ini menetapkan zon masa pelaporan sebelum menukar cap masa kepada tarikh. Jawapan utama mensasarkan PostgreSQL; dialek lain memerlukan aritmetik tarikh yang berbeza.

Tugas teras ialah masalah gaps-and-islands: ubah tarikh yang disusun supaya setiap tarikh dalam satu jujukan berturut-turut berkongsi kunci yang stabil, agregatkan setiap kunci menjadi pulau (island), dan kemudian kekalkan semua pulau yang terikat untuk panjang maksimum bagi setiap pengguna.

Perkara yang Dinilai oleh Penemu Duga

Isyarat pertama ialah sama ada calon menentukan butiran (grain) data sebelum menulis fungsi tetingkap (window function). Butiran sumber ialah satu peristiwa log masuk, tetapi butiran perniagaan ialah satu baris bagi setiap pengguna dan tarikh kalendar tempatan. Melangkau penukaran tersebut membolehkan peristiwa pendua pada hari yang sama melambungkan ROW_NUMBER(), kiraan, dan sempadan rentetan.

Isyarat kedua ialah sama ada calon boleh menerbitkan kunci pulau (island key). Selepas tarikh berbeza diisih, kedua-dua tarikh dan ROW_NUMBER() bertambah satu di dalam jujukan berturut-turut. Oleh itu, menolak ofset nombor baris daripada setiap tarikh menghasilkan nilai yang sama sepanjang jujukan tersebut. Pada jurang (gap), tarikh melompat lebih daripada satu manakala nombor baris bertambah tepat satu, jadi kuncinya berubah.

Isyarat ketiga ialah disiplin kontrak. "Rentetan terpanjang" adalah kabur apabila dua jujukan mempunyai panjang yang sama. Kueri yang menggunakan ROW_NUMBER() untuk memilih satu keputusan secara senyap membuang ikatan seri yang sah. Gesaan ini memerlukan setiap maksimum yang terikat, jadi jawapan membandingkan setiap panjang pulau dengan panjang pulau maksimum untuk pengguna tersebut.

Isyarat keempat ialah ketepatan zon masa. Menghantar (casting) login_at secara terus kepada date menggunakan zon masa sesi pangkalan data, yang mungkin berbeza antara persekitaran. Jawapan ini menukar setiap timestamptz kepada zon perniagaan yang dinamakan terlebih dahulu dan hanya selepas itu mengambil tarikhnya. Ofset UTC tetap tidak mencukupi untuk zon yang ofsetnya berubah mengikut peraturan waktu jimat siang.

Isyarat terakhir ialah pengesahan dan pertimbangan skala. Kueri yang betul harus diuji pada setiap CTE, dengan peristiwa pendua, jujukan satu hari, jurang, ikatan seri, kes tengah malam tempatan, dan sempadan waktu jimat siang. Pada jadual peristiwa besar yang sering dikueri, calon harus menyedari bahawa mengurangkan peristiwa mentah kepada satu baris tersimpan bagi setiap pengguna-hari boleh menjadi lebih bernilai daripada mengoptimumkan mikro kueri tetingkap akhir.

Soalan untuk Dijelaskan Sebelum Menjawab

• Apakah yang mentakrifkan sehari? Zon masa perniagaan yang dinamakan, UTC, atau zon masa pengguna sendiri mengubah penukaran

tarikh dan mungkin jawapannya. Gesaan ini menggunakan America/New_York untuk setiap pengguna.

• Adakah log masuk berbilang kali pada satu hari dikira lebih daripada sekali? Tidak untuk kes ini, jadi penyahduplikasian (deduplication) mesti berlaku

sebelum penomboran. Jika metriknya ialah peristiwa berturut-turut, butiran dan peraturan pengelompokan akan berubah.

• Adakah satu tarikh yang hilang sentiasa memutuskan rentetan? Ya. Soalan penyesianan (sessionization) dengan ambang

30 minit memerlukan perbandingan baris sebelumnya dan bukannya kedekatan kalendar yang ketat.

• Bagaimanakah keputusan seri harus dikembalikan? Kontrak ini mengembalikan setiap pulau terpanjang yang terikat. Memilih rentetan

yang paling terkini memerlukan pemutus seri yang berbeza dan eksplisit.

• Adakah julat dihadkan? Penapis tarikh boleh mengurangkan kerja, tetapi ia juga memotong rentetan yang bermula

sebelum julat tersebut. Pemanggil mesti menyatakan sama ada hasilnya "dalam julat" atau rentetan lengkap yang melintasi sempadannya.

• Bolehkah user_id atau login_at bernilai null? Skema menyatakan tidak. Jika null dibenarkan, pengendaliannya

perlu dinyatakan sebelum menyusun atau mengelompokkan.

• Adakah ini kueri sekali sahaja atau metrik produk yang berulang? Jawapan ad hoc boleh mengimbas dan menyusun baris

harian. Papan pemuka yang kerap disegarkan mungkin mewajarkan jadual pengguna-hari yang diselenggara secara bertambah (incrementally).

Rangka Kerja Jawapan 30 Saat

“Saya akan menukar setiap timestamptz kepada zon masa perniagaan yang dipersetujui terlebih dahulu dan menyahduplikasi kepada satu baris bagi setiap pengguna dan tarikh tempatan. Bagi setiap pengguna, saya menyusun tarikh tersebut dan menetapkan ROW_NUMBER(). Untuk tarikh berturut-turut yang ketat, login_day - row_number × one day kekal malar di dalam rentetan dan berubah selepas jurang, jadi saya mengelompokkan mengikut kunci terbitan tersebut untuk mendapatkan sempadan dan panjang setiap rentetan. Saya kemudian membandingkan setiap panjang dengan maksimum pengguna, yang mengekalkan ikatan seri. Saya akan menguji peristiwa pendua pada hari yang sama, rentetan satu hari, jurang, maksimum yang sama, kes tengah malam tempatan dan waktu jimat siang, serta memeriksa pelan pelaksanaan pada data yang representatif.”

Perbincangan Mendalam Langkah demi Langkah

Mulakan dengan menormalkan aliran peristiwa kepada butiran perniagaan. Untuk timestamptz, AT TIME ZONE dengan zon yang dinamakan menghasilkan cap masa jam dinding dalam zon tersebut. Menghantar hasil tersebut kepada date memberikan tarikh kalendar perniagaan. SELECT DISTINCT kemudiannya menjamin tepat satu baris bagi setiap pengguna-hari.

Kueri lengkap adalah:

WITH login_days AS (
  SELECT DISTINCT
    user_id,
    (login_at AT TIME ZONE 'America/New_York')::date AS login_day
  FROM user_logins
),
numbered AS (
  SELECT
    user_id,
    login_day,
    ROW_NUMBER() OVER (
      PARTITION BY user_id
      ORDER BY login_day
    ) AS rn
  FROM login_days
),
grouped AS (
  SELECT
    user_id,
    login_day,
    login_day - (rn * INTERVAL '1 day') AS island_key
  FROM numbered
),
streaks AS (
  SELECT
    user_id,
    MIN(login_day) AS streak_start,
    MAX(login_day) AS streak_end,
    COUNT(*) AS streak_days
  FROM grouped
  GROUP BY user_id, island_key
),
scored AS (
  SELECT
    user_id,
    streak_start,
    streak_end,
    streak_days,
    MAX(streak_days) OVER (PARTITION BY user_id) AS max_streak_days
  FROM streaks
)
SELECT
  user_id,
  streak_start,
  streak_end,
  streak_days
FROM scored
WHERE streak_days = max_streak_days
ORDER BY user_id, streak_start;

Pembuktian mengikut baris harian yang disusun. Bagi seorang pengguna, panggil tarikh yang berbeza sebagai d1, d2, ... dan nombor baris sebagai 1, 2, .... Jika d(i+1) = d(i) + 1 day, maka menolak ofset nombor baris seterusnya akan membuang hari tambahan yang sama, jadi kunci terbitan adalah sama. Jika sekurang-kurangnya satu tarikh hilang, d(i+1) bertambah sebanyak dua atau lebih hari manakala nombor baris bertambah satu; kunci terbitan meningkat dan memulakan kumpulan baharu. Penyahduplikasian menjadikan COUNT(*) bersamaan dengan hari kalendar, manakala MIN dan MAX ialah sempadan pulau yang tepat.

Maksimum akhir sengaja menggunakan MAX bertetingkap, bukan satu lagi ROW_NUMBER(). Setiap pulau yang panjangnya sama dengan maksimum pengguna dikekalkan. Jika produk kemudiannya meminta hanya satu rentetan, tambah peraturan yang dinyatakan seperti “tarikh tamat terkini menang” dan gunakan susunan deterministik; jangan reka peraturan tersebut di dalam kueri.

Pertimbangkan tarikh ternormal untuk dua pengguna:

user 1: Mar 07, Mar 08, Mar 09, Mar 11, Mar 12
user 2: Nov 01, Nov 02, Nov 04, Nov 05

result:
user 1 | Mar 07 | Mar 09 | 3
user 2 | Nov 01 | Nov 02 | 2
user 2 | Nov 04 | Nov 05 | 2

Pengguna 1 mempunyai maksimum tiga hari. Pengguna 2 mempunyai dua maksimum dua hari yang berasingan, jadi kedua-dua baris diperlukan. Pelbagai peristiwa mentah pada mana-mana tarikh yang dipaparkan tidak mengubah keputusan. Sekitar perubahan waktu jimat siang, soalan yang berkaitan tetap sama ada tarikh tempatan bersebelahan, bukan sama ada cap masa terpisah tepat 24 jam.

Untuk N peristiwa mentah dan D baris pengguna-hari yang berbeza, penyahduplikasian membaca N baris dan mungkin melakukan hash atau susun; langkah tetingkap menyusun sehingga D baris mengikut pengguna dan tarikh. Batasan temu duga yang berguna ialah masa O(N log N + D log D) dalam pelan berasaskan susunan dan ruang perantaraan O(D), sambil mengambil perhatian bahawa pengoptimum mungkin menggunakan hash, susunan sedia ada, keselarian, atau limpahan cakera (disk spills). Pelan pelaksanaan, bukan Big-O semata-mata, yang menentukan sama ada kueri pengeluaran boleh diterima.

Bagi metrik berulang pada berbilion-bilion peristiwa, cipta jadual yang diselenggara secara bertambah dengan kunci unik pada (user_id, login_day). Ini memindahkan penukaran zon masa dan penyahduplikasian hari yang sama ke sempadan penyerapan (ingestion) atau kelompok (batch), jadi kueri rentetan membaca D baris harian dan bukannya N peristiwa. Jika kueri ad hoc mempunyai julat masa, gunakan sempadan cap masa UTC sargable sebelum penukaran tarikh tempatan, tetapi terbitkan sempadan UTC tersebut daripada tengah malam tempatan zon bernama supaya perubahan waktu jimat siang dihormati.

Periksa hasil perantaraan dan bukannya menganggap jadual akhir sebagai bukti:

-- These checks are run against the corresponding CTE or materialized test result.
SELECT user_id, login_day, COUNT(*)
FROM login_days
GROUP BY user_id, login_day
HAVING COUNT(*) > 1;

SELECT *
FROM numbered
ORDER BY user_id, login_day;

SELECT *
FROM streaks
WHERE streak_days <> (streak_end - streak_start + 1);

Semakan pertama dan ketiga tidak sepatutnya mengembalikan sebarang baris. Output bernombor menjadikan butiran atau susunan yang salah kelihatan jelas. Jalankan kueri lengkap yang diawali dengan EXPLAIN (ANALYZE, BUFFERS) untuk mendedahkan imbasan, susunan, anggaran baris, I/O sementara, dan sama ada mengurangkan peristiwa mentah lebih awal memberi kesan. Gunakan salinan representatif yang selamat apabila melaksanakan penyataan pengeluaran itu sendiri terlalu mahal.

Teknik shifted-date tidak bersifat universal. Jika sesi baharu bermula apabila jurang melebihi 30 minit, atau pulau berterusan selagi nilai status kekal tidak berubah, gunakan LAG() untuk memeriksa baris sebelumnya, tandakan setiap sempadan, dan ambil SUM() terkumpul bagi bendera tersebut. Peraturan keputusannya mudah: gunakan kunci anjakan untuk jujukan unit demi unit yang ketat; gunakan bendera sempadan apabila kesinambungan bergantung pada perbandingan tersuai.

Contoh Jawapan Berkualiti Tinggi

“Sebelum menulis SQL, saya akan mengunci butiran data dan kontrak ikatan seri. Sumber mempunyai banyak peristiwa bagi setiap pengguna, tetapi metrik ini mengira satu tarikh kalendar America/New_York bagi setiap pengguna. Oleh itu, saya akan menukar timestamptz kepada zon yang dinamakan itu, menghantar kepada date, dan menyahduplikasi sebelum sebarang fungsi tetingkap. Ini juga menghalang zon masa sesi daripada mengubah keputusan secara senyap.

Bagi langkah gaps-and-islands, saya menetapkan ROW_NUMBER() yang disusun mengikut tarikh tempatan bagi setiap pengguna. Semasa jujukan berturut-turut, kedua-dua tarikh dan nombor baris bertambah satu, jadi menolak ofset hari nombor baris menghasilkan kunci malar. Tarikh yang hilang menjadikan tarikh melompat lebih jauh daripada nombor baris dan mengubah kuncinya. Pengelompokan mengikut pengguna dan kunci tersebut memberikan tarikh mula, tamat, dan bilangan tarikh aktif untuk setiap rentetan.

Saya akan menggunakan maksimum bertetingkap pada panjang rentetan dan mengekalkan baris yang sama dengan maksimum tersebut. Ini mengembalikan semua rentetan terpanjang yang terikat, seperti yang diperlukan, dan bukannya memilih satu secara senyap. Had atas berasaskan susunan adalah kira-kira O(N log N + D log D), di mana N ialah peristiwa mentah dan D ialah pengguna-hari yang berbeza, walaupun saya akan memeriksa pelan sebenar dan limpahan cakera.

Data ujian saya akan merangkumi beberapa peristiwa pada satu tarikh, pengguna satu hari, tarikh yang hilang, dua maksimum yang sama, peristiwa pada kedua-dua belah tengah malam tempatan, dan peralihan waktu jimat siang. Bagi metrik skala besar yang berulang, saya akan mengekalkan jadual pengguna-hari yang unik dan menjalankan logik tetingkap pada butiran yang lebih kecil itu. Jika kesinambungan berubah daripada kedekatan kalendar kepada jurang ambang, saya akan beralih kepada LAG() serta bendera sempadan dan jumlah terkumpul.”

Kesilapan Biasa

• Menomborkan peristiwa log masuk mentah → peristiwa pendua memajukan nombor baris dan melambungkan kiraan →

nyahduplikasi kepada satu baris pengguna-hari sebelum menggunakan tetingkap.

• Menghantar timestamptz secara terus kepada date → jawapan bergantung pada zon masa sesi →

tukar kepada zon perniagaan yang dinamakan terlebih dahulu.

• Menggunakan ofset UTC tetap → tarikh tempatan menjadi salah apabila zon yang dinamakan mengubah ofset →

gunakan zon IANA dengan peraturan kalendarnya.

• Membandingkan cap masa terpisah 24 jam → hari tempatan 23 jam atau 25 jam memutuskan rentetan kalendar yang sah

→ bandingkan tarikh tempatan, kerana kontraknya ialah kedekatan kalendar.

• Mengelompokkan mengikut tarikh anjakan sahaja → pengguna dengan kunci terbitan yang sama bergabung bersama → **kelompokkan mengikut

kedua-dua user_id dan island_key.**

• Mengambil satu baris dengan ROW_NUMBER() → rentetan terpanjang yang terikat dibuang → **bandingkan setiap pulau

dengan maksimum bagi setiap pengguna.**

• Menapis selang pelaporan tanpa peraturan sempadan → rentetan yang melintasi tarikh mula akan

dipotong dan mungkin tersalah label → takrifkan sama ada keputusan adalah setempat julat (range-local) atau pulau lengkap.

• Menggunakan LAG() tanpa mengendalikan baris pertama → pulau pertama kehilangan sempadan → **anggap baris

sebelumnya yang bernilai null sebagai permulaan kumpulan.**

• Hanya memetik Big-O → limpahan susunan atau anggaran kardinaliti yang lemah kekal tidak kelihatan → **periksa

kiraan perantaraan dan EXPLAIN (ANALYZE, BUFFERS).**

• Mengimbas sejarah mentah untuk setiap penyegaran papan pemuka → penukaran dan penyahduplikasian berulang mendominasi

kos → kekalkan butiran pengguna-hari yang unik apabila beban kerja mewajarkannya.

Soalan Susulan dan Maklum Balas

Susulan 1: Bagaimanakah anda mengembalikan rentetan terpanjang yang paling terkini sahaja?

Kekalkan pembinaan pulau yang sama. Selepas mengira rentetan, susun kedudukannya bagi setiap pengguna mengikut streak_days DESC, kemudian streak_end DESC, dan akhirnya streak_start DESC sebagai pemutus seri deterministik yang terakhir. Kembalikan kedudukan pertama. Nyatakan bahawa ini mengubah kontrak output: panjang yang sama tidak lagi semuanya dikekalkan.

Susulan 2: Apakah yang berubah jika sesi tamat selepas 30 minit tidak aktif?

Penolakan kalendar tidak lagi memodelkan kesinambungan. Susun peristiwa mengikut cap masa, gunakan LAG(login_at) bagi setiap pengguna, tandakan baris pertama atau sebarang jurang yang melebihi 30 minit sebagai sesi baharu, dan kira SUM terkumpul bagi bendera tersebut dengan bingkai ROWS UNBOUNDED PRECEDING yang eksplisit. Agregatkan mengikut pengguna dan ID sesi yang dijana.

Susulan 3: Bagaimanakah anda mengendalikan zon masa setiap pengguna sendiri?

Gabungkan (join) peristiwa kepada nilai zon masa pengguna berversi yang sah untuk masa peristiwa tersebut, kemudian tukar sebelum mengambil tarikh. Satu tetapan profil semasa boleh menulis semula hari sejarah selepas pengguna berpindah. Jelaskan sama ada produk mahukan aktiviti sejarah dibekukan di bawah zon semasa ketika itu atau dikira semula di bawah zon semasa pengguna; kedua-duanya adalah metrik yang berbeza.

Susulan 4: Bagaimanakah anda menyoal hanya 90 hari tempatan yang terakhir?

Takrifkan sama ada rentetan boleh bermula sebelum tetingkap. Untuk keputusan khusus tetingkap, terbitkan dua waktu UTC yang sepadan dengan tengah malam tempatan pada permulaan dan penamat dalam zon yang dinamakan, tapis login_at mengikut sempadan tersebut, kemudian normalkan. Untuk pulau lengkap, sertakan baris harian sebelumnya yang mencukupi untuk mencari jurang sebenar yang pertama; pemotongan 90 hari secara membuta tuli tidak dapat membuktikan permulaan yang sebenar.

Susulan 5: Bagaimanakah anda menjadikan ini cekap untuk papan pemuka harian?

Selenggara user_login_days(user_id, login_day) dengan kunci unik dan upsert idempoten. Kemas kini ia daripada saluran paip peristiwa menggunakan peraturan zon masa yang dipersetujui. Kira semula hanya pengguna yang baris hariannya berubah, atau bina semula secara berkala daripada tetingkap bertindih untuk menyerap peristiwa yang lewat tiba. Selaraskan kiraan baris harian dengan sumber mentah sebelum menerbitkannya.

Susulan 6: Ujian manakah yang anda perlukan sebelum penghantaran ke persekitaran pengeluaran?

Gunakan lekapan berasaskan jadual (table-driven fixtures) untuk pendua, pengguna satu baris, jurang dalaman, maksimum terikat, peristiwa tengah malam tempatan, permulaan dan penamat waktu jimat siang, peristiwa lewat tiba, dan peristiwa melintasi sempadan pelaporan. Pastikan bahawa baris harian adalah unik, setiap pulau memenuhi streak_days = streak_end - streak_start + 1, dan setiap rentetan yang dikembalikan sama dengan maksimum penggunanya. Bandingkan jadual harian bertambah dengan pengiraan semula peristiwa mentah pada pengguna yang disampel, kemudian periksa pelan kueri dan I/O sementara pada kardinaliti yang menyerupai pengeluaran.