Symptoms

You may receive the following error message:

Error occurred trying to Execute (SmoSPDocument) - Microsoft.SharePoint.Client.ServerException: The attempted operation is prohibited because it exceeds the list View threshold enforced by the administrator.

While using SharePoint 2010 broker against 5000 items library (folders/documents) and despite querying specific folder in the library which by itself contain just a few documents (way below configured threshold).
 

Diagnoses

SharePoint list threshold enforcement is an expected behavior which was introduced to safeguard against SQL server side locks on backend SharePoint content database. This feature described in Microsoft documentation:

"Manage lists and libraries with many items" (APPLIES TO: SharePoint Foundation 2010)

"Manage lists and libraries with many items" (APPLIES TO: SharePoint Online, SharePoint Foundation 2013, SharePoint Server 2013 Enterprise, SharePoint Server 2016 Enterprise)

In case your K2 environment is configured according to K2 requirements described in Set up the K2 Service Account section of K2 documentation then K2 SharePoint broker calls will not be subjected to the threshold as in this case K2 service account will not be a subject to SharePoint list threshold being granted local administrator rights on SharePoint web front end server. As per aforementioned Microsoft documentation:

"To assist central administration, the computer administrator of the front-end computer and the central administrator site owner accessing a list or library with many items are not subject to the following resource throttles and limits."

In case you unable to grant local administrator rights on SharePoint web front-end to K2 service account due to security considerations/compliance requirements you have to use filtering by indexed columns instead of folders which will cater for most of the scenarios.
Folders in SharePoint is a legacy technology introduced only to facilitate migrations from file shares "as is" (when there are no possibility to sort out/structure data). Microsoft recommends avoid using SharePoint folders due to costly SQL joins on the back end which are required to support this feature.

Instead of folders it is recommended to use approach with filtering by indexed column and with this approach it is possible to pull specified number of documents from library which has overall number of items which exceeding the threshold when using filtering by indexed column as far as total number of items returned with this filter is below the threshold.

NOTE: When using number type of column as indexed column and specifying value for it in K2 broker, K2 broker sends "Contains" or "Begins With" instead of "Equals" and SharePoint rejects this request with the following error:

Microsoft.SharePoint.Client.ServerException: Exception from HRESULT: 0x80131904

This is known issue (TFS 613004) with SharePoint 2010 Content Broker with existing workarounds which are the following:
1) TEXT COLUMN
You can change a column type from Number to Single Line of Text in SharePoint, you just have to update the SmartObject afterwards.
2) FILTER:
* In Tester Tool: When executing the SmartObject you will notice a Filter Section on the Right Hand side.
Click on "SET"
First Drop Down "Your Indexed Column"
Second Dropdown ""
Third Dropdown "Equals"
Right Property Value "2" (some specific ID value, 2 it is just an example)
Click on "Add"
Click on "Ok"
Execute
To use this in a workflow:
You can start by adding a SmartObject Method Reference and selecting the Get Documents Reference
No Inputs.
When you use this field in the process, you get an option to apply a filter.

 

Resolution

Best way around is without granting excessive rights or increasing SharePoint threshold settings is to use filtering by indexed column. From performance side/Microsoft best practices side it is also recommended to move away from folder structure. It is not recommended to use folders in SharePoint as they have performance impact (handling of folders requires costly JOIN operations on SharePoint SQL back end) and not recommended by Microsoft.

NOTE: Moving away from folders won't allow you to have multiple files with the same file name in your library in the root of the list (file has to have unique URL which won't be the case her). This is by design in SharePoint, and you have either ensure document name uniqueness or use Document Sets as alternative to folders (it will allow you have the same document name repeated once per each document set once per library, this is the case because document set name included into URL thus despite duplicate document names URL still will be unique).
From K2 side it is relatively easy to generate unique file names for example by adding some ID to the file name. You also may include current date or some other extra values into file name to ensure its uniqueness.