I am fairly new to learning the XGBoost algorithm and had a question about how the algorithm knows which feature to break the tree on first.
Here is my understanding (and please correct me if I'm wrong):
Each tree starts as a single leaf and all of the residuals go to that leaf. Then we calculate the similarity score and try to split amongst some feature characteristics. For example, say we only had one feature - height. We could split the residual if its respective x-value was say height > $180cm$ or height < $180cm$. And then proceed to calculate the similarity scores and the gain for the new leaves and continue down our tree.
My question is now say we had two or more features such as height, age, weight, education, etc. How does the algorithm know where to break the initial residuals? Does it compute it over all possible features and finds the best gain? I can imagine for large datasets to go through all features, then break it at some threshold and compare must take a long time.
Or does it start at some random feature and work its way down kind of like a random forest? I know there is a parameter within the algorithm that allows you to set the percentage of features per tree so adding on to my question once we specify this percentage how does it pick the features and more importantly once those features are picked how does it know which one to pick to break the initial leaf of residuals.
Edit: I tried reading the paper where the algorithm was first published but found it a bit too difficult to conceptualize and understand.