基于BigQuery分析百亿级登录日志的认证路径查询求助

Alright, let's tackle this recursive authentication path problem you're stuck on—10 billion rows is a massive dataset, so we need a solution that's both correct and efficient to avoid wasting resources. From your sample data, I get that we need to map all sequential login paths for each user (like U12’s C04 → C11 → C14 chain). Recursion is the right call here, but we’ll need to optimize for scale.

Step-by-Step Solution #

1. Preprocess Logs for Chronological Order #

First, we’ll sort each user’s logs by time and assign a sequence number. This ensures we build paths in the correct order and avoid accidental cycles (like looping between two computers).

2. Recursive CTE to Build Paths #

BigQuery supports recursive CTEs, which we’ll use to incrementally build paths: start with individual login entries, then recursively extend paths where a target computer from one entry becomes the source computer of a later entry for the same user.

Here’s the full query tailored to your schema:

WITH sorted_logs AS (
  SELECT
    user_id,
    source_computer,
    target_computer,
    event_time,
    -- Assign a unique sequence number to each user's logs ordered by time
    ROW_NUMBER() OVER(PARTITION BY user_id ORDER BY event_time) AS log_seq
  FROM `your-project.your-dataset.login_logs`
  -- Optional: Deduplicate identical log entries to cut down on redundant work
  DISTINCT user_id, source_computer, target_computer, event_time
),
recursive_paths AS (
  -- Base case: Each single login is a path of length 1
  SELECT
    user_id,
    source_computer AS path_start,
    target_computer AS path_end,
    ARRAY[source_computer, target_computer] AS full_path,
    event_time AS last_event_time,
    log_seq,
    1 AS path_length
  FROM sorted_logs

  UNION ALL

  -- Recursive step: Extend paths by linking to subsequent logins
  SELECT
    rp.user_id,
    rp.path_start,
    sl.target_computer AS path_end,
    ARRAY_CONCAT(rp.full_path, [sl.target_computer]) AS full_path,
    sl.event_time AS last_event_time,
    sl.log_seq,
    rp.path_length + 1 AS path_length
  FROM recursive_paths rp
  INNER JOIN sorted_logs sl
    ON rp.user_id = sl.user_id
    AND rp.path_end = sl.source_computer
    AND sl.log_seq > rp.log_seq  -- Ensure we only use later log entries to avoid cycles
)
-- Final output: All possible paths, adjust filters as needed
SELECT
  user_id,
  path_start,
  path_end,
  path_length,
  full_path,
  last_event_time
FROM recursive_paths
-- Optional: Filter out single-step paths if you only care about multi-hop chains
-- WHERE path_length >= 2
ORDER BY user_id, path_length, last_event_time
-- Optional: Increase recursion depth if you need longer paths (max allowed is 1000)
OPTIONS(MAX_RECURSION = 100);

Critical Optimizations for 1B Rows #

1. Partition & Cluster Your Table: If your login_logs table is partitioned by event_time and clustered by user_id, BigQuery will only scan relevant user subsets during recursion—this cuts down query time drastically.
2. Deduplicate Early: Removing duplicate log entries upfront (as shown in sorted_logs) avoids redundant processing of identical paths.
3. Limit Recursion Depth: Use OPTIONS(MAX_RECURSION = N) to cap path length if you don’t need extremely long chains (the default is 100).
4. Filter Early: Add a WHERE path_length >= X clause in the final SELECT to reduce the size of your output if you only care about paths of a certain length.

Edge Case Notes #

• Cycles: The sl.log_seq > rp.log_seq condition prevents infinite loops (like C01 → C02 → C01) since log sequences are strictly increasing.
• Branching Paths: If a user has multiple logins from the same target computer at different times, the query will capture all possible branching paths automatically.

内容的提问来源于stack exchange，提问作者Edo Lopez