[
https://issues.apache.org/jira/browse/NIFI-16467?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Jakub Augustyniak updated NIFI-16467:
-------------------------------------
Description:
When a record reader infers the schema of JSON whose nested records have the
same shape at many levels but differ at the bottom, inference takes
exponentially longer with depth. The time roughly doubles with each nesting
level. Rich text documents with deeply nested lists produce exactly this
structure, for example:
{code:java}
{"type":"doc","content":[
{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph"},
{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph"},
{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[
{"type":"text","text":"a"}
]}]}]}
]}]}
]}]},
{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph"},
{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[
{"type":"text","text":"a"}
]}]}]}
]}]}
]}{code}
The document holds two sibling lists of different depth. Every level has the
same shape: a {{listItem}} holding an empty {{paragraph}} and a nested
{{{}bulletList{}}}. Where the shorter list ends, its {{listItem}} holds a
{{paragraph}} with {{{}text{}}}, while the longer one still holds a nested
{{{}bulletList{}}}. Neither record is wider than the other, and that is only
found after comparing every level above it. The example nests the lists 3 and 2
levels deep. Each further level wraps the innermost {{listItem}} in another
{code:java}
{"type":"listItem","content":[{"type":"paragraph"},{"type":"bulletList","content":[...]}]}{code}
Each list level is two record levels ({{{}bulletList{}}} and {{{}listItem{}}}),
so time grows about 4x per list level: 0.2 s for lists 9 and 8 levels deep, 2.5
s for 11 and 10, and no result after 30 s for 13 and 12 or more. Two lists of
the same depth infer in milliseconds.
The example above is too shallow to stall. The attached
NIFI-16467-nested-lists.json has the same structure with lists 18 and 15 levels
deep, like the original document. Main gave no result after 60 s; with the fix
it takes 24 ms.
Observed with JsonTreeReader using Infer Schema, on a 1.7 MB array of 100
records, two of which contain a document with sibling lists nested up to 18
levels deep:
* Inference did not finish within 5 minutes. In a real deployment it ran for
hours without completing.
* Either of the two deep documents alone is enough: it still didn't finish
after 60 s.
* With those documents removed, inference on the same input takes 26 ms.
* The processor thread can't be stopped, because inference doesn't respond to
interruption, and the same FlowFile is picked up again after every restart.
That blocks the queue indefinitely.
was:
When a record reader infers the schema of JSON whose nested records have the
same shape at many levels but differ at the bottom, inference takes
exponentially longer with depth. The time roughly doubles with each nesting
level. Rich text documents with deeply nested lists produce exactly this
structure, for example:
{code:java}
{"type":"doc","content":[
{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph"},
{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph"},
{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[
{"type":"text","text":"a"}
]}]}]}
]}]}
]}]},
{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph"},
{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[
{"type":"text","text":"a"}
]}]}]}
]}]}
]}{code}
The document holds two sibling lists of different depth. Every level has the
same shape: a {{listItem}} holding an empty {{paragraph}} and a nested
{{{}bulletList{}}}. Where the shorter list ends, its {{listItem}} holds a
{{paragraph}} with {{{}text{}}}, while the longer one still holds a nested
{{{}bulletList{}}}. Neither record is wider than the other, and that is only
found after comparing every level above it. The example nests the lists 3 and 2
levels deep. Each further level wraps the innermost {{listItem}} in another
{code:java}
{"type":"listItem","content":[{"type":"paragraph"},{"type":"bulletList","content":[...]}]}{code}
Each list level is two record levels ({{{}bulletList{}}} and {{{}listItem{}}}),
so time grows about 4x per list level: 0.2 s for lists 9 and 8 levels deep, 2.5
s for 11 and 10, and no result after 30 s for 13 and 12 or more. Two lists of
the same depth infer in milliseconds.
Observed with JsonTreeReader using Infer Schema, on a 1.7 MB array of 100
records, two of which contain a document with sibling lists nested up to 18
levels deep:
* Inference did not finish within 5 minutes. In a real deployment it ran for
hours without completing.
* Either of the two deep documents alone is enough: it still didn't finish
after 60 s.
* With those documents removed, inference on the same input takes 26 ms.
* The processor thread can't be stopped, because inference doesn't respond to
interruption, and the same FlowFile is picked up again after every restart.
That blocks the queue indefinitely.
> Schema inference hangs on deeply nested JSON records
> ----------------------------------------------------
>
> Key: NIFI-16467
> URL: https://issues.apache.org/jira/browse/NIFI-16467
> Project: Apache NiFi
> Issue Type: Bug
> Reporter: Jakub Augustyniak
> Assignee: Jakub Augustyniak
> Priority: Major
> Attachments: NIFI-16467-nested-lists.json
>
> Time Spent: 1h 40m
> Remaining Estimate: 0h
>
> When a record reader infers the schema of JSON whose nested records have the
> same shape at many levels but differ at the bottom, inference takes
> exponentially longer with depth. The time roughly doubles with each nesting
> level. Rich text documents with deeply nested lists produce exactly this
> structure, for example:
> {code:java}
> {"type":"doc","content":[
>
> {"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph"},
>
> {"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph"},
>
> {"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[
> {"type":"text","text":"a"}
> ]}]}]}
> ]}]}
> ]}]},
>
> {"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph"},
>
> {"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[
> {"type":"text","text":"a"}
> ]}]}]}
> ]}]}
> ]}{code}
> The document holds two sibling lists of different depth. Every level has the
> same shape: a {{listItem}} holding an empty {{paragraph}} and a nested
> {{{}bulletList{}}}. Where the shorter list ends, its {{listItem}} holds a
> {{paragraph}} with {{{}text{}}}, while the longer one still holds a nested
> {{{}bulletList{}}}. Neither record is wider than the other, and that is only
> found after comparing every level above it. The example nests the lists 3 and
> 2 levels deep. Each further level wraps the innermost {{listItem}} in another
> {code:java}
> {"type":"listItem","content":[{"type":"paragraph"},{"type":"bulletList","content":[...]}]}{code}
> Each list level is two record levels ({{{}bulletList{}}} and
> {{{}listItem{}}}), so time grows about 4x per list level: 0.2 s for lists 9
> and 8 levels deep, 2.5 s for 11 and 10, and no result after 30 s for 13 and
> 12 or more. Two lists of the same depth infer in milliseconds.
> The example above is too shallow to stall. The attached
> NIFI-16467-nested-lists.json has the same structure with lists 18 and 15
> levels deep, like the original document. Main gave no result after 60 s; with
> the fix it takes 24 ms.
> Observed with JsonTreeReader using Infer Schema, on a 1.7 MB array of 100
> records, two of which contain a document with sibling lists nested up to 18
> levels deep:
> * Inference did not finish within 5 minutes. In a real deployment it ran for
> hours without completing.
> * Either of the two deep documents alone is enough: it still didn't finish
> after 60 s.
> * With those documents removed, inference on the same input takes 26 ms.
> * The processor thread can't be stopped, because inference doesn't respond
> to interruption, and the same FlowFile is picked up again after every
> restart. That blocks the queue indefinitely.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
