Which sorting algorithm does bigquery ORDER BY clause uses?

Question

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?

Answer 1

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.