4

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 1

3

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.

5
  • Thanks Elliott, Is there any additional information available around these? Oct 28, 2018 at 5:39
  • Around what, specifically? Oct 28, 2018 at 5:42
  • 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.