Speculative Distributed CSV Data Parsing for Big Data Analytics
Ge, Chang
Li, Yinan
Eilebrecht, Eric
Chandramouli, Badrish
Kossmann, Donald
There has been a recent flurry of interest in providing query capability on raw data in today's big data systems. These raw data must be parsed before processing or use in analytics. Thus, a fundamental challenge in distributed big data systems is that of efficient parallel parsing of raw data. The difficulties come from the inherent ambiguity while independently parsing chunks of raw data without knowing the context of these chunks. Specifically, it can be difficult to find the beginnings and ends of fields and records in these chunks of raw data. To parallelize parsing, this paper proposes a speculation-based approach for the CSV format, arguably the most commonly used raw data format. Due to the syntactic and statistical properties of the format, speculative parsing rarely fails and therefore parsing is efficiently parallelized in a distributed setting. Our speculative approach is also robust, meaning that it can reliably detect syntax errors in CSV data. We experimentally evaluate the speculative, distributed parsing approach in Apache Spark using more than 11,000 real-world datasets, and show that our parser produces significant performance benefits over existing methods.
 I'm Chang Ge, I'm a student from University Waterloo. Today I'm going to talk about speculative distributist SV data parsing for big data analytics. This work was done during my internship at Microsoft research with my great mentor E9D and collaborators Eric Alebridge, Badges Treadomoli and Donald Cosman. Organizations have been generating a lot of data. It's very expensive both in terms of a computation course and human efforts to cook and bannerize all their data. In the traditional world, only a small amount of data was cooked and loaded into the database systems in the binary format. And the majority of the data stays uncooked, untouched and stored in the raw data format such as JSON and CSV which is usually generated by the data source. In recent years, the cloud and big data systems reduce the cost to process raw data. For example, systems like Spark supports queries directly over CSV and JSON format. Although uncooked, this raw data now can be queried on demand. In the raw data, all the data is stored in plain text format and must be passed to get the structure and a binary value before processing. In database systems, parsing is an important step during loading and it usually occurs one time cost. However, when querying on demand, parsing occurs every time when the data is queried and hence is on the critical path. Even more, big data systems work in a cluster of machines in a distributed way. As a result, parsing must be distributed too. Otherwise, the benefit of parallelizing other tasks will be diminished. This work, we focus on CSV, which is the most popular tabular data format and is widely used in data analytics, exchange, motion learning. Distributed CSV parsing has many use cases. For example, in parallel query processing, systems such as Spark, query services such as Google BigQuery and even software libraries such as Pandas, queries are executed in parallel by multiple workers or cores. So, given a CSV file, each of the workers, each of the nodes only access a piece of it and the parsing must be distributed in order to fully utilize the parallelism. For another example, in distributed stories such as SDFS, a CSV file can be trunked into multiple partitions. When the data is retrieved, it's often desirable not to return all the data, but just a subset of data that are relevant. So in production systems like Azure Quick Query and AWS S3 Threat, they have already supported pushing down the queries to the stories layer and the storage layer tests the predicates and returns only the subset of data. So in this setup, each of the trunks must be parsed before applying the predicates. Okay, now let's look at the problem. Suppose we have a CSV file, it looks like this. Sorry, well, it starts with our unquoted string div and this comma is a field delimiter and the next field is a quoted comma and the next field is a one, two, three, four and this new line is a record delimiter to distinguish two different records. Okay, and based by the specification, a field can be either quoted or unquoted and it can contain almost the arbitrary chargers in the field. When we store this file in the distributed storage, the storage has no idea what the data looks like and how to align the boundaries. So in fact, the storage just trunked the CSV into fixed size trunks. Okay, suppose we have split this CSV into three trunks. Okay, and now consider you as a worker and you are assigned with this trunk number two. Can you tell me how to pass this data? Well, you might consider, well, this E belongs to the boundary partial records and this comma is a field delimiter and the next field is a quoted comma followed by another field 17 and this new line is a record delimiter. Alternatively, you can interpret this E and a comma together as a partial field that's inside of this quote and the second comma as a field delimiter and the next field is this long string that is inside of this quote and the second new line is the record delimiter. Oh, sorry, record, sorry, this is a field delimiter and this is a record delimiter. Okay, based on the specification, both alternatives are possible and you can imagine the query's final result can be dramatically different given different interpretations. So the challenge related to the trigger parsing is it's fundamentally impossible to disambigot without the context. Okay, even if it's impossible, we should never give up. Okay, fortunately, we have found some opportunities. The first one is we observe that most of the trunks are not ambiguous. For example, for this set of trunks, most of them are not ambiguous. So the question is, how can we quickly determine whether a trunk is ambiguous or not? Okay, for the second opportunity, even the trunks are ambiguous, we can still guess and hopefully we can guess it correct. Consider these same, those two interpretations. Take a second look and can you tell me what do you think which one is more likely correct? Well, it turns out the first one is more likely because if the second one was, then it would be too coincidental that this quoted string satisfied the CSV specification in the other interpretation. So the question is, how can we speculate for an ambiguous trunk? Okay, before I answer those two questions, let me first show you the overview of our solution. So each trunk is assigned to a worker and the worker individually and independently tests whether the trunk is ambiguous or not. If yes, then speculate. If not, or after speculation, we find the position of the first starting point, the position of the first record delimiter to identify the first new record in this trunk. After that, the starting position is passed to a regular existing CSV parser and the parser passes the trunk using the start position as if it's a complete CSV file. It repents the parsing result and the start position and the end position of the last record in the trunk, which could be somewhere in the next third trunk. So this information is sent to the master for validation. We can prove that the speculation is successful if all the start and are connected end to end. If not successful, then mis-prediction happens and then we redo. So we revert to a two-part support. Basically in the first part, you sequentially scan all the chunks to get the context and then you use the context in the second part to parsing. But as I will show you later, this prediction in the real world is really rare and it's almost never happened. And also I would like to highlight is our approach is robust to syntax error, the EU-informed CSV data, which is quite common than exception in the real world. I will skip this and let's start with question one. How can we quickly determine the ambiguity? In essence, parsing is a finite state machine problem. Normally, you can start with the beginning of the file and run a finite state machine based on the current state and the next state, and the next chart you'll see. So in the finite state machine for CSV, we can have five states, let's say the record start, field start, on-courted field, courted field, and on-court ends. And we can classify the charts into four big categories, quote, comma, new line, and the rest that belong to the other. Okay, for example, if your current state is a record start and your next chart is a quote, then your new state will be translated into the courted field. You know you are now inside the courted field. Okay, so this is quite straightforward, but the problem is in distributed setting, we don't know what the beginning state is and that's exactly what we want to know. So we take this idea of finite state machine and augment this finite state machine to this approach. So since we don't know the beginning state, then let's assume all the states are possible and we run multiple state machines. So we can prove that if the trunk is ambiguous, then there will be more than one valid state after the first new line. And if the trunk is ambiguous, then there is only one valid state. So the drawback of this approach is not that efficient because we need to run multiple finite state machines and even running one state machine is super slow compared to the speed of a parting. Okay, can we do it better? Well, we observe a simple and super fast method to do this. So it's summarized like this. So if a trunk is ambiguous, if and only if it contains a quote or other quote pattern strings. So quote is the chart, quote, other is a quote, not a quote comma and a new line. Okay, so we can basically prove like this. So consider one direction. If the trunk contains these patterns, then the trunk is ambiguous. We can prove using the finite state table and the key idea is no matter what the beginning state is, after you see a pattern, all the possible states now converge to only one possible state. Okay, and the other direction, we also formally prove the other direction, which is that if the trunk is ambiguous, then the trunk must contain one of the patterns. Okay, then now our process is straight forward. So we want to look for those patterns in the truck. So we can use the same D instructions to quickly detect those patterns. Okay, if a trunk does not contain such a pattern, then we speculate how. Okay, take another local of one of the possible interpretation. Okay, the position in the red rectangles are all the positions that make this trunk ambiguous. In another word, if any of these charts is other, then this trunk becomes unambiguous. How likely it is? Therefore, we can compute the likelihood of the random string make that trunk ambiguous and model this as a conditional probability problem. Okay, and we will speculate and choose the spec interpretation with the highest probability. We also integrate our solution into Spark using only Spark primitives. So this implies that our solution also includes the fault tolerance characters. Okay, we did a lot of evaluations using clusters and on our Spark integration. And one thing I would like to highlight during our evaluation is at the time of experiment, we downloaded all the CSV files from the Kaggle repository. And those are more than 11,000 CSV files. The size ranges from three bytes to 11 gigabytes. And here are just some examples. Okay, the first example is we want to compare the overall speed up over the two parts of course. As I briefly mentioned when describing this system, the first parts determine the context and then the second parts take that context and do the parting. So the x-axis is a file size and the y-axis measures the speed up. And each of the circles represent a data set. On the left hand side, it shows the performance using the default CSV parser in Spark. So when the data size is small, the parting time is short and it's portabated by Spark mechanisms such as job scheduling and memory management. And when the file size increases, as you can see, the speed up is about between one to 1.5x. On your right hand side, we show the performance using a MISOM parser, which is the state of art parser. And as you can see, the overall speed up is between 1.5x to up to 2.3x. So this shows that the speculative parsing is more beneficial with a more than faster parser, which is the trend. The second example is we want to consider the overhead compared to an ideal approach. So the ideal approach is we assume there's an oracle that can magically determine the context with no cost. So this is simulated by disabling the multi-line option in Spark. So as you can see, the comparison is almost one here, and it means that the speculative parsing has a measurable overhead compared to an even ideal approach. The next example I would like to show is about the MIS prediction ratio. So in this case, we trunk all the 11,000 CSV data files to different trunk size, and the trunk size ranges from 16 bytes to one megabytes. And we will speculate using this trunk size. And when the trunk size is small, the MIS prediction ratio is high, as you can see, because some long-stream values are larger than the trunks, and this small trunks usually has limited information and can be misleading. And when you increase the trunk size, then you'll see a quick drop of this MIS prediction ratio. And here, because there's only one MIS prediction trunks, and when you increase the trunk size, the number of trunks goes small, then the ratio goes up a little bit. But still, as you can see, the speculation feels less than once in one million trunks. And in practice, the trunk size usually ranges from a dozen megabytes, far larger than the record size. So this area really happens. To summarize, in this work, we designed a speculative distributed CSV data parsing solution that has less than once in 10 million failure rates. It has a noticeable overhead compared to an average distributed parsing solution, and it's a rule-boss to syntax error, and it can compose with any existing CSV parser. So that concludes my talk, and I'm happy to take questions. Thank you. Thank you.
 I'm Chang Ge, I'm a student from University Waterloo.  Today I'm going to talk about  speculative distributist SV data parsing  for big data analytics.  This work was done during my internship  at Microsoft research with my great mentor E9D  and collaborators Eric Alebridge,  Badges Treadomoli and Donald Cosman.  Organizations have been generating a lot of data.  It's very expensive both in terms of a computation course  and human efforts to cook and bannerize all their data.  In the traditional world,  only a small amount of data was cooked  and loaded into the database systems in the binary format.  And the majority of the data stays uncooked, untouched  and stored in the raw data format such as JSON and CSV  which is usually generated by the data source.  In recent years, the cloud and big data systems  reduce the cost to process raw data.  For example, systems like Spark  supports queries directly over CSV and JSON format.  Although uncooked, this raw data now can be queried on demand.  In the raw data, all the data is stored in plain text format  and must be passed to get the structure  and a binary value before processing.  In database systems,  parsing is an important step during loading  and it usually occurs one time cost.  However, when querying on demand,  parsing occurs every time when the data is queried  and hence is on the critical path.  Even more, big data systems work in a cluster of machines  in a distributed way.  As a result, parsing must be distributed too.  Otherwise, the benefit of parallelizing other tasks  will be diminished.  This work, we focus on CSV,  which is the most popular tabular data format  and is widely used in data analytics,  exchange, motion learning.  Distributed CSV parsing has many use cases.  For example, in parallel query processing,  systems such as Spark, query services such as Google BigQuery  and even software libraries such as Pandas,  queries are executed in parallel  by multiple workers or cores.  So, given a CSV file, each of the workers,  each of the nodes only access a piece of it  and the parsing must be distributed  in order to fully utilize the parallelism.  For another example, in distributed stories such as SDFS,  a CSV file can be trunked into multiple partitions.  When the data is retrieved,  it's often desirable not to return all the data,  but just a subset of data that are relevant.  So in production systems like Azure Quick Query  and AWS S3 Threat, they have already supported  pushing down the queries to the stories layer  and the storage layer tests the predicates  and returns only the subset of data.  So in this setup, each of the trunks must be parsed  before applying the predicates.  Okay, now let's look at the problem.  Suppose we have a CSV file, it looks like this.  Sorry, well, it starts with our unquoted string div  and this comma is a field delimiter  and the next field is a quoted comma  and the next field is a one, two, three, four  and this new line is a record delimiter  to distinguish two different records.  Okay, and based by the specification,  a field can be either quoted or unquoted  and it can contain almost the arbitrary chargers  in the field.  When we store this file in the distributed storage,  the storage has no idea what the data looks like  and how to align the boundaries.  So in fact, the storage just trunked the CSV  into fixed size trunks.  Okay, suppose we have split this CSV into three trunks.  Okay, and now consider you as a worker  and you are assigned with this trunk number two.  Can you tell me how to pass this data?  Well, you might consider, well, this E  belongs to the boundary partial records  and this comma is a field delimiter  and the next field is a quoted comma  followed by another field 17  and this new line is a record delimiter.  Alternatively, you can interpret this E  and a comma together as a partial field  that's inside of this quote  and the second comma as a field delimiter  and the next field is this long string  that is inside of this quote  and the second new line is the record delimiter.  Oh, sorry, record, sorry, this is a field delimiter  and this is a record delimiter.  Okay, based on the specification,  both alternatives are possible  and you can imagine the query's final result  can be dramatically different  given different interpretations.  So the challenge related to the trigger parsing is  it's fundamentally impossible to disambigot  without the context.  Okay, even if it's impossible,  we should never give up.  Okay, fortunately, we have found some opportunities.  The first one is we observe that  most of the trunks are not ambiguous.  For example, for this set of trunks,  most of them are not ambiguous.  So the question is, how can we quickly determine  whether a trunk is ambiguous or not?  Okay, for the second opportunity,  even the trunks are ambiguous, we can still guess  and hopefully we can guess it correct.  Consider these same, those two interpretations.  Take a second look and can you tell me  what do you think which one is more likely correct?  Well, it turns out the first one is more likely  because if the second one was,  then it would be too coincidental  that this quoted string satisfied the CSV specification  in the other interpretation.  So the question is, how can we speculate  for an ambiguous trunk?  Okay, before I answer those two questions,  let me first show you the overview of our solution.  So each trunk is assigned to a worker  and the worker individually and independently  tests whether the trunk is ambiguous or not.  If yes, then speculate.  If not, or after speculation,  we find the position of the first starting point,  the position of the first record delimiter  to identify the first new record in this trunk.  After that, the starting position is passed  to a regular existing CSV parser  and the parser passes the trunk  using the start position as if it's a complete CSV file.  It repents the parsing result and the start position  and the end position of the last record in the trunk,  which could be somewhere in the next third trunk.  So this information is sent to the master for validation.  We can prove that the speculation is successful  if all the start and are connected end to end.  If not successful, then mis-prediction happens  and then we redo.  So we revert to a two-part support.  Basically in the first part, you sequentially scan  all the chunks to get the context  and then you use the context in the second part to parsing.  But as I will show you later,  this prediction in the real world is really rare  and it's almost never happened.  And also I would like to highlight is our approach  is robust to syntax error, the EU-informed CSV data,  which is quite common than exception in the real world.  I will skip this and let's start with question one.  How can we quickly determine the ambiguity?  In essence, parsing is a finite state machine problem.  Normally, you can start with the beginning of the file  and run a finite state machine based on the current state  and the next state, and the next chart you'll see.  So in the finite state machine for CSV,  we can have five states, let's say the record start,  field start, on-courted field,  courted field, and on-court ends.  And we can classify the charts into four big categories,  quote, comma, new line, and the rest that belong to the other.  Okay, for example, if your current state is a record start  and your next chart is a quote,  then your new state will be translated  into the courted field.  You know you are now inside the courted field.  Okay, so this is quite straightforward,  but the problem is in distributed setting,  we don't know what the beginning state is  and that's exactly what we want to know.  So we take this idea of finite state machine  and augment this finite state machine to this approach.  So since we don't know the beginning state,  then let's assume all the states are possible  and we run multiple state machines.  So we can prove that if the trunk is ambiguous,  then there will be more than one valid state  after the first new line.  And if the trunk is ambiguous,  then there is only one valid state.  So the drawback of this approach is not that efficient  because we need to run multiple finite state machines  and even running one state machine is super slow  compared to the speed of a parting.  Okay, can we do it better?  Well, we observe a simple and super fast method to do this.  So it's summarized like this.  So if a trunk is ambiguous,  if and only if it contains a quote  or other quote pattern strings.  So quote is the chart, quote,  other is a quote, not a quote comma and a new line.  Okay, so we can basically prove like this.  So consider one direction.  If the trunk contains these patterns,  then the trunk is ambiguous.  We can prove using the finite state table  and the key idea is no matter what the beginning state is,  after you see a pattern,  all the possible states now converge  to only one possible state.  Okay, and the other direction,  we also formally prove the other direction,  which is that if the trunk is ambiguous,  then the trunk must contain one of the patterns.  Okay, then now our process is straight forward.  So we want to look for those patterns in the truck.  So we can use the same D instructions  to quickly detect those patterns.  Okay, if a trunk does not contain such a pattern,  then we speculate how.  Okay, take another local of one of the possible interpretation.  Okay, the position in the red rectangles  are all the positions that make this trunk ambiguous.  In another word, if any of these charts is other,  then this trunk becomes unambiguous.  How likely it is?  Therefore, we can compute the likelihood  of the random string make that trunk ambiguous  and model this as a conditional probability problem.  Okay, and we will speculate and choose the spec  interpretation with the highest probability.  We also integrate our solution into Spark  using only Spark primitives.  So this implies that our solution also  includes the fault tolerance characters.  Okay, we did a lot of evaluations using clusters  and on our Spark integration.  And one thing I would like to highlight  during our evaluation is at the time of experiment,  we downloaded all the CSV files from the Kaggle repository.  And those are more than 11,000 CSV files.  The size ranges from three bytes to 11 gigabytes.  And here are just some examples.  Okay, the first example is we want to compare  the overall speed up over the two parts of course.  As I briefly mentioned when describing  this system, the first parts determine the context  and then the second parts take that context  and do the parting.  So the x-axis is a file size  and the y-axis measures the speed up.  And each of the circles represent a data set.  On the left hand side, it shows the performance  using the default CSV parser in Spark.  So when the data size is small,  the parting time is short  and it's portabated by Spark mechanisms  such as job scheduling and memory management.  And when the file size increases, as you can see,  the speed up is about between one to 1.5x.  On your right hand side,  we show the performance using a MISOM parser,  which is the state of art parser.  And as you can see, the overall speed up  is between 1.5x to up to 2.3x.  So this shows that the speculative parsing  is more beneficial with a more than faster parser,  which is the trend.  The second example is we want to consider  the overhead compared to an ideal approach.  So the ideal approach is we assume there's an oracle  that can magically determine the context with no cost.  So this is simulated by disabling  the multi-line option in Spark.  So as you can see, the comparison is almost one here,  and it means that the speculative parsing  has a measurable overhead compared to an even ideal approach.  The next example I would like to show  is about the MIS prediction ratio.  So in this case, we trunk all the 11,000 CSV data files  to different trunk size,  and the trunk size ranges from 16 bytes to one megabytes.  And we will speculate using this trunk size.  And when the trunk size is small,  the MIS prediction ratio is high, as you can see,  because some long-stream values are larger than the trunks,  and this small trunks usually has limited information  and can be misleading.  And when you increase the trunk size,  then you'll see a quick drop of this MIS prediction ratio.  And here, because there's only one MIS prediction trunks,  and when you increase the trunk size,  the number of trunks goes small,  then the ratio goes up a little bit.  But still, as you can see,  the speculation feels less than once in one million trunks.  And in practice, the trunk size usually ranges  from a dozen megabytes, far larger than the record size.  So this area really happens.  To summarize, in this work,  we designed a speculative distributed CSV data parsing solution  that has less than once in 10 million failure rates.  It has a noticeable overhead compared to an average  distributed parsing solution,  and it's a rule-boss to syntax error,  and it can compose with any existing CSV parser.  So that concludes my talk, and I'm happy to take questions.  Thank you.  Thank you.
