Forberedelse til SQL-interview · Lektion

Undgåelse af uendelig rekursion

Cyklusdetektion, dybdegrænser og den rekursionsbeskyttelse, som alle interviewere leder efter

Lektion 4 af 413 trin

Undgåelse af uendelig rekursion er en gratis Forberedelse til SQL-interview-lektion på CoddyKit. Dette er lektion 4 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i Forberedelse til SQL-interview, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Forberedelse til SQL-interview-kurset indeholder 4 lektioner i alt.

Spørgsmålet bag spørgsmålet

Efter at du har skrevet en rekursiv CTE, spørger en skarp interviewer: "Hvad sker der, hvis dataene indeholder en cyklus?" Det undersøger, om du forstår, at rekursion kan køre for evigt — og om du ved, hvordan du beskytter dig mod det.

En cyklus opstår, når hierarkiet løber tilbage i sig selv: A rapporterer til B, og B rapporterer til A. Den naive rekursive del vil skifte mellem dem uden ende.

Sådan opstår en cyklus

Træer skal være acykliske, men virkelige data er rodede. En forkert opdatering kan gøre en medarbejder til sin egen (indirekte) leder. En graf — som "brugere, der følger brugere" — er cyklisk af natur.

Når den rekursive del møder et knudepunkt, som den allerede har besøgt, producerer den knudepunktet igen, hvilket på ny udløser dets underordnede knudepunkter, og løkken tømmes aldrig. Rekursion stopper kun, når et trin returnerer ingen rækker; en cyklus sikrer, at der altid returneres rækker.

Sikkerhedsforanstaltning 1: En dybdegrænse

Det enkleste sikkerhedsnet er en dybdetæller med en grænse i den rekursive del. Selv hvis der findes en cyklus, stopper rekursionen ved grænsen.

Det er et groft værktøj — det begrænser også legitimt dybe træer — men det er hurtigt og velegnet til interviews.

WITH RECURSIVE org AS (
    SELECT id, name, manager_id, 1 AS depth
    FROM employees WHERE manager_id IS NULL
    UNION ALL
    SELECT e.id, e.name, e.manager_id, o.depth + 1
    FROM employees e JOIN org o ON e.manager_id = o.id
    WHERE o.depth < 50
)
SELECT * FROM org;

Sikkerhedsforanstaltning 2: En besøgt sti

En præcis sikkerhedsforanstaltning holder styr på stien over besøgte knudepunkter og nægter at gå ind i et knudepunkt, der allerede findes på stien. Saml id'er i en streng eller et array, og kontrollér, om id'et allerede findes, før du fortsætter rekursionen.

Det stopper cyklusser præcist, samtidig med at legitimt dybe træer stadig kan have en vilkårlig dybde.

WITH RECURSIVE org AS (
    SELECT id, name, manager_id,
           CAST(',' || id || ',' AS VARCHAR(2000)) AS path
    FROM employees WHERE manager_id IS NULL
    UNION ALL
    SELECT e.id, e.name, e.manager_id,
           o.path || e.id || ','
    FROM employees e JOIN org o ON e.manager_id = o.id
    WHERE o.path NOT LIKE '%,' || e.id || ',%'
)
SELECT id, name, path FROM org;

Derfor virker stitjekket

Betingelsen path NOT LIKE '%,' || e.id || ',%' betyder "følg kun denne kant, hvis det underordnede id ikke allerede findes på stien." Kommaerne fungerer som afgrænsere, så id 1 ikke fejlagtigt matches inde i id 15.

Hvis en cyklus ville besøge et knudepunkt igen, filtrerer WHERE rækken fra, den rekursive del returnerer til sidst ingen rækker, og rekursionen afsluttes korrekt.

Sikkerhedsforanstaltning 3: Den indbyggede CYCLE-klausul

Moderne Postgres (14+) og SQL-standarden har en indbygget CYCLE-klausul, der automatiserer stitjekket og markerer cyklusser for dig. Det er det reneste svar, når databasemotoren understøtter det.

WITH RECURSIVE org AS (
    SELECT id, name, manager_id FROM employees WHERE manager_id IS NULL
    UNION ALL
    SELECT e.id, e.name, e.manager_id
    FROM employees e JOIN org o ON e.manager_id = o.id
)
CYCLE id SET is_cycle USING cycle_path
SELECT id, name, is_cycle FROM org;

SQL Servers MAXRECURSION

SQL Server håndhæver som standard en grænse på 100 rekursionsniveauer. Hvis en cyklus eller et dybt træ overskrider den, giver forespørgslen en fejl i stedet for at køre for evigt — en indbygget sikkerhedsventil.

Du kan hæve eller fjerne grænsen med OPTION (MAXRECURSION n), hvor 0 betyder ubegrænset. Men hvis du fjerner grænsen uden en stisikkerhedsforanstaltning, genindfører du risikoen for en uendelig løkke i cykliske data.

