Complexity will lead to both big challenges and opportunities in big data research. Complexity in big data can be caused by many factors, including: large number of features, which are related to each other through a rich variety of relationships ranging from simple to complicated; a large number of heterogeneous dimensions, which offer a variety of kinds of insights and require different treatments, in addition to a large number of data records; a large variety of heterogeneous types, such as vectors, sequences, (labeled) graphs, images, and multimedia, in addition to a large number of instances; a rich set of logical, semantic, and ontological relationships. Complexity has often been used to successfully characterize various kinds of complicated subjects, for example in computational complexity, descriptive complexity, Kolmogorov complexity. Since big data have many complicated parts with intricate relationships to each other, the study of complexity for big data has potential to be highly successful. Research on complexity of big data needs to consider the following facts, among others: Big data can be used for different purposes such as data integration, cross domain fertilization, and data mining; Structures among various parts of big data can be explicit or hidden, and can be described using a rich variety of patterns and models.