Does it use bubble sort/merge sort.. type of algorithms? Is there any documentation/information available around the background execution of these type of statements?
1 Answer
Not sure why you're being downvoted, since I don't think this is described anywhere. Within a single partition, BigQuery uses introsort, with a some tricks depending on the types and number of columns in the ORDER BY clause. For example, if you have an INT64
column named x
and you run a query of this form:
SELECT x
FROM dataset.table
ORDER BY x
BigQuery will load all of the x
values into a vector, then sort and return them. It's less straightforward if you have multiple columns in the select list or ORDER BY clause, though.
-
Thanks Elliott, Is there any additional information available around these? Oct 28, 2018 at 5:39
-
-
Execution algorithms for different kinds of SQL statements Oct 28, 2018 at 6:11
-
2@ElliottBrossard: I suspect it's getting down voted because it's quite broad and not specially related to programming/SQL. The sorting algorithm is completely abstracted away from users, with no way to control it programmatically. I agree it's interesting to know how BigQuery does its sort, but maybe it's a question more suited to stackexchange or Quora? Just my 2 cent. Oct 28, 2018 at 9:40
-
Very cool information! I for one think the question is welcome, knowing the complexity of sorting algorithms is quite important for deciding how much data we'd be willing to use. I still wonder though if clustering a table on a given column would affect the sorting as well. For what I understood it seems to work sort of like an index, maybe there's optimizations to further diminish expectation of worst case scenario complexity in this case. Oct 30, 2018 at 2:52