Ge_Eilebrecht_Chandramouli_Kossmann_0_143.png Ge_Eilebrecht_Chandramouli_Kossmann_144_527.png Ge_Eilebrecht_Chandramouli_Kossmann_528_779.png Ge_Eilebrecht_Chandramouli_Kossmann_780_971.png Ge_Eilebrecht_Chandramouli_Kossmann_972_1199.png Ge_Eilebrecht_Chandramouli_Kossmann_1200_1799.png Ge_Eilebrecht_Chandramouli_Kossmann_1800_2051.png Ge_Eilebrecht_Chandramouli_Kossmann_2052_3047.png Ge_Eilebrecht_Chandramouli_Kossmann_3048_3179.png Ge_Eilebrecht_Chandramouli_Kossmann_3180_4931.png Ge_Eilebrecht_Chandramouli_Kossmann_4932_8171.png Ge_Eilebrecht_Chandramouli_Kossmann_8172_8519.png Ge_Eilebrecht_Chandramouli_Kossmann_8520_8831.png Ge_Eilebrecht_Chandramouli_Kossmann_8832_9059.png Ge_Eilebrecht_Chandramouli_Kossmann_9060_9827.png Ge_Eilebrecht_Chandramouli_Kossmann_9828_12407.png Ge_Eilebrecht_Chandramouli_Kossmann_12408_15107.png Ge_Eilebrecht_Chandramouli_Kossmann_15108_16775.png Ge_Eilebrecht_Chandramouli_Kossmann_16776_17819.png Ge_Eilebrecht_Chandramouli_Kossmann_17820_18827.png Ge_Eilebrecht_Chandramouli_Kossmann_18828_20915.png Ge_Eilebrecht_Chandramouli_Kossmann_20916_24467.png Ge_Eilebrecht_Chandramouli_Kossmann_24468_24589.png
I'm Chang Ge, I'm a student from University Waterloo. Today I'm going to talk about speculative distributist SV data parsing for big data analytics. This work was done during my internship at Microsoft research with my great mentor E9D and collaborators Eric Alebridge, Badges Treadomoli and Donald Cosman. Organizations have been generating a lot of data. It's very expensive both in terms of a computation course and human efforts to cook and bannerize all their data. In the traditional world, only a small amount of data was cooked and loaded into the database systems in the binary format. And the majority of the data stays uncooked, untouched and stored in the raw data format such as JSON and CSV which is usually generated by the data source. In recent years, the cloud and big data systems reduce the cost to process raw data. For example, systems like Spark supports queries directly over CSV and JSON format. Although uncooked, this raw data now can be queried on demand. In the raw data, all the data is stored in plain text format and must be passed to get the structure and a binary value before processing. In database systems, parsing is an important step during loading and it usually occurs one time cost. However, when querying on demand, parsing occurs every time when the data is queried and hence is on the critical path. Even more, big data systems work in a cluster of machines in a distributed way. As a result, parsing must be distributed too. Otherwise, the benefit of parallelizing other tasks will be diminished. This work, we focus on CSV, which is the most popular tabular data format and is widely used in data analytics, exchange, motion learning. Distributed CSV parsing has many use cases. For example, in parallel query processing, systems such as Spark, query services such as Google BigQuery and even software libraries such as Pandas, queries are executed in parallel by multiple workers or cores. So, given a CSV file, each of the workers, each of the nodes only access a piece of it and the parsing must be distributed in order to fully utilize the parallelism. For another example, in distributed stories such as SDFS, a CSV file can be trunked into multiple partitions. When the data is retrieved, it's often desirable not to return all the data, but just a subset of data that are relevant. So in production systems like Azure Quick Query and AWS S3 Threat, they have already supported pushing down the queries to the stories layer and the storage layer tests the predicates and returns only the subset of data. So in this setup, each of the trunks must be parsed before applying the predicates. Okay, now let's look at the problem. Suppose we have a CSV file, it looks like this. Sorry, well, it starts with our unquoted string div and this comma is a field delimiter and the next field is a quoted comma and the next field is a one, two, three, four and this new line is a record delimiter to distinguish two different records. Okay, and based by the specification, a field can be either quoted or unquoted and it can contain almost the arbitrary chargers in the field. When we store this file in the distributed storage, the storage has no idea what the data looks like and how to align the boundaries. So in fact, the storage just trunked the CSV into fixed size trunks. Okay, suppose we have split this CSV into three trunks. Okay, and now consider you as a worker and you are assigned with this trunk number two. Can you tell me how to pass this data? Well, you might consider, well, this E belongs to the boundary partial records and this comma is a field delimiter and the next field is a quoted comma followed by another field 17 and this new line is a record delimiter. Alternatively, you can interpret this E and a comma together as a partial field that's inside of this quote and the second comma as a field delimiter and the next field is this long string that is inside of this quote and the second new line is the record delimiter. Oh, sorry, record, sorry, this is a field delimiter and this is a record delimiter. Okay, based on the specification, both alternatives are possible and you can imagine the query's final result can be dramatically different given different interpretations. So the challenge related to the trigger parsing is it's fundamentally impossible to disambigot without the context. Okay, even if it's impossible, we should never give up. Okay, fortunately, we have found some opportunities. The first one is we observe that most of the trunks are not ambiguous. For example, for this set of trunks, most of them are not ambiguous. So the question is, how can we quickly determine whether a trunk is ambiguous or not? Okay, for the second opportunity, even the trunks are ambiguous, we can still guess and hopefully we can guess it correct. Consider these same, those two interpretations. Take a second look and can you tell me what do you think which one is more likely correct? Well, it turns out the first one is more likely because if the second one was, then it would be too coincidental that this quoted string satisfied the CSV specification in the other interpretation. So the question is, how can we speculate for an ambiguous trunk? Okay, before I answer those two questions, let me first show you the overview of our solution. So each trunk is assigned to a worker and the worker individually and independently tests whether the trunk is ambiguous or not. If yes, then speculate. If not, or after speculation, we find the position of the first starting point, the position of the first record delimiter to identify the first new record in this trunk. After that, the starting position is passed to a regular existing CSV parser and the parser passes the trunk using the start position as if it's a complete CSV file. It repents the parsing result and the start position and the end position of the last record in the trunk, which could be somewhere in the next third trunk. So this information is sent to the master for validation. We can prove that the speculation is successful if all the start and are connected end to end. If not successful, then mis-prediction happens and then we redo. So we revert to a two-part support. Basically in the first part, you sequentially scan all the chunks to get the context and then you use the context in the second part to parsing. But as I will show you later, this prediction in the real world is really rare and it's almost never happened. And also I would like to highlight is our approach is robust to syntax error, the EU-informed CSV data, which is quite common than exception in the real world. I will skip this and let's start with question one. How can we quickly determine the ambiguity? In essence, parsing is a finite state machine problem. Normally, you can start with the beginning of the file and run a finite state machine based on the current state and the next state, and the next chart you'll see. So in the finite state machine for CSV, we can have five states, let's say the record start, field start, on-courted field, courted field, and on-court ends. And we can classify the charts into four big categories, quote, comma, new line, and the rest that belong to the other. Okay, for example, if your current state is a record start and your next chart is a quote, then your new state will be translated into the courted field. You know you are now inside the courted field. Okay, so this is quite straightforward, but the problem is in distributed setting, we don't know what the beginning state is and that's exactly what we want to know. So we take this idea of finite state machine and augment this finite state machine to this approach. So since we don't know the beginning state, then let's assume all the states are possible and we run multiple state machines. So we can prove that if the trunk is ambiguous, then there will be more than one valid state after the first new line. And if the trunk is ambiguous, then there is only one valid state. So the drawback of this approach is not that efficient because we need to run multiple finite state machines and even running one state machine is super slow compared to the speed of a parting. Okay, can we do it better? Well, we observe a simple and super fast method to do this. So it's summarized like this. So if a trunk is ambiguous, if and only if it contains a quote or other quote pattern strings. So quote is the chart, quote, other is a quote, not a quote comma and a new line. Okay, so we can basically prove like this. So consider one direction. If the trunk contains these patterns, then the trunk is ambiguous. We can prove using the finite state table and the key idea is no matter what the beginning state is, after you see a pattern, all the possible states now converge to only one possible state. Okay, and the other direction, we also formally prove the other direction, which is that if the trunk is ambiguous, then the trunk must contain one of the patterns. Okay, then now our process is straight forward. So we want to look for those patterns in the truck. So we can use the same D instructions to quickly detect those patterns. Okay, if a trunk does not contain such a pattern, then we speculate how. Okay, take another local of one of the possible interpretation. Okay, the position in the red rectangles are all the positions that make this trunk ambiguous. In another word, if any of these charts is other, then this trunk becomes unambiguous. How likely it is? Therefore, we can compute the likelihood of the random string make that trunk ambiguous and model this as a conditional probability problem. Okay, and we will speculate and choose the spec interpretation with the highest probability. We also integrate our solution into Spark using only Spark primitives. So this implies that our solution also includes the fault tolerance characters. Okay, we did a lot of evaluations using clusters and on our Spark integration. And one thing I would like to highlight during our evaluation is at the time of experiment, we downloaded all the CSV files from the Kaggle repository. And those are more than 11,000 CSV files. The size ranges from three bytes to 11 gigabytes. And here are just some examples. Okay, the first example is we want to compare the overall speed up over the two parts of course. As I briefly mentioned when describing this system, the first parts determine the context and then the second parts take that context and do the parting. So the x-axis is a file size and the y-axis measures the speed up. And each of the circles represent a data set. On the left hand side, it shows the performance using the default CSV parser in Spark. So when the data size is small, the parting time is short and it's portabated by Spark mechanisms such as job scheduling and memory management. And when the file size increases, as you can see, the speed up is about between one to 1.5x. On your right hand side, we show the performance using a MISOM parser, which is the state of art parser. And as you can see, the overall speed up is between 1.5x to up to 2.3x. So this shows that the speculative parsing is more beneficial with a more than faster parser, which is the trend. The second example is we want to consider the overhead compared to an ideal approach. So the ideal approach is we assume there's an oracle that can magically determine the context with no cost. So this is simulated by disabling the multi-line option in Spark. So as you can see, the comparison is almost one here, and it means that the speculative parsing has a measurable overhead compared to an even ideal approach. The next example I would like to show is about the MIS prediction ratio. So in this case, we trunk all the 11,000 CSV data files to different trunk size, and the trunk size ranges from 16 bytes to one megabytes. And we will speculate using this trunk size. And when the trunk size is small, the MIS prediction ratio is high, as you can see, because some long-stream values are larger than the trunks, and this small trunks usually has limited information and can be misleading. And when you increase the trunk size, then you'll see a quick drop of this MIS prediction ratio. And here, because there's only one MIS prediction trunks, and when you increase the trunk size, the number of trunks goes small, then the ratio goes up a little bit. But still, as you can see, the speculation feels less than once in one million trunks. And in practice, the trunk size usually ranges from a dozen megabytes, far larger than the record size. So this area really happens. To summarize, in this work, we designed a speculative distributed CSV data parsing solution that has less than once in 10 million failure rates. It has a noticeable overhead compared to an average distributed parsing solution, and it's a rule-boss to syntax error, and it can compose with any existing CSV parser. So that concludes my talk, and I'm happy to take questions. Thank you. Thank you.
the cloud and big data systems reduce the cost to be queried on demand. In the raw data, all the before processing. In database systems, parsing in a cluster of machines in a distributed way. As CSV, which is the most popular tabular data format and is widely used in data analytics, parallel query processing, systems such as Spark, So in this setup, each of the trunks must be parsed before applying the predicates. Okay, now distinguish two different records. Okay, and quoted or unquoted and it can contain almost the challenge related to the trigger parsing is it's is ambiguous or not? Okay, for the second you use the context in the second part to to highlight is our approach is robust to syntax in distributed setting, we don't know what the these patterns, then the trunk is ambiguous. We implies that our solution also includes the fault experiment, we downloaded all the CSV files from right hand side, we show the performance using a more than faster parser, which is the trend. The that the speculative parsing has a measurable all the 11,000 CSV data files to different trunk speculative distributed CSV data parsing solution