-- Cap recursion at 200 levels in SQL Server
SELECT * FROM org
OPTION (MAXRECURSION 200);

At opdage kontra at forhindre cyklusser

Interviewere kan skelne mellem to mål:

Forhindr — spring den cykliske kant over uden at vise det, så forespørgslen færdiggøres (den sti-kontrollerende WHERE-betingelse).
Opdag og rapportér — vis, hvilke rækker der indgår i en cyklus, så et data team kan rette de fejlbehæftede data (flaget is_cycle i CYCLE-klausulen).

At kende begge mål og vide, hvornår hvert af dem er passende, er en forskel på seniorniveau.

Overvejelser om ydeevne

Rekursion kan være krævende, selv uden cyklusser. Tip, som interviewere gerne hører:

Indeksér forbindelseskolonnen, f.eks. manager_id, så forbindelsen i hver iteration går hurtigt.
Filtrér tidligt i ankerdelen, så du kun starter med det undertræ, du har brug for, og ikke hele tabellen.
Undgå SELECT * — medtag kun de kolonner, rekursionen kræver, samt din depth/path.

En sikker skabelon

Kombinér sikkerhedsforanstaltningerne i en skabelon, som du kan genskabe under pres: en dybdekolonne som ekstra sikkerhedsnet og et stitjek som den præcise foranstaltning. Selv hvis den ene er overflødig for rene data, viser det grundighed at medtage begge.

WITH RECURSIVE walk AS (
    SELECT id, parent_id, 1 AS depth,
           CAST(',' || id || ',' AS VARCHAR(4000)) AS path
    FROM nodes WHERE parent_id IS NULL
    UNION ALL
    SELECT n.id, n.parent_id, w.depth + 1,
           w.path || n.id || ','
    FROM nodes n JOIN walk w ON n.parent_id = w.id
    WHERE w.depth < 100
      AND w.path NOT LIKE '%,' || n.id || ',%'
)
SELECT id, depth FROM walk;

Typiske faldgruber i interviews

De sidste fælder, du skal undgå:

Fjern ikke MAXRECURSION i SQL Server uden en anden sikkerhedsforanstaltning — det genåbner risikoen for en uendelig løkke.
En strengkolonne til stien, der er deklareret for kort, så den afkortes, og sikkerhedsforanstaltningen dermed bryder sammen uden tydelige tegn.
Sammenligning af id'er uden kommaafgrænsere, så id 1 fejlagtigt matches inde i id 21.
Antag ikke, at dataene er acykliske, bare fordi de "burde" være det — spørg altid.

Hurtigt tjek

Vælg den sikkerhedsforanstaltning, der stopper cyklusser præcist uden at begrænse legitim dybde.

Besvar den i den interaktive lektion

Opsummering

Alle svar med rekursive CTE'er bør forholde sig til sikkerhed:

Cyklusser får den rekursive del til aldrig at returnere tomt, så rekursionen aldrig stopper.
Dybdegrænse = hurtigt sikkerhedsnet; tjek af besøgt sti = præcis forebyggelse af cyklusser; CYCLE-klausul = indbygget registrering i moderne databasemotorer.
SQL Servers MAXRECURSION 100 er en indbygget sikkerhedsventil — fjern den ikke uden en anden sikkerhedsforanstaltning.
Indeksér forbindelseskolonnen, og vælg et snævert startpunkt for at opnå god ydeevne.

Du kan nu skrive, gennemløbe, generere og sikre rekursive CTE'er fra start til slut.

Gratis at komme i gang

Lær SQL med en AI-underviser — gratis

Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.

Kurser: 30
Lektioner: 120

Start gratis Se hele kurset

Ofte stillede spørgsmål

Er lektionen “Undgåelse af uendelig rekursion” gratis?

Ja — hele teksten til “Undgåelse af uendelig rekursion” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af Forberedelse til SQL-interview-kurset, skal du opgradere til CoddyKit PRO. Forberedelse til SQL-interview-kurset indeholder 4 lektioner i alt.

Hvad lærer jeg i “Undgåelse af uendelig rekursion”?

Cyklusdetektion, dybdegrænser og den rekursionsbeskyttelse, som alle interviewere leder efter Du øver dig i Forberedelse til SQL-interview med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.

Skal jeg have erfaring for at begynde på Forberedelse til SQL-interview?

Der kræves ingen tidligere erfaring. Forberedelse til SQL-interview på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 4 af 4.

Hvor lang tid tager lektionen “Undgåelse af uendelig rekursion”?

De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.

Kan jeg skrive og køre kode i denne Forberedelse til SQL-interview-lektion?

Ja. Alle Forberedelse til SQL-interview-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.

Alle lektioner i dette kursus

← Tilbage til Forberedelse til SQL-